6
$\begingroup$

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.

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

$\endgroup$
  • $\begingroup$ I have just found that a related question 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. $\endgroup$ – nbro Nov 1 '20 at 23:37
  • 1
    $\begingroup$ 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) $\endgroup$ – Neil Slater Nov 2 '20 at 8:24
  • $\begingroup$ @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. $\endgroup$ – nbro Nov 2 '20 at 9:45
  • $\begingroup$ 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. $\endgroup$ – Hai Nguyen Nov 2 '20 at 13:05
  • $\begingroup$ @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. $\endgroup$ – nbro Nov 2 '20 at 13:23
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – nbro Nov 5 '20 at 19:13
  • $\begingroup$ 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. $\endgroup$ – nbro Nov 5 '20 at 19:27
  • $\begingroup$ 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. Or maybe start by stating your assumpions. $\endgroup$ – nbro Nov 5 '20 at 19:48

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.