Dynamic programming algorithms assume we have perfect knowledge of the transition and reward structure. In this respect, they are distinguished from most RL algorithms which observe the agent interacting with the environment to gather information about these quantities directly.
The state values are initialized arbitrarily (usually to zero). The deterministic policy is also initialized (e.g., by choosing a random action for each state). The algorithm then alternates between iteratively computing the state values for the current policy (policy evaluation) and improving that policy (policy improvement).
Policy evaluation: We sweep through the states , updating their values:
where is the successor state and is the state transition probability. Each update makes consistent with the value at the successor state using the Bellman equation for state values. This is termed bootstrapping.
Policy improvement: To update the policy, we greedily choose the action that maximizes the value for each state:
This is guaranteed to improve the policy according to the policy improvement theorem.
These two steps are iterated until the policy converges.
There are many variations of this approach:
- In policy iteration, the policy evaluation step is iterated until convergence before policy improvement. The values can be updated either in place or synchronously in each sweep.
- In value iteration, the policy evaluation procedure sweeps through the values just once before policy improvement.
- Asynchronous dynamic programming algorithms don’t have to systematically sweep through all the values at each step but can update a subset of the states in place in an arbitrary order.