56
$\begingroup$

I see the following equation in "In Reinforcement Learning. An Introduction", but don't quite follow the step I have highlighted in blue below. How exactly is this step derived?

enter image description here

$\endgroup$
1

11 Answers 11

28
$\begingroup$

There are already a great many answers to this question, but most involve few words describing what is going on in the manipulations. I'm going to answer it using way more words, I think. To start,

$$G_{t} \doteq \sum_{k=t+1}^{T} \gamma^{k-t-1} R_{k}$$

is defined in equation 3.11 of Sutton and Barto, with a constant discount factor $0 \leq \gamma \leq 1$ and we can have $T = \infty$ or $\gamma = 1$, but not both. Since the rewards, $R_{k}$, are random variables, so is $G_{t}$ as it is merely a linear combination of random variables.

$$\begin{align} v_\pi(s) & \doteq \mathbb{E}_\pi\left[G_t | S_t = s\right] \\ & = \mathbb{E}_\pi\left[R_{t+1} + \gamma G_{t+1} | S_t = s\right] \\ & = \mathbb{E}_{\pi}\left[ R_{t+1} | S_t = s \right] + \gamma \mathbb{E}_{\pi}\left[ G_{t+1} | S_t = s \right] \end{align}$$

That last line follows from the linearity of expectation values. $R_{t+1}$ is the reward the agent gains after taking action at time step $t$. For simplicity, I assume that it can take on a finite number of values $r \in \mathcal{R}$.

Work on the first term. In words, I need to compute the expectation values of $R_{t+1}$ given that we know that the current state is $s$. The formula for this is

$$\begin{align} \mathbb{E}_{\pi}\left[ R_{t+1} | S_t = s \right] = \sum_{r \in \mathcal{R}} r p(r|s). \end{align}$$

In other words the probability of the appearance of reward $r$ is conditioned on the state $s$; different states may have different rewards. This $p(r|s)$ distribution is a marginal distribution of a distribution that also contained the variables $a$ and $s'$, the action taken at time $t$ and the state at time $t+1$ after the action, respectively:

$$\begin{align} p(r|s) = \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} p(s',a,r|s) = \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} \pi(a|s) p(s',r | a,s). \end{align}$$

Where I have used $\pi(a|s) \doteq p(a|s)$, following the book's convention. If that last equality is confusing: forget the sums, suppress the $s$ (the probability now looks like a joint probability), use the law of multiplication, and finally reintroduce the condition on $s$ in all the new terms.

A short proof for the same is below. $$\begin{align} p(s',r,a|s)=p(s',r|a,s)p(a|s)=p(s',r|a,s)\pi(a|s) \end{align}$$

It is now easy to see that the first term is

$$\begin{align} \mathbb{E}_{\pi}\left[ R_{t+1} | S_t = s \right] = \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} r \pi(a|s) p(s',r | a,s), \end{align}$$

as required. On to the second term, where I assume that $G_{t+1}$ is a random variable that takes on a finite number of values $g \in \Gamma$. Just like the first term:

$$\begin{align} \mathbb{E}_{\pi}\left[ G_{t+1} | S_t = s \right] = \sum_{g \in \Gamma} g p(g|s). \qquad\qquad\qquad\qquad (*) \end{align}$$

Once again, I "un-marginalize" the probability distribution by writing (law of multiplication again)

$$\begin{align} p(g|s) & = \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} p(s',r,a,g|s) = \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} p(g | s', r, a, s) p(s', r, a | s) \\ & = \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} p(g | s', r, a, s) p(s', r | a, s) \pi(a | s) \\ & = \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} p(g | s') p(s', r | a, s) \pi(a | s) \qquad\qquad\qquad\qquad (**) \end{align}$$

The last line in there follows from the Markovian property. Remember that $G_{t+1}$ is the sum of all the future (discounted) rewards that the agent receives after state $s'$. The Markovian property is that the process is memory-less with regards to previous states, actions and rewards. Future actions (and the rewards they reap) depend only on the state in which the action is taken, so $p(g | s', r, a, s) = p(g | s')$, by assumption. Ok, so the second term in the proof is now

$$\begin{align} \gamma \mathbb{E}_{\pi}\left[ G_{t+1} | S_t = s \right] & = \gamma \sum_{g \in \Gamma} \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} g p(g | s') p(s', r | a, s) \pi(a | s) \\ & = \gamma \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} \mathbb{E}_{\pi}\left[ G_{t+1} | S_{t+1} = s' \right] p(s', r | a, s) \pi(a | s) \\ & = \gamma \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} v_{\pi}(s') p(s', r | a, s) \pi(a | s) \end{align}$$

as required, once again. Combining the two terms completes the proof

$$\begin{align} v_\pi(s) & \doteq \mathbb{E}_\pi\left[G_t \mid S_t = s\right] \\ & = \sum_{a \in \mathcal{A}} \pi(a | s) \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} p(s', r | a, s) \left[ r + \gamma v_{\pi}(s') \right]. \end{align}$$

UPDATE

