domande Markov processo decisionale [chiusa]

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 una determinata azione? Vuol dire che ogni volta che cerca di compiere un'azione A, sarà il 70% del tempo di fare che l'azione A e l'altro 30% fare l'azione che porta allo stesso stato, o semplicemente che è come se avesse sempre fatto l'azione A, ma solo il 30% delle volte che proprio non lo fa? 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. Conoscere solo le informazioni che ho dato sopra, è possibile dedurre quello che è il fattore di sconto (gamma)? Se sì, come?
4. E 'possibile calcolare il Ricompensa per gli stati? Come?

Answer 1

C'è un modello a che fare con la maggior parte dei problemi di MDP, ma penso che probabilmente avete omesse alcune informazioni dalla descrizione del problema, molto probabilmente ha a che fare con lo stato si sta cercando di raggiungere, o il modo in cui un episodio estremità (cosa succede se si esegue il bordo della griglia). Ho fatto del mio meglio per rispondere alle vostre domande, ma ho accodato un primer sul processo che uso per affrontare questi tipi di problemi.

In primo luogo l'utilità è una misura abbastanza astratto di quanto si vuole essere in un determinato stato. E 'sicuramente possibile avere due stati con uguale utilità, anche quando si misura l'utilità con semplici euristiche (euclidee o di Manhattan a distanza). In questo caso, suppongo che il valore d'uso e la ricompensa sono intercambiabili.

A lungo termine, l'obiettivo in questi tipi di problemi tende ad essere, come si fa a massimizzare il (lungo termine) ricompensa attesa? Il tasso di apprendimento, gamma, controlla quanta enfasi si posto sullo stato attuale rispetto a dove si vuole finire - in modo efficace si può pensare di gamma come uno spettro che va da, 'fare la cosa i benefici più mi ha in questo passo temporale' per all'altro estremo < em> 'esplorare tutte le opzioni, e tornare alla migliore' . Sutton e Barto in là libro su hanno qualche veramente bello 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. Qual è un'azione? Quante azioni sono lì?
3. Se si avvia 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 da 5, quindi ci sono 25 stati.
2. Ci sono quattro azioni possibili, {E, N, S, W}
3. La probabilità di raggiungere con successo uno stato adiacente dopo l'applicazione di un'azione adatto è 0,7, la probabilità di non muoversi (rimanendo nello stesso stato è 0,3). Supponendo (0,0) è la cella a sinistra e (4,4) è la cella in basso a destra, la tabella seguente 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 ha un numero adeguato di voci. Su un 5 per 5 griglia ci sono 25 stati e 4 azioni, così la tabella devono avere 100 voci.
2. Controllare per assicurarsi che per una coppia di stato / azione di avvio, solo due voci hanno non nulla probabilità di corso.

---

Modifica. rispondendo alla richiesta di probabilità di transizione a lo stato di destinazione. La notazione seguente presume

• v è lo 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

IND.1) probabilmente non è quel robot deve sempre muoversi - vale a dire quelli del 30% sono "ah, ora mi riposo un po '" o "non vi era alcun potere di spostare a tutti ".

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, v'è una rappresentazione griglia codice colore delle azioni raccomandate per ogni stato, nonche la griglia originale premio / matrice.

Rivedere la politica / strategia finale Fase 4. Condivide la vostra intuizione?