Home » Intelligenza Artificiale » 📋 URL
Un processo decisionale di Markov è un problema di tipo sequenziale in un ambiente completamente osservabile e stocastico. Tali problemi sono caratterizzati dalle presenza di:
- Un insieme di stati s_i
- Un insieme di azioni che denotiamo tramite \texttt{actions}(s)
- Un transition model che indichiamo tramite P(s \mid s, \, a)
- Una reward function denotata da R(s, \, a, \, s)
In un MDP è inoltre utilizzato il concetto di policy, ovvero una funzione che riesca a restituire le azioni migliori che sono contenute in \texttt{actions}(s).
Tramite tale policy utilizziamo dunque il concetto di utilità di uno stato s U(s) rispetto all’obiettivo finale. Per assegnate tale utilità ad s possiamo utilizzare la probabilità. Indicheremo tramite P(s) la probabilità di essere nello stato s. Vogliamo ora quantificare la probabilità di raggiungere un nuovo stato s' (partendo da s) tramite l’azione a. Denotiamo tale probabilità come
P(\texttt{result}(a)=s')=\sum_s P(s) P(s' \mid s, \, a)Chiamiamo inoltre utilità attesa (expected utility) EU(s) l’utilità media di tutti i possibili stati che possiamo raggiungere partendo da s.
EU(a) = \sum_s P(\texttt{result}(a)=s')U(s')Nota: la media viene calcolata tramite il peso di ogni stato—ovvero la sua probabilità di verificarsi.
In generale può essere utile normalizzare la scala dell’utilità esprimendo
U(s) \in [0, \,1]
Esempio: consideriamo un robot che si muove, con probabilità 0.8 nella direzione prefissata, mentre con probabilità 0.2 nelle direzioni di destra o sinistra rispetto a quella prefissata (consideriamo dunque probabilità 0.1 di muoversi verso destra e 0.1 di muoversi invece verso sinistra). Tale robot viene posizionato all’interno del percorso riportato in figura
e deve riuscire a raggiungere il quadrato con il +1 senza cadere nel -1.
Nota: andare contro uno dei muri (i bordi del rettangolo) oppure scontrarsi contro il muro interno rappresentato dal blocco blu equivale a non spostarsi.
L’esplorazione di questo mondo può portare a diversi risultati in base al parametro di reward r che utilizziamo per far esplorare il mondo all’agente e, più tempo passa all’interno del mondo, più viene “punito”—dunque deve cercare di arrivare al +1 nel minor tempo possibile e senza cadere nel -1.
Possiamo essere, al variare di r, in una delle seguenti situazioni
dove le diverse frecce rappresentano, per ogni cella, la direzione migliore da prendere.
Nella figura (a) sono rappresentati i percorsi ottimali che il robot può seguire nel caso in cui venga utilizzato un reward r=0.04. Notiamo infatti che il robot può scegliere di prendere due diverse strade: quella che passa vicino al -1—che è più corta però rischiosa—e quella invece che aggira il muro blu—più lunga ma con meno probabilità di finire della cella del -1.
Naturalmente, con valori di r diversi si ottengono dei risultati diversi. In particolare si avranno i seguenti casi:
- r< -1.6497: a causa del reward negativo (ancora più negativo della cella -1!) il robot preferisce uscire dal percorso il prima possibile e a tutti i costi, accettando anche di andare nella direzione stessa del -1, che in questo caso avrebbe un valore meno negativo del reward!
- -0.7311<r< -0.4526: il reward non è molto negativo, però già dall’esplorazione di sole due celle si ottengono dei valori di reward piuttosto negativi che rendono l’agente a preferire il -1 nella cella in basso a sinistra, oppure a cercare di esplorare il mondo il meno possibile
- -0.0274<r<0: il reward inizia a essere vicino allo zero, dunque si incentiva di più l’esplorazione del mondo rispetto al punto precedente cercando di non cadere mai nel -1 prendendo, piuttosto, la strada più lunga
- r>0: il reward positivo rende l’esplorazione stessa del mondo migliore rispetto all’avvicinamento all’obiettivo. Il robot cerca dunque di allontanarsi sia dal -1 che dal +1: rimanere ad esplorare il mondo è l’azione migliore, ovvero quella che porta al maggior guadagno
Come scegliere la funzione utilità
Distinguiamo ora diverse possibili scelte per la funzione utilità in base agli orizzonti temporali che il problema in questione pone.
Possiamo avere orizzonti temporali:
- Finiti: rappresenta un caso improbabile (nei problemi reali) ed è caratterizzato dalla capacità dell’agente di conoscere interamente il mondo dopo aver effettuato un certo numero di osservazioni
- Infiniti: non esiste un limite temporale alle osservazioni utili che l’agente può fare per conoscere meglio l’ambiente. Un caso probabile, anche nella realtà, è quello in cui l’orizzonte temporale sia infinito, però dopo una certa quantità di tempo l’agente riesce a comprendere il mondo a tal punto da rendere di importanza infinitesima, o comunque decrescente, ogni ulteriore osservazione che può essere fatta del mondo
Nel caso di orizzonte temporale infinito, per indicare a un algoritmo che dopo una certa quantità di tempo le nuove osservazioni sono d’importanza sempre minore—dunque anche l’utilità ad essa collegata è sempre minore—possiamo utilizzare un parametro \gamma\in[0,\,1] che viene elevato ad esponenti sempre più grandi (ottenendo così dei numeri sempre più piccoli), che andranno a moltiplicare il valore della funzione di reward citata a inizio pagina. Supponendo inoltre che la funzione sia limitata da \pm R_{\max} si ha
U_h([s_0,\,a_0, \, s_1,\,a_1, \, s_2,\,a_2,\,\dots])=\sum_{t=0}^{+\infty}\gamma^t R(s_t,\, a_t, \, s_{t+1})\leq\underbrace{\sum_{t=0}^{+\infty}\gamma^t}_{\text{geom.}}\,R_{\max}=\dfrac{R_{\max}}{1-\gamma}Un altro modo che possiamo utilizzare per trovare l’utilità di uno stato è tramite la l’equazione di Bellman, attraverso cui si riesce a tenere in considerazione sia il reward immediato che i reward futuri che possono essere ottenuti nel caso in cui venga presa la decisione corretta
U(s)= \max_{a\in A(x)}\left(\sum_{s'} P(s' \mid s, \, a)[R(s, \, a, \, s') + \gamma U(s')]\right)A parole: l’utilità di uno stato s si può calcolare come l’azione che massimizza non solo l’utilità dello stato successivo rispetto a quello corrente, ma viene anche tenuta in considerazione l’utilità futura U(s') calcolata in maniera ricorsiva invocando nuovamente la funzione U(\cdot) su s' anziché su s. L’utilità U(s') viene inoltre pesata tramite il fattore \gamma che rende meno importanti i reward distanti nel futuro. Ognuna di tali quantità viene inoltre pesata nella sommatoria su s' in base alla probabilità di arrivare nello stato s' se si è nello stato s e si esegue l’azione a.
Tale formula è alla base di due algoritmi utilizzati nella risoluzione di un MDP:
- Value iteration
- Policy iteration
Value iteration
Di fatto si tratta semplicemente di utilizzare l’equazione di Bellman appena spiegata e aggiornare iterativamente il valore trovato tramite tale formula, continuando ad aggiornarlo finché non converge. Sarà dunque necessario un test della convergenza per capire se l’equazione di Bellman è conversa (ovvero il suo valore rimane costante in iterazioni successive) oppure se è sufficientemente vicina al valore di convergenza.
Policy iteration
L’algoritmo è di fatto molto simile a quello del value iteration solo che invece di aggiornare un valore si aggiornano i parametri di una policy per migliorarne le performance iterativamente:
- Partiamo da una policy arbitraria \pi_0
- Passiamo poi alla policy evaluation dove utilizziamo un’equazione con la stessa struttura di quella di Bellman per capire “quanto bene” funziona la nostra policy corrente
- Effettuiamo in maniera iterativa la policy improvement per aggiornare la policy in maniera greedy, scegliendo cercando di migliorare le performance attuali
- Controlliamo per ogni aggiornamento della policy se essa converge al risultato desiderato che risolve effettivamente il problema
Q-Learning
L’algoritmo di Q-Learning tenta di imparare una policy che massimizzi il valore del reward totale.
Nota: si chiama “Q”-Learning per evidenziare la Qualità di un’azione, ovvero la sua utilità rispetto all’ottenimento della massima quantità di reward.
L’algoritmo utilizza una tabella chiamata q-table per mappare il mondo tramite delle azioni esplorative (effettuate in maniera casuale) o per sfruttarlo (exploit) una volta che è stata trovata la combinazione di azioni che massimizza l’utilità di ogni azione che viene presa.
Value iteration vs. policy iteration vs. q-learning
L’algoritmo di q-learning, a differenza dei value iteration e policy iteration non ha bisogno di un modello dell’ambiente in cui viene utilizzato (conoscendo, ad esempio, le diverse probabilità di transizione tra gli stati o i vari reward che possono essere ottenuti), ma riesce a esplorare l’ambiente e trovare in questo modo la miglior policy per il problema posto.
In poche parole
✅ Un MDP (Markov Decision Process) è un problema sequenziale in un ambiente completamente osservabile e stocastico. Gli algoritmi di Value-Iteration e Policy-Iteration sono utilizzati per risolvere i MDPs.
- Value-Iteration: È un algoritmo che utilizza l’equazione di Bellman per calcolare iterativamente il valore ottimale per ogni stato dell’MDP. Inizia con una funzione di valore iniziale arbitraria e la aggiorna ripetutamente fino a convergere alla soluzione ottimale. Ad ogni iterazione si calcola il valore di un determinato stato come la somma dei reward immediati e dei valori di reward degli stati successivi, ponderati dalle probabilità di transizione da uno stato all’altro. Si continua a iterare fino a quando i valori convergono.
- Policy-Iteration: È un algoritmo che combina la policy evaluation e la policy improvement in un processo iterativo. Si inizia con una policy arbitraria e si valuta iterativamente il valore di ogni stato seguendo un’equazione strutturalmente simile a quella di Bellman. Successivamente, si migliora la policy selezionando le azioni che massimizzano i valori dei successivi stati. Questo processo di valutazione e miglioramento viene ripetuto fino a quando la policy converge alla soluzione ottimale.
✅ Entrambi gli algoritmi sono utilizzati per trovare la migliore policy per un MDP, ma differiscono nel modo in cui aggiornano i valori e le policy durante l’iterazione. Mentre Value-Iteration si concentra principalmente sulla valutazione dei valori, Policy-Iteration combina sia la valutazione che il miglioramento della policy per raggiungere la soluzione ottimale.