# How do I convert an MDP with the reward function in the form $R(s,a,s')$ to and an MDP with a reward function in the form $R(s,a)$?

The AIMA book has an exercise about showing that an MDP with rewards of the form $$r(s, a, s')$$ can be converted to an MDP with rewards $$r(s, a)$$, and to an MDP with rewards $$r(s)$$ with equivalent optimal policies.

In the case of converting to $$r(s)$$ I see the need to include a post-state, as the author's solution suggests. However, my immediate approach to transform from $$r(s,a,s')$$ to $$r(s,a)$$ was to simply take the expectation of $$r(s,a,s')$$ with respect to s' (*). That is:

$$r(s,a) = \sum_{s'} r(s,a,s') \cdot p(s'|s,a)$$

The authors however suggest a pre-state transformation, similar to the post-state one. I believe that the expectation-based method is much more elegant and shows a different kind of reasoning that complements the introduction of artificial states. However, another resource I found also talks about pre-states.

Is there any flaw in my reasoning that prevents taking the expectation of the reward and allow a much simpler transformation? I would be inclined to say no since the accepted answer here seems to support this. This answer mentions Sutton and Barto's book, by the way, which also seems to be fine with taking the expectation of $$r(s, a, s')$$.

This is the kind of existential question that bugs me from time to time and I wanted to get some confirmation.

(*) Of course, that doesn't work in the $$r(s, a)$$ to $$r(s)$$ case, as we do not have a probability distribution over the actions (that would be a policy, in fact, and that's what we are after).

• You might want to see this How are the reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ equivalent? answer. May 25 '20 at 13:18
• I actually had that thread linked in my question, but: 1) I'm not claiming that the different reward functions can be made equivalent, but that the optimal policy to the overall MDP can; 2) In their solutions book, Norvig and Russell describe a transformation based on extending the state space with pre and post states, and a few more changes to the discount factor and the transitions to account for these additional states; 3) I wanted to know if taking the expectation over s' can do the trick too, at least for the R(s,a,s') to the R(s,a) case. May 25 '20 at 14:58
• sorry, my bad for not noticing the link. Note that if you have a joint distribution of $(X,Y)$ you can't find $\mathbb{E}[Y]$ by simply summing over $y$ and using the joint pmf - you would first need to marginalise the joint pmf to get the single pmf of $Y$, so your expectation doesn't work out. May 25 '20 at 15:09
• I understand, but I think I didn't imply that...? In fact I'm kinda saying that you could get away by marginalizing s,a in the r(s,a,s') function (if you can say marginalize in this context, since r(s,a,s') is not a probability distribution). May 25 '20 at 15:24
• $r(s,a,s') = \mathbb{E}[R_t | S_{t-1} = s, A_{t-1} = a, S_t = s']$? May 25 '20 at 15:36

I think I may be in position to answer my own question. The Bellman equation (for the optimal policy) for a MDP with $$r(s,a,s')$$ rewards would look like this:

$$V(s) = \max_a \left\{ \sum_{s'} p(s'|s,a)(r(s,a,s') + \gamma V(s')) \right\}$$ $$V(s) = \max_a \left\{ \sum_{s'} p(s'|s,a) \cdot r(s,a,s') + \gamma \sum_{s'} p(s'|a,s) \cdot V(s') \right\}$$

Now, $$\sum_{s'} p(s'|s,a) \cdot r(s,a,s')$$ is precisely $$\mathbb{E}\left[ r(s,a,s') | s,a \right] = r(s,a)$$.

So all in all, the resulting Bellman equation looks like this:

$$V(s) = \max_a \left\{r(s,a) + \gamma \sum_{s'} p(s'|s,a) \cdot V(s') \right\}$$

It is clear, then, that a process with $$r(s,a,s')$$ rewards can be transformed to a $$r(s,a)$$ process without introducing artificial states and maintaining the optimal policies.

As a side note unrelated to the question itself, that leads me to believe that $$r(s,a,s')$$ functions may be convenient in some scenarios, but they do not add "expressive power", in the sense that they do not allow to model problems more compactly (as it happens when we extend $$r(s)$$ to $$r(s,a)$$).

• Fair enough, since I'm interested just in the optimal policy. Maybe I should edit the answer to reflect that (although I was under the impression that the Bellman equation already conveyed optimality)? I thought that $p(s,a,s')$ was a fairly understood notation for the transition probability, meaning: probability of transitioning to $s'$ after taking action $a$ in $s$. I've replaced it by $p(s'|s,a)$. May 26 '20 at 13:37
• Good, made that clear. May 26 '20 at 13:49
• "My BSc was in Maths and MSc in Stats" -> That would explain the obsession for rigor, clear notation and proper terminology ;) Thank you for your notes, mate. May 26 '20 at 15:35