I want to address what might look like a sleight of hand in the derivation of the second term. In the equation marked with $(*)$, I use a term $p(g|s)$ and then later in the equation marked $(**)$ I claim that $g$ doesn't depend on $s$, by arguing the Markovian property. So, you might say that if this is the case, then $p(g|s) = p(g)$. But this is not true. I can take $p(g | s', r, a, s) \rightarrow p(g | s')$ because the probability on the left side of that statement says that this is the probability of $g$ conditioned on $s'$, $a$, $r$, and $s$. Because we either know or assume the state $s'$, none of the other conditionals matter, because of the Markovian property. If you do not know or assume the state $s'$, then the future rewards (the meaning of $g$) will depend on which state you begin at, because that will determine (based on the policy) which state $s'$ you start at when computing $g$.

If that argument doesn't convince you, try to compute what $p(g)$ is:

$$\begin{align} p(g) & = \sum_{s' \in \mathcal{S}} p(g, s') = \sum_{s' \in \mathcal{S}} p(g | s') p(s') \\ & = \sum_{s' \in \mathcal{S}} p(g | s') \sum_{s,a,r} p(s', a, r, s) \\ & = \sum_{s' \in \mathcal{S}} p(g | s') \sum_{s,a,r} p(s', r | a, s) p(a, s) \\ & = \sum_{s \in \mathcal{S}} p(s) \sum_{s' \in \mathcal{S}} p(g | s') \sum_{a,r} p(s', r | a, s) \pi(a | s) \\ & \doteq \sum_{s \in \mathcal{S}} p(s) p(g|s) = \sum_{s \in \mathcal{S}} p(g,s) = p(g). \end{align}$$

As can be seen in the last line, it is not true that $p(g|s) = p(g)$. The expected value of $g$ depends on which state you start in (i.e. the identity of $s$), if you do not know or assume the state $s'$.

$\endgroup$
3
  • $\begingroup$ Two comments on this interesting answer: 1. Even if the reward is either 0 or 1, the values that $G_t$ may take can nevertheless be bigger so we need an integral instead of a sum over $\gamma$. 2. What exactly is $p(g|...)$ supposed to be? Let's start simple: what is $p(g)$ supposed to be? It is the density of $G_{t+1}$, right? Why does this random variable even have a density? Even if it had a density, why exactly does it not depend on $s$ in the sense that you wrote down? This is not the Markov property (Markov says that the single variables $S_t, A_t, R_t$ do not depend on the whole past... $\endgroup$ Dec 17, 2020 at 22:41
  • $\begingroup$ but only on the variables $S_{t-1}, A_{t-1}, R_{t-1}$... ). So if you say that then you have a different definition of 'markovian' than everybody else I guess... $\endgroup$ Dec 17, 2020 at 22:42
  • 1
    $\begingroup$ superb answer, cleared up a lot of things! $\endgroup$
    – bilibraker
    Jan 18 at 0:43
20
$\begingroup$

Here is my proof. It is based on the manipulation of conditional distributions, which makes it easier to follow. Hope this one helps you. \begin{align} v_{\pi}(s)&=E{\left[G_t|S_t=s\right]} \nonumber \\ &=E{\left[R_{t+1}+\gamma G_{t+1}|S_t=s\right]} \nonumber \\ &= \sum_{s'}\sum_{r}\sum_{g_{t+1}}\sum_{a}p(s',r,g_{t+1}, a|s)(r+\gamma g_{t+1}) \nonumber \\ &= \sum_{a}p(a|s)\sum_{s'}\sum_{r}\sum_{g_{t+1}}p(s',r,g_{t+1} |a, s)(r+\gamma g_{t+1}) \nonumber \\ &= \sum_{a}p(a|s)\sum_{s'}\sum_{r}\sum_{g_{t+1}}p(s',r|a, s)p(g_{t+1}|s', r, a, s)(r+\gamma g_{t+1}) \nonumber \\ &\text{Note that $p(g_{t+1}|s', r, a, s)=p(g_{t+1}|s')$ by assumption of MDP} \nonumber \\ &= \sum_{a}p(a|s)\sum_{s'}\sum_{r}p(s',r|a, s)\sum_{g_{t+1}}p(g_{t+1}|s')(r+\gamma g_{t+1}) \nonumber \\ &= \sum_{a}p(a|s)\sum_{s'}\sum_{r}p(s',r|a, s)(r+\gamma\sum_{g_{t+1}}p(g_{t+1}|s')g_{t+1}) \nonumber \\ &=\sum_{a}p(a|s)\sum_{s'}\sum_{r}p(s',r|a, s)\left(r+\gamma v_{\pi}(s')\right) \label{eq2} \end{align} This is the famous Bellman equation.

$\endgroup$
5
  • $\begingroup$ Do you mind explaining this comment 'Note that ...' a little more? Why do these random variables $G_{t+1}$ and the state and action variables even have a common density? If so, why do you know this property that you are using? I can see that it is true for a finite sum but if the random variable is a limit... ??? $\endgroup$ Jan 10, 2019 at 7:20
  • $\begingroup$ To Fabian: First let's recall what is $G_{t+1}$. $G_{t+1}=R_{t+2}+R_{t+3}+\cdots$. Note that $R_{t+2}$ only directly depends on $S_{t+1}$ and $A_{t+1}$ since $p(s', r|s, a)$ captures all the transition information of a MDP (More precisely, $R_{t+2}$ is independent of all states, actions, and rewards before time $t+1$ given $S_{t+1}$ and $A_{t+1}$). Similarly, $R_{t+3}$ only depends on $S_{t+2}$ and $A_{t+2}$. As a result, $G_{t+1}$ is independent of $S_t$, $A_t$, and $R_t$ given $S_{t+1}$, which explains that line. $\endgroup$
    – Jie Shi
    Jan 28, 2019 at 18:52
  • $\begingroup$ Sorry, that only 'motivates' it, it doesn't actually explain anything. For example: What is the density of $G_{t+1}$? Why are you sure that $p(g_{t+1}|s_{t+1}, s_t) = p(g_{t+1}|s_{t+1})$? Why do these random variables even have a common density? You know that a sum transforms into a convolution in densities so what... $G_{t+1}$ should have an infinite amount of integrals in the density??? There is absolutely no candidate for the density! $\endgroup$ Jan 28, 2019 at 21:47
  • $\begingroup$ To Fabian: I do not get your question. 1. You want the exact form of the marginal distribution $p(g_{t+1})$? I do not know it and we do not need it in this proof. 2. why $p(g_{t+1}|s_{t+1}, s_t)=p(g_{t+1}|s_{t+1})$? Because as I mentioned earlier $g_{t+1}$ and $s_t$ are independent given $s_{t+1}$. 3. What do you mean by "common density"? You mean joint distribution? You want to know why these random variables have a joint distribution? All random variables in this universe can have a joint distribution. If this is your question, I would suggest you find a probability theory book and read it. $\endgroup$
    – Jie Shi
    Jan 29, 2019 at 0:07
  • $\begingroup$ Let us move this discussion to chat: chat.stackexchange.com/rooms/88952/bellman-equation $\endgroup$ Jan 29, 2019 at 12:17
15
$\begingroup$

This is the answer for everybody who wonders about the clean, structured math behind it (i.e. if you belong to the group of people that knows what a random variable is and that you must show or assume that a random variable has a density then this is the answer for you ;-)):

First of all we need to have that the Markov Decision Process has only a finite number of $L^1$-rewards, i.e. we need that there exists a finite set $E$ of densities, each belonging to $L^1$ variables, i.e. $\int_{\mathbb{R}}x \cdot e(x) dx < \infty$ for all $e \in E$ and a map $F : A \times S \to E$ such that $$p(r_t|a_t, s_t) = F(a_t, s_t)(r_t)$$ (i.e. in the automata behind the MDP, there may be infinitely many states but there are only finitely many $L^1$-reward-distributions attached to the possibly infinite transitions between the states)

Theorem 1: Let $X \in L^1(\Omega)$ (i.e. an integrable real random variable) and let $Y$ be another random variable such that $X,Y$ have a common density then $$E[X|Y=y] = \int_\mathbb{R} x p(x|y) dx$$

Proof: Essentially proven in here by Stefan Hansen.

Theorem 2: Let $X \in L^1(\Omega)$ and let $Y,Z$ be further random variables such that $X,Y,Z$ have a common density then $$E[X|Y=y] = \int_{\mathcal{Z}} p(z|y) E[X|Y=y,Z=z] dz$$ where $\mathcal{Z}$ is the range of $Z$.

Proof: \begin{align*} E[X|Y=y] &= \int_{\mathbb{R}} x p(x|y) dx \\ &~~~~\text{(by Thm. 1)}\\ &= \int_{\mathbb{R}} x \frac{p(x,y)}{p(y)} dx \\ &= \int_{\mathbb{R}} x \frac{\int_{\mathcal{Z}} p(x,y,z) dz}{p(y)} dx \\ &= \int_{\mathcal{Z}} \int_{\mathbb{R}} x \frac{ p(x,y,z) }{p(y)} dx dz \\ &= \int_{\mathcal{Z}} \int_{\mathbb{R}} x p(x|y,z)p(z|y) dx dz \\ &= \int_{\mathcal{Z}} p(z|y) \int_{\mathbb{R}} x p(x|y,z) dx dz \\ &= \int_{\mathcal{Z}} p(z|y) E[X|Y=y,Z=z] dz \\ &~~~~\text{(by Thm. 1)} \end{align*}

Put $G_t = \sum_{k=0}^\infty \gamma^k R_{t+k}$ and put $G_t^{(K)} = \sum_{k=0}^K \gamma^k R_{t+k}$ then one can show (using the fact that the MDP has only finitely many $L^1$-rewards) that $G_t^{(K)}$ converges and that since the function $\sum_{k=0}^\infty \gamma^k |R_{t+k}|$ is still in $L^1(\Omega)$ (i.e. integrable) one can also show (by using the usual combination of the theorems of monotone convergence and then dominated convergence on the defining equations for [the factorizations of] the conditional expectation) that $$\lim_{K \to \infty} E[G_t^{(K)} | S_t=s_t] = E[G_t | S_t=s_t]$$ Now one shows that $$E[G_t^{(K)} | S_t=s_t] = E[R_{t} | S_t=s_t] + \gamma \int_S p(s_{t+1}|s_t) E[G_{t+1}^{(K-1)} | S_{t+1}=s_{t+1}] ds_{t+1}$$ using $G_t^{(K)} = R_t + \gamma G_{t+1}^{(K-1)}$, Thm. 2 above then Thm. 1 on $E[G_{t+1}^{(K-1)}|S_{t+1}=s', S_t=s_t]$ and then using a straightforward marginalization war, one shows that $p(r_q|s_{t+1}, s_t) = p(r_q|s_{t+1})$ for all $q \geq t+1$. Now we need to apply the limit $K \to \infty$ to both sides of the equation. In order to pull the limit into the integral over the state space $S$ we need to make some additional assumptions:

Either the state space is finite (then $\int_S = \sum_S$ and the sum is finite) or all the rewards are all positive (then we use monotone convergence) or all the rewards are negative (then we put a minus sign in front of the equation and use monotone convergence again) or all the rewards are bounded (then we use dominated convergence). Then (by applying $\lim_{K \to \infty}$ to both sides of the partial / finite Bellman equation above) we obtain

$$ E[G_t | S_t=s_t] = E[G_t^{(K)} | S_t=s_t] = E[R_{t} | S_t=s_t] + \gamma \int_S p(s_{t+1}|s_t) E[G_{t+1} | S_{t+1}=s_{t+1}] ds_{t+1}$$

and then the rest is usual density manipulation.

REMARK: Even in very simple tasks the state space can be infinite! One example would be the 'balancing a pole'-task. The state is essentially the angle of the pole (a value in $[0, 2\pi)$, an uncountably infinite set!)

REMARK: People might comment 'dough, this proof can be shortened much more if you just use the density of $G_t$ directly and show that $p(g_{t+1}|s_{t+1}, s_t) = p(g_{t+1}|s_{t+1})$' ... BUT ... my questions would be:

  1. How come that you even know that $G_{t+1}$ has a density?
  2. How come that you even know that $G_{t+1}$ has a common density together with $S_{t+1}, S_t$?
  3. How do you infer that $p(g_{t+1}|s_{t+1}, s_t) = p(g_{t+1}|s_{t+1})$? This is not only the Markov property: The Markov property only tells you something about the marginal distributions but these do not necessarily determine the whole distribution, see e.g. multivariate Gaussians!
$\endgroup$
7
  • $\begingroup$ It's an interesting answer but I struggle to follow as usually the framework used in ML, RL etc is the discrete case. $\endgroup$ Nov 2, 2020 at 16:34
  • $\begingroup$ Yes, all the 'games' scenarios (chess, pong, ...) are discrete with a huge and complicated finite state spaces, you are right. However, there are also simple examples where the state space is not finite: For example, the case of a swinging pendulum being mounted on a car is an example where the state space is the (almost compact) interval [0,2pi) (i.e. all real numbers=angles between 0 and 2*pi) and that is an uncountably infinite set of states... Also the concept becomes clearer when using integrals: in the end, sums are nothing else than integrals w.r.t. the counting measure :-) $\endgroup$ Nov 2, 2020 at 17:42
  • $\begingroup$ I agree, but it's a framework not usually used in DL/ML. I think I'd need more context and a better framework to compare your answer for example with existing literature. Maybe given your background it might sound easy and trivial, but for someone like me who hasn't touched probability theory in a while (the "measure theory" based one). I'll still read through it anyway cause I find your answer interesting. $\endgroup$ Nov 2, 2020 at 17:46
  • $\begingroup$ Let me know if I can help with additional clarification :-) $\endgroup$ Nov 2, 2020 at 18:24
  • $\begingroup$ maybe you can answer this : stats.stackexchange.com/questions/494931/… $\endgroup$ Nov 3, 2020 at 18:21
14
$\begingroup$

Let total sum of discounted rewards after time $t$ be:
$G_t = R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+...$

Utility value of starting in state,$s$ at time,$t$ is equivalent to expected sum of
discounted rewards $R$ of executing policy $\pi$ starting from state $s$ onwards.
$U_\pi(S_t=s) = E_\pi[G_t|S_t = s]$
$\\ = E_\pi[(R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+...)|S_t = s]$ By definition of $G_t$
$= E_\pi[(R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+...))|S_t = s]$
$= E_\pi[(R_{t+1}+\gamma (G_{t+1}))|S_t = s]$
$= E_\pi[R_{t+1}|S_t = s]+\gamma E_\pi[ G_{t+1}|S_t = s]$ By law of linearity
$= E_\pi[R_{t+1}|S_t = s]+\gamma E_\pi[E_\pi(G_{t+1}|S_{t+1} = s')|S_t = s]$ By law of Total Expectation
$= E_\pi[R_{t+1}|S_t = s]+\gamma E_\pi[U_\pi(S_{t+1}= s')|S_t = s]$ By definition of $U_\pi$
$= E_\pi[R_{t+1} + \gamma U_\pi(S_{t+1}= s')|S_t = s]$ By law of linearity

Assuming that the process satisfies Markov Property:
Probability $Pr$ of ending up in state $s'$ having started from state $s$ and taken action $a$ ,
$Pr(s'|s,a) = Pr(S_{t+1} = s', S_t=s,A_t = a)$ and
Reward $R$ of ending up in state $s'$ having started from state $s$ and taken action $a$,
$R(s,a,s') = [R_{t+1}|S_t = s, A_t = a, S_{t+1}= s']$

Therefore we can re-write above utility equation as,
$= \sum_a \pi(a|s) \sum_{s'} Pr(s'|s,a)[R(s,a,s')+ \gamma U_\pi(S_{t+1}=s')]$

Where; $\pi(a|s)$ : Probability of taking action $a$ when in state $s$ for a stochastic policy. For deterministic policy, $\sum_a \pi(a|s)= 1$

$\endgroup$
9
  • $\begingroup$ Just a few notes: The sum over $\pi$ equals to 1 even in a stochastic policy, but in a deterministic policy, there is just one action that receives the full weight (ie, $\pi(a|s) = 1$ and the rest receive 0 weight, so that term is removed from the equation. Also in the line you used the law of total expectation, the order of the condtionals is reversed $\endgroup$ Jun 29, 2018 at 10:07
  • 1
    $\begingroup$ I am pretty sure that this answer is incorrect: Let us follow the equations just until the line involving the law of total expectation. Then the left hand side does not depend on $s'$ while the right hand side does... I.e. if the equations are correct then for which $s'$ are they correct? You must have some kind of integral over $s'$ already at that stage. The reason is probably your misunderstanding of the difference of $E[X|Y]$ (a random variable) vs. its factorization $E[X|Y=y]$ (a deterministic function!)... $\endgroup$ Jan 9, 2019 at 21:36
  • $\begingroup$ @FabianWerner I agree this is not correct. The answer from Jie Shi is the right answer. $\endgroup$
    – teucer
    Jan 9, 2019 at 23:03
  • $\begingroup$ @teucer This answer can be fixed because there is just missing some "symmetrization", i.e. $E[A|C=c] = \int_{\text{range}(B)} p(b|c) E[A|B=b, C=c] dP_B(b)$ but still, the question is the same as in Jie Shis answer: Why is $E[G_{t+1}|S_{t+1}=s_{t+1}, S_t=s_t] = E[G_{t+1}|S_{t+1}=s_{t+1}]$? This is not only the Markov property because $G_{t+1}$ is a really complicated RV: Does it even converge? If so, where? What is the common density $p(g_{t+1}, s_{t+1}, s_t)$? We only know this expression for finite sums (complicated convolution) but for the infinite case? $\endgroup$ Jan 10, 2019 at 7:15
  • $\begingroup$ @FabianWerner not sure if I can answer all the questions. Below some pointers. For the convergence of the $G_{t+1}$, given that it is the sum of discounted rewards, it is reasonable to assume that the series converges (discounting factor is $<1$ and to where it converges does not really matter). I don't get the concern with the density (one can always define a joint density as long as we have random variables), it only matters if it is well defined and in that case it is. $\endgroup$
    – teucer
    Jan 10, 2019 at 14:14
4
$\begingroup$

I know there is already an accepted answer, but I wish to provide a probably more concrete derivation. I would also like to mention that although @Jie Shi trick somewhat makes sense, but it makes me feel very uncomfortable:(. We need to consider the time dimension to make this work. And it is important to note that, the expectation is actually taken over the entire infinite horizon, rather than just over $s$ and $s'$. Let assume we start from $t=0$ (in fact, the derivation is the same regardless of the starting time; I do not want to contaminate the equations with another subscript $k$) \begin{align} v_{\pi}(s_0)&=\mathbb{E}_{\pi}[G_{0}|s_0]\\ G_0&=\sum_{t=0}^{T-1}\gamma^tR_{t+1}\\ \mathbb{E}_{\pi}[G_{0}|s_0]&=\sum_{a_0}\pi(a_0|s_0)\sum_{a_{1},...a_{T}}\sum_{s_{1},...s_{T}}\sum_{r_{1},...r_{T}}\bigg(\prod_{t=0}^{T-1}\pi(a_{t+1}|s_{t+1})p(s_{t+1},r_{t+1}|s_t,a_t)\\ &\times\Big(\sum_{t=0}^{T-1}\gamma^tr_{t+1}\Big)\bigg)\\ &=\sum_{a_0}\pi(a_0|s_0)\sum_{a_{1},...a_{T}}\sum_{s_{1},...s_{T}}\sum_{r_{1},...r_{T}}\bigg(\prod_{t=0}^{T-1}\pi(a_{t+1}|s_{t+1})p(s_{t+1},r_{t+1}|s_t,a_t)\\ &\times\Big(r_1+\gamma\sum_{t=0}^{T-2}\gamma^tr_{t+2}\Big)\bigg) \end{align} NOTED THAT THE ABOVE EQUATION HOLDS EVEN IF $T\rightarrow\infty$, IN FACT IT WILL BE TRUE UNTIL THE END OF UNIVERSE (maybe be a bit exaggerated :) )
At this stage, I believe most of us should already have in mind how the above leads to the final expression--we just need to apply sum-product rule($\sum_a\sum_b\sum_cabc\equiv\sum_aa\sum_bb\sum_cc$) painstakingly. Let us apply the law of linearity of Expectation to each term inside the $\Big(r_{1}+\gamma\sum_{t=0}^{T-2}\gamma^tr_{t+2}\Big)$

Part 1 $$\sum_{a_0}\pi(a_0|s_0)\sum_{a_{1},...a_{T}}\sum_{s_{1},...s_{T}}\sum_{r_{1},...r_{T}}\bigg(\prod_{t=0}^{T-1}\pi(a_{t+1}|s_{t+1})p(s_{t+1},r_{t+1}|s_t,a_t)\times r_1\bigg)$$

Well this is rather trivial, all probabilities disappear (actually sum to 1) except those related to $r_1$. Therefore, we have $$\sum_{a_0}\pi(a_0|s_0)\sum_{s_1,r_1}p(s_1,r_1|s_0,a_0)\times r_1$$

Part 2
Guess what, this part is even more trivial--it only involves rearranging the sequence of summations. $$\sum_{a_0}\pi(a_0|s_0)\sum_{a_{1},...a_{T}}\sum_{s_{1},...s_{T}}\sum_{r_{1},...r_{T}}\bigg(\prod_{t=0}^{T-1}\pi(a_{t+1}|s_{t+1})p(s_{t+1},r_{t+1}|s_t,a_t)\bigg)\\=\sum_{a_0}\pi(a_0|s_0)\sum_{s_1,r_1}p(s_1,r_1|s_0,a_0)\bigg(\sum_{a_1}\pi(a_1|s_1)\sum_{a_{2},...a_{T}}\sum_{s_{2},...s_{T}}\sum_{r_{2},...r_{T}}\bigg(\prod_{t=0}^{T-2}\pi(a_{t+2}|s_{t+2})p(s_{t+2},r_{t+2}|s_{t+1},a_{t+1})\bigg)\bigg)$$

And Eureka!! we recover a recursive pattern in side the big parentheses. Let us combine it with $\gamma\sum_{t=0}^{T-2}\gamma^tr_{t+2}$, and we obtain $v_{\pi}(s_1)=\mathbb{E}_{\pi}[G_1|s_1]$ $$\gamma\mathbb{E}_{\pi}[G_1|s_1]=\sum_{a_1}\pi(a_1|s_1)\sum_{a_{2},...a_{T}}\sum_{s_{2},...s_{T}}\sum_{r_{2},...r_{T}}\bigg(\prod_{t=0}^{T-2}\pi(a_{t+2}|s_{t+2})p(s_{t+2},r_{t+2}|s_{t+1},a_{t+1})\bigg)\bigg(\gamma\sum_{t=0}^{T-2}\gamma^tr_{t+2}\bigg)$$
and part 2 becomes $$\sum_{a_0}\pi(a_0|s_0)\sum_{s_1,r_1}p(s_1,r_1|s_0,a_0)\times \gamma v_{\pi}(s_1)$$

Part 1 + Part 2 $$v_{\pi}(s_0) =\sum_{a_0}\pi(a_0|s_0)\sum_{s_1,r_1}p(s_1,r_1|s_0,a_0)\times \Big(r_1+\gamma v_{\pi}(s_1)\Big) $$

And now if we can tuck in the time dimension and recover the general recursive formulae

$$v_{\pi}(s) =\sum_a \pi(a|s)\sum_{s',r} p(s',r|s,a)\times \Big(r+\gamma v_{\pi}(s')\Big) $$

Final confession, I laughed when I saw people above mention the use of law of total expectation. So here I am

$\endgroup$
20
  • $\begingroup$ Erm... what is the symbol '$\sum_{a_0, ..., a_{\infty}}$' supposed to mean? There is no $a_\infty$... $\endgroup$ Mar 4, 2019 at 15:18
  • $\begingroup$ Another question: Why is the very first equation true? I know $E[f(X)|Y=y] = \int_{\mathcal{X}} f(x) p(x|y) dx$ but in our case, $X$ would be an infinite sequence of random variables $(R_0, R_1, R_2, ........)$ so we would need to compute the density of this variable (consisting of an infinite amount of variables of which we know the density) together with something else (namely the state)... how exactly do you du that? I.e. what is $p(r_0, r_1, ....)$? $\endgroup$ Mar 4, 2019 at 15:22
  • $\begingroup$ @FabianWerner. Take a deep breath to calm your brain first:). Let me answer your first question. $ \sum_{a_0,...,a_{\infty}} \equiv \sum_{a_0}\sum_{a_1},...,\sum_{a_{\infty}} $. If you recall the definition of the value function, it is actually a summation of discounted future rewards. If we consider an infinite horizon for our future rewards, we then need to sum infinite number of times. A reward is result of taking an action from a state, since there is an infinite number of rewards, there should be an infinite number of actions, hence $a_{\infty}$. $\endgroup$ Mar 4, 2019 at 23:23
  • 1
    $\begingroup$ let us assume that I agree that there is some weird $a_\infty$ (which I still doubt, usually, students in the very first semester in math tend to confuse the limit with some construction that actually involves an infinite element)... I still have one simple question: how is “$\sum_{a_1} ... \sum_{a_\infty}$ defined? I know what this expression is supposed to mean with a finite amount of sums... but infinitely many of them? What do you understand that this expression does? $\endgroup$ Mar 5, 2019 at 13:08
  • 1
    $\begingroup$ internet. Could you refer me to a page or any place that defines your expression? If not then you actually defined something new and there is no point in discussing that because it is just a symbol that you made up (but there is no meaning behind it)... you agree that we are only able to discuss about the symbol if we both know what it means, right? So, I do not know what it means, please explain... $\endgroup$ Mar 6, 2019 at 10:09
3
$\begingroup$

This is just a comment/addition to the accepted answer.

I was confused at the line where law of total expectation is being applied. I don't think the main form of law of total expectation can help here. A variant of that is in fact needed here.

If $X,Y,Z$ are random variables and assuming all the expectation exists, then the following identity holds:

$E[X|Y] = E[E[X|Y,Z]|Y]$

In this case, $X= G_{t+1}$, $Y = S_t$ and $Z = S_{t+1}$. Then

$E[G_{t+1}|S_t=s] = E[E[G_{t+1}|S_t=s, S_{t+1}=s'|S_t=s]$, which by Markov property eqauls to $E[E[G_{t+1}|S_{t+1}=s']|S_t=s]$

From there, one could follow the rest of the proof from the answer.

$\endgroup$
3
  • 1
    $\begingroup$ Welcome to CV! Please use the answers only for answering the question. Once you have enough reputation (50), you can add comments. $\endgroup$ Sep 28, 2018 at 2:13
  • $\begingroup$ Thank you. Yes, since I could not comment due to not having enough reputation, I thought it might be useful to add the explanation to the answers. But I will keep that in mind. $\endgroup$ Sep 28, 2018 at 14:13
  • $\begingroup$ I upvoted but still, this answer is missing details: Even if $E[X|Y]$ satisfies this crazy relationship then nobody guarantees that this is true for the factorizations of the conditional expectations as well! I.e. as in the case with the answer of Ntabgoba: The left hand side does not depend on $s'$ while the right hand side does. This equation cannot be correct! $\endgroup$ Jan 9, 2019 at 21:38
3
$\begingroup$

even though the correct answer has already been given and some time has passed, I thought the following step by step guide might be useful:
By linearity of the Expected Value we can split $E[R_{t+1} + \gamma E[G_{t+1}|S_{t}=s]]$ into $E[R_{t+1}|S_t=s]$ and $\gamma E[G_{t+1}|S_{t}=s]$.
I will outline the steps only for the first part, as the second part follows by the same steps combined with the Law of Total Expectation.

\begin{align} E[R_{t+1}|S_t=s]&=\sum_r{ r P[R_{t+1}=r|S_t =s]} \\ &= \sum_a{ \sum_r{ r P[R_{t+1}=r, A_t=a|S_t=s]}} \qquad \text{(III)} \\ &=\sum_a{ \sum_r{ r P[R_{t+1}=r| A_t=a, S_t=s] P[A_t=a|S_t=s]}} \\ &= \sum_{s^{'}}{ \sum_a{ \sum_r{ r P[S_{t+1}=s^{'}, R_{t+1}=r| A_t=a, S_t=s] P[A_t=a|S_t=s] }}} \\ &=\sum_a{ \pi(a|s) \sum_{s^{'},r}{p(s^{'},r|s,a)} } r \end{align}

Whereas (III) follows form: \begin{align} P[A,B|C]&=\frac{P[A,B,C]}{P[C]} \\ &= \frac{P[A,B,C]}{P[C]} \frac{P[B,C]}{P[B,C]}\\ &= \frac{P[A,B,C]}{P[B,C]} \frac{P[B,C]}{P[C]}\\ &= P[A|B,C] P[B|C] \end{align}

$\endgroup$
2
$\begingroup$

What's with the following approach?

$$\begin{align} v_\pi(s) & = \mathbb{E}_\pi\left[G_t \mid S_t = s\right] \\ & = \mathbb{E}_\pi\left[R_{t+1} + \gamma G_{t+1} \mid S_t = s\right] \\ & = \sum_a \pi(a \mid s) \sum_{s'} \sum_r p(s', r \mid s, a) \cdot \,\\ & \qquad \mathbb{E}_\pi\left[R_{t+1} + \gamma G_{t+1} \mid S_{t} = s, A_{t+1} = a, S_{t+1} = s', R_{t+1} = r\right] \\ & = \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) \left[r + \gamma v_\pi(s')\right]. \end{align}$$

The sums are introduced in order to retrieve $a$, $s'$ and $r$ from $s$. After all, the possible actions and possible next states can be . With these extra conditions, the linearity of the expectation leads to the result almost directly.

I am not sure how rigorous my argument is mathematically, though. I am open for improvements.

$\endgroup$
1
  • $\begingroup$ The last line only works because of the MDP property. $\endgroup$
    – teucer
    Jan 9, 2019 at 23:10
1
$\begingroup$

$\mathbb{E}_\pi(\cdot)$ usually denotes the expectation assuming the agent follows policy $\pi$. In this case $\pi(a|s)$ seems non-deterministic, i.e. returns the probability that the agent takes action $a$ when in state $s$.

It looks like $r$, lower-case, is replacing $R_{t+1}$, a random variable. The second expectation replaces the infinite sum, to reflect the assumption that we continue to follow $\pi$ for all future $t$. $\sum_{s',r} r \cdot p(s′,r|s,a)$ is then the expected immediate reward on the next time step; The second expectation—which becomes $v_\pi$—is the expected value of the next state, weighted by the probability of winding up in state $s'$ having taken $a$ from $s$.

Thus, the expectation accounts for the policy probability as well as the transition and reward functions, here expressed together as $p(s', r|s,a)$.

$\endgroup$
3
  • $\begingroup$ Thanks. Yes, what you mentioned about $\pi(a|s)$ is correct (it's the probability of the agent taking action $a$ when in state $s$). $\endgroup$ Oct 31, 2016 at 14:54
  • $\begingroup$ What I don't follow is what terms exactly get expanded into what terms in the second step (I'm familiar with probability factorization and marginalization, but not so much with RL). Is $R_t$ the term being expanded? I.e. what exactly in the previous step equals what exactly in the next step? $\endgroup$ Oct 31, 2016 at 14:55
  • 1
    $\begingroup$ It looks like $r$, lower-case, is replacing $R_{t+1}$, a random variable, and the second expectation replaces the infinite sum (probably to reflect the assumption that we continue to follow $\pi$ for all future $t$). $\Sigma p(s',r|s,a)r$ is then the expected immediate reward on the next time step, and the second expectation—which becomes $v_\pi$—is the expected value of the next state, weighted by the probability of winding up in state $s'$ having taken $a$ from $s$. $\endgroup$ Oct 31, 2016 at 15:20
1
$\begingroup$

Here is an approach that uses the results of exercises in the book (assuming you are using the 2nd edition of the book). In exercise 3.12 you should have derived the equation $$v_\pi(s) = \sum_a \pi(a \mid s) q_\pi(s,a)$$ and in exercise 3.13 you should have derived the equation $$q_\pi(s,a) = \sum_{s',r} p(s',r\mid s,a)(r + \gamma v_\pi(s'))$$ Using these two equations, we can write $$\begin{align}v_\pi(s) &= \sum_a \pi(a \mid s) q_\pi(s,a) \\ &= \sum_a \pi(a \mid s) \sum_{s',r} p(s',r\mid s,a)(r + \gamma v_\pi(s'))\end{align}$$ which is the Bellman equation. Of course, this pushes most of the work into exercise 3.13 (but assuming you are reading/doing the exercises linearly, this shouldn't be a problem). Actually, it's a little strange that Sutton and Barto decided to go for the straight derivation (I guess they didn't want to give away the answers to the exercises).

$\endgroup$
0
$\begingroup$

I wasn't satisfied with any of the above solutions, so I'll give it a try. I find the solution proposed by riceissa the most elegant one, but he only proved the last step. I want to add the missing pieces. So let's go ...

Proof of $v_\pi(s) = \sum_a\pi(a|s)q_\pi(s,a)$:

\begin{eqnarray*} v_\pi(s) &=& \mathbb{E}_\pi[G_t|S_t=s]\\ &=&\sum_g g p(g|s)\\ &=&\sum_g g \sum_a p(g,a|s)\\ &=&\sum_g \sum_a g p(g|a,s)p(a|s)\\ &=&\sum_a p(a|s) \sum_g g p(g|a,s)\\ &=&\sum_a \pi(a|s) \mathbb{E}_\pi[G_t|S_t=s,A_t=a]\\ &=&\sum_a\pi(a|s)q_\pi(s,a) \end{eqnarray*}

Proof of $q_\pi(s,a) = \sum_{s',r}p(s',r|s,a)[r+\gamma v_\pi(s')]$:

\begin{eqnarray*} q_\pi(s,a) &=& \mathbb{E}_\pi[G_t|S_t=s,A_t=a]\\ &=&\mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1}|S_t=s,A_t=a]\\ &=&\mathbb{E}_\pi[R_{t+1}|S_t=s,A_t=a] + \gamma\mathbb{E}_\pi[G_{t+1}|S_t=s,A_t=a]\\ &=&\sum_r rp(r|s,a) + \gamma\mathbb{E}_\pi[G_{t+1}|S_t=s,A_t=a]\\ &=&\sum_r r\sum_{s'}p(s',r|s,a) + \gamma\mathbb{E}_\pi[G_{t+1}|S_t=s,A_t=a]\\ &=&\sum_{s',r}rp(s',r|s,a) + \gamma\mathbb{E}[\mathbb{E}_\pi[G_{t+1}|S_t=s,A_t=a,R_{t+1},S_{t+1}]] \quad (*)\\ &=&\sum_{s',r} rp(s',r|s,a) + \gamma\sum_{s',r}\mathbb{E}_\pi[G_{t+1}|S_t=s,A_t=a,R_{t+1}=r,S_{t+1}=s']p(s',r|s,a)\\ &=&\sum_{s',r} p(s',r|s,a)[r + \gamma\mathbb{E}_\pi[G_{t+1}|S_t=s,A_t=a,R_{t+1}=r,S_{t+1}=s']\\ &=&\sum_{s',r} p(s',r|s,a)[r + \gamma\mathbb{E}_\pi[G_{t+1}|S_{t+1}=s'] \quad (**)\\ &=&\sum_{s',r} p(s',r|s,a)[r + \gamma v_\pi(s')]\\ \end{eqnarray*}

(*) Law of total expectation

(**) $S_{t+1} = s'$ holds all information, so all other variables can be dropped (Markov property).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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