Answers.Body: <p>This statement:</p>
  <blockquote>
  <p>(it is well-known that the optimal policy is invariant to positive affine transformation of the reward function).</p>
  </blockquote>
  <p>is, as far as I know, and as you summarise, incorrect* because simple translations to reward signal do affect the optimal policy, and the affine transform of a real number <span class="math-container">$x$</span> can be given by <span class="math-container">$f(x) = mx + c$</span></p>
  <p>It <em>is</em> well known that optimal policy is unaffected by multiplying all rewards by a positive scaling, e.g. <span class="math-container">$f(x) = mx$</span> where <span class="math-container">$m$</span> is positive.</p>
  <p>It is also worth noting that if an optimal policy is derived from Q values using <span class="math-container">$\pi(s) = \text{argmax}_a Q(s,a)$</span>, then that policy function <em>is</em> invariant to positive affine transformations of <em>action values</em> given by <span class="math-container">$Q(s,a)$</span>. Perhaps that was what the paper authors meant to write, given that they go on to apply normalisation to Q values.</p>
  <p>The impact of the mistake is not relevant to the the rest of the paper as far as I can see (caveat: I have not read the whole paper).</p>
  <hr />
  <p>* It is possible to make the statement correct even for episodic problems, <em>if</em>:</p>
  <ul>
  <li><p>You model episodic problems with an &quot;absorbing state&quot; and treat it as a continuing problem.</p>
  </li>
  <li><p>You apply the same affine transform to the (usually zero reward) absorbing state.</p>
  </li>
  <li><p>You still account for the infinite repeats of the absorbing state (requiring a value of discount factor <span class="math-container">$\gamma$</span> less than one). In practice this means either granting an additional reward of <span class="math-container">$\frac{b}{1-\gamma}$</span> for ending the episode, or not ending a simulation in the terminal state, but running learning algorithms over repeated time steps whilst still in the terminal state, so they can collect the non-zero reward.</p>
  </li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-17T09:11:38.080Z
Answers.Text: Can you kindly add the proof?
Answers.UserDisplayName: Nathan G
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-17T11:28:25.850Z
Answers.Text: @NathanG proof of which statement? Maybe I can add it or link one. If it is specific nature of proof you are looking for, a new question may be better
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-03T07:25:38.090Z
Answers.LastActivityDate: 2021-12-14T19:25:16.503Z
Answers.LastEditDate: 2021-12-14T19:25:16.503Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>In framing the problem as an <em>episodic</em> reinforcement learning problem, the goal is to find a policy that optimizes <span class="math-container">$\mathbb{E}[\sum_{t=0}^\tau r(s_t)],$</span> where <span class="math-container">$\tau$</span> is the random time at which the robot leaves the maze. This implicitly assigns a reward of 0 to the out-of-maze state, <span class="math-container">$s_{terminal}$</span>. If you include this state then the transformation <span class="math-container">$r\rightarrow 1\cdot r - 1$</span> does not change the optimal policy.</p>
  <p>If we rewrite this episodic objective accounting for <span class="math-container">$s_{terminal}$</span> (and a horizon <span class="math-container">$H$</span>) we get the following objective:
  <span class="math-container">\begin{align*}\mathbb{E}\left[\sum_{t=0}^\tau r(s_t) + \sum_{\tau}^H r(s_{terminal})\right] &amp;= \mathbb{E}\left[(H-\tau) r(s_{terminal}) + \sum_{t=0}^\tau r(s_t)\right]\\
  &amp;= \mathbb{E}\left[(H-\tau) r(s_{terminal}) + r(s_{goal}) + (\tau-1) r(s_{maze}) \right]\end{align*}</span></p>
  <p>Where <span class="math-container">$s_{goal}$</span> is the exit state from the maze, the goal, and <span class="math-container">$s_{maze}$</span> represents the other states of the maze. In the question, 1 is subtracted from <span class="math-container">$s_{goal}$</span> and <span class="math-container">$s_{maze}$</span>, but not <span class="math-container">$s_{terminal}$</span>. Thus, this is not a positive affine transformation of the reward function. In effect, this changes the relative value of <span class="math-container">$s_{terminal}$</span> from <span class="math-container">$\min_s r(s)$</span> to <span class="math-container">$\max_s r(s)$</span>, and that changes the optimal policy.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-14T19:11:03.213Z
