Answers.Body: <blockquote>
  <p>There is no simulation in dynamic programming.</p>
  </blockquote>
  <p>In fact there is.</p>
  <p>Using the model <span class="math-container">$p(r, s'|s,a)$</span> (or other variations of it that are possible in Policy Iteration and Value Iteration) to predict outcomes of immediate reward and next state <em>is</em> a simulation of the environment.</p>
  <p>Therefore the update rule for Value Iteration:</p>
  <p><span class="math-container">$$v(s) \leftarrow \text{max}_a \sum_{r,s'} p(r,s')(r + \gamma v(s')) $$</span></p>
  <p>includes <em>simulated experience</em> of the outcome from being in state <span class="math-container">$s$</span> and picking the currently greedy action. Technically it is a sum over all possible outcomes predicted by the model, weighted by probability.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-13T16:28:06.597Z
Answers.LastActivityDate: 2024-05-13T16:56:55.923Z
Answers.LastEditDate: 2024-05-13T16:56:55.923Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>Dynamic programming is a algorithm paradigm, that is, an approach to design algorithms for problems that meet specific criteria (<strong>optimal substructure</strong> and <strong>overlapping sub-problems</strong>). So, it's not just used to solve MDPs. If you're interested in this topic, I'd recommend <em>Introduction to Algorithms</em> by CRLS.</p>
  <p>Planning is the process of searching for a plan (a sequence of actions) or policy like <span class="math-container">$\pi(s)$</span>. 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.</p>
  <p>In RL, the goal is also to find policies, but we interact with the environment using a <strong>trial-and-error</strong> 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).</p>
  <p>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.</p>
  <p>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 <span class="math-container">$p(s' \mid s, a)$</span> and any policy, you could simulate a trajectory. In policy iteration, we use <span class="math-container">$p(s' \mid s, a)$</span>, 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.</p>
  <p>In conclusion, policy iteration is a planning algorithm because it finds a policy using the model <span class="math-container">$p(s' \mid s, a)$</span> rather than by trial-and-error.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-13T15:07:40.260Z
Answers.LastActivityDate: 2024-05-13T15:19:16.577Z
Answers.LastEditDate: 2024-05-13T15:19:16.577Z
Answers.UserDisplayName: nbro
Body: <p>Sutton-Barto, page 160, towards bottom:</p>
  <p><a href="https://i.sstatic.net/lGjDofc9.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/lGjDofc9.png" alt="enter image description here" /></a></p>
  <p>Why is dynamic programming an example of planning? There is no simulation in dynamic programming.</p>
  
Tags: <reinforcement-learning><sutton-barto><dynamic-programming><planning>
Title: Why is dynamic programming an example of planning?
UserDisplayName: DSPinfinity
ThreadText: # Why is dynamic programming an example of planning?
  
  (Asked by: username_0 on 2024-05-13)
  
  Sutton-Barto, page 160, towards bottom:
  
  [![enter image description here](https://i.sstatic.net/lGjDofc9.png)](https://i.sstatic.net/lGjDofc9.png)
  
  Why is dynamic programming an example of planning? There is no simulation in dynamic programming.
  
  **Tags:** reinforcement-learning, sutton-barto, dynamic-programming, planning
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2024-05-13. Score: 2 | Accepted answer
  
  > 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.
  
  
  ---
  
  ### Answer by username_2 on 2024-05-13. Score: 3
  
  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.
  
  
  ---
  
  