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

$\endgroup$
2
$\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$
  • $\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 Apr 11 at 10:42
  • 1
    $\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 Apr 11 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 Apr 11 at 14:36
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$
  • $\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$ – DuttaA Apr 11 at 14:25
  • $\begingroup$ The OP never mentions "policy evaluation" in their post, so I am not sure why you think they were asking about that. The OP is clearly confused and is not expressing their doubts clearly. $\endgroup$ – nbro Apr 11 at 14:29
  • $\begingroup$ OP is clearly asking about the policy evaluation algorithm which is the subject of 4.1 $\endgroup$ – FourierFlux Apr 11 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.