L'algoritmo MDP con ricompense scontate

L'algoritmo MDP con ricompense scontate analizza una sequenza di decisioni per valutare l'utilità attesa di una politica, attribuendo un peso maggiore alle prime decisioni e progressivamente minore alle decisioni successive.

il metodo delle ricompense scontate

In ogni turno la ricompensa R(st) ottenuta nello stato st viene moltiplicata per un fattore di sconto γt compreso tra 0 e 1 ed elevato a potenza con esponente pari al numero dei passi (t).

A cosa serve?

Se il fattore γ è inferiore a 1, il fattore di sconto si riduce col passare del tempo, rendendo progressivamente meno utili i passi successivi rispetto ai precedenti.

il fattore di sconto si riduce con il tempo

Preferenze non stazionarie. Se il fattore di sconto è inferiore a 1, ad esempio y=0.5, le ricompense iniziali sono più importanti delle successive. Questo causa la non stazionarietà delle preferenze.
le ricompense scontate generano delle preferenze non stazionarie che cambiano con l'ordine delle decisioni
Le preferenze non sono stazionarie perché l'utilità di uno stato S della sequenza cambia in base alla posizione nella sequenza decisionale. Pertanto, non si può affermare che uno stato sia sempre preferibile a un altro.

    I vantaggi del metodo delle ricompense scontate

    Il metodo ricompense scontate ha diversi vantaggi negli algoritmi MDP ( Markov Decision Process ) rispetto al metodo delle ricompense additive, perché trasforma una sequenza decisionale infinita in una sequenza finita.

    una catena di decisioni

    Se la sequenza di decisioni è molto lunga, con il metodo additivo l'utilità attesa tende a infinito.

    Questo causa un problema. E' infatti impossibile confrontare due sequenze che tendono entrambe a infinito.

    Inoltre, se non esiste una soluzione ( stato terminale ) l'agente entra in un loop senza fine, consumando inutilmente tempo e risorse per elaborare una sequenza infinita di passi.

    Nota. Quando una politica non raggiunge mai uno stato terminale è detta politica impropria. Viceversa, se la raggiunge è detta politica propria.

    Il metodo delle ricompense scontate, invece, riduce progressivamente l'utilità addizionale del passo successivo, rendendola sempre più piccola.

    un esempio di calcolo coni il metodo delle ricompense scontate

    Quando l'utilità scontata aggiuntiva diventa troppo piccola ( es. γt=0.05 ossia 5% ) l'agente può interrompere anticipatamente il processo di ricerca, evitando così di elaborare altri passi con valori infinitesimali.

    In questo modo, l'agente ottiene un valore approssimativo dell'utilità della politica che sta esaminando ma risparmia tempo e risorse.

    Il metodo delle ricompense scontate ha eliminato il rischio di incappare in un loop infinito e ha migliorato l'efficienza computazionale dell'algoritmo.

     


     

    Segnalami un errore, un refuso o un suggerimento per migliorare gli appunti

    FacebookTwitterLinkedinLinkedin
    knowledge base

    Libri di approfondimento

    Il ragionamento artificiale