How are these two versions of the Bellman optimality equation related?

Question

I saw two versions of the optimality equation for $V_{*}(s)$ and $Q_{*}(s,a)$.

The first one is:

$$ V_{*}(s)=\max _{a} \sum_{s^{\prime}} P_{s s^{\prime}}^{a}\left(r(s, a)+\gamma V_{*}\left(s^{\prime}\right)\right) $$

and

$$ Q_{*}(s, a)=\sum_{s^{\prime}} P_{s s^{\prime}}^{a}\left(r(s, a)+\gamma \max _{a^{\prime}} Q_{*}\left(s^{\prime}, a^{\prime}\right)\right) $$

The second one is:

$$ V_{*}(s)=\max _{a \in \mathcal{A}}\left(R(s, a)+\gamma \sum_{s^{\prime} \in \mathcal{S}} P_{s s^{\prime}}^{a} V_{*}\left(s^{\prime}\right)\right) $$

and for $Q_*$

$$ Q_{*}(s, a)=R(s, a)+\gamma \sum_{s^{\prime} \in \mathcal{S}} P_{s s^{\prime}}^{a} \max _{a^{\prime} \in \mathcal{A}} Q_{*}\left(s^{\prime}, a^{\prime}\right) $$

If following distributive property to get from the first to the second expression. Why there is no summation term for the reward, for example, $$V_{*}(s) = \max_{a}(\sum_{s'}P^{a}_{ss'}r(s,a)+\gamma\sum_{s'}P^{a}_{ss'}V_{*}(s'))$$?

My guess is that $r(s,a)$ is the constant so it can be moved out of the summation, leaving $$r(s,a)\sum_{s'}P^{a}_{ss'} = r(s,a).$$

But is it always the case that $r(s,a)$ is independent of $s'$? I think the reward of moving from state $s$ to $s'$ may vary.

Answer 1

My guess is that $r(s,a)$ is the constant so it can be moved out of the summation, leaving $r(s,a)\sum_{s'}P^{a}_{ss'} = r(s,a)$

Yes, this is the case. More specifically:

• $r(s,a)$ is the expected reward after taking action $a$ in state $s$.
• Reward may depend on the state arrived in, $s'$, but that is ignored in the equations.
• Reward may vary randomly, but by using the expected reward, this can be ignored.

The first equations you quote, which sum over $s'$ but use $r(s,a)$ inside that sum, are very misleading IMO, since the individual terms may not represent anything meaningful within the MDP. That is the term $r(s,a) + \gamma V^*(s')$ does not correspond to any part of the trajectory of the agent.

Although the sum is still mathematically sound, it is more normal to see a different term $r(s,a,s')$ (the expected reward similar to $r(s,a)$ but also conditional on $s'$) where the expected reward is used inside the sum of next states. The term $r(s,a,s') + \gamma V^*(s')$ does correspond to nodes on the trajectory of the agent. It is the expected future return from $s,a$ conditional on the state transitioning to $s'$.

but is it always the case that $r(s,a)$ is independent of $s'$. I think the reward of moving from state $s$ to $s'$ may vary.

Yes $r(s,a)$ is independent of $s'$. Although individual rewards may vary stochastically, and may depend on $s'$ too, the term is already the expected reward when taking the action $a$ in state $s$. So it already includes any effects of random state transition and random reward. For the Bellman equations to work as written, the expectation needs to be independent of the policy $\pi$ thus a property of the environment, and this is the case.

I think both sets of equations are a little bit awkward from using a combination of expected reward, yet summing up expectations over the state transition matrix. I prefer the notation used in second edition of Sutton & Barto's Reinforcement Learning: An Introduction:

$$v^*(s) = \text{max}_a \sum_{r,s'} p(r,s'|s,a)(r + \gamma v^*(s'))$$

Where $p(r, s'|s,a)$ is the conditional probability of observing reward $r$ and next state $s'$ given initial state $s$ and action $a$. The $p(r, s'|s,a)$ function replaces the combination of state transition matrices $P_{ss'}^a$ and the expected reward (either $r(s,a)$ or $r(s,a,s')$). Those objects can be derived from $p(r,s'|a,s)$ if you want, but personally I find the newer notation easier to follow.