Tecniche Computazionali

Avanzate

Enza MessinaA.A. 2007/08

Modelli Probabilistici per le Decisioni

Markov Decision Problem

Come utilizare la conoscenza dell’ambiente perprendere decisioni nel caso in cui il risultatodelle azioni sia incerto e il payoff dipende da unadelle azioni sia incerto e il payoff dipende da unasequenza di decisioni

La soluzione

Problemi di decisioni sequenziali in condizionidi incertezza possono essere risolti calcolandouna politica che associa una decisione ottimauna politica che associa una decisione ottimaad ogni stato raggiungibile =>

Markov Decision Process (MDP)

Robot Example

� Si immagini un robot con solo un sensore locale� Che deve andare da A a B

� Le azioni hanno un risultato incerto – può muoversi ad angolo retto rispetto alla direzione muoversi ad angolo retto rispetto alla direzione prevista

� Vogliamo insegnare al robot come muoversi

� Problema di decisione sequenziale

Esempio

+13 0.8

Il mondo Le azioni hannoconseguenze incerte

-1

1

2

1 2 3 4

start

0.1 0.1

Markov decision model

� Gli ingredienti di un modello di decisione di Markov sono:

� Un insieme di possibili stati S� Un insieme di possibili stati S

� Un insieme di possibili azioni A

� Una funzione di ricompensa R(s,a)

� Una descrizione T degli effetti di un’azione in ogni stato

Modelli di decisione sequenziali

� Stato iniziale� S0

� Modello di transizione� T (s, a, s’)

� Come si applica qui la proprietà Markoviana?� Come si applica qui la proprietà Markoviana?

� Incertezza possibile

� Funzione ricompensa � R(s)

� Finita per ogni stato

Determinazione di una politica

� Che aspetto ha la soluzione a tale problema?� Qualsiasi sequenza di azioni potrebbe fallire

� La prob che la sequenza “Su Su Destra Destra Destra” porti il robot al traguardo e’ 0,85 =0,32768 e c’e’ la possibilità di raggiungere l’obiettivo passando accidentalmente per un’altro percorso, con prob 0,14*0,8=0,00008, quindi la un’altro percorso, con prob 0,14*0,8=0,00008, quindi la prob di raggiungere l’obiettivo è 0,32776

� Bisogna evitare strade senza uscita

� Bisogna evitare ripetizioni inutili

� La soluzione dovrà specificare quello che l’agente deve fare in ogni stato potenzialmente raggiungibile

� Specificare una soluzione per ogni stato iniziale� Costruire una politica che fornisca l’azione migliore per ogni stato

politica = π

Determinazione di una politica

� politica = π� Politica nello stato s = π(s)

� Politica completa copre tutti i possibili stati di input

� Politica ottima, π*, fornisce l’utilità attesa più alta

� Perchè attesa?

� Le transizioni sono stocastiche

Determinazione di una politica

Determinazione di una politica

Determinazione di una politica

Determinazione di una politica

Determinazione di una politica

Determinazione di una politica

Determinazione di una politica

Esempio: soluzione

- --

-

-

Utilizzo di una politica

� Un agente nello stato s� s è la percezione disponibile all’agente

� π*(s) un’azione che massimizza l’utilità attesa

� La politica è la descrizione di un semplice riflesso

Bilanciare rischi e ricompense

� Diverse politiche dimostrano un bilanciamento tra rischi e ricompense� Caratteristica interessante solo negli ambienti stocastici (non deterministici)

Caratteristica di molti problemi reali� Caratteristica di molti problemi reali

� La costruzione di una politica ottima è difficile!

Attributi dell’ottimalità

� Vogliamo trovare una politica ottima che massimizzi l’utilità degli agenti durante un certo orizzonte temporale� Massimizzare U([s0, s1, s2, …, sn)]

� Quanto è lungo l’orizzonte temporale?� Orizzonte finito – Il numero di transizioni di stato è conosciuto e finito

� Dopo N passi non conta più nulla

� U([s0, s1, s2, …, sn)] = U([s0, s1, s2, …, sn, sn+1, sn+k)] per k>0

� Orizzonte infinito – possono sempre avvenire nuove transizioni di stato

Orizzonte temporale

� Posizione di partenza (3,1)� Orizzonte N = 3

� Orizzonte N = 8

� Orizzonte N = 20

� Orizzonte N = inf

� π* cambia?

� Politica ottima non stazionaria con orizzonte finito

Valutazione di una sequenza di stati

� Assunzione� Se dico che preferirò lo stato a allo stato b domani devo anche dire che preferisco lo stato a allo stato b oggi

