6
$\begingroup$

In section 7.1 (about the n-step bootstrapping) of the book Reinforcement Learning: An Introduction (2nd edition), by Andrew Barto and Richard S. Sutton, the authors write about what they call the "n-step return error reduction property":

enter image description here

But they don't prove it. I was thinking it should not be too hard but how can we show this? I was thinking of using the definition of n-step return (eq. 7.1 on previous page):

$$G_{t:t+n} = R_{t+1} + \gamma*R_{t+2} + ... + \gamma^{n-1}*R_{t+n} + \gamma^{n}*V_{t+n-1}(S_{t+n})$$

Because then this has the $V_{t+n-1}$ in it already. But in the definition above of the n-step return it uses $V_{t+n-1}(S_{t+n})$ but on the right side of the inequality (7.3) that we want to prove it is just little s $V_{t+n-1}(s)$ ? So kind of confused here which state s it is using? And then I guess after this probably pull out a $\gamma^{n}$ term or something, how should we go from here?

This is the newest Sutton Barto book (book page 144, equation 7.3): https://drive.google.com/file/d/1opPSz5AZ_kVa1uWOdOiveNiBFiEOHjkG/view

$\endgroup$
5
$\begingroup$

Let's start by looking at:

$$\max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert.$$

We can rewrite this by plugging in the definition of $G_{t:t+n}$:

\begin{aligned} & \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert \\ % =& \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ R_{t + 1} + \gamma R_{t + 2} + \dots + \gamma^{n - 1} R_{t + n} + \gamma^n V_{t + n - 1}(S_{t + n}) \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert \\ % =& \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ R_{t:t+n} + \gamma^n V_{t + n - 1}(S_{t + n}) \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert, \end{aligned}

where $R_{t:t+n} \doteq R_{t + 1} + \gamma R_{t + 2} + \dots + \gamma^{n - 1} R_{t + n}$.

If you go all the way back to page 58 of the book, you can see the definition of $v_{\pi}(s)$:

\begin{aligned} v_{\pi}(s) &\doteq \mathbb{E}_{\pi} \left[ \sum_{k = 0}^{\infty} \gamma^k R_{t + k + 1} \mid S_t = s \right] \\ % &= \mathbb{E}_{\pi} \left[ R_{t:t+n} + \gamma^n \sum_{k = 0}^{\infty} \gamma^k R_{t + n + k + 1} \mid S_t = s \right] \\ % &= \mathbb{E}_{\pi} \left[ R_{t:t+n} \mid S_t = s \right] + \gamma^n \mathbb{E}_{\pi} \left[ \sum_{k = 0}^{\infty} \gamma^k R_{t + n + k + 1} \mid S_t = s \right] \end{aligned}

Using this, we can continue rewriting where we left off above:

\begin{aligned} & \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ R_{t:t+n} + \gamma^n V_{t + n - 1}(S_{t + n}) \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert \\ % =& \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ \gamma^n V_{t + n - 1}(S_{t + n}) \mid S_t = s \right] - \gamma^n \mathbb{E}_{\pi} \left[ \sum_{k = 0}^{\infty} \gamma^k R_{t + n + k + 1} \mid S_t = s \right] \Bigr\rvert \\ % =& \gamma^n \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ V_{t + n - 1}(S_{t + n}) - \sum_{k = 0}^{\infty} \gamma^k R_{t + n + k + 1} \mid S_t = s \right] \Bigr\rvert \end{aligned}

Because the absolute value function is convex, we can use Jensen's inequality to show that the absolute value of an expectation is less than or equal to the expectation of the corresponding absolute value:

$$\left| \mathbb{E} \left[ X \right] \right| \leq \mathbb{E} \left[ \left| X \right| \right].$$

This means that:

\begin{aligned} \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} - v_{\pi}(s) \mid S_t = s \right] \Bigr\rvert &\leq \gamma^n \max_s \mathbb{E}_{\pi} \left[ \Bigl\lvert V_{t + n - 1}(S_{t + n}) - \sum_{k = 0}^{\infty} \gamma^k R_{t + n + k + 1} \Bigr\rvert \mid S_t = s \right] \\ % \end{aligned}

Now, the important trick here is to see that:

$$\max_s \mathbb{E}_{\pi} \left[ \Bigl\lvert V_{t + n - 1}(S_{t + n}) - \sum_{k = 0}^{\infty} \gamma^k R_{t + n + k + 1} \Bigr\rvert \mid S_t = s \right] \leq \max_s \mathbb{E}_{\pi} \left[ \Bigl\lvert V_{t + n - 1}(S_{t}) - \sum_{k = 0}^{\infty} \gamma^k R_{t + k + 1} \Bigr\rvert \mid S_t = s \right]$$

