Chapter 4: Dynamic Programming

English The term dynamic programming (DP) refers to a collection of algorithms that can be used to compute optimal policies given a perfect model of the environment as a Markov decision process (MDP). Classical DP algorithms are of limited utility in reinforcement learning both because of their assumption of a perfect model and because of their great computational expense, but they are still important theoretically. DP provides an essential foundation for understanding the methods in the rest of this book.

English 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 Bellman equations into assignments, that is, into update rules for improving approximations of the desired value functions.

English Computing the state-value function v_π for an arbitrary policy π is called policy evaluation or the prediction problem. If the environment's dynamics are completely known, then the Bellman equation for v_π is a system of |S| simultaneous linear equations in |S| unknowns. We use an iterative method: a sequence of approximations v₀, v₁, v₂, ... where each successive approximation is obtained by using the Bellman equation as an update rule:

English The sequence {v_k} converges to v_π as k→∞. This algorithm is called iterative policy evaluation. Each iteration does an expected update — the new value of each state is computed from the expected values of successor states. In practice, the in-place version (updating values in a single array) usually converges faster.

English Our reason for computing the value function is to help find better policies. Given a deterministic policy π, we ask: should we change to deterministically choose action a ≠ π(s) in state s? The key criterion is whether q_π(s,a) > v_π(s). If it is better to select a once in s and thereafter follow π, then one would expect the new policy (selecting a every time s is encountered) to be better overall.

English Let π and π' be any pair of deterministic policies such that q_π(s, π'(s)) ≥ v_π(s) for all s∈S. Then π' must be as good as, or better than, π: v_π'(s) ≥ v_π(s) for all s. Moreover, if there is strict inequality at any state, then there must be strict inequality at that state in the value functions.

English We extend to consider changes at all states to all possible actions, selecting at each state the action that appears best according to q_π. This new greedy policy π' is:

English By construction, the greedy policy meets the conditions of the policy improvement theorem, so it is as good as or better than the original policy. If the new greedy policy is as good as but not better than π, then v_π' = v_π, and it follows that v_π' must satisfy the Bellman optimality equation — meaning both π and π' are optimal policies.

English Once a policy π has been improved using v_π to yield π', we can compute v_π' and improve again. This produces a sequence of monotonically improving policies and value functions:

English Because a finite MDP has only a finite number of policies, this process must converge to an optimal policy in a finite number of iterations. This is called policy iteration. Each policy evaluation is started with the value function for the previous policy, which typically results in fast convergence.

English One drawback to policy iteration is that each iteration involves policy evaluation, which may itself require multiple sweeps through the state set. The policy evaluation step can be truncated — an important special case is stopping after just one sweep. This algorithm is called value iteration:

English Value iteration is obtained simply by turning the Bellman optimality equation into an update rule. It effectively combines one sweep of policy evaluation and one sweep of policy improvement in each sweep.

English Asynchronous DP algorithms do not require systematic sweeps of the entire state set. They can update the values of states in any order, using whatever values of other states happen to be available. This gives great flexibility in selecting which states to update, enabling us to improve the value of interesting states first, perhaps those most relevant to the agent's experience.

English Generalized Policy Iteration (GPI) refers to the general idea of letting policy evaluation and policy improvement interact regardless of the details and granularity of the two processes. Nearly all reinforcement learning methods can be viewed as instances of GPI — each has identifiable policies and value functions, with the policy always being improved relative to the value function and the value function always being driven toward the value function for the policy.

English DP may be of little practical utility for today's large problems due to the curse of dimensionality: computational requirements grow exponentially with the number of state variables. However, DP has been shown to be polynomially efficient in the size of the state set |S| and the action set |A|. In practice, DP algorithms can be used to solve MDPs with millions of states.