Policy-Iteration.md

POLICY-ITERATION

AIMA3e

function POLICY-ITERATION(mdp) returns a policy
 inputs: mdp, an MDP with states S, actions A(s), transition model P(s′ | s, a)
 local variables: U, a vector of utilities for states in S, initially zero
        π, a policy vector indexed by state, initially random

 repeat
   U ← POLICY-EVALUATION(π, U, mdp)
   unchanged? ← true
   for each state s in S do
     if max_{a ∈ A(s)} Σ_s′ P(s′ | s, a) U[s′] > Σ_s′ P(s′ | s, π[s]) U[s′] then do
       π[s] ← argmax_{a ∈ A(s)} Σ_s′ P(s′ | s, a) U[s′]
       unchanged? ← false
 until unchanged?
 return π

---

Figure ?? The policy iteration algorithm for calculating an optimal policy.

---

AIMA4e

function POLICY-ITERATION(mdp) returns a policy
 inputs: mdp, an MDP with states S, actions A(s), transition model P(s′ | s, a)
 local variables: U, a vector of utilities for states in S, initially zero
        π, a policy vector indexed by state, initially random

 repeat
   U ← POLICY-EVALUATION(π, U, mdp)
   unchanged? ← true
   for each state s in S do
     a ^* ← argmax_{a ∈ A(s)} Q-VALUE(mdp,s,a,U)
     if Q-VALUE(mdp,s,a^*,U) > Q-VALUE(mdp,s,π[s],U) then do
       π[s] ← a^* ; unchanged? ← false
 until unchanged?
 return π

---

Figure ?? The policy iteration algorithm for calculating an optimal policy.