Risolvere l’esempio utilizzando l’iterazione del valore
VI dovrebbe avere ancora più senso una volta completato un problema di esempio, quindi torniamo al nostro MDP sul golf. Lo abbiamo formalizzato come MDP ma attualmente l’agente non conosce la migliore strategia quando si gioca a golf, quindi risolviamo l’MDP del golf utilizzando VI.
Inizieremo definendo i parametri del nostro modello utilizzando valori abbastanza standard:
γ = 0.9 // discount factor
θ = 0.01 // convergence threshold
Successivamente inizializzeremo la nostra tabella dei valori su 0 per gli stati in S:
// value tableV(s0) = 0
V(s1) = 0
V(s2) = 0
Ora possiamo iniziare nel ciclo esterno:
Δ = 0
E tre passaggi del ciclo interno per ogni stato in cui si trova S:
// Bellman update rule
// V(s) ← maxₐ Σₛ′, ᵣ p(s′, r|s, a) * (r + γV(s′))//******************* state s0 *******************//
v = 0
// we have only looked at one action here as only one is available from s0
// we know that the others are not possible and would therefore sum to 0
V(s0) = max(T(s0 | s0, hit to green) * (R(s0, hit to green, s0) + γ * V(s0)) +
T(s1 | s0, hit to green) * (R(s0, hit to green, s1) + γ * V(s1)))
V(s0) = max(0.1 * (0 + 0.9 * 0) +
0.9 * (0 + 0.9 * 0))
V(s0) = max(0) = 0
// Delta update rule
// Δ ← max(Δ,| v - V(s)|)
Δ = max(Δ, |v - v(s0)|) = max(0, |0 - 0|) = 0
//******************* state s1 *******************//
v = 0
// there are 2 available actions here
V(s1) = max(T(s0 | s1, hit to fairway) * (R(s1, hit to fairway, s0) + γ * V(s0)) +
T(s1 | s1, hit to fairway) * (R(s1, hit to fairway, s1) + γ * V(s1)),
T(s1 | s1, hit in hole) * (R(s1, hit in hole, s1) + γ * V(s1)) +
T(s2 | s1, hit in hole) * (R(s1, hit in hole, s2) + γ * V(s2)))
V(s1) = max(0.9 * (0 + 0.9 * 0) +
0.1 * (0 + 0.9 * 0),
0.1 * (0 + 0.9 * 0) +
0.9 * (10 + 0.9 * 0))
V(s1) = max(0, 9) = 9
Δ = max(Δ, |v - v(s1)|) = max(0, |0 - 9|) = 9
//******************* state s2 *******************//
// terminal state with no actions
Questo ci dà il seguente aggiornamento alla nostra tabella dei valori:
V(s0) = 0
V(s1) = 9
V(s2) = 0
Non dobbiamo preoccuparci s2 poiché si tratta di uno stato terminale, il che significa che qui non è possibile alcuna azione.
Ora rompiamo il ciclo interno e continuiamo il ciclo esterno, eseguendo un controllo di convergenza su:
Δ < θ = 9 < 0.01 = False
Poiché non abbiamo raggiunto la convergenza, eseguiamo una seconda iterazione del ciclo esterno:
Δ = 0
E altri 3 passaggi del ciclo interno, utilizzando la tabella dei valori aggiornata:
//******************* state s0 *******************//v = 0
V(s0) = max(T(s0 | s0, hit to green) * (R(s0, hit to green, s0) + γ * V(s0)) +
T(s1 | s0, hit to green) * (R(s0, hit to green, s1) + γ * V(s1)))
V(s0) = max(0.1 * (0 + 0.9 * 0) +
0.9 * (0 + 0.9 * 9))
V(s0) = max(7.29) = 7.29
Δ = max(Δ, |v - v(s0)|) = max(0, |0 - 7.29|) = 7.29
//******************* state s1 *******************//
v = 9
V(s1) = max(T(s0 | s1, hit to fairway) * (R(s1, hit to fairway, s0) + γ * V(s0)) +
T(s1 | s1, hit to fairway) * (R(s1, hit to fairway, s1) + γ * V(s1)),
T(s1 | s1, hit in hole) * (R(s1, hit in hole, s1) + γ * V(s1)) +
T(s2 | s1, hit in hole) * (R(s1, hit in hole, s2) + γ * V(s2)))
V(s1) = max(0.9 * (0 + 0.9 * 7.29) +
0.1 * (0 + 0.9 * 9),
0.1 * (0 + 0.9 * 9) +
0.9 * (10 + 0.9 * 0))
V(s1) = max(6.7149, 9.81) = 9.81
Δ = max(Δ, |v - v(s1)|) = max(7.29, |9 - 9.81|) = 7.29
//******************* state s2 *******************//
// terminal state with no actions
Alla fine della seconda iterazione, i nostri valori sono:
V(s0) = 7.29
V(s1) = 9.81
V(s2) = 0
Controlla ancora una volta la convergenza:
Δ < θ = 7.29 < 0.01 = False
Ancora nessuna convergenza, quindi continuiamo lo stesso processo di cui sopra finché Δ < θ. Non mostrerò tutti i calcoli, i due precedenti sono sufficienti per capire il processo.
Dopo 6 iterazioni, la nostra politica converge. Questi sono i nostri valori e il tasso di convergenza che cambiano durante ogni iterazione:
Iteration V(s0) V(s1) V(s2) Δ Converged
1 0 9 0 9 False
2 7.29 9.81 0 7.29 False
3 8.6022 9.8829 0 1.3122 False
4 8.779447 9.889461 0 0.177247 False
5 8.80061364 9.89005149 0 0.02116664 False
6 8.8029969345 9.8901046341 0 0.0023832945 True
Ora possiamo estrarre la nostra policy:
// Policy extraction rule
// π(s) = argmaxₐ Σₛ′, ᵣ p(s′, r|s, a) * (r + γV(s′))//******************* state s0 *******************//
// we know there is only one possible action from s0, but let's just do it anyway
π(s0) = argmax(T(s0 | s0, hit to green) * (R(s0, hit to green, s0) + γ * V(s0)) +
T(s1 | s0, hit to green) * (R(s0, hit to green, s1) + γ * V(s1))
π(s0) = argmax(0.1 * (0 + 0.9 * 8.8029969345) +
0.9 * (0 + 0.9 * 9.8901046341))
π(s0) = argmax(8.80325447773)
π(s0) = hit to green
//******************* state s1 *******************//
π(s1) = argmax(T(s0 | s1, hit to fairway) * (R(s1, hit to fairway, s0) + γ * V(s0)) +
T(s1 | s1, hit to fairway) * (R(s1, hit to fairway, s1) + γ * V(s1)),
T(s1 | s1, hit in hole) * (R(s1, hit in hole, s1) + γ * V(s1)) +
T(s2 | s1, hit in hole) * (R(s1, hit in hole, s2) + γ * V(s2)))
V(s1) = max(0.9 * (0 + 0.9 * 8.8029969345) +
0.1 * (0 + 0.9 * 9.8901046341),
0.1 * (0 + 0.9 * 9.8901046341) +
0.9 * (10 + 0.9 * 0))
π(s1) = argmax(8.02053693401, 9.89010941707)
π(s1) = hit in hole
La nostra politica finale è:
π(s0) = hit to green
π(s1) = hit to hole
π(s2) = terminal state (no action)
Quindi, quando il nostro agente è in Palla sul fairway stato (s0), l’azione migliore è quella colpire al verde. Ciò sembra abbastanza ovvio poiché è l’unica azione disponibile. Tuttavia, dentro s1dove ci sono due azioni possibili, la nostra politica ha imparato a farlo colpito nel buco. Ora possiamo offrire questa politica appresa ad altri agenti che vogliono giocare a golf!
E il gioco è fatto! Abbiamo appena risolto un problema RL molto semplice utilizzando l’iterazione del valore.
Fonte: towardsdatascience.com
