Chapter 4 — dynamic programming.

Dynamic programming (DP) is the collection of algorithms that compute optimal policies given a perfect model of the environment as an MDP. DP turns the Bellman equations into update rules. This page covers iterative policy evaluation (prediction), the policy improvement theorem, policy iteration, value iteration, asynchronous DP, the unifying idea of generalized policy iteration, and DP's efficiency and limits. DP is of limited practical use because of its assumptions and cost, but it is the theoretical foundation every later method approximates. Maps to lectures CS4–CS6.

What dynamic programming assumes

The term dynamic programming refers to a collection of algorithms that can be used to compute optimal policies given a perfect model of the environment as a finite MDP. Classical DP is of limited utility in RL both because of its assumption of a perfect model and because of its great computational expense — but it is still important theoretically. DP provides an essential foundation for understanding all the methods in the rest of the book; in a sense, all of them can be viewed as attempts to achieve much the same effect as DP, only with less computation and without assuming a perfect model.

The key idea of DP, and of reinforcement learning generally, is the use of value functions to organize and structure the search for good policies. DP algorithms are obtained by turning the Bellman equations into update rules for improving approximations of the desired value functions.

Policy evaluation (prediction)

First consider how to compute the state-value function \(v_\pi\) for an arbitrary policy \(\pi\). This is called policy evaluation, or the prediction problem. Recall the Bellman expectation equation: if the environment's dynamics are completely known, this is a system of \(|\mathcal{S}|\) simultaneous linear equations in \(|\mathcal{S}|\) unknowns (the values). In principle solvable directly, but an iterative solution method is most suitable. Consider a sequence of approximate value functions \(v_0, v_1, v_2,\dots\); using the Bellman equation as an update rule:

Clearly \(v_k=v_\pi\) is a fixed point of this update. Indeed the sequence \(\{v_k\}\) converges to \(v_\pi\) as \(k\to\infty\). This algorithm is called iterative policy evaluation. Each round of updates is called a sweep through the state space.

The update is called an expected update because it is based on an expectation over all possible next states, rather than on a sample next state. To write a program, you would use two arrays (old \(v_k\), new \(v_{k+1}\)) — but DP algorithms usually update in place, sweeping through the states and overwriting each value immediately. In-place updates typically converge faster, because they use new data as soon as it is available.

