1
$\begingroup$

I am currently trying to wrap my head around the Bellman equation and found the following two definitions. The first one is taken from cs229 Stanford - link to the sources is avaiable below.

The second equation is taken from own lecture notes and I find them more difficult to understand.

  1. $V_\pi (s) = R(s) + \lambda \sum\limits_{s'∈S } P_{s\pi(s)}(s')V_\pi (s')$

  2. $V \pi (s) =\sum\limits_a \pi(a|s)\sum\limits_{s_{t+1},r}p(s_{t+1}, r |s, a) [r + \lambda V_\pi(s_{t+1})]$

I would like to know:

  1. Do these equations actually describe the same thing the same way? Are they equivalent?
  2. In the 2nd equation: Why do we have the term $\sum\limits_a p(a|s)$? What does it do?
  3. In the 2nd equation: Why do we also sum over all $r$ in this $\sum\limits_{s_{t+1},r}\dots$ ?

Links I found useful:

http://cs229.stanford.edu/notes/cs229-notes12.pdf

Why is the optimal policy in Markov Decision Process (MDP), independent of the initial state?

Are these three different ways of expressing the optimal value function $V^*$ the same? (reinforcement learning)

$\endgroup$
1
$\begingroup$

Your two equations describe the same relationship between value of current state and value of next state, and are roughly equivalent, but the second one is more general. That is because the first equation uses $R(s)$ for expected immediate reward, which assumes that expected reward only depends on the current state - i.e. it is independent of the action taken. Also in the first equation, a deterministic policy function $\pi(s)$ is assumed to output action choice $a$.

In the second equation, the term $\sum\limits_a \pi(a|s)$ is a weighted sum over the policy for the second sum, which is "nested" inside the first sum and evaluated per action. It assumes a stochastic policy where $\pi(a|s)$ returns the probabilty of selecting action $a$ in state $s$. A stochastic policy is another generalisation, making the second equation applicable to a wider range of MDPs.

Also in the second equation, the sum over all (discrete) reward and next state values is used instead of requiring an expected reward function. This is a free choice, it does not make the equation more general, but may help with intuition on what the equation is doing. Most notably, the right hand side of the Bellman equation $V_{\pi}(s)$ is an expectation, and on the left hand side there is only one expectation for $V_{\pi}(s_{t+1})$ - everything else has been resolved to indvidual values and probabilities.

If you were to use an expected reward function instead in the second equations, it might look like $R(s,a,s_{t+1})$ - so that it depends on all variables defined by parameters and containing sums. An equivalent second term would then be $\sum\limits_{s_{t+1}} P_{sa}(s_{t+1}) ( R(s,a,s_{t+1}) + \lambda V(s_{t+1}))$ where $P_{sa}(s_{t+1})$ is probability of transition $s \rightarrow s_{t+1}$ given action $a$.

If you read more literature on reinforcement learning, you will find many similar minor variations in terminology and notation. It helps to be familiar with the derivations of the Bellman equations from first principles - then you will quickly spot which variants are being used.

$\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.