Answers.Body: <p>Let <span class="math-container">$R(s)$</span> denote a probability distribution over rewards that our agent may get in some MDP as a reward for entering a state <span class="math-container">$s$</span>. The easiest case is to demonstrate that we can also choose to write this as <span class="math-container">$R(s, a)$</span> or <span class="math-container">$R(s, a, s')$</span>: simply take <span class="math-container">$\forall a: R(s, a) = R(s)$</span>, or <span class="math-container">$\forall a \forall s': R(s, a, s') = R(s)$</span>, as also described in <a href="https://ai.stackexchange.com/a/10444/1641">Neil's answer</a>.</p>
  
  <hr>
  
  <p>Let <span class="math-container">$R(s, a)$</span> denote a probability distribution over rewards that our agent may get as a reward for executing action <span class="math-container">$a$</span> in state <span class="math-container">$s$</span>. The easy case of demonstrating equivalence to <span class="math-container">$R(s, a, s')$</span> is already handled above, but can we also construct an MDP in which we only use the <span class="math-container">$R(s)$</span> notation?</p>
  
  <p>The easiest way I can think of to do so (may not be the cleanest way) would be to construct a new MDP with a bunch of "dummy" states <span class="math-container">$z(s, a)$</span>, such that executing action <span class="math-container">$a$</span> in state <span class="math-container">$s$</span> in the original MDP deterministically leads to a dummy state <span class="math-container">$z(s, a)$</span> in the new MDP. Note that I write <span class="math-container">$z(s, a)$</span> to make the connection back to the original MDP explicit, but this is a completely independent MDP and you should view it as just a state "<span class="math-container">$z$</span>".</p>
  
  <p>Then, the reward distribution <span class="math-container">$R(s, a)$</span> that was associated with the state-action pair <span class="math-container">$(s, a)$</span> in the original MDP can be written as <span class="math-container">$R(z(s, a))$</span>, which is now only a function of the state in the new MDP. In this dummy state <span class="math-container">$z(s, a)$</span> in the new MDP, every possible action <span class="math-container">$\alpha$</span> should have exactly the same transition probabilities towards new states <span class="math-container">$s'$</span> as the original transition probabilities for executing <span class="math-container">$a$</span> in <span class="math-container">$s$</span> back in the original MDP. This guarantees that the same policy has the same probabilities of reaching certain states in both MDPs; only in our new MDP the agent is forced to transition through these dummy states in between.</p>
  
  <p>If you also have a discount factor <span class="math-container">$\gamma$</span> in the original MDP, I guess you should use a discount factor <span class="math-container">$\sqrt{\gamma}$</span> in the new MDP, because every step in the original MDP requires two steps (one step into a dummy state, and one step out of it again) in the new MDP.</p>
  
  <hr>
  
  <p>The final case for <span class="math-container">$R(s, a, s')$</span> could be done in a very similar way, but it would get even more complicated to write out formally. The intuition would be the same though. Above, we pretty much "baked" state-action pairs <span class="math-container">$(s, a)$</span> from the original MDP into additional dummy states, such that in the new MDP we have states that "carry the same amount of information" as a full state-action pair in the original MDP. For the <span class="math-container">$R(s, a, s')$</span> case, you'd need to devise an even uglier solution with even more information "baked into" dummy states, such that you can treat full <span class="math-container">$(s, a, s')$</span> triples as single <span class="math-container">$z(s, a, s')$</span> states in the new MDP.</p>
  
  <hr>
  
  <blockquote>
    <p>Finally, when should we use one representation over the other and why are there three representations? I suppose it is because one representation may be more convenient than another in certain cases: which cases? How do you decide which representation to use?</p>
  </blockquote>
  
  <p>I would recommend always using the <strong>simplest representation</strong> that happens to be <strong>sufficient</strong> to describe how the rewards work in your environment in a natural way. </p>
  
  <p>For example, if you have a two-player zero-sum game where terminal game states give a reward of <span class="math-container">$-1$</span>, <span class="math-container">$0$</span>, or <span class="math-container">$1$</span> for losses, draws, or wins, it is sufficient to use the <span class="math-container">$R(s)$</span> notation; the reward depends on the terminal game state reached, not on how it was reached. Another example would be a maze with a specific goal position, as described in Neil's answer. You could use the more complex <span class="math-container">$R(s, a)$</span> or <span class="math-container">$R(s, a, s')$</span> notations... but there wouldn't be much of a point in doing so really.</p>
  
  <p>If you have an environment in which the reached state and the played action both have influence on the reward distribution, then it's much more sensible to just use the <span class="math-container">$R(s, a)$</span> notation rather than trying to define a massively overcomplicated MDP with dummy states as I've tried to do above. An example would be... let's say we're playing a quizz, where <span class="math-container">$s$</span> denotes the current question, and different actions <span class="math-container">$a$</span> are different answers that the agent can give. Then it's natural to model the problem as an MDP where <span class="math-container">$R(s, a)$</span> is only positive if <span class="math-container">$a$</span> is the correct answer to the question <span class="math-container">$s$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-09T14:29:24.320Z
Answers.Text: I would like to note that $R(s)$, $R(s, a)$ and $R(s, a, s')$ can be intuitively interpreted differently. We can think of $R(s)$ as the reward you obtain for entering, exiting or staying in the state $s$ (no matter what action we take or which next state we may end up in). $R(s, a)$, intuitively, can be thought of as the reward you obtain for taking action $a$ in state $s$. Finally, $R(s, a, s')$ can be thought of as the reward you obtain for taking action $a$ in state $s$ and ending up in state $s'$.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-09T14:30:38.630Z
Answers.Text: I recall that the environment may be stochastic, so, in general, if we take action $a$ in state $s$, we may not end up always in the same next state, that is, if we take action $a$ in the state $s$ twice, the resulting next state may be different.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-07T19:43:01.373Z
Answers.LastActivityDate: 2019-02-07T19:43:01.373Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>In general the different reward functions <span class="math-container">$R(s)$</span>, <span class="math-container">$R(s, a)$</span> and <span class="math-container">$R(s, a, s')$</span> are <em>not</em> equivalent mathematically, so you will not find any formal proof.</p>
  <p>It is possible for the functions to resolve to the same value in a specific MDP, if, for instance, you use <span class="math-container">$R(s, a, s')$</span> and the value returned only depends on <span class="math-container">$s$</span>, then <span class="math-container">$R(s, a, s') = R(s)$</span>. This is not true in general, but as the reward functions are often under your control, it can be the case quite often.</p>
  <p>For instance, in scenarios where the agent's goal is to reach some pre-defined state, as in the grid world example from the video, then there is no difference between <span class="math-container">$R(s, a, s')$</span> or <span class="math-container">$R(s)$</span>. Given that is the case, for those example problems you may as well use <span class="math-container">$R(s)$</span>, as it simplifies the expressions that you need to calculate for algorithms like Q-learning.</p>
  <p>I think the lecturer did not mean &quot;equivalent&quot; in the mathematical sense, but in the sense that future lectures will use one of the functions, and a lot of what you will learn is going to be much the same as if you had used a different reward function.</p>
  <blockquote>
  <p>Finally, when should we use one representation over the other and why are there three representations?</p>
  </blockquote>
  <p>Typically, I don't use any of those representations by default. I tend to use Sutton &amp; Barto's <span class="math-container">$p(s', r|s, a)$</span> notation for combined state transitions and rewards. That expression returns probability of transitioning to state <span class="math-container">$s'$</span> and receiving reward <span class="math-container">$r$</span> when starting in state <span class="math-container">$s$</span> and taking action <span class="math-container">$a$</span>. For discrete actions, you can re-write the expectation of the different functions <span class="math-container">$R$</span> in terms of this function as follows:</p>
  <p><span class="math-container">$$\mathbb{E}[R(s)] = \sum_{a \in \mathcal{A}(s)}\sum_{s' \in \mathcal{S}}\sum_{r \in {R}}rp(s', r|s, a)\qquad*$$</span></p>
  <p><span class="math-container">$$\mathbb{E}[R(s,a)] = \sum_{s' \in \mathcal{S}}\sum_{r \in {R}}rp(s', r|s, a)$$</span></p>
  <p><span class="math-container">$$\mathbb{E}[R(s,a, s')] = \sum_{r \in {R}}r\frac{p(s', r|s, a)}{p(s'|s, a)}$$</span></p>
  <p>I think this is one way to see how the functions in the video are closely related.</p>
  <p>Which one would you use? Depends on what you are doing. If you want to simplify an equation or code, then use the simplest version of the reward function that fits with the reward scheme you set up for the goals of the problem. For instance, if there is one goal state to exit a maze, and an episode ends as soon as this happens, then you don't care how you got to that state or what the previous state was, and can use <span class="math-container">$R(s)$</span></p>
  <p>In practice, what happens if you use a different reward function is that you need to pay attention to where it appears in things like the Bellman equation for theoretical treatments. When you get to implement model-free methods like Q-learning, <span class="math-container">$R(s)$</span> or its variants don't really appear except in the theory.</p>
  <hr />
  <p>* This is not technically correct in all cases. The assumption I have made is that <span class="math-container">$R(s)$</span> is a reward granted at the point of <em>leaving</em> state <span class="math-container">$s$</span>, and is independent of how the state is left and where the agent ends up next.</p>
  <p>If this was a fixed reward for <em>entering</em> state <span class="math-container">$s$</span>, regardless of how, then it could be written around <span class="math-container">$R(s')$</span> as follows:</p>
  <p><span class="math-container">$$\mathbb{E}[R(s')] = \sum_{s \in \mathcal{S}}\sum_{a \in \mathcal{A}(s)}\sum_{r \in {R}}rp(s', r|s, a)$$</span></p>
  <p>i.e. by summing all the rewards that end up at <span class="math-container">$s'$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-06T14:57:36.813Z
Answers.Text: Sutton & Barto define $r(s, a, s')$ differently, which does not seem to be equivalent to your definition. See [equation 3.6 of the 2nd edition](http://incompleteideas.net/book/RLbook2020.pdf#page=71). They also use a different notation to denote these reward functions, but it's also true that, in my original question, I also used a notation different than the one in this version of the book (so maybe it's _not_ a good idea to edit your answer to be consistent with the book).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-06T15:46:10.767Z
Answers.Text: @nbro: As you'd expect Sutton&Barto are right here. I missed that fixing $s'$ means needing to normalise the values. I have fixed it, though I could also expand what $p(s'|s,a)$ is, I think it is fairly clear given other definitions.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-07T17:49:41.827Z
Answers.LastActivityDate: 2021-01-27T16:14:02.840Z
Answers.LastEditDate: 2021-01-27T16:14:02.840Z
Answers.UserDisplayName: Neil Slater
Body: <p>In this <a href="https://www.youtube.com/watch?v=Jw3ZnWFjDfM" rel="nofollow noreferrer">video</a>, the lecturer states that <span class="math-container">$R(s)$</span>, <span class="math-container">$R(s, a)$</span> and <span class="math-container">$R(s, a, s')$</span> are equivalent representations of the reward function. Intuitively, this is the case, according to the same lecturer, because <span class="math-container">$s$</span> can be made to represent the state and the action. Furthermore, apparently, the Markov decision process would change depending on whether we use one representation or the other.</p>
  
  <p>I am looking for a formal proof that shows that these representations are equivalent. Moreover, how exactly would the Markov decision process change if we use one representation over the other? Finally, when should we use one representation over the other and why are there three representations? I suppose it is because one representation may be more convenient than another in certain cases: which cases? How do you decide which representation to use?</p>
  
Tags: <reinforcement-learning><markov-decision-process><proofs><notation><reward-functions>
Title: How are the reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ equivalent?
UserDisplayName: nbro
ThreadText: # How are the reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ equivalent?
  
  (Asked by: username_0 on 2019-02-07)
  
  In this [video](https://www.youtube.com/watch?v=Jw3ZnWFjDfM), the lecturer states that $R(s)$, $R(s, a)$ and $R(s, a, s')$ are equivalent representations of the reward function. Intuitively, this is the case, according to the same lecturer, because $s$ can be made to represent the state and the action. Furthermore, apparently, the Markov decision process would change depending on whether we use one representation or the other.
  
  I am looking for a formal proof that shows that these representations are equivalent. Moreover, how exactly would the Markov decision process change if we use one representation over the other? Finally, when should we use one representation over the other and why are there three representations? I suppose it is because one representation may be more convenient than another in certain cases: which cases? How do you decide which representation to use?
  
  **Tags:** reinforcement-learning, markov-decision-process, proofs, notation, reward-functions
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2019-02-07. Score: 8
  
  In general the different reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ are *not* equivalent mathematically, so you will not find any formal proof.
  
  It is possible for the functions to resolve to the same value in a specific MDP, if, for instance, you use $R(s, a, s')$ and the value returned only depends on $s$, then $R(s, a, s') = R(s)$. This is not true in general, but as the reward functions are often under your control, it can be the case quite often.
  
  For instance, in scenarios where the agent's goal is to reach some pre-defined state, as in the grid world example from the video, then there is no difference between $R(s, a, s')$ or $R(s)$. Given that is the case, for those example problems you may as well use $R(s)$, as it simplifies the expressions that you need to calculate for algorithms like Q-learning.
  
  I think the lecturer did not mean "equivalent" in the mathematical sense, but in the sense that future lectures will use one of the functions, and a lot of what you will learn is going to be much the same as if you had used a different reward function.
  
  > Finally, when should we use one representation over the other and why are there three representations?
  
  Typically, I don't use any of those representations by default. I tend to use Sutton & Barto's $p(s', r|s, a)$ notation for combined state transitions and rewards. That expression returns probability of transitioning to state $s'$ and receiving reward $r$ when starting in state $s$ and taking action $a$. For discrete actions, you can re-write the expectation of the different functions $R$ in terms of this function as follows:
  
  $$\mathbb{E}[R(s)] = \sum\_{a \in \mathcal{A}(s)}\sum\_{s' \in \mathcal{S}}\sum\_{r \in {R}}rp(s', r|s, a)\qquad\*$$
  
  $$\mathbb{E}[R(s,a)] = \sum\_{s' \in \mathcal{S}}\sum\_{r \in {R}}rp(s', r|s, a)$$
  
  $$\mathbb{E}[R(s,a, s')] = \sum\_{r \in {R}}r\frac{p(s', r|s, a)}{p(s'|s, a)}$$
  
  I think this is one way to see how the functions in the video are closely related.
  
  Which one would you use? Depends on what you are doing. If you want to simplify an equation or code, then use the simplest version of the reward function that fits with the reward scheme you set up for the goals of the problem. For instance, if there is one goal state to exit a maze, and an episode ends as soon as this happens, then you don't care how you got to that state or what the previous state was, and can use $R(s)$
  
  In practice, what happens if you use a different reward function is that you need to pay attention to where it appears in things like the Bellman equation for theoretical treatments. When you get to implement model-free methods like Q-learning, $R(s)$ or its variants don't really appear except in the theory.
  
  ---
  
  \* This is not technically correct in all cases. The assumption I have made is that $R(s)$ is a reward granted at the point of *leaving* state $s$, and is independent of how the state is left and where the agent ends up next.
  
  If this was a fixed reward for *entering* state $s$, regardless of how, then it could be written around $R(s')$ as follows:
  
  $$\mathbb{E}[R(s')] = \sum\_{s \in \mathcal{S}}\sum\_{a \in \mathcal{A}(s)}\sum\_{r \in {R}}rp(s', r|s, a)$$
  
  i.e. by summing all the rewards that end up at $s'$
  
  > **Comments:**
  > **username_0**: Sutton & Barto define $r(s, a, s')$ differently, which does not seem to be equivalent to your definition. See [equation 3.6 of the 2nd edition](http://incompleteideas.net/book/RLbook2020.pdf#page=71). They also use a different notation to denote these reward functions, but it's also true that, in my original question, I also used a notation different than the one in this version of the book (so maybe it's _not_ a good idea to edit your answer to be consistent with the book).  
  > **username_2**: @nbro: As you'd expect Sutton&Barto are right here. I missed that fixing $s'$ means needing to normalise the values. I have fixed it, though I could also expand what $p(s'|s,a)$ is, I think it is fairly clear given other definitions.  
  
  ---
  
  ### Answer by username_1 on 2019-02-07. Score: 5
  
  Let $R(s)$ denote a probability distribution over rewards that our agent may get in some MDP as a reward for entering a state $s$. The easiest case is to demonstrate that we can also choose to write this as $R(s, a)$ or $R(s, a, s')$: simply take $\forall a: R(s, a) = R(s)$, or $\forall a \forall s': R(s, a, s') = R(s)$, as also described in [Neil's answer](https://ai.stackexchange.com/a/10444/1641).
  
  ---
  
  Let $R(s, a)$ denote a probability distribution over rewards that our agent may get as a reward for executing action $a$ in state $s$. The easy case of demonstrating equivalence to $R(s, a, s')$ is already handled above, but can we also construct an MDP in which we only use the $R(s)$ notation?
  
  The easiest way I can think of to do so (may not be the cleanest way) would be to construct a new MDP with a bunch of "dummy" states $z(s, a)$, such that executing action $a$ in state $s$ in the original MDP deterministically leads to a dummy state $z(s, a)$ in the new MDP. Note that I write $z(s, a)$ to make the connection back to the original MDP explicit, but this is a completely independent MDP and you should view it as just a state "$z$".
  
  Then, the reward distribution $R(s, a)$ that was associated with the state-action pair $(s, a)$ in the original MDP can be written as $R(z(s, a))$, which is now only a function of the state in the new MDP. In this dummy state $z(s, a)$ in the new MDP, every possible action $\alpha$ should have exactly the same transition probabilities towards new states $s'$ as the original transition probabilities for executing $a$ in $s$ back in the original MDP. This guarantees that the same policy has the same probabilities of reaching certain states in both MDPs; only in our new MDP the agent is forced to transition through these dummy states in between.
  
  If you also have a discount factor $\gamma$ in the original MDP, I guess you should use a discount factor $\sqrt{\gamma}$ in the new MDP, because every step in the original MDP requires two steps (one step into a dummy state, and one step out of it again) in the new MDP.
  
  ---
  
  The final case for $R(s, a, s')$ could be done in a very similar way, but it would get even more complicated to write out formally. The intuition would be the same though. Above, we pretty much "baked" state-action pairs $(s, a)$ from the original MDP into additional dummy states, such that in the new MDP we have states that "carry the same amount of information" as a full state-action pair in the original MDP. For the $R(s, a, s')$ case, you'd need to devise an even uglier solution with even more information "baked into" dummy states, such that you can treat full $(s, a, s')$ triples as single $z(s, a, s')$ states in the new MDP.
  
  ---
  
  > Finally, when should we use one representation over the other and why are there three representations? I suppose it is because one representation may be more convenient than another in certain cases: which cases? How do you decide which representation to use?
  
  I would recommend always using the **simplest representation** that happens to be **sufficient** to describe how the rewards work in your environment in a natural way.
  
  For example, if you have a two-player zero-sum game where terminal game states give a reward of $-1$, $0$, or $1$ for losses, draws, or wins, it is sufficient to use the $R(s)$ notation; the reward depends on the terminal game state reached, not on how it was reached. Another example would be a maze with a specific goal position, as described in Neil's answer. You could use the more complex $R(s, a)$ or $R(s, a, s')$ notations... but there wouldn't be much of a point in doing so really.
  
  If you have an environment in which the reached state and the played action both have influence on the reward distribution, then it's much more sensible to just use the $R(s, a)$ notation rather than trying to define a massively overcomplicated MDP with dummy states as I've tried to do above. An example would be... let's say we're playing a quizz, where $s$ denotes the current question, and different actions $a$ are different answers that the agent can give. Then it's natural to model the problem as an MDP where $R(s, a)$ is only positive if $a$ is the correct answer to the question $s$.
  
  > **Comments:**
  > **username_0**: I would like to note that $R(s)$, $R(s, a)$ and $R(s, a, s')$ can be intuitively interpreted differently. We can think of $R(s)$ as the reward you obtain for entering, exiting or staying in the state $s$ (no matter what action we take or which next state we may end up in). $R(s, a)$, intuitively, can be thought of as the reward you obtain for taking action $a$ in state $s$. Finally, $R(s, a, s')$ can be thought of as the reward you obtain for taking action $a$ in state $s$ and ending up in state $s'$.  
  > **username_0**: I recall that the environment may be stochastic, so, in general, if we take action $a$ in state $s$, we may not end up always in the same next state, that is, if we take action $a$ in the state $s$ twice, the resulting next state may be different.  
  
  ---
  
  