Interactive demo · Probabilistic Machine Learning: Advanced Topics · Chapter 34

Planning in an MDP: value iteration and policy iteration

When the transition model and the rewards are known, an optimal policy can be computed. Value iteration repeats the Bellman backup \(V_{k+1}=T^*V_k\) (best action, then expected next value), which shrinks the sup-norm error by the factor \(\gamma\) at every sweep. Policy iteration evaluates the current policy exactly (a linear system) and then acts greedily; it stops after a handful of sweeps. Choose a world, the discount \(\gamma\), the probability that the agent slips sideways and the cost of a step, then move the iteration slider to watch the value function and the greedy policy settle.

World

Method

Discount γ

Slip probability (grid world)

Step cost (grid world)

Iteration k

Try these

Grid world: actions up, right, down, left; with probability equal to the slip the agent moves at a right angle instead (half to each side); walls and the border block moves; the goal G pays +1 and the pit X pays −1 when entered and both are absorbing; every other step costs the step cost. Value iteration starts from \(V_0=0\); policy iteration starts from the policy "always up" and keeps its old action when a tie occurs. Values at the absorbing states are 0.

In the lecture notes