3
$\begingroup$

I'd like to prove this "second form" of Bellman's equation: $v(s) = \mathbb{E}[R_{t + 1} + \gamma v(S_{t+1}) \mid S_{t} = s]$ starting from Bellman's equation: $v(s) = \mathbb{E}[G_{t} \mid S_{t} = s]$ where the return $G_{t}$ is defined as follows: $G_{t} = \sum_{k=0}^{\infty}{\gamma^{k}R_{t+k+1}}$.

I tried to use the linearity of the expectation as follows: $v(s) = \mathbb{E}[R_{t+1} \mid S_{t} = s] + \mathbb{E}[\sum_{k = 1}^{\infty}{\gamma^{k}R_{t+k+1}} \mid S_{t} = s]$

Which gives us: $v(s) = \mathbb{E}[R_{t+1} \mid S_{t} = s] + \gamma\mathbb{E}[\sum_{k = 0}^{\infty}{\gamma^{k}R_{(t + 1) + k + 1}} \mid S_{t} = s] = \mathbb{E}[R_{t+1} \mid S_{t} = s] + \gamma\mathbb{E}[G_{t + 1} \mid S_{t} = s]$

I also tried to develop the second formula: $v(s) = \mathbb{E}[R_{t+1} \mid S_{t} = s] + \gamma\mathbb{E}[v(S_{t+1}) \mid S_{t} = s]$ and I'm tempted to say that $\mathbb{E}[G_{t+1} \mid S_{t} = s] = \mathbb{E}[v(S_{t+1}) \mid S_{t} = s]$ but that would only be right in the case that both follow conditions are verified:

  1. We have the value function of a particular state $s^\prime$ inside the expectation of the second term (something like $\mathbb{E}[v(s^\prime) \mid S_{t} = s]$ which would directly give $v(s^\prime)$ since it's a scalar) and not $v(S_{t+1})$.
  2. We have $\mathbb{E}[G_{t+1} \mid S_{\textbf{t+1}} = s^\prime]$ in the second term.

I'm probably not understanding something correctly especially what $v(S_{t+1})$ would mean (that wasn't covered in the material I'm following but for me it would be just a function that maps the possible states at time step $t+1$ to the expected return starting from that step at that time step).

$\endgroup$
7
  • $\begingroup$ This seems like it would be more appropriate for cs.stackexchange. $\endgroup$ Jun 14, 2021 at 23:33
  • $\begingroup$ @ThePointer thank you for your comment. I'm sorry I didn't see it earlier, I've already solved my question and posted it as an answer. I wonder if I should just delete the question if it's irrelevant to this forum. $\endgroup$
    – Daviiid
    Jun 14, 2021 at 23:44
  • $\begingroup$ It might not be irrelevant (there's a tag for the Bellman equations in the context of reinforcement learning), but cs.stackexchange might have been the better place for this question. Nonetheless, I suggest you leave it, so that others may benefit from it in the future. And close your question by accepting your answer when the system allows. $\endgroup$ Jun 14, 2021 at 23:46
  • $\begingroup$ @ThePointer thank you! I'll keep that in mind for future similar questions. $\endgroup$
    – Daviiid
    Jun 14, 2021 at 23:47
  • 1
    $\begingroup$ @ThePointer I disagree, in as much as questions about the maths behind reinforcement learning - or any AI-related topic - are very much on-topic here. It is more often the coding problems that get marked as off-topic here. When the coding issue is regardling theory comprehension (as opposed to more obvious bug or programming language issue) then I believe that should be on topic here too. If you'd like to clarify or debate further, then you could take it to meta. $\endgroup$ Jun 15, 2021 at 6:46

1 Answer 1

1
$\begingroup$

Since my question arose from my incomprehension of $v(S_{t + 1})$ and since I got clarifications on it by Neil Slater, I thought I'd go back to this question and try to answer it again.

So I'm assuming that $v(S_{t + 1})$ is a random variable made by the composition of the state-value function $v$ and the random variable $S_{t + 1}$.

Since $v(s) = \mathbb{E}[G_{t + 1} \mid S_{t + 1} = s]$, the random variable $v(S_{t + 1})$ is $\mathbb{E}[G_{t + 1} \mid S_{t + 1}]$. Using a corollary of the total expectation theorem we get that $\mathbb{E}[v(S_{t + 1}) \mid S_{t} = s] = \mathbb{E}[G_{t+1} \mid S_{t} = s]$. This proved, we can conclude using first developments of the question.

$\endgroup$

You must log in to answer this question.

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