Answers.Body: <blockquote>
    <p>Why are we allowed to convert the Bellman equations into update rules?</p>
  </blockquote>
  
  <p>There is a simple reason for this: <strong>convergence</strong>. The same <a href="http://incompleteideas.net/book/bookdraft2017nov5.pdf" rel="noreferrer">chapter 4</a> of the same book mentions it. For example, in the case of <em>policy evaluation</em>, the produced sequence of estimates <span class="math-container">$\{v_k\}$</span> is guaranteed to converge to <span class="math-container">$v_\pi$</span> as <span class="math-container">$k$</span> (i.e. the number of iterations) goes to infinity. There are other RL algorithms that are also guaranteed to converge (e.g. tabular Q-learning). </p>
  
  <p>To conclude, in many cases, the update rules of simple reinforcement learning (or dynamic programming) algorithms are very similar to their mathematical formalization because algorithms based on those update rules are often guaranteed to converge. However, note that many more advanced reinforcement learning algorithms (especially, the ones that use function approximators, such as neural networks, to represent the value functions or policies) are not guaranteed or known to converge.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-11T10:42:11.287Z
Answers.Text: Thank you for your answer. I understand that since the update rule version of the formula converges it is practical to use it. But my question is how we can use a formula which is not an update rule as an update rule (which converges)?
Answers.UserDisplayName: Saeid Ghafouri
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-11T12:32:58.150Z
Answers.Text: @SaeidGhafouri That formula is converted to an update rule because WE CAN DO THAT (and nobody prevents us from doing that), it's a NATURAL way of implementing that equation in an algorithm, and it turns out that this is the RIGHT thing to do in many cases (because algorithms based on such update rules converge!). There's no rule that tells you that equations need to be turned or not into update rules. We (humans) just do it because that's a natural way of implementing an algorithm that approximates that function.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-11T14:36:38.093Z
Answers.Text: Note that this is done in other areas of mathematics too. For example, consider the equation of a line. We can easily represent (or approximate) a line in a computer by expressing it in the same way as the mathematical equation.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-11T01:10:13.457Z
Answers.LastActivityDate: 2020-04-11T03:50:26.233Z
Answers.LastEditDate: 2020-04-11T03:50:26.233Z
Answers.UserDisplayName: nbro
Answers.Body: <p>To me, Bellman update is simply supervised learning: right hand side (bootstrap) is a sample of the left hand side (conditional expectation).. The Bellman equation simply explains that the right hand side is such a sample.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-12T06:13:16.343Z
Answers.LastActivityDate: 2020-12-12T06:13:16.343Z
Answers.UserDisplayName: kaiwenw
Answers.Body: <p>You're asking why the finite horizon policy evaluation converges to the infinite right?</p>
  
  <p>Since the total reward is bounded(by the discount factor) you know that you can make your finite horizon policy evaluation get arbitrarily close to it in a finite number of steps.</p>
  
  <p>People praise Bartos book but I find it annoying to read as he's not formal enough with mathematics.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-11T13:55:09.633Z
