Answers.Body: <h1>Your examples are equivalent. But it is possible to find a constant yielding  a different optimal policy.</h1>
  <p>Your examples are absolutely equivalent. The agent maximizes the reward, and only way to do so is by reaching <span class="math-container">$s^*$</span>.</p>
  <p>Consider <span class="math-container">$r_3$</span> :</p>
  <p><span class="math-container">$$
  r_3(s, a)=
  \begin{cases}
  1, &amp; \text{ if }  s \neq s^*\\
  2, &amp; \text{ otherwise}
  \end{cases}
  $$</span></p>
  <p>With a sufficiently large <span class="math-container">$\gamma$</span>, moving infinitely without reaching <span class="math-container">$s^*$</span> is now the optimal solution.</p>
  <p>For the generic case</p>
  <p><span class="math-container">$$
  r_4(s, a)=
  \begin{cases}
  \alpha, &amp; \text{ if }  s \neq s^*\\
  \beta, &amp; \text{ otherwise}
  \end{cases}
  $$</span></p>
  <p>the threshold is found by comparing the results of the series <span class="math-container">$\alpha + \alpha^2 + \alpha^3 + ... + \alpha^{t_m}$</span>, where <span class="math-container">$t_m$</span> is the maximum episode length, and <span class="math-container">$\alpha + \alpha^2 + \alpha^3 + ... + \alpha^{t^*}$</span>, where <span class="math-container">$t^*$</span> is the length of the episode following the fastest policy.</p>
  <p>In the example of <span class="math-container">$r_3$</span>, it is trivial to find examples where the fastest policy isn't optimal. Imagine a race, the agent starts on the left and gets either <span class="math-container">$\alpha$</span> or <span class="math-container">$\beta$</span> points, depending on where it is. With <span class="math-container">$\gamma = 0.9$</span> and no time-limit (infinite episodes) the optimal policy is  to move randomly, but in the second-to-last house, avoid the goal state. With <span class="math-container">$\gamma = 0.1$</span>, the optimal policy is to move randomly (not really, probably there would be a slight advantage in moving right), but in the second-to-last house, enter the goal.</p>
  <p><a href="https://i.sstatic.net/JBRyt.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/JBRyt.png" alt="enter image description here" /></a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-05T19:13:32.677Z