I'm skipping the formal steps to show that this is the case to save space, but the intuition is that:

  • The left-hand side of this inequality involves finding an $S_t = s$ such that some function of $S_{t + n}$ is maximized, whereas the right-hand side involves finding an $S_t = s$ such that exactly the same function of $S_{t}$ is maximized.
  • In the left-hand side, selecting an $S_t = s$ implicitly induces a probability distribution over multiple possible states $S_{t + n}$, given by $S_t$, the environment's transition dynamics, and the policy $\pi$. Intuitively, this is more "restrictive" for the $\max$ operator, it does not have the "freedom" to directly select a single state $S_{t + n}$ such that the function of $S_{t + n}$ is maximized. The right-hand side is free to choose any single state $S_t = s$ such that $S_t$ in the right-hand side were equal to an "optimal" $S_{t+n}$ on the left-hand side, but it is also free to make even better choices which might never be uniquely reachable after $n$ steps on the left-hand side.

We can use this to rewrite the previous inequality we had (where we might be making the right-hand side a bit bigger than it was, but that's fine, it already was an upper bound anyway so that inequality will still hold):

\begin{aligned} \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} - v_{\pi}(s) \mid S_t = s \right] \Bigr\rvert &\leq \gamma^n \max_s \mathbb{E}_{\pi} \left[ \Bigl\lvert V_{t + n - 1}(S_{t}) - \sum_{k = 0}^{\infty} \gamma^k R_{t + k + 1} \Bigr\rvert \mid S_t = s \right] \\ % &= \gamma^n \max_s \mathbb{E}_{\pi} \left[ \Bigl\lvert V_{t + n - 1}(S_{t}) - v_{\pi}(s) \Bigr\rvert \mid S_t = s \right]. \end{aligned}

After this rewriting we've got a hidden $\mathbb{E}_{\pi}$ "inside" another $\mathbb{E}_{\pi}$ (because the definition of $v_{\pi}(s)$ contains an $\mathbb{E}_{\pi}$), which I suppose is kind of ugly... but mathematically meaningless.

The maximum of a random variable is an upper bound on the expectation of that random variable, so we can get rid of the expectation in the right-hand side (again potentially increasing the right-hand side, which again is still fine since it's already an upper bound anyway):

\begin{aligned} \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} - v_{\pi}(s) \mid S_t = s \right] \Bigr\rvert &\leq \gamma^n \max_s \Bigl\lvert V_{t + n - 1}(s) - v_{\pi}(s) \Bigr\rvert, \end{aligned}

which we can finally rewrite to Equation (7.3) in the book by moving the subtraction of $v_{\pi}(s)$ outside of the expectation on the left-hand side of the inequality (which is fine because, as I already mentioned above, the definition of $v_{\pi}(s)$ itself contains another $\mathbb{E}_{\pi}$ anyway).

$\endgroup$
  • $\begingroup$ Your bullet points explaining the "trick" make intuitive sense. Could you provide a link to someone showing the formal steps? $\endgroup$ – Philip Raeisghasem Mar 18 at 9:13
  • $\begingroup$ @PhilipRaeisghasem I don't know of any such links by heart, so can't provide one, sorry :( $\endgroup$ – Dennis Soemers Mar 18 at 19:18
  • $\begingroup$ I'd argue that, if it's that hard to find this information, then including it in the post would greatly increase the post's value. Or maybe as a separate, linked question? $\endgroup$ – Philip Raeisghasem Mar 18 at 19:50
  • 1
    $\begingroup$ @Phizaz Hmmm not exactly. Close to that, I'd say "given a completely free, unrestricted choice for $S_t$, the set of possible states $S_{t+n}$ is a subset of the set of possible states $S_t$". Very often it will not be a proper subset though, very often they'll be equal. But even then, a very important other point is that the probability distributions over those sets will be different. When the choice of $S_t$ is unrestricted, you can assign full probability mass to whichever is "best". Even if that best state may still be possible for $S_{t+n}$, it may no longer have full probability mass $\endgroup$ – Dennis Soemers Aug 29 at 8:15
  • 1
    $\begingroup$ @DennisSoemers I agree. However, will we not be able to prove without the probability mass argument? $\endgroup$ – Phizaz Aug 30 at 12:59

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.