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

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.

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.