Answers.Text: This answer is unclear (to me at least). You say "With a sufficiently large $\gamma$". Why can't that also be said for $r_1$ and $r_2$? $\gamma \in [0, 1)$: this is an assumption. I also don't get your point here "it is trivial to find examples where the fastest policy isn't optimal.". Note that we are talking about "optimal policies" associated with theoretically equivalent reward functions (i.e. theoretically, they have the same optimal policy or policies, which follows from the proof).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-05T19:27:09.640Z
Answers.Text: I think you're assuming that you have some RL algorithm that, _in a finite number of steps_, does not reach the goal and prefers to wander around, given that _seems_ to be optimal policy. And, as someone had already stated in the comments, in practice, these reward functions may lead to different policies, _in a finite number of steps_, with some algorithm like Q-learning. However, your answer is not clear enough.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-05T19:48:04.140Z
Answers.Text: What are these $a$ and $b$ letters in your diagram? It's not even clear what algorithm you're assuming (if any). It's not clear where this conclusion "the optimal policy is to move randomly, but in the second-to-last house, avoid the goal state" comes from too. As far as I am concerned, this answer is not clear. Maybe start from your definition of the optimal Bellman equation and express it in terms of rewards. If that's where you started from, then find the contradiction to (or mistake in) [the proof](https://ai.stackexchange.com/a/24354/2444). Or maybe start by stating your assumpions.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-05T18:51:51.147Z
Answers.LastActivityDate: 2020-11-05T19:37:35.970Z
Answers.LastEditDate: 2020-11-05T19:37:35.970Z
Answers.UserDisplayName: BlueMoon93
Body: <p>If we shift the rewards by any constant (which is a type of reward shaping), the optimal state-action value function (and so optimal policy) does not change. The proof of this fact can be found <a href="https://nbro.gitlab.io/blogging/2020/11/01/optimal-value-function-of-shifted-rewards/" rel="nofollow noreferrer">here</a>.</p>
  <p>If that's the case, then why does a negative reward for every step encourage the agent to quickly reach the goal (which is a specific type of behavior/policy), given that such a reward function has the same optimal policy as the shifted reward function where all rewards are positive (or non-negative)?</p>
  <p>More precisely, let <span class="math-container">$s^*$</span> be the goal state, then consider the following reward function</p>
  <p><span class="math-container">$$
  r_1(s, a)=
  \begin{cases}
  -1, &amp; \text{ if }  s \neq s^*\\
  0, &amp; \text{ otherwise}
  \end{cases}
  $$</span></p>
  <p>This reward function <span class="math-container">$r_1$</span> is supposed to encourage the agent to reach <span class="math-container">$s^*$</span> as quickly as possible, so as to avoid being penalized.</p>
  <p>Let us now define a second reward function as follows</p>
  <p><span class="math-container">\begin{align}
  r_2(s, a) 
  &amp;\triangleq r_1(s, a) + 1\\
  &amp;=
  \begin{cases}
  0, &amp; \text{ if }  s \neq s^*\\
  1, &amp; \text{ otherwise}
  \end{cases}
  \end{align}</span></p>
  <p>This reward function has the same optimal policy as <span class="math-container">$r_1$</span>, but does not incentivize the agent to reach <span class="math-container">$s^*$</span> as quickly as possible, given that the agent does not get penalized for every step. So, in theory, <span class="math-container">$r_1$</span> and <span class="math-container">$r_2$</span> lead to the same behavior. If that's the case, then why do people say that <span class="math-container">$r_1$</span> encourage the agents to reach <span class="math-container">$s^*$</span> as quickly as possible? Is there a proof that shows that <span class="math-container">$r_1$</span> encourages a different type of behaviour than <span class="math-container">$r_2$</span> (and how is that even possible given what I have just said)?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-01T23:37:01.523Z
Comments.Text: I have just found that [a related question](https://ai.stackexchange.com/q/22285/2444) had already been asked, but my question is different, in that I am looking for a proof (or, at least, good logical argument) that shows that $r_1$ and $r_2$ lead to different behaviours, although they shouldn't.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-02T08:24:08.107Z
Comments.Text: The linked proof is not valid for episodic problems. More concretely, it assumes that absorbing states are also modified, but that would break the episodic nature (because reward values other than zero would be processed after the end of an episode)
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-02T09:45:07.030Z
Comments.Text: @NeilSlater Why do you say that it assumes that "absorbing states" are modified? Do you mean that I assumed that the reward for the terminal/absorbing state can also be changed (i.e. be different than zero)? Maybe you should comment under the answer/proof to that linked post, and we can discuss there the limitations of that proof.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-02T13:05:15.573Z
Comments.Text: I think here "quickly" means that the training itself will be faster. If I imagine a gridworld problem for a moment, both $r_1$ and $r_2$ will result in a policy that gives the shortest path to the goal cell. I would say negative rewards encourage exploration and "quickly" means that we converge to the optimal policy quicker.
Comments.UserDisplayName: Hai Nguyen
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-02T13:23:14.293Z
Comments.Text: @HaiNguyen You may be right (i.e. the final policy may be the same, but the way you get to it may be different), but I would like to see a formal proof or, at least, an step-by-step example that shows that's the case. We probably can come up with such an example in a very simple environment with 2-3 states or in simple grid world.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><proofs><reward-shaping><reward-functions>
Title: Why does a negative reward for every step really encourage the agent to reach the goal as quickly as possible?
UserDisplayName: nbro
ThreadText: # Why does a negative reward for every step really encourage the agent to reach the goal as quickly as possible?
  
  (Asked by: username_0 on 2020-11-01)
  
  If we shift the rewards by any constant (which is a type of reward shaping), the optimal state-action value function (and so optimal policy) does not change. The proof of this fact can be found [here](https://username_0.gitlab.io/blogging/2020/11/01/optimal-value-function-of-shifted-rewards/).
  
  If that's the case, then why does a negative reward for every step encourage the agent to quickly reach the goal (which is a specific type of behavior/policy), given that such a reward function has the same optimal policy as the shifted reward function where all rewards are positive (or non-negative)?
  
  More precisely, let $s^\*$ be the goal state, then consider the following reward function
  
  $$
  r\_1(s, a)=
  \begin{cases}
  -1, & \text{ if } s \neq s^\*\\
  0, & \text{ otherwise}
  \end{cases}
  $$
  
  This reward function $r\_1$ is supposed to encourage the agent to reach $s^\*$ as quickly as possible, so as to avoid being penalized.
  
  Let us now define a second reward function as follows
  
  \begin{align}
  r\_2(s, a)
  &\triangleq r\_1(s, a) + 1\\
  &=
  \begin{cases}
  0, & \text{ if } s \neq s^\*\\
  1, & \text{ otherwise}
  \end{cases}
  \end{align}
  
  This reward function has the same optimal policy as $r\_1$, but does not incentivize the agent to reach $s^\*$ as quickly as possible, given that the agent does not get penalized for every step. So, in theory, $r\_1$ and $r\_2$ lead to the same behavior. If that's the case, then why do people say that $r\_1$ encourage the agents to reach $s^\*$ as quickly as possible? Is there a proof that shows that $r\_1$ encourages a different type of behaviour than $r\_2$ (and how is that even possible given what I have just said)?
  
  **Tags:** reinforcement-learning, proofs, reward-shaping, reward-functions
  
  > **Comments:**
  > **username_0**: I have just found that [a related question](https://ai.stackexchange.com/q/22285/2444) had already been asked, but my question is different, in that I am looking for a proof (or, at least, good logical argument) that shows that $r_1$ and $r_2$ lead to different behaviours, although they shouldn't.  
  > **username_1**: The linked proof is not valid for episodic problems. More concretely, it assumes that absorbing states are also modified, but that would break the episodic nature (because reward values other than zero would be processed after the end of an episode)  
  > **username_0**: @username_1 Why do you say that it assumes that "absorbing states" are modified? Do you mean that I assumed that the reward for the terminal/absorbing state can also be changed (i.e. be different than zero)? Maybe you should comment under the answer/proof to that linked post, and we can discuss there the limitations of that proof.  
  > **username_2**: I think here "quickly" means that the training itself will be faster. If I imagine a gridworld problem for a moment, both $r_1$ and $r_2$ will result in a policy that gives the shortest path to the goal cell. I would say negative rewards encourage exploration and "quickly" means that we converge to the optimal policy quicker.  
  > **username_0**: @username_2 You may be right (i.e. the final policy may be the same, but the way you get to it may be different), but I would like to see a formal proof or, at least, an step-by-step example that shows that's the case. We probably can come up with such an example in a very simple environment with 2-3 states or in simple grid world.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2020-11-05. Score: 1
  
  # Your examples are equivalent. But it is possible to find a constant yielding a different optimal policy.
  
  Your examples are absolutely equivalent. The agent maximizes the reward, and only way to do so is by reaching $s^\*$.
  
  Consider $r\_3$ :
  
  $$
  r\_3(s, a)=
  \begin{cases}
  1, & \text{ if } s \neq s^\*\\
  2, & \text{ otherwise}
  \end{cases}
  $$
  
  With a sufficiently large $\gamma$, moving infinitely without reaching $s^\*$ is now the optimal solution.
  
  For the generic case
  
  $$
  r\_4(s, a)=
  \begin{cases}
  \alpha, & \text{ if } s \neq s^\*\\
  \beta, & \text{ otherwise}
  \end{cases}
  $$
  
  the threshold is found by comparing the results of the series $\alpha + \alpha^2 + \alpha^3 + ... + \alpha^{t\_m}$, where $t\_m$ is the maximum episode length, and $\alpha + \alpha^2 + \alpha^3 + ... + \alpha^{t^\*}$, where $t^\*$ is the length of the episode following the fastest policy.
  
  In the example of $r\_3$, it is trivial to find examples where the fastest policy isn't optimal. Imagine a race, the agent starts on the left and gets either $\alpha$ or $\beta$ points, depending on where it is. With $\gamma = 0.9$ and no time-limit (infinite episodes) the optimal policy is to move randomly, but in the second-to-last house, avoid the goal state. With $\gamma = 0.1$, the optimal policy is to move randomly (not really, probably there would be a slight advantage in moving right), but in the second-to-last house, enter the goal.
  
  [![enter image description here](https://i.sstatic.net/JBRyt.png)](https://i.sstatic.net/JBRyt.png)
  
  > **Comments:**
  > **username_0**: This answer is unclear (to me at least). You say "With a sufficiently large $\gamma$". Why can't that also be said for $r_1$ and $r_2$? $\gamma \in [0, 1)$: this is an assumption. I also don't get your point here "it is trivial to find examples where the fastest policy isn't optimal.". Note that we are talking about "optimal policies" associated with theoretically equivalent reward functions (i.e. theoretically, they have the same optimal policy or policies, which follows from the proof).  
  > **username_0**: I think you're assuming that you have some RL algorithm that, _in a finite number of steps_, does not reach the goal and prefers to wander around, given that _seems_ to be optimal policy. And, as someone had already stated in the comments, in practice, these reward functions may lead to different policies, _in a finite number of steps_, with some algorithm like Q-learning. However, your answer is not clear enough.  
  > **username_0**: What are these $a$ and $b$ letters in your diagram? It's not even clear what algorithm you're assuming (if any). It's not clear where this conclusion "the optimal policy is to move randomly, but in the second-to-last house, avoid the goal state" comes from too. As far as I am concerned, this answer is not clear. Maybe start from your definition of the optimal Bellman equation and express it in terms of rewards. If that's where you started from, then find the contradiction to (or mistake in) [the proof](https://ai.stackexchange.com/a/24354/2444). Or maybe start by stating your assumpions.  
  
  ---
  
  