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.
Starting with this chapter, we usually assume that the environment is a finite MDP. That is, we assume that its state, action, and reward sets, $\cal S$, $\cal A$, and $\cal R$, are finite, and that its dynamics are given by a set of probabilities $p(s', r|s, a)$, for all $s \in\cal S$, $a \in\cal A(s)$, $r \in\cal R$, and $s' \in \cal S^+$ ($\cal S^+$ is $\cal S$ plus a terminal state if the problem is episodic). Although DP ideas can be applied to problems with continuous state and action spaces, exact solutions are possible only in special cases.
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. In this chapter we show how DP can be used to compute the value functions defined in the previous chapter.
As discussed in that chapter, we can easily obtain optimal policies once we have found the optimal value functions, $v_$ or $q_$, which satisfy the Bellman optimality equations:
or
for all $s \in\cal S$, $a \in \cal A(s)$, and $s' \in \cal S^+$. As we shall see, DP algorithms are obtained by turning Bellman equations such as these into assignments, that is, into update rules for improving approximations of the desired value functions.
First, we consider how to compute the state-value function $v_\pi$ for an arbitrary policy $\pi$. This is called policy evaluation in the DP literature. We also refer to it as the prediction problem. Recall that for all $s\in\cal S$:
Where $\pi(a|s)$ is the probability of taking action $a$ in state s under policy $\pi$, and the expectations are subscripted by $\pi$ to indicate that they are conditional on $\pi$ being followed. The existence and uniqueness of $v_\pi$ are guaranteed as long as either $\gamma < 1$ or eventual termination is guaranteed from all states under the policy $\pi$.
Other forms of the Bellman Equation:
All of these lead to the same result.
If the environment’s dynamics are completely known, then (4.4) is a system of $\cal |S|$ simultaneous linear equations in $\cal |S|$ unknowns (the $v_\pi(s)$, $s \in\cal S$). In principle, its solution is a straightforward, if tedious, computation.
For our purposes, iterative solution methods are most suitable. Consider a sequence of approximate value functions $v_0, v_1, v_2, . . .$, each mapping $\cal S^+$ to $\R$ (the real numbers). The initial approximation, $v_0$, is chosen arbitrarily (except that the terminal state, if any, must be given value 0), and each successive approximation is obtained by using the Bellman equation for $v_\pi$ (4.4) as an update rule:
