4
$\begingroup$

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')]$$

Improve this question
$\endgroup$
1
  • $\begingroup$ Check out this proof by Francisco S. Melo. $\endgroup$
    – Qimen Xu
    Commented May 19, 2022 at 18:26

3 Answers 3

Reset to default
5
$\begingroup$

Why are we allowed to convert the Bellman equations into update rules?

There is a simple reason for this: convergence. The same chapter 4 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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)? $\endgroup$
    – Saeid Ghafouri
    Commented Apr 11, 2020 at 10:42
  • 2
    $\begingroup$ @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. $\endgroup$
    – nbro
    Commented Apr 11, 2020 at 12:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – nbro
    Commented Apr 11, 2020 at 14:36
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I am guessing you are saying$\gamma$ should be less than 1 for convergence? In my Sutton and Barto it is mentioned that the value needs to be less than 1 for existence of $v_{\pi}$ $\endgroup$
    – user9947
    Commented Apr 11, 2020 at 14:25

You must log in to answer this question.

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