Answers.Text: It's been a while since you provided this answer, but, in the second case, it seems that you assume that the rewards are equal for all maze states but $s_\text{goal}$.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-07T18:06:48.280Z
Answers.LastActivityDate: 2020-08-07T18:06:48.280Z
Answers.UserDisplayName: Dylan Hadfield-Menell
Answers.Body: <p><strong>Neil answer is wrong</strong>, <strong>Dylan gives the correct one</strong>!</p>
  <p>Optimal policies are invariant under positive affine transformations of the reward function. and the reason why it's not the case in your example is explained in Dylan's answer.</p>
  <p>Reference:
  From the book <strong>Artificial intelligence a modern approach 4th edition 16.1.3</strong></p>
  <p>&quot;<em>the scale of utilities is arbitrary: an affine transformation leaves the optimal decision unchanged. We can replace U(s) by U'(s) = m U(s)+ b where m and b are any constants such that m &gt; 0. It is easy to see, from the definition of utilities as discounted sums of rewards, that a similar transformation of rewards will leave the optimal policy unchanged
  in an MDP</em>&quot;</p>
  <p>** Edit:</p>
  <ul>
  <li>Since the answer has been updated, the answer is fully correct now :)</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-14T16:35:58.503Z
Answers.Text: The book is incorrect. I can easily construct an episodic MDP where there is a huge difference between receiving +1 reward per time step instead of -1 when determining the optimal policy (it doesn't matter whether b is constrained because you can simply start the other side of 0 for the comparison).
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-14T17:45:21.170Z
Answers.Text: @NeilSlater Optimal policies are invariant under affine transformations of the reward function ([here](https://ai.stackexchange.com/q/24353/2444)). [This is widely known in RL](https://people.eecs.berkeley.edu/~pabbeel/cs287-fa09/readings/NgHaradaRussell-shaping-ICML1999.pdf). Under which conditions this is true, right now, I don't remember, I need to read that paper again. Anyway, this does not mean, however, that certain reward functions are not more efficient than others in practice, given certain initializations of the value functions. That's why we have reward shaping too.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-14T17:53:13.940Z
Answers.Text: I had asked a similar question in the past (as you maybe remember). I still didn't find a convincing answer to that question and I didn't take the time to think about it more, but I think we can find a good answer to this question.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-14T18:47:07.297Z
Answers.Text: @nbro: It's true for non-episodic environments and positive $m$ in $r' = mr + b$. Not true in general for all MDPs, specifically not true for episodic problems, which applies to the OP's environment.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-14T18:53:19.923Z
Answers.Text: @NeilSlater Ng's famous paper assumes that we have an absorbing state (after which no reward is given) for undiscounted MDPs.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-14T19:00:24.027Z
Answers.Text: @nbro: You also have to transform the absorbing state to make it work, and solve the infinite series using $\gamma$ - adding a "lump sum" at the end of an episode. Which is not too hard I suppose, but really needs to be called out in any answer. It's definitely not a "natural" part of the affine transform. Also, it forces discounting into episodic environments.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-14T19:26:59.710Z
Answers.Text: I have updated my answer to make this assumption more explicit. I think it is reasonable, but there's quite a lot of assumed detail not originally in the question, so differences in the answers boil down to differing definitions of MDPs, and what it means for an MDP to be episodic
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-14T14:51:28.263Z
Answers.LastActivityDate: 2021-12-26T13:18:22.897Z
Answers.LastEditDate: 2021-12-26T13:18:22.897Z
Answers.UserDisplayName: Yacine Ben Ameur
Body: <p>In the context of a Markov decision process, <a href="https://arxiv.org/pdf/1902.09725.pdf" rel="nofollow noreferrer">this paper</a> says</p>
  <blockquote>
  <p>it is well-known that the optimal policy is invariant to positive affine transformation of the reward function</p>
  </blockquote>
  <p>On the other hand, exercise 3.7 of <a href="http://incompleteideas.net/book/the-book-2nd.html" rel="nofollow noreferrer">Sutton and Barto</a> gives an example of a robot in a maze:</p>
  <blockquote>
  <p>Imagine that you are designing a robot to run a maze. You decide to give it a reward of +1 for escaping from the maze and a reward of zero at all other times. The task seems to break down naturally into episodes—the successive runs through the maze—so you decide to treat it as an episodic task, where the goal is to maximize expected total reward (3.7). After running the learning agent for a while, you find that it is showing no improvement in escaping from the maze. What is going wrong? Have you effectively communicated to the agent what you want it to achieve?</p>
  </blockquote>
  <p>It seems like the robot is not being rewarded for escaping quickly (escaping in 10 seconds gives it just as much reward as escaping in 1000 seconds). One fix seems to be to subtract 1 from each reward, so that each timestep the robot stays in the maze, it accumulates <span class="math-container">$-1$</span> in reward, and upon escape it gets zero reward. This seems to change the set of optimal policies (now there are way fewer policies which achieve the best possible return). In other words, a positive affine transformation <span class="math-container">$r \mapsto 1 \cdot r - 1$</span> seems to have changed the optimal policy.</p>
  <p>How can I reconcile &quot;the optimal policy is invariant to positive affine transformation of the reward function&quot; with the maze example?</p>
  
Tags: <reinforcement-learning><markov-decision-process><policies><reward-functions><reward-shaping>
Title: Is the policy really invariant under affine transformations of the reward function?
UserDisplayName: IssaRice
ThreadText: # Is the policy really invariant under affine transformations of the reward function?
  
  (Asked by: username_0 on 2020-03-03)
  
  In the context of a Markov decision process, [this paper](https://arxiv.org/pdf/1902.09725.pdf) says
  
  > it is well-known that the optimal policy is invariant to positive affine transformation of the reward function
  
  On the other hand, exercise 3.7 of [Sutton and Barto](http://incompleteideas.net/book/the-book-2nd.html) gives an example of a robot in a maze:
  
  > Imagine that you are designing a robot to run a maze. You decide to give it a reward of +1 for escaping from the maze and a reward of zero at all other times. The task seems to break down naturally into episodes—the successive runs through the maze—so you decide to treat it as an episodic task, where the goal is to maximize expected total reward (3.7). After running the learning agent for a while, you find that it is showing no improvement in escaping from the maze. What is going wrong? Have you effectively communicated to the agent what you want it to achieve?
  
  It seems like the robot is not being rewarded for escaping quickly (escaping in 10 seconds gives it just as much reward as escaping in 1000 seconds). One fix seems to be to subtract 1 from each reward, so that each timestep the robot stays in the maze, it accumulates $-1$ in reward, and upon escape it gets zero reward. This seems to change the set of optimal policies (now there are way fewer policies which achieve the best possible return). In other words, a positive affine transformation $r \mapsto 1 \cdot r - 1$ seems to have changed the optimal policy.
  
  How can I reconcile "the optimal policy is invariant to positive affine transformation of the reward function" with the maze example?
  
  **Tags:** reinforcement-learning, markov-decision-process, policies, reward-functions, reward-shaping
  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2020-03-03. Score: 2
  
  This statement:
  
  > (it is well-known that the optimal policy is invariant to positive affine transformation of the reward function).
  
  is, as far as I know, and as you summarise, incorrect\* because simple translations to reward signal do affect the optimal policy, and the affine transform of a real number $x$ can be given by $f(x) = mx + c$
  
  It *is* well known that optimal policy is unaffected by multiplying all rewards by a positive scaling, e.g. $f(x) = mx$ where $m$ is positive.
  
  It is also worth noting that if an optimal policy is derived from Q values using $\pi(s) = \text{argmax}\_a Q(s,a)$, then that policy function *is* invariant to positive affine transformations of *action values* given by $Q(s,a)$. Perhaps that was what the paper authors meant to write, given that they go on to apply normalisation to Q values.
  
  The impact of the mistake is not relevant to the the rest of the paper as far as I can see (caveat: I have not read the whole paper).
  
  ---
  
  \* It is possible to make the statement correct even for episodic problems, *if*:
  
  * You model episodic problems with an "absorbing state" and treat it as a continuing problem.
  * You apply the same affine transform to the (usually zero reward) absorbing state.
  * You still account for the infinite repeats of the absorbing state (requiring a value of discount factor $\gamma$ less than one). In practice this means either granting an additional reward of $\frac{b}{1-\gamma}$ for ending the episode, or not ending a simulation in the terminal state, but running learning algorithms over repeated time steps whilst still in the terminal state, so they can collect the non-zero reward.
  
  > **Comments:**
  > **username_2**: Can you kindly add the proof?  
  > **username_1**: @username_2 proof of which statement? Maybe I can add it or link one. If it is specific nature of proof you are looking for, a new question may be better  
  
  ---
  
  ### Answer by username_3 on 2020-08-07. Score: 1
  
  In framing the problem as an *episodic* reinforcement learning problem, the goal is to find a policy that optimizes $\mathbb{E}[\sum\_{t=0}^\tau r(s\_t)],$ where $\tau$ is the random time at which the robot leaves the maze. This implicitly assigns a reward of 0 to the out-of-maze state, $s\_{terminal}$. If you include this state then the transformation $r\rightarrow 1\cdot r - 1$ does not change the optimal policy.
  
  If we rewrite this episodic objective accounting for $s\_{terminal}$ (and a horizon $H$) we get the following objective:
  \begin{align\*}\mathbb{E}\left[\sum\_{t=0}^\tau r(s\_t) + \sum\_{\tau}^H r(s\_{terminal})\right] &= \mathbb{E}\left[(H-\tau) r(s\_{terminal}) + \sum\_{t=0}^\tau r(s\_t)\right]\\
  &= \mathbb{E}\left[(H-\tau) r(s\_{terminal}) + r(s\_{goal}) + (\tau-1) r(s\_{maze}) \right]\end{align\*}
  
  Where $s\_{goal}$ is the exit state from the maze, the goal, and $s\_{maze}$ represents the other states of the maze. In the question, 1 is subtracted from $s\_{goal}$ and $s\_{maze}$, but not $s\_{terminal}$. Thus, this is not a positive affine transformation of the reward function. In effect, this changes the relative value of $s\_{terminal}$ from $\min\_s r(s)$ to $\max\_s r(s)$, and that changes the optimal policy.
  
  > **Comments:**
  > **username_4**: It's been a while since you provided this answer, but, in the second case, it seems that you assume that the rewards are equal for all maze states but $s_\text{goal}$.  
  
  ---
  
  ### Answer by username_5 on 2021-12-14. Score: -1
  
  **username_1 answer is wrong**, **username_3 gives the correct one**!
  
  Optimal policies are invariant under positive affine transformations of the reward function. and the reason why it's not the case in your example is explained in username_3's answer.
  
  Reference:
  From the book **Artificial intelligence a modern approach 4th edition 16.1.3**
  
  "*the scale of utilities is arbitrary: an affine transformation leaves the optimal decision unchanged. We can replace U(s) by U'(s) = m U(s)+ b where m and b are any constants such that m > 0. It is easy to see, from the definition of utilities as discounted sums of rewards, that a similar transformation of rewards will leave the optimal policy unchanged
  in an MDP*"
  
  \*\* Edit:
  
  * Since the answer has been updated, the answer is fully correct now :)
  
  > **Comments:**
  > **username_1**: The book is incorrect. I can easily construct an episodic MDP where there is a huge difference between receiving +1 reward per time step instead of -1 when determining the optimal policy (it doesn't matter whether b is constrained because you can simply start the other side of 0 for the comparison).  
  > **username_4**: @username_1 Optimal policies are invariant under affine transformations of the reward function ([here](https://ai.stackexchange.com/q/24353/2444)). [This is widely known in RL](https://people.eecs.berkeley.edu/~pabbeel/cs287-fa09/readings/NgHaradaRussell-shaping-ICML1999.pdf). Under which conditions this is true, right now, I don't remember, I need to read that paper again. Anyway, this does not mean, however, that certain reward functions are not more efficient than others in practice, given certain initializations of the value functions. That's why we have reward shaping too.  
  > **username_4**: I had asked a similar question in the past (as you maybe remember). I still didn't find a convincing answer to that question and I didn't take the time to think about it more, but I think we can find a good answer to this question.  
  > **username_1**: @username_4: It's true for non-episodic environments and positive $m$ in $r' = mr + b$. Not true in general for all MDPs, specifically not true for episodic problems, which applies to the OP's environment.  
  > **username_4**: @username_1 Ng's famous paper assumes that we have an absorbing state (after which no reward is given) for undiscounted MDPs.  
  > **username_1**: @username_4: You also have to transform the absorbing state to make it work, and solve the infinite series using $\gamma$ - adding a "lump sum" at the end of an episode. Which is not too hard I suppose, but really needs to be called out in any answer. It's definitely not a "natural" part of the affine transform. Also, it forces discounting into episodic environments.  
  > **username_1**: I have updated my answer to make this assumption more explicit. I think it is reasonable, but there's quite a lot of assumed detail not originally in the question, so differences in the answers boil down to differing definitions of MDPs, and what it means for an MDP to be episodic  
  
  ---
  
  