Answers.Body: <p>All value-based methods in Reinforcement Learning use a backup process of some kind to calculate returns or expected returns.</p>
  <p>There are multiple types of backup, but in general they consist of taking actual returns or estimated returns from timestamps after a certain point in a trajectory, and using them to calculate a return or expected return from that point.</p>
  <p><a href="http://incompleteideas.net/book/ebook/node34.html" rel="nofollow noreferrer">Backup diagrams (see fig 3.4 here)</a> are a way to visualise the different possible approaches.</p>
  <p>In Dynamic Programming (DP), there are two types of backup used, for Policy Iteration and Value Iteration. This is why the text you quoted uses the more generic terminology.</p>
  <p>For Policy Iteration, the update is:</p>
  <p><span class="math-container">$$v(s) \leftarrow \sum_{a} \pi(a|s) \sum_{r,s'} p(r,s'|s,a)(r + \gamma v(s'))$$</span></p>
  <p>For Value Iteration, the update is:</p>
  <p><span class="math-container">$$v(s) \leftarrow \text{max}_{a} \sum_{r,s'} p(r,s'|s,a)(r + \gamma v(s'))$$</span></p>
  <p>You can view the right hand side of these rules as a summary of the backup process - the sum and max operation are the procedure for obtaining an update target, and in the case of DP, there is no learning rate or taking account of the current estimated value (although you could add this, it would not do anything useful in tabular DP).</p>
  <p>To be clear, the backup and the update are not always as simply related as with DP. The backup is the part that calculates a new estimate or target value, and the update step may use that in various ways. Basic DP directly uses the backed up value as the new value in the update step, but most other RL methods have a more complex update step.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-09T10:18:03.057Z
Answers.Text: So, there is no clearly defined  "target" in DP methods as in MC where the target is the return $G_t$, Right? Do they assume target=backed up value id DP methods?
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-09T10:26:00.500Z
Answers.Text: @DSPinfinity Basic DP doesn't need to make the distinction between update and target, but if you want to use those labels for consistency, then yes. S&B doesn't cover all possible DP methods in detail, and some will make a distinction - e.g. you can use DP with function approximation.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-09T08:03:45.603Z
Answers.LastActivityDate: 2024-05-09T08:20:29.783Z
Answers.LastEditDate: 2024-05-09T08:20:29.783Z
Answers.UserDisplayName: Neil Slater
Body: <p>Sutton-Barto, page 160:</p>
  <p><a href="https://i.sstatic.net/eyXAcIvI.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/eyXAcIvI.png" alt="enter image description here" /></a></p>
  <blockquote>
  <p>Dynamic programming methods clearly fit this structure: they make sweeps through the
  space of states, generating for each state the distribution of possible transitions. Each
  distribution is then used to compute a backed-up value (update target) and update the
  state’s estimated value.</p>
  </blockquote>
  <p>This part is not clear for me: Each
  distribution is then used to compute a backed-up value (update target) and update the
  state’s estimated value.</p>
  <p>What is the backed-up value in DP and the corresponding update based on this backed up value?</p>
  
Tags: <reinforcement-learning><sutton-barto>
Title: What is the backed-up value in dynamic programming and the corresponding update based on this backed up value?
UserDisplayName: DSPinfinity
ThreadText: # What is the backed-up value in dynamic programming and the corresponding update based on this backed up value?
  
  (Asked by: username_0 on 2024-05-09)
  
  Sutton-Barto, page 160:
  
  [![enter image description here](https://i.sstatic.net/eyXAcIvI.png)](https://i.sstatic.net/eyXAcIvI.png)
  
  > Dynamic programming methods clearly fit this structure: they make sweeps through the
  > space of states, generating for each state the distribution of possible transitions. Each
  > distribution is then used to compute a backed-up value (update target) and update the
  > state’s estimated value.
  
  This part is not clear for me: Each
  distribution is then used to compute a backed-up value (update target) and update the
  state’s estimated value.
  
  What is the backed-up value in DP and the corresponding update based on this backed up value?
  
  **Tags:** reinforcement-learning, sutton-barto
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-05-09. Score: 1 | Accepted answer
  
  All value-based methods in Reinforcement Learning use a backup process of some kind to calculate returns or expected returns.
  
  There are multiple types of backup, but in general they consist of taking actual returns or estimated returns from timestamps after a certain point in a trajectory, and using them to calculate a return or expected return from that point.
  
  [Backup diagrams (see fig 3.4 here)](http://incompleteideas.net/book/ebook/node34.html) are a way to visualise the different possible approaches.
  
  In Dynamic Programming (DP), there are two types of backup used, for Policy Iteration and Value Iteration. This is why the text you quoted uses the more generic terminology.
  
  For Policy Iteration, the update is:
  
  $$v(s) \leftarrow \sum\_{a} \pi(a|s) \sum\_{r,s'} p(r,s'|s,a)(r + \gamma v(s'))$$
  
  For Value Iteration, the update is:
  
  $$v(s) \leftarrow \text{max}\_{a} \sum\_{r,s'} p(r,s'|s,a)(r + \gamma v(s'))$$
  
  You can view the right hand side of these rules as a summary of the backup process - the sum and max operation are the procedure for obtaining an update target, and in the case of DP, there is no learning rate or taking account of the current estimated value (although you could add this, it would not do anything useful in tabular DP).
  
  To be clear, the backup and the update are not always as simply related as with DP. The backup is the part that calculates a new estimate or target value, and the update step may use that in various ways. Basic DP directly uses the backed up value as the new value in the update step, but most other RL methods have a more complex update step.
  
  > **Comments:**
  > **username_0**: So, there is no clearly defined  "target" in DP methods as in MC where the target is the return $G_t$, Right? Do they assume target=backed up value id DP methods?  
  > **username_1**: @username_0 Basic DP doesn't need to make the distinction between update and target, but if you want to use those labels for consistency, then yes. S&B doesn't cover all possible DP methods in detail, and some will make a distinction - e.g. you can use DP with function approximation.  
  
  ---
  
  