� Le preferenze sono stazionarie

� Ci sono due modi possibili di assegnare utilità alle � Ci sono due modi possibili di assegnare utilità alle sequenze:� Ricompensa additiva

� U[(a, b, c, …)] = R(a) + R(b) + R(c) + …

� Ricompensa scontata

� U[(a, b, c, …)] = R(a) + γR(b) + γ2R(c) + …� γ è il fattore di sconto, compreso tra 0 e 1

� Cosa vuol dire?

Valutazione con orizzonte infinito

� Come possiamo calcolare la somma con un orizzonte infinito?

� U[(a, b, c, …)] = R(a) + R(b) + R(c) + …� U[(a, b, c, …)] = R(a) + R(b) + R(c) + …

� Se il fattore di sconto γ è minore di 1

� Nota: Rmax è finito per definizione di MDP

� Come possiamo calcolare la somma con un orizzonte infinito?

� Se è garantito che l’agente finisca in uno stato

Valutazione con orizzonte infinito

� Se è garantito che l’agente finisca in uno stato terminale allora

� Non dovremo mai confrontare sequenze infinite

� Possiamo permettere che γ sia 1

Valutazione di una politica

� Ogni politica π genera sequenze multiple di stati� La funzione di transizione T(s, a, s’) è stocastica

� Il valore di una politica è la somma attesa delle ricompense scontate calcolata su tutte le possibili ricompense scontate calcolata su tutte le possibili sequenze di stati che potrebbero risultare dalla sua esecuzione

� Una politica ottima soddisfa:

Determinazione della politica ottima

g Iterazione dei valori

gCalcola l’utilità di tutti gli stati e la utilizzaper scegliere l’azione ottima in ogni statoper scegliere l’azione ottima in ogni stato

g Iterazione delle politiche

gCalcola il valore di una politica e cerca di“migliorarla”

� Iterazione dei valori� Calcolare l’utilità di ogni stato

� Utilizzare l’utilità dello stato per selezionare l’azione ottima in ogni stato

La politica è semplice – andare nello stato con

Determinazione di una politica

� La politica è semplice – andare nello stato con utilità maggiore

� L’utilità dello stato deve essere accurata� Attraverso un processo iterativo si possono assegnare i valori corretti ai valori di utilità degli stati

Utilità degli stati

� L’utilità di uno stato s è…� Il valore atteso di utilità della sequenza di stati che possono seguirlo

� La conseguente sequenza di stati è funzione di π(s)

� L’utilità di uno stato data la politica π è…

� La vera utilità di uno stato sarà

)(*

sU π

Esempio

� Sia γ = 1 e R(s) = -0.04Nota:� L’utilità maggiore vicino all’obiettivo riflette che ci saranno meno termini -0.04 nella somma

Restating the policy

� Abbiamo detto di scegliere lo stato con utilità maggiore

� In realtà…� Andare nello stato con massima utilità attesa� Andare nello stato con massima utilità attesa

� Gli stati raggiungibili con maggiore utilità possono avere probabilità minore di essere raggiunti

� Dipende dalle azioni disponibili, dalla funzione di transizione, dagli stati risultanti

Massimizza l’utilità attesa degli stati successivi

Mettiamo insieme i pezzi

� Abbiamo detto che l’utilità di uno stato è:

� La politica è massimizzare l’utilità attesa

� Quindi, l’utilità di uno stato è la ricompensa immediata per lo stato più l’utilità attesa del prossimo stato

Perchè conviene

� Molto meno onerosa da valutare:

Invece di:� Invece di:

� Richard Bellman ha inventato la famosa equazione

� Bellman equation (1957)

Esempio di Equazione di Bellman

� Riprendiamo l’esempio 4x3

� Utilità della cella (1, 1)

� Consideriamo gli outcome di tutte le possibili azioni per selezionare l’azione ottima e assegnare la sua utilità attesa al valore del prossimo stato nell’equazione di Bellman

L’eq. di Bellman per risolvere MDPs

� Si consideri un particolare MDP� n possibili stati

� n equazioni di Bellman (una per ogni stato)

� n equazioni con n incognite (U(s) per ogni stato)stato)

� n equazioni e n incognite… si puo’ risolvere ?

�No, a causa della nonlinearità causata da argmax( )

�Puo’ essere utilizzata una procedura iterativa

Soluzione iterativa

� Si parte con valori arbitrari di utilità degli stati

� Aggiornare l’utilità di ogni stato in funzione dei suoi vicini

� Ripetere fino a che non si raggiunge un equilibrio

Aggiornamento

� Aggiornamento iterativo

