5
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ You might want to see this How are the reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ equivalent? answer. $\endgroup$ – David Ireland May 25 at 13:18
  • $\begingroup$ 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. $\endgroup$ – Asher May 25 at 14:58
  • $\begingroup$ 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. $\endgroup$ – David Ireland May 25 at 15:09
  • $\begingroup$ 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). $\endgroup$ – Asher May 25 at 15:24
  • $\begingroup$ $r(s,a,s') = \mathbb{E}[R_t | S_{t-1} = s, A_{t-1} = a, S_t = s']$? $\endgroup$ – David Ireland May 25 at 15:36
2
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ I don't think that your definition of $V(s)$ is correct - the way you have defined it would only hold for the optimal policy. In general the value function is the average of $Q(s,a)$ where the average is taken over $a$. Also, what are you defining $p(s,a,s')$ to be? $\endgroup$ – David Ireland May 26 at 12:07
  • $\begingroup$ 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)$. $\endgroup$ – Asher May 26 at 13:37
  • $\begingroup$ No, the Bellman optimality equation conveys optimality. My BSc was in Maths and MSc in Stats and I would say your notation would be used for a joint distribution over $s,s',a$, not a conditional distribution. Sutton and Barto also use the conditioned on notation e.g. $p(s',r|s,a)$. $\endgroup$ – David Ireland May 26 at 13:45
  • $\begingroup$ Good, made that clear. $\endgroup$ – Asher May 26 at 13:49
  • $\begingroup$ "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. $\endgroup$ – Asher May 26 at 15:35

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.