17  MDPs and Value/Policy Iteration

Lecture 17

Keywords

Bellman equation, value iteration, policy iteration, Markov decision processes, exploration versus exploitation

Based on the lecture by Andrew Ng — CS229, Stanford University, Autumn 2018.

Lecture 16 defined a Markov decision process and claimed an optimal policy for the 11-state gridworld without saying where it came from. This lecture supplies the method. It defines three objects: VπV^\pi, the value of following a fixed policy; V∗V^*, the best value any policy can achieve; and π∗\pi^*, the policy that achieves it. Each satisfies a version of Bellman’s equation, and the two standard algorithms, value iteration and policy iteration, are two ways of solving those equations. The lecture then drops the assumption that the transition probabilities are known. It estimates them from the robot’s own experience, and this raises the question of how much the robot should explore.

17.1 The value of a policy

6:46 For a policy π\pi, the value function Vπ:S→RV^\pi : S \to \mathbb{R} gives the expected total payoff of starting in ss and following π\pi for ever:

Vπ(s)=E[R(s0)+γR(s1)+γ2R(s2)+⋯  |  s0=s, π]. V^\pi(s) = \mathbb{E}\left[ R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \cdots \;\middle|\; s_0 = s,\ \pi \right].

8:40 Ng’s example is deliberately poor. From some states it drives straight for the −1-1. The left half of Figure 17.1 uses a concrete policy of that kind, East from every state. On the top row it reaches the +1+1 and is worth about 0.6 to 0.76. Along the middle and bottom rows it runs into the −1-1, or stalls against the east wall paying −0.02-0.02 a step, and is worth about −0.3-0.3 to −1.1-1.1. The ±1\pm 1 cells are absorbing: once the robot reaches one, it collects that reward and the world ends.

10:57 The equation that governs VπV^\pi comes from splitting the payoff after its first term. Factor one γ\gamma out of everything after R(s0)R(s_0):

R(s0)+γ(R(s1)+γR(s2)+⋯ ). R(s_0) + \gamma \bigl( R(s_1) + \gamma R(s_2) + \cdots \bigr).

The bracket is the payoff of a robot that starts in s1s_1 and follows π\pi. Its expectation is Vπ(s1)V^\pi(s_1), and s1s_1 is drawn from Psπ(s)P_{s\pi(s)}, because in state ss the policy takes action π(s)\pi(s). Writing s′s' for the next state gives Bellman’s equation for VπV^\pi:

Vπ(s)=R(s)+γ∑s′∈SPsπ(s)(s′) Vπ(s′).(17.1) V^\pi(s) = R(s) + \gamma \sum_{s' \in S} P_{s\pi(s)}(s')\, V^\pi(s'). \tag{17.1}

The first term is the immediate reward, which the robot gets just for waking up in ss. The second is the discounted expected future reward.

19:42 For a fixed π\pi, Equation 17.1 is linear in the unknowns Vπ(s)V^\pi(s). For s=(3,1)s = (3, 1), with π\pi going North, it reads

Vπ(3,1)=R(3,1)+γ[0.8 Vπ(3,2)+0.1 Vπ(2,1)+0.1 Vπ(4,1)], V^\pi(3,1) = R(3,1) + \gamma\bigl[0.8\,V^\pi(3,2) + 0.1\,V^\pi(2,1) + 0.1\,V^\pi(4,1)\bigr],

and one such equation for each of the 11 states gives 11 linear equations in 11 unknowns. A linear solver handles that instantly. The generator solves the system for the East policy and checks the result against 5,000 sweeps of repeated substitution into Equation 17.1. The two agree to 10−910^{-9}.

Figure 17.1: Left: the policy “always go East” and its value VπV^\pi, solved from the 11 Bellman equations. Right: the optimal policy and the optimal value function V∗V^* for R=−0.02R = -0.02, γ=0.99\gamma = 0.99. Cell (3,1)(3, 1), whose action the lecture works out by hand, is highlighted.

17.2 The optimal value function and the optimal policy

24:47 The optimal value function is the best value any policy achieves from each state:

V∗(s)=max⁡πVπ(s). V^*(s) = \max_\pi V^\pi(s).

Ng flags a terminology trap. Both VπV^\pi and V∗V^* are called “value functions”, but one belongs to a particular policy, good or bad, and the other to the best of them. The maximum is over a combinatorially large set, 494^9 policies even for this small grid, so the definition does not suggest how to compute V∗V^*. Its Bellman equation does.

27:12 Run the same argument as for Equation 17.1, but let the robot choose its first action well. It collects R(s)R(s) for waking up in ss. Whatever action aa it takes, it then lands in s′∼Psas' \sim P_{sa} and can collect at most V∗(s′)V^*(s') from there. The best first action is the one with the largest expected continuation, so