Answers.LastActivityDate: 2020-04-11T13:55:09.633Z
Answers.UserDisplayName: FourierFlux
Body: <p>In chapter 4.1 of Sutton's book, the Bellman equation is turned into an update rule by simply changing the indices of it. How is it mathematically justified? I didn't quite get the initiation of why we are allowed to do that?</p>
  
  <p><span class="math-container">$$v_{\pi}(s) = \mathbb E_{\pi}[G_t|S_t=s]$$</span></p>
  
  <p><span class="math-container">$$ = \mathbb E_{\pi}[R_{t+1} + \gamma G_{t+1}|S_t=s]$$</span></p>
  
  <p><span class="math-container">$$= \mathbb E_{\pi}[R_{t+1} + \gamma v_{\pi}(S_{t+1})|S_t=s]$$</span></p>
  
  <p><span class="math-container">$$ = \sum_a \pi(a|s)\sum_{s',r} p(s',r|s,a)[r+ \gamma v_{\pi}(s')]$$</span></p>
  
  <p>from which it goes to the update equation:</p>
  
  <p><span class="math-container">$$v_{k+1}(s) =  \mathbb E_{\pi}[R_{t+1} + \gamma v_{k}(S_{t+1})|S_t=s]$$</span></p>
  
  <p><span class="math-container">$$=\sum_a \pi(a|s)\sum_{s',r} p(s',r|s,a)[r+ \gamma v_{k}(s')]$$</span></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-19T18:26:59.913Z
Comments.Text: Check out this [proof](http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf) by Francisco S. Melo.
Comments.UserDisplayName: Qimen Xu
Tags: <reinforcement-learning><implementation><convergence><bellman-equations><policy-evaluation>
Title: Why can the Bellman equation be turned into an update rule?
UserDisplayName: Saeid Ghafouri
ThreadText: # Why can the Bellman equation be turned into an update rule?
  
  (Asked by: username_0 on 2020-04-10)
  
  In chapter 4.1 of Sutton's book, the Bellman equation is turned into an update rule by simply changing the indices of it. How is it mathematically justified? I didn't quite get the initiation of why we are allowed to do that?
  
  $$v\_{\pi}(s) = \mathbb E\_{\pi}[G\_t|S\_t=s]$$
  
  $$ = \mathbb E\_{\pi}[R\_{t+1} + \gamma G\_{t+1}|S\_t=s]$$
  
  $$= \mathbb E\_{\pi}[R\_{t+1} + \gamma v\_{\pi}(S\_{t+1})|S\_t=s]$$
  
  $$ = \sum\_a \pi(a|s)\sum\_{s',r} p(s',r|s,a)[r+ \gamma v\_{\pi}(s')]$$
  
  from which it goes to the update equation:
  
  $$v\_{k+1}(s) = \mathbb E\_{\pi}[R\_{t+1} + \gamma v\_{k}(S\_{t+1})|S\_t=s]$$
  
  $$=\sum\_a \pi(a|s)\sum\_{s',r} p(s',r|s,a)[r+ \gamma v\_{k}(s')]$$
  
  **Tags:** reinforcement-learning, implementation, convergence, bellman-equations, policy-evaluation
  
  > **Comments:**
  > **username_1**: Check out this [proof](http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf) by Francisco S. Melo.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2020-04-11. Score: 5
  
  > Why are we allowed to convert the Bellman equations into update rules?
  
  There is a simple reason for this: **convergence**. The same [chapter 4](http://incompleteideas.net/book/bookdraft2017nov5.pdf) of the same book mentions it. For example, in the case of *policy evaluation*, the produced sequence of estimates $\{v\_k\}$ is guaranteed to converge to $v\_\pi$ as $k$ (i.e. the number of iterations) goes to infinity. There are other RL algorithms that are also guaranteed to converge (e.g. tabular Q-learning).
  
  To conclude, in many cases, the update rules of simple reinforcement learning (or dynamic programming) algorithms are very similar to their mathematical formalization because algorithms based on those update rules are often guaranteed to converge. However, note that many more advanced reinforcement learning algorithms (especially, the ones that use function approximators, such as neural networks, to represent the value functions or policies) are not guaranteed or known to converge.
  
  > **Comments:**
  > **username_0**: Thank you for your answer. I understand that since the update rule version of the formula converges it is practical to use it. But my question is how we can use a formula which is not an update rule as an update rule (which converges)?  
  > **username_2**: @username_0 That formula is converted to an update rule because WE CAN DO THAT (and nobody prevents us from doing that), it's a NATURAL way of implementing that equation in an algorithm, and it turns out that this is the RIGHT thing to do in many cases (because algorithms based on such update rules converge!). There's no rule that tells you that equations need to be turned or not into update rules. We (humans) just do it because that's a natural way of implementing an algorithm that approximates that function.  
  > **username_2**: Note that this is done in other areas of mathematics too. For example, consider the equation of a line. We can easily represent (or approximate) a line in a computer by expressing it in the same way as the mathematical equation.  
  
  ---
  
  ### Answer by username_3 on 2020-12-12. Score: 1
  
  To me, Bellman update is simply supervised learning: right hand side (bootstrap) is a sample of the left hand side (conditional expectation).. The Bellman equation simply explains that the right hand side is such a sample.
  
  
  ---
  
  ### Answer by username_4 on 2020-04-11. Score: 0
  
  You're asking why the finite horizon policy evaluation converges to the infinite right?
  
  Since the total reward is bounded(by the discount factor) you know that you can make your finite horizon policy evaluation get arbitrarily close to it in a finite number of steps.
  
  People praise Bartos book but I find it annoying to read as he's not formal enough with mathematics.
  
  
  ---
  
  