Is the policy really invariant under affine transformations of the reward function?

In the context of a Markov decision process, this paper 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 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?

• Here and here are 2 related/similar questions.
– nbro
Oct 5 '21 at 16:56

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.

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.

• 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}$.
– nbro
Dec 14 '21 at 19:11

Neil answer is wrong, Dylan 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 Dylan'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 :)
• 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). Dec 14 '21 at 16:35
• @NeilSlater Optimal policies are invariant under affine transformations of the reward function (here). This is widely known in RL. 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.
– nbro
Dec 14 '21 at 17:45
• I had asked a similar question in the past here (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.
– nbro
Dec 14 '21 at 17:53
• @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. Dec 14 '21 at 18:47
• @NeilSlater Ng's famous paper assumes that we have an absorbing state (after which no reward is given) for undiscounted MDPs.
– nbro
Dec 14 '21 at 18:53