Iterative Policy Evaluation (in place):
  Input: policy π, dynamics p, discount γ, threshold θ>0
  Initialize V(s)=0 for all s
  repeat
    Δ ← 0
    for each state s:
       v ← V(s)
       V(s) ← Σ_a π(a|s) Σ_{s',r} p(s',r|s,a)[ r + γ V(s') ]
       Δ ← max(Δ, |v − V(s)|)
  until Δ < θ
  return V ≈ v_π

What policy evaluation looks like

In the grid-world picture shown in lecture ("values after 100 iterations"), each cell holds the current estimate of the value of being in that cell under the policy. With each sweep the estimates become more accurate, the high values spreading outward from the goal cell, until they stop changing. That visual is precisely iterative policy evaluation running to convergence. The lecture grid (noisy movement, \(-0.1\) per step, \(+1\) at the goal, \(-1\) at the pit) is a perfect small MDP to evaluate a policy on.

Policy improvement

We compute \(v_\pi\) in order to find better policies. Suppose we have \(v_\pi\) for a deterministic policy \(\pi\). For some state \(s\) we want to know whether we should change the policy to deterministically choose an action \(a\neq\pi(s)\). The way to decide is to consider selecting \(a\) in \(s\) and thereafter following the existing \(\pi\) — the value of this way of behaving is exactly \(q_\pi(s,a)\):

If this is greater than \(v_\pi(s)\), then it is better to select \(a\) once in \(s\) and thereafter follow \(\pi\) than it would be to follow \(\pi\) all the time — and, crucially, it is then better to select \(a\) every time \(s\) is encountered. The policy improvement theorem formalizes this: if \(\pi'\) is any policy such that \(q_\pi(s,\pi'(s)) \ge v_\pi(s)\) for all \(s\), then \(\pi'\) is at least as good as \(\pi\) (\(v_{\pi'}(s)\ge v_\pi(s)\) for all \(s\)); and if the inequality is strict at any state, then \(\pi'\) is strictly better there.

The greedy policy

It is natural to consider the new policy that is greedy with respect to \(v_\pi\) — at each state, select the action that looks best according to \(q_\pi(s,a)\):

The greedy policy takes the action that looks best after one step of lookahead. By construction it meets the conditions of the policy improvement theorem, so it is as good as, or better than, the original policy. The process of making a new policy that improves on an original by making it greedy with respect to the value function of the original is called policy improvement. If the improved policy is just as good as (not better than) the old one, then \(v_{\pi'}=v_\pi\), and both satisfy the Bellman optimality equation — so both are optimal. Policy improvement thus gives a strictly better policy except when the original is already optimal.

Policy iteration

Once a policy \(\pi\) has been improved using \(v_\pi\) to yield a better \(\pi'\), we can compute \(v_{\pi'}\) and improve again to yield an even better \(\pi''\). We can thus obtain a sequence of monotonically improving policies and value functions:

where \(\xrightarrow{E}\) denotes a policy evaluation and \(\xrightarrow{I}\) a policy improvement. Each policy is guaranteed to be a strict improvement over the previous one (unless it is already optimal). Because a finite MDP has only a finite number of policies, this process must converge to an optimal policy and the optimal value function in a finite number of iterations. This is policy iteration.

Value iteration

One drawback of policy iteration is that each iteration involves policy evaluation, which may itself require many sweeps and converges only in the limit. Must we wait for exact convergence before improving? No. The policy-evaluation step of policy iteration can be truncated in several ways without losing the convergence guarantees. An important special case is to stop after just one sweep (one update of each state). This algorithm is called value iteration, and it is obtained by turning the Bellman optimality equation into an update rule:

For arbitrary \(v_0\), the sequence \(\{v_k\}\) converges to \(v_*\). Value iteration effectively combines, in each of its sweeps, one sweep of policy evaluation and one sweep of policy improvement. It requires the max to be taken over all actions, the only difference from the policy-evaluation update. Once \(v_k\) changes by only a small amount in a sweep, we stop and output the greedy policy with respect to the resulting value function — which is optimal.

Value Iteration:
  Initialize V(s)=0 for all s
  repeat
    Δ ← 0
    for each state s:
       v ← V(s)
       V(s) ← max_a Σ_{s',r} p(s',r|s,a)[ r + γ V(s') ]
       Δ ← max(Δ, |v − V(s)|)
  until Δ < θ
  return policy π(s) = argmax_a Σ_{s',r} p(s',r|s,a)[ r + γ V(s') ]

Asynchronous DP

A major drawback of the DP methods so far is that they involve operations over the entire state set — a sweep. If the state set is very large, even a single sweep can be prohibitively expensive. Asynchronous DP algorithms are in-place iterative methods that are not organized in terms of systematic sweeps; they update the values of states in any order whatsoever, using whatever values of other states happen to be available. To converge correctly, an asynchronous algorithm must continue to update the values of all states — it cannot ignore any state after some point. This flexibility means we can choose the states to update so as to improve the algorithm's rate of progress, and we can intermix computation with real-time interaction: run the algorithm at the same time as the agent actually experiences the MDP, focusing the updates on the states the agent visits.

Generalized policy iteration

Policy iteration consists of two simultaneous, interacting processes — one making the value function consistent with the current policy (evaluation), and the other making the policy greedy with respect to the current value function (improvement). In policy iteration these alternate, each completing before the other begins, but this is not necessary. In value iteration, for example, only a single evaluation sweep is performed between improvements. In asynchronous methods they are interleaved at an even finer grain. The term generalized policy iteration (GPI) refers to the general idea of letting policy-evaluation and policy-improvement processes interact, independent of the granularity and other details of the two processes.

Almost all RL methods are well described as GPI. The two processes can be viewed as both competing and cooperating: making the policy greedy with respect to the value function typically makes the value function incorrect for the changed policy, and making the value function consistent with the policy typically causes the policy to no longer be greedy. In the long run, the two processes interact to find a single joint solution: a policy and a value function that are unchanged by either process — which can occur only when a policy has been found that is greedy with respect to its own evaluation, meaning the Bellman optimality equation holds, and the policy and value function are optimal.

Efficiency of DP and the curse of dimensionality

DP may not be practical for very large problems, but compared with other methods for solving MDPs it is actually quite efficient. In the worst case the time DP methods take to find an optimal policy is polynomial in the number of states and actions — exponentially faster than any direct search in policy space, and faster than linear programming for large state spaces. The real obstacle is the curse of dimensionality: the number of states often grows exponentially with the number of state variables. Large state sets create difficulty, but these are inherent difficulties of the problem, not of DP as a solution method. On problems with millions of states, DP (especially asynchronous DP) can still be the best approach when a model is available.

Bootstrapping

DP methods update estimates of the values of states based on estimates of the values of successor states. That is, they update estimates on the basis of other estimates. We call this general idea bootstrapping. Many RL methods bootstrap, even ones that, unlike DP, do not require a perfect model of the environment. The next chapter, Monte Carlo, is the principal method that does not bootstrap — it learns from complete actual returns instead. Contrasting bootstrapping (DP) with non-bootstrapping (MC) is one of the most illuminating axes for organizing all of RL.

Lecture map & recap

References & next

• Chapter 5 — Monte Carlo Methods → · learning without a model
• ← Chapter 3 — Finite MDPs
• CS4–CS6 — Slides Explained · the lecture version