� Dopo infiniti aggiornamenti, si raggiunge un punto di equilibrio che risolve le equazioni di Bellmanequilibrio che risolve le equazioni di Bellman

� Le soluzioni sono uniche

� La politica corrispondente è ottimale

� L’utilità degli stati vicino all’obiettivo convergerà velocemente e di conseguenza converceranno i vicini….

� L’informazione viene propagata nello spazio degli stati attraverso aggiornamenti locali

Convergenza dell’iterazione dei valori

� Quanto sono vicino alla politica ottima dopo iaggiornamenti?� Il libro mostra come

Convergenza dell’iterazione dei valori

� Il libro mostra come calcolare l’errore al passo i come funzione dell’errore al passo i –1 e del fattore di sconto γ

� Matematicamente rigoroso dovuto alle funzioni di contrazione

Iterazione delle politiche

� Immaginiamo che qualcuno ci dia una politica.� Quanto è buona?

� Assumiamo di conoscere γ e R

� A occhio?

� Provare qualche passo

� In modo più preciso…

� Valutazione di una politica

� Per iniziare, calcoliamo un’utilità di ogni stato secondo l’equazione di Bellman (per questa particolare iterazione i)

Iterazione della politica

� Valutazione di una politicaNon conosciamo Ui(s’)

� n equazioni di Bellman nincognite

� Le equazioni sono lineari

Iterazione della politica

� Le equazioni sono lineari� Possiamo risolvere per n

incognite in un tempo pari a O(n3) utilizzando metodi standard dell’algebra lineare.

Iterazione della politica

)1,2(1,0)1,1(1,0)2,1(8,004,0)1,1( iiii UUUU +++−=

)2,1(2,0)3,1(8,004,0)2,1( iii UUU ++−=

……….

� Valutazione di una politica� Ora conosciamo U(s) per ogni s

� Per ogni s, calcolare

Iterazione della politica

� Questa è l’azione migliore

� Se questa è differente dalla

politica, aggiornare la politica

Policy Iteration Algorithm

function policy-iteration(MDP) returns a policylocal variables: U, a utility function, π, a policyrepeat

U← value-determination(π,U,MDP,R)unchanged? ← truefor each state s dofor each state s do

unchanged? ← falseend

until unchanged?return π

∑←/

)(),,()( //maxargsa

sUsasTsπ

thensUsssTsUsasTifssa

>∑∑

//

)()),(,()(),,( ////max π

� Spesso l’approccio più efficiente� Richiede uno spazio degli stati O(n3)

� Sono possibili approssimazioni� Piuttosto che risolvere U esattamente, approssimare eseguendo un certo numero di iterazioni dei valori

Iterazione della politica

eseguendo un certo numero di iterazioni dei valori (semplificati perchè la politica è fissata)

� Esplorare (aggiornare la politica) solo di un sottoinsieme di stati

� Non ci si cura di aggiornare gli stati che crediamo “cattivi”

MDP parzialmente osservabili (POMDP)

� In un ambiente non accessibile, la percezione nonoffre informazione sufficiente per determinare lostato o la probabilità di transizione

� POMDP

� Funzione di transizione di stato: P(st+1 | st, at)

� Funzione osservazione: P(ot | st, at)� Funzione osservazione: P(ot | st, at)

� Funzione Ricompensa: E(rt | st, at)

� Approccio

� Calcolare una distribuzione di probabilità deipossibili stati date le percezioni precedenti ebasare la decisione su questa distribuzione

� Difficoltà

� Le azioni causano nuove percezioni che causanocambiamenti di “beliefs” molto complessi dadescrivere

MDP parzialmente osservabili (POMDP)

� Distribuzione stato iniziale� P(S0)

� Modello di transizione� T (s, a, s’)� T (s, a, s’)

� Funzione ricompensa � R(s)

� Finita per ogni stato

� Modello delle osservazioni� O(s,o) prob di percepire o nello stato s

MDP parzialmente osservabili

� L’azione ottima dipende dallo stato credenza corrente

� La politica ottima può essere descritta specificando la corrispondenza tra stati credenza e azioni

� Quindi il ciclo di decisione è:

� Dato lo stato credenza corrente b esegui l’azione a=

Ricevi l’osservazione o

)(* bπ� Ricevi l’osservazione o

� Determina la nuova distribuzione di stati credenza e ripeti

∑=s

jjj sbsasTosOsb )(),,(),()( α

MDP parzialmente osservabili (POMDP)

MDP parzialmente osservabili (POMDP)

∑=s

jjj sbsasTosOsb )(),,(),()( α

MDP parzialmente osservabili (POMDP)