Answers.Body: <p>I think I may be in position to answer my own question. The Bellman equation (for the optimal policy) for a MDP with <span class="math-container">$r(s,a,s')$</span> rewards would look like this:</p>
  
  <p><span class="math-container">$$V(s) = \max_a \left\{ \sum_{s'} p(s'|s,a)(r(s,a,s') + \gamma V(s')) \right\} $$</span>
  <span class="math-container">$$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\} $$</span></p>
  
  <p>Now, <span class="math-container">$ \sum_{s'} p(s'|s,a) \cdot r(s,a,s') $</span> is precisely <span class="math-container">$ \mathbb{E}\left[ r(s,a,s') | s,a \right] = r(s,a) $</span>.</p>
  
  <p>So all in all, the resulting Bellman equation looks like this:</p>
  
  <p><span class="math-container">$$V(s) = \max_a \left\{r(s,a) + \gamma \sum_{s'} p(s'|s,a) \cdot V(s') \right\} $$</span></p>
  
  <p>It is clear, then, that a process with <span class="math-container">$ r(s,a,s') $</span> rewards can be transformed to a <span class="math-container">$ r(s,a) $</span> process without introducing artificial states and maintaining the optimal policies.</p>
  
  <p>As a side note unrelated to the question itself, that leads me to believe that <span class="math-container">$ r(s,a,s') $</span> 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 <span class="math-container">$ r(s) $</span> to <span class="math-container">$ r(s,a) $</span>).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-26T13:37:12.483Z
Answers.Text: 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)$.
Answers.UserDisplayName: Asher
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-26T13:49:20.620Z
Answers.Text: Good, made that clear.
Answers.UserDisplayName: Asher
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-26T15:35:39.440Z
Answers.Text: "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.
Answers.UserDisplayName: Asher
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-26T11:37:17.783Z
Answers.LastActivityDate: 2020-05-26T13:41:29.293Z
Answers.LastEditDate: 2020-05-26T13:41:29.293Z
Answers.UserDisplayName: Asher
Body: <p>The AIMA book has an exercise about showing that an MDP with rewards of the form <span class="math-container">$r(s, a, s')$</span> can be converted to an MDP with rewards <span class="math-container">$r(s, a)$</span>, and to an MDP with rewards <span class="math-container">$r(s)$</span> with equivalent optimal policies.</p>
  <p>In the case of converting to <span class="math-container">$r(s)$</span> I see the need to include a post-state, as the author's solution suggests. However, my immediate approach to transform from <span class="math-container">$r(s,a,s')$</span> to <span class="math-container">$r(s,a)$</span> was to simply take the expectation of <span class="math-container">$r(s,a,s')$</span> with respect to s' (*). That is:</p>
  <p><span class="math-container">$$ r(s,a) = \sum_{s'} r(s,a,s') \cdot p(s'|s,a) $$</span></p>
  <p>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, <a href="https://edge.edx.org/assets/courseware/v1/749efba05a2ecb46dc276aaa3dd252cf/c4x/BerkeleyX/CS188-FA14/asset/section_8_solutions.pdf" rel="nofollow noreferrer">another resource</a> I found also talks about pre-states.</p>
  <p>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 <a href="https://ai.stackexchange.com/q/10442/2444">here</a> 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 <span class="math-container">$r(s, a, s')$</span>.</p>
  <p>This is the kind of existential question that bugs me from time to time and I wanted to get some confirmation.</p>
  <p>(*) Of course, that doesn't work in the <span class="math-container">$r(s, a)$</span> to <span class="math-container">$r(s)$</span> 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).</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-25T13:18:57.867Z
Comments.Text: You might want to see this [How are the reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ equivalent?](https://ai.stackexchange.com/q/10442/2444) answer.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-25T14:58:42.863Z
Comments.Text: 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.
Comments.UserDisplayName: Asher
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-25T15:09:50.123Z
Comments.Text: 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.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-25T15:24:35.310Z
Comments.Text: 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).
Comments.UserDisplayName: Asher
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-25T15:36:20.520Z
Comments.Text: $r(s,a,s') = \mathbb{E}[R_t | S_{t-1} = s, A_{t-1} = a, S_t = s']$?
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-25T15:44:59.947Z
Comments.Text: If so then you would be able to get  $\mathbb{E}[R_t | S_{t-1} = s, A_{t-1} = a] = \sum_{s'} \mathbb{E}[R_t | S_{t-1} = s, A_{t-1} = a, S_t = s'] \mathbb{P}(S_t = s' | s, a) = r(s,a)$
Comments.UserDisplayName: David
Tags: <reinforcement-learning><markov-decision-process><proofs><reward-functions>
Title: 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)$?
UserDisplayName: Asher
ThreadText: # 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)$?
  
  (Asked by: username_0 on 2020-05-25)
  
  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](https://edge.edx.org/assets/courseware/v1/749efba05a2ecb46dc276aaa3dd252cf/c4x/BerkeleyX/CS188-FA14/asset/section_8_solutions.pdf) 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](https://ai.stackexchange.com/q/10442/2444) 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).
  
  **Tags:** reinforcement-learning, markov-decision-process, proofs, reward-functions
  
  > **Comments:**
  > **username_1**: You might want to see this [How are the reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ equivalent?](https://ai.stackexchange.com/q/10442/2444) answer.  
  > **username_0**: 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.  
  > **username_1**: 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.  
  > **username_0**: 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).  
  > **username_1**: $r(s,a,s') = \mathbb{E}[R_t | S_{t-1} = s, A_{t-1} = a, S_t = s']$?  
  > **username_1**: If so then you would be able to get  $\mathbb{E}[R_t | S_{t-1} = s, A_{t-1} = a] = \sum_{s'} \mathbb{E}[R_t | S_{t-1} = s, A_{t-1} = a, S_t = s'] \mathbb{P}(S_t = s' | s, a) = r(s,a)$  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2020-05-26. Score: 3 | Accepted answer
  
  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) $).
  
  > **Comments:**
  > **username_0**: 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)$.  
  > **username_0**: Good, made that clear.  
  > **username_0**: "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.  
  
  ---
  
  