V∗(s)=R(s)+max⁡a∈A  γ∑s′∈SPsa(s′) V∗(s′).(17.2) V^*(s) = R(s) + \max_{a \in A}\; \gamma \sum_{s' \in S} P_{sa}(s')\, V^*(s'). \tag{17.2}

29:44 If V∗V^* were known, the optimal action would be the one that attains that maximum. Ng asks the room what to do in state ss, and the answer is already in Equation 17.2:

π∗(s)=arg⁡max⁡a∈A∑s′∈SPsa(s′) V∗(s′).(17.3) \pi^*(s) = \arg\max_{a \in A} \sum_{s' \in S} P_{sa}(s')\, V^*(s'). \tag{17.3}

γ\gamma is dropped because a positive constant does not move an argmax. 32:50 Ng states, without proof, that this policy is optimal from every state at once: V∗(s)=Vπ∗(s)≥Vπ(s)V^*(s) = V^{\pi^*}(s) \ge V^\pi(s) for every π\pi and every ss. One policy is best everywhere, so no state has to trade off against another. The generator checks both halves. The value of the greedy policy, solved from its own linear system, equals V∗V^* to 10−910^{-9}, and V∗V^* is at least VπV^\pi, state by state, for 3,000 random policies. The plan is therefore to find V∗V^* and then read off π∗\pi^* with Equation 17.3.

17.3 Value iteration

35:22 Value iteration treats Equation 17.2 as an update rule:

  1. Initialise V(s):=0V(s) := 0 for every ss.
  2. Repeat until convergence: for every ss, V(s):=R(s)+max⁡aγ∑s′Psa(s′) V(s′)V(s) := R(s) + \max_a \gamma \sum_{s'} P_{sa}(s')\, V(s').

38:07 There are two ways to carry out step 2, and Ng compares them to gradient descent. A synchronous update computes the right-hand side for all 11 states from the old values, then overwrites all 11 at once. In vector form this is V:=B(V)V := B(V), where BB is called the Bellman backup operator. An asynchronous update sweeps through the states one at a time and overwrites each value as soon as it is computed, so later states in the sweep already use the new values. Both converge to V∗V^*.

Ng’s default is the synchronous form, because it is a matrix operation and vectorises. He says “asynchronous” at this point in the recording, but the reason he gives, vectorisation, and the procedure he describes, compute all eleven and then update, are the synchronous one. The asynchronous form has the opposite advantage: it needs fewer sweeps. On the gridworld with γ=0.99\gamma = 0.99, the max-norm error falls below 10−610^{-6} after 21 asynchronous sweeps against 29 synchronous ones (Figure 17.2).

40:32 A student asks how to code the absorbing states. One way is to give them transition probabilities of zero to every state, so that their value is just RR. Another is to add a twelfth, zero-reward “sink” state that they lead to and that loops on itself. Ng calls the second cleaner and the first more common. Both give the same values.

43:07 Why does it converge? The problem set shows that BB is a contraction in the max norm: ∥B(V)−B(V′)∥∞≤γ∥V−V′∥∞\lVert B(V) - B(V')\rVert_\infty \le \gamma \lVert V - V'\rVert_\infty. Since V∗=B(V∗)V^* = B(V^*), each synchronous sweep shrinks the error by at least a factor γ\gamma, so ∥Vk−V∗∥∞≤γk∥V0−V∗∥∞\lVert V_k - V^*\rVert_\infty \le \gamma^k \lVert V_0 - V^*\rVert_\infty. Ng turns this into a rule of thumb: at γ=0.99\gamma = 0.99, value iteration needs a few hundred iterations, and at γ=0.9\gamma = 0.9 a few dozen.

The bound is right but, for this MDP, very loose. Taken literally, it needs 1,375 sweeps per unit of initial error to reach 10−610^{-6} at γ=0.99\gamma = 0.99, and 132 at γ=0.9\gamma = 0.9. The gridworld gets there in 29 sweeps at γ=0.99\gamma = 0.99 and 21 at γ=0.9\gamma = 0.9. The generator asserts that every synchronous sweep is within the bound, so nothing here contradicts the theorem. The reason is the absorbing states. After kk sweeps the remaining error is roughly the discounted value of what happens beyond step kk. Under π∗\pi^*, starting from (1,1)(1, 1), the robot is still wandering after 10 steps with probability 0.04, and after 20 steps with probability essentially zero, so there is little left to discount. The factor γ\gamma only governs the rate when the process can run on for a long time without ending. The more useful fact for practice is that the policy converges before the values. With γ=0.99\gamma = 0.99, the greedy policy Equation 17.3 of the synchronous estimate is already exactly π∗\pi^* after 11 sweeps, while the values are still off by as much as 0.08.

Figure 17.2: Value iteration on the gridworld: base-10 logarithm of the max-norm error against the number of sweeps, synchronous and asynchronous, at γ=0.99\gamma = 0.99 and γ=0.9\gamma = 0.9. Dotted lines are the guarantee γk∥V0−V∗∥∞\gamma^k \lVert V_0 - V^*\rVert_\infty, which every synchronous curve stays below, by a wide margin here because the robot is absorbed within a few steps.

17.4 Reading the policy off V∗V^*

45:15 Ng writes the converged V∗V^* on the board and uses it to justify the West arrow at (3,1)(3, 1) that lecture 16 asserted. Going West reaches (2,1)(2, 1) with probability 0.8, where V∗≈0.75V^* \approx 0.75. It slips North to (3,2)(3, 2), worth 0.69, with probability 0.1, and South into the wall, staying at (3,1)(3, 1), worth 0.71, with probability 0.1. The expected value is 0.740. Going North gives 0.8×0.69+0.1×0.75+0.1×0.49=0.6760.8 \times 0.69 + 0.1 \times 0.75 + 0.1 \times 0.49 = 0.676, so West wins.

The generator’s V∗V^* (Figure 17.1, right) matches the board values to two decimals: 0.746, 0.687, 0.709 and 0.491. Computed from the unrounded values, the two expectations are 0.736 and 0.674. Ng adds that a full check compares all four actions, and the full check is instructive. South, at 0.691, beats North: bumping into the wall and staying put is the second-best action, because North risks the slip into −1-1. East is last at 0.532.

17.5 Policy iteration

50:18 Policy iteration keeps a policy, not a value function, at the centre:

  1. Initialise π\pi randomly.
  2. Repeat until π\pi stops changing:
    1. V:=VπV := V^\pi, by solving the linear system Equation 17.1;
    2. for every ss, π(s):=arg⁡max⁡a∑s′Psa(s′) V(s′)\pi(s) := \arg\max_a \sum_{s'} P_{sa}(s')\, V(s').

Step (b) pretends that the current VV is optimal and acts greedily on it. Value iteration waits until VV has converged to extract a policy. Policy iteration extracts a new one on every round. 54:44 The trade-off, as Ng puts it, is the linear solve in step (a). For 11 states, or a few hundred, it is trivial, and policy iteration is fast. For 10,000 states or a million, solving the system on every round is expensive, and he would use value iteration. He also notes a more academic difference. Value iteration approaches V∗V^* and never exactly reaches it, as gradient descent approaches the minimum of a least-squares cost. Policy iteration stops after a finite number of rounds, at exactly π∗\pi^* and exactly V∗V^*, the way the normal equations jump straight to the answer. It must stop, because each round improves the policy, by the policy improvement theorem, and there are only finitely many policies to improve through.

The generator checks this on the gridworld. Started from 200 random policies, policy iteration needs between 2 and 8 evaluations, 5 on average, and always ends at the π∗\pi^* of Figure 17.1. From “always East” it needs 3. The values never decrease from one round to the next, in any state. In practice, Ng says, he sees value iteration used more, because real problems are large. For small ones policy iteration may converge a little faster.

NoteIn the official notes

Both algorithms, the synchronous and asynchronous variants, and the statement that policy iteration terminates are in cs229-notes12, section 2. The contraction argument for value iteration is a homework problem in the course.

17.6 Learning the model

58:41 So far PsaP_{sa} has been given. For a real robot, a helicopter or a chess opponent, it usually is not, and has to be estimated from experience. Run some policy for a while, count what happens, and use the maximum-likelihood estimate

P^sa(s′)=#{times action a was taken in s and led to s′}#{times action a was taken in s}.(17.4) \hat P_{sa}(s') = \frac{\#\{\text{times action } a \text{ was taken in } s \text{ and led to } s'\}}{\#\{\text{times action } a \text{ was taken in } s\}}. \tag{17.4}

When the denominator is zero, because aa has never been tried in ss, the common heuristic is a uniform guess, P^sa(s′)=1/∣S∣\hat P_{sa}(s') = 1/\lvert S\rvert.

1:01:41 Laplace smoothing would also avoid the 0/00/0: add 1 to every numerator and ∣S∣\lvert S\rvert to every denominator. Ng says it is allowed but uncommon, because, unlike naive Bayes, MDP solvers are not badly hurt by zero estimates. The generator suggests a stronger statement: on the gridworld, smoothing makes things worse. It runs a uniformly random policy for a given number of moves, builds P^\hat P with and without smoothing, solves for the policy, and scores it by its true loss, the largest V∗(s)−Vπ^(s)V^*(s) - V^{\hat\pi}(s) over states, averaged over 40 runs. The plain counts lose 0.078 after 1,000 moves and 0.010 after 10,000. With smoothing the losses are 0.263 and 0.023. The reason is visible in the formula. Smoothing gives every action a small probability of moving the robot to every state, including straight to the +1+1 or −1-1 from across the grid. With 11 states and only a few visits per state-action pair, that invented mass is large, and it is exactly the mass the optimal policy is most sensitive to. Exact recovery of π∗\pi^* is rare either way, 14 runs in 40 even after 10,000 moves without smoothing, because of the 0.0005 margin at (3,2)(3, 2) noted in lecture 16. Measuring the loss, not whether the policy is exactly π∗\pi^*, is the fair test.

1:03:01 Put together, the practical loop is:

  1. Take actions according to some policy π\pi to gain experience in the MDP.
  2. Update the estimates of PsaP_{sa} from the counts, and of RR if it is unknown.
  3. Solve Bellman’s equations for the estimated MDP by value iteration, warm-started from the previous VV if convenient, to get a new VV.
  4. Update π\pi to be greedy with respect to VV, and repeat.

1:06:03 The reward is usually part of the problem specification, but not always. For a trading application the reward is a day’s return, and for a car it might be a penalty for every pothole. Both are random functions of the state, so the same loop estimates the expected reward of each state by averaging what it observes.

17.7 Exploration versus exploitation

1:07:33 The loop above is greedy: it always acts on its current best estimate. Ng shows the trouble with a different MDP. A robot starts with a +1+1 nearby and a +10+10 farther away. If its first runs happen to reach the +1+1, the estimated model says that going there works, and the greedy policy keeps going there. Every trip ends at the +1+1, so the robot’s experience stays in that half of the state space, and the +10+10 is never found. Acting on what is known is exploitation. Trying actions that look worse to learn something new is exploration. The tension between them is not academic. Ng’s example is online advertising. Showing only the ads a user is predicted to click maximises short-term revenue. Showing occasional others is how the platform discovers interests nobody knew the user had.

1:13:28 The standard fix is ε-greedy exploration. On each step, with probability 1−ε1-\varepsilon take the action π(s)\pi(s), and with probability ε\varepsilon, for instance 0.1, take a random one. Ng points out that the name is backwards, since ε\varepsilon is the probability of acting randomly, not greedily, but it is the name everyone uses. With ε>0\varepsilon > 0 every action keeps being tried in every state the robot can reach, so the estimated model converges to the true one and the planned policy to π∗\pi^*, though finding a remote reward by chance can take a long time.

Figure 17.3 makes Ng’s example concrete in one dimension, in a toy of our own: an eight-cell corridor with the +10+10 five steps to the left of the start and the +1+1 two steps to the right. Moves slip 20% of the time, each step costs 0.02, γ=0.95\gamma = 0.95, and the robot learns both PsaP_{sa} and RR as above. Going left is worth about 7.65 and going right 0.86, so the right answer is not close. Over 200 independent learners, the fraction whose policy heads for the +10+10 after 150 episodes is 0.62 for the greedy learner, 0.68 with ε=0.1\varepsilon = 0.1 and 0.78 with ε=0.2\varepsilon = 0.2. Two details are worth noticing. The greedy learner is not completely stuck: its curve keeps creeping up, presumably because slipping moves sometimes carry it left without being asked. And none of the curves has reached 1, which is Ng’s caveat about how long a remote reward can take to find.

Figure 17.3: A toy version of the lecture’s exploration example, not from the lecture. Left: the corridor, with the start between a distant +10+10 and a nearby +1+1. Right: over 200 learners that estimate the model from experience and re-plan after each episode, the fraction whose current policy heads for the +10+10, for ε = 0 (greedy), 0.1 and 0.2.

1:16:17 Asked whether ε\varepsilon should stay fixed, Ng says there are many heuristics, and a reasonable one is to start large and shrink it. Another is Boltzmann exploration. Instead of a uniformly random action with probability ε\varepsilon, choose action aa with probability proportional to exp⁡(Q(s,a)/τ)\exp\bigl(Q(s, a)/\tau\bigr), where Q(s,a)=∑s′Psa(s′)V(s′)Q(s, a) = \sum_{s'} P_{sa}(s') V(s') is the estimated value of taking aa and τ\tau is a temperature. Actions that look nearly as good as the best are tried often, and actions that look terrible almost never. A student asks about rewarding the robot for visiting states it has never seen. That is intrinsic motivation, a research line Ng suggests looking up. And asked how often to re-plan, he says as often as the computation allows. It does no harm. With a physical robot or helicopter, where each flight is a session, re-planning between flights is the natural rhythm.

NoteIn the official notes

Estimating PsaP_{sa} and RR from experience, with the 1/∣S∣1/\lvert S\rvert rule for untried actions and the warm-started value iteration loop, is in cs229-notes12, section 3. The notes do not treat exploration. Lecture 18 extends the framework to continuous states, covered in section 4 of the same notes.