Markov processo decisionale

Question

alt text http://img693.imageshack.us/img693/724/markov.png

Sono un po 'confuso su alcuni punti qui:

1. Che cosa significa dire che avrà successo il 70% del tempo che cerca un dato di fatto azione? Significa che ogni volta che tenta di eseguire un'azione A, il 70% delle volte fa quell'azione A e l'altro 30% fa l'azione che porta allo stesso stato, o semplicemente è come se lo avesse sempre fatto l'azione A, ma solo il 30% delle volte non lo fa proprio? Spero che sto facendo io chiaro :(
2. Come è possibile avere diversi stati consecutivi con la stessa utilità? In teoria l'utilità non dovrebbe sempre ridurre, quanto più si è da stati con una ricompensa?
3. Knowing solo le informazioni che ho dato sopra, è possibile dedurre quello che è il fattore di sconto (gamma)? Se sì, come?
4. E 'possibile calcolare la Ricompensa per gli stati? in che modo?

Answer 1

C'è un modello per gestire la maggior parte dei problemi MDP, ma penso che probabilmente hai omesso alcune informazioni dalla descrizione del problema, molto probabilmente ha a che fare con lo stato che stai cercando di raggiungere, o il modo in cui un l'episodio termina (cosa succede se corri dal bordo della griglia). Ho fatto del mio meglio per rispondere alle tue domande, ma ho aggiunto un manuale sul processo che utilizzo per affrontare questi tipi di problemi.

In primo luogo l'utilità è una misura abbastanza astratta di quanto si desidera essere in un determinato stato. È sicuramente possibile avere due stati con uguale utilità, anche quando si misura l'utilità con una semplice euristica (distanza Euclidea o Manhattan). In questo caso, suppongo che il valore dell'utilità e il premio siano intercambiabili.

A lungo termine, l'obiettivo in questi tipi di problemi tende ad essere, come massimizzare il rendimento atteso (a lungo termine)? Il tasso di apprendimento, gamma, controlla la quantità di enfasi che si pone sullo stato corrente rispetto a dove si vorrebbe finire - in effetti si può pensare alla gamma come uno spettro che va da, 'fare la cosa che mi giova di più in questo timestep ' all'estremo opposto ' esplora tutte le mie opzioni e torna al migliore '. Sutton e Barto in là prenotano su reinforcement learning hanno un bel explanations di come funziona.

---

Prima di iniziare, tornare indietro attraverso la questione e fare in modo che si può tranquillamente rispondere alle seguenti domande.

1. Che cos'è uno stato? Quanti stati ci sono?
2. Che cos'è un'azione? Quante azioni ci sono?
3. Se si inizia in stato u e si applica un'azione a, qual è la probabilità di raggiungere un nuovo stato v?

Quindi le risposte alle domande?

1. Uno stato è un vettore (x, y). La griglia è 5 per 5, quindi ci sono 25 stati.
2. Sono possibili quattro azioni, {E, N, S, W}
3. La probabilità di raggiungere con successo uno stato adiacente dopo aver applicato un'azione adeguata è 0,7, la probabilità di non muoversi (rimanendo nello stesso stato è 0,3). Supponendo che (0,0) sia la cella in alto a sinistra e (4,4) sia la cella in basso a destra, la seguente tabella mostra un piccolo sottoinsieme di tutte le possibili transizioni.

 
Start State Action   Final State Probability 
--------------------------------------------------- 
(0,0)   E    (0,0)   0.3 
(0,0)   E    (1,0)   0.7 
(0,0)   E    (2,0)   0 
... 
(0,0)   E    (0,1)   0 
... 
(0,0)   E    (4,4)   0 
(0,0)   N    (0,0)   0.3 
... 
(4,4)   W    (3,4)   0.7 
(4,4)   W    (4,4)   0.3 

Come possiamo verificare che questo ha un senso per questo problema?

1. Verificare che la tabella abbia un numero appropriato di voci. Su una griglia 5 per 5 ci sono 25 stati e 4 azioni, quindi la tabella dovrebbe avere 100 voci.
2. Verificare che per una coppia di stato/azione di avvio, solo due voci abbiano una probabilità diversa da zero.

---

Modifica. rispondendo alla richiesta per le probabilità di transizione a lo stato di destinazione. Notazione seguente assume

• v è stato finale
• u è stato fonte
• a è l'azione, dove non è menzionato, è implicito che l'azione applicata non è rilevante.

 
P(v=(3,3) | u =(2,3), a=E) = 0.7 
P(v=(3,3) | u =(4,3), a=W) = 0.7 
P(v=(3,3) | u =(3,2), a=N) = 0.7 
P(v=(3,3) | u =(3,4), a=S) = 0.7 
P(v=(3,3) | u =(3,3)) = 0.3 

Answer 2

ad.1) probabilmente non è che il robot abbia sempre per muovere - cioè quei 30% sono "ah, ora mi riposo un po '" o "non c'era potere di muovere affatto".

Answer 3

ho formulato questo problema come una decisione processo Finite-Horizon Markov e risolto tramite la politica di iterazione. A destra di ogni iterazione, vi è una rappresentazione a griglia con codice colore delle azioni raccomandate per ogni stato, nonché la griglia/matrice di ricompensa originale.

Rivedere la politica/strategia finale allo stage 4. È d'accordo con il tuo intuito?