Answers.Body: <p>The equation (1) you mentioned is a simplified form of the temporal difference TD(0) update rule, specifically for the case of episodic tasks where there's no discounting <span class="math-container">$\gamma$</span> and the only reward is at the episodic terminating state such as tic-tac-toe. Equation (2) is a more general form applicable to both episodic and continuing tasks, considering future rewards through discounting which is the one typically used in RL TD learning methods.</p>
  <p>As for the connection to value iteration of dynamic programming, it seems not much since value iteration update rule is based on Bellman optimality operator of the Bellman optimality equation (BOE) whose convergence is based on contraction mapping fixed point theorem, while the convergence of TD learning is based on <a href="https://www.degruyter.com/document/doi/10.1525/9780520313880-007/html" rel="nofollow noreferrer">Dvoretzky’s convergence theorem</a> of stochastic approximation.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-11T05:58:02.737Z
Answers.Text: Thanks for the answer! Is there any similarity to DP at all? In Sutton&Barto they state in the section on DP that other methods try to mimic DP without the assumption of complete knowledge. Surely it must be more similarites than the common goal of finding an optimal policy, or?
Answers.UserDisplayName: mNugget
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-11T06:09:49.803Z
Answers.Text: Of course their goal to find optimal policy is similar while DP is usually model-base given your transition dynamics thus it's more like planning with precision and often better convergence, and TD is model-free method so you cannot use transition dynamics and thus more trial and error training needed.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-11T05:13:00.550Z
Answers.LastActivityDate: 2024-04-11T05:13:00.550Z
Answers.UserDisplayName: cinch
Body: <p>In section <span class="math-container">$1.5$</span> of the book &quot;Reinforcement Learning: An Introduction&quot; by Sutton and Barto they use tic-tac-toe as an example of an RL use case. They provide the following temporal difference update rule in that section:
  <span class="math-container">$$
  V(S_{t}) \leftarrow V(S_t) + \alpha[V(S_{t+1}) - V(S_t)] \tag{1}
  $$</span>
  However, in the chapter on TD methods they state that the &quot;simplest TD method makes the update&quot;:
  <span class="math-container">$$
  V(S_{t}) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)] \tag{2}
  $$</span></p>
  <p>Does any one have an explanation for where <span class="math-container">$(1)$</span> comes from? I can't see it to be equivalent to <span class="math-container">$(2)$</span>.</p>
  <p>I am also wondering if anyone has a way of relating this update rule to dynamic programming. Is this supposed to be some sort of approximation of value iteration when the environments dynamics, <span class="math-container">$p(s', r | s, a)$</span>, is unknown?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-04-11T03:23:02.613Z
Comments.Text: I wish I could answer this but I'm struggling with the notation a bit as well.  If gamma is 1 and the rewards are sparse (0 for non winning moves, 100 for winning, etc) I can see the similarity between the equations.
Comments.UserDisplayName: foreverska
Tags: <reinforcement-learning><sutton-barto><temporal-difference-methods><dynamic-programming><tic-tac-toe>
Title: Where does the TD formula for tic-tac-toe in Sutton & Barto come from?
UserDisplayName: mNugget
ThreadText: # Where does the TD formula for tic-tac-toe in Sutton & Barto come from?
  
  (Asked by: username_0 on 2024-04-11)
  
  In section $1.5$ of the book "Reinforcement Learning: An Introduction" by Sutton and Barto they use tic-tac-toe as an example of an RL use case. They provide the following temporal difference update rule in that section:
  $$
  V(S\_{t}) \leftarrow V(S\_t) + \alpha[V(S\_{t+1}) - V(S\_t)] \tag{1}
  $$
  However, in the chapter on TD methods they state that the "simplest TD method makes the update":
  $$
  V(S\_{t}) \leftarrow V(S\_t) + \alpha[R\_{t+1} + \gamma V(S\_{t+1}) - V(S\_t)] \tag{2}
  $$
  
  Does any one have an explanation for where $(1)$ comes from? I can't see it to be equivalent to $(2)$.
  
  I am also wondering if anyone has a way of relating this update rule to dynamic programming. Is this supposed to be some sort of approximation of value iteration when the environments dynamics, $p(s', r | s, a)$, is unknown?
  
  **Tags:** reinforcement-learning, sutton-barto, temporal-difference-methods, dynamic-programming, tic-tac-toe
  > **Comments:**
  > **username_1**: I wish I could answer this but I'm struggling with the notation a bit as well.  If gamma is 1 and the rewards are sparse (0 for non winning moves, 100 for winning, etc) I can see the similarity between the equations.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2024-04-11. Score: 4 | Accepted answer
  
  The equation (1) you mentioned is a simplified form of the temporal difference TD(0) update rule, specifically for the case of episodic tasks where there's no discounting $\gamma$ and the only reward is at the episodic terminating state such as tic-tac-toe. Equation (2) is a more general form applicable to both episodic and continuing tasks, considering future rewards through discounting which is the one typically used in RL TD learning methods.
  
  As for the connection to value iteration of dynamic programming, it seems not much since value iteration update rule is based on Bellman optimality operator of the Bellman optimality equation (BOE) whose convergence is based on contraction mapping fixed point theorem, while the convergence of TD learning is based on [Dvoretzky’s convergence theorem](https://www.degruyter.com/document/doi/10.1525/9780520313880-007/html) of stochastic approximation.
  
  > **Comments:**
  > **username_0**: Thanks for the answer! Is there any similarity to DP at all? In Sutton&Barto they state in the section on DP that other methods try to mimic DP without the assumption of complete knowledge. Surely it must be more similarites than the common goal of finding an optimal policy, or?  
  > **username_2**: Of course their goal to find optimal policy is similar while DP is usually model-base given your transition dynamics thus it's more like planning with precision and often better convergence, and TD is model-free method so you cannot use transition dynamics and thus more trial and error training needed.  
  
  ---
  
  