Sutton-Barto, page 160, towards bottom:

enter image description here

Why is dynamic programming an example of planning? There is no simulation in dynamic programming.


2 Answers 2


There is no simulation in dynamic programming.

In fact there is.

Using the model $p(r, s'|s,a)$ (or other variations of it that are possible in Policy Iteration and Value Iteration) to predict outcomes of immediate reward and next state is a simulation of the environment.

Therefore the update rule for Value Iteration:

$$v(s) \leftarrow \text{max}_a \sum_{r,s'} p(r,s')(r + \gamma v(s')) $$

includes simulated experience of the outcome from being in state $s$ and picking the currently greedy action. Technically it is a sum over all possible outcomes predicted by the model, weighted by probability.


Dynamic programming is a algorithm paradigm, that is, an approach to design algorithms for problems that meet specific criteria (optimal substructure and overlapping sub-problems). So, it's not just used to solve MDPs. If you're interested in this topic, I'd recommend Introduction to Algorithms by CRLS.

Planning is the process of searching for a plan (a sequence of actions) or policy like $\pi(s)$. You usually need to know something about the environment to plan. For example, to find a policy for an MDP using e.g. policy iteration, you need to know the cost of your actions (reward function) and how an action affects the next state (transition model). Similarly, to find the shortest-path in a graph using a state-space search algorithm (like the Dijkstra's algorithm), you need to know the cost of the edges.

In RL, the goal is also to find policies, but we interact with the environment using a trial-and-error approach. In RL, we also need to know the rules of the environment (e.g. the actions you can take) and have the environment emit rewards, even if we don't know the reward function beforehand (although often we design the reward function, so we know it, but we don't usually know the transition model).

So, in planning, you need to know the reward function, transition model or the weights of the graph edges before you start doing something. In RL, you just need an environment that gives you some feedback and to know the actions you can take.

I don't know the exact definition of simulated experience used here. I suppose it just refers to any data that you collect by not interacting with the environment via trial-and-error but by using a model. For example, if you had $p(s' \mid s, a)$ and any policy, you could simulate a trajectory. In policy iteration, we use $p(s' \mid s, a)$, but we don't really compute trajectories and then do something with them. We do something else, i.e. we compute values, but we do that using the transition model.

In conclusion, policy iteration is a planning algorithm because it finds a policy using the model $p(s' \mid s, a)$ rather than by trial-and-error.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .