How do I derive Sutton and Barto Equation 3.14?

Question

I'm having trouble going to the 2nd to last line of (3.14),

http://incompleteideas.net/book/RLbook2020.pdf#page=81

$$ \require{enclose} \begin{aligned} v_{\pi}(s) & \doteq \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^{\prime}} \sum_{r} p\left(s^{\prime}, r \mid s, a\right)\left[r+\gamma \mathbb{E}_{\pi}\left[G_{t+1} \mid \enclose{circle}[mathcolor="red"]{S_{t+1}}=s^{\prime}\right]\right] \\ &=\sum_{a} \pi(a \mid s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r \mid s, a\right)\left[r+\gamma v_{\pi}\left(s^{\prime}\right)\right], \quad \text { for all } s \in \mathcal{S}, \end{aligned} $$

I don't understand where the red circled term comes from. Namely, where the $S_{t+1}$ comes from, since I was expecting an $S_t$ from the previous line.

Can you please explain? Thank you.

Answer 1

Here is a detailed derivation of the Bellman equation:

\begin{align*} v_\pi(s) &=\mathbb{E}[G_t|S_t=s]\\ &=\mathbb{E}[R_{t+1}+\gamma G_{t+1} | S_t=s]\\ &={\mathbb{E}[R_{t+1}|S_t=s]}+\gamma {\mathbb{E}[G_{t+1}|S_t=s]} \end{align*} where we have two terms.

The first term can be calculated as \begin{align*} \mathbb{E}[R_{t+1}|S_t=s] &=\sum_{a}\pi(a|s)\mathbb{E}[R_{t+1}|S_t=s,A_t=a]\\ &=\sum_{a}\pi(a|s)\sum_{r}p(r|s,a)r \end{align*}

The second term can be calculated as \begin{align*} \mathbb{E}[G_{t+1}|S_t=s] &=\sum_{s'}\mathbb{E}[G_{t+1}|S_t=s,S_{t+1}=s']p(s'|s)\\ &=\sum_{s'}\mathbb{E}[G_{t+1}|S_{t+1}=s']p(s'|s)\\ &=\sum_{s'}v_\pi(s')p(s'|s)\\ &=\sum_{s'}v_\pi(s')\sum_{a}p(s'|s,a)\pi(a|s) \end{align*}

A tricky point, which may have confused you, was that the memory-less Markov property is used.

Combining the two terms gives the Bellman equation. More details can be found in the book Mathematical Foundations of Reinforcement Learning. See chapter 3 specifically.

Answer 2

for first, let's see what $S_{t+1}$ means: that means from next time-step. please remember what was V(s) define: what you expect to gain from this state($S_t$) until end of trajectory. so, you need to know for each action what is expected reward and that is the probability of next state occurrence if you choose action $a$ in state $s$ ($p(s',a|s,a)$) multiply in (reward and next state value function). in fact it is a bootstrapping formula:

python code:

values = list()
for s in P:
    values.append(list())
    for a in P[s]:
        values[-1].append(sum([prob * (reward + gamma * V[next_state])
                                  for prob, next_state, reward, _ in P[s][a]]))

mind that P is $MDP$