2
$\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 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 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 at 23:46
  • $\begingroup$ @ThePointer thank you! I'll keep that in mind for future similar questions. $\endgroup$
    – Daviiid
    Jun 14 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 at 6:46
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$

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.