0
$\begingroup$

Similarly to this question that I asked some time ago, what is the optimal value function of the shifted (by some constant $c$) version of some reward function? More precisely, let's assume that $r(s, a)$ is our original reward function and $q_*(s, a)$ the corresponding optimal state-action value function. What would be the optimal state-action value function of the new reward function $r'(s, a) \triangleq r(s, a) + c$, where $c \in \mathbb{R}$?

$\endgroup$
1
$\begingroup$

Theorem

The optimal state-action value function of $r'(s, a) \triangleq r(s, a) + c$, for $c \in \mathbb{R}$, would be

\begin{align} q_*(s, a) + c + c\gamma + c \gamma^2 + c \gamma^3 + \dots &=q_*(s, a) + c \left( 1 + \gamma + \gamma^2 + \gamma^3 + \dots \right) \\ &= q_*(s, a) + c \left( \sum_{k=0}^{\infty} \gamma^{k} \right) \\ &=q_*(s, a) + c\left(\frac{1}{1 - \gamma}\right) \\ &=q_*(s, a) + \frac{c}{1 - \gamma}, \end{align} where $\gamma < 1$ is the discount factor (and $\sum_{k=0}^{\infty} \gamma^{k}$ is a geometric series).

Therefore, the optimal policy does not change if we shift the reward function by some constant.

Proof

The proof follows the same reasoning of the proof in this answer, i.e. we show that the Bellman optimality equation also holds in this case.

\begin{align} q_*(s,a) + \frac{c}{1 - \gamma} &= \sum_{s' \in \mathcal{S}, r \in \mathcal{R}}p(s',r \mid s,a)\left((r + c) + \gamma \max_{a' \in\mathcal{A}(s')} \left( q_*(s',a') + \frac{c}{1 - \gamma} \right) \right) \tag{1}\label{1} \end{align}

Given that $\frac{c}{1 - \gamma}$ is a constant, it does not affect the max, given that we add this constant to all pairs $(s', a')$, for all $a' \in\mathcal{A}(s')$. This holds even if $c$ is negative. So, we can take that addition out of the max, but note that we sum (rather than multiply, like the proof in the other answer).

\begin{align} q_*(s,a) + \frac{c}{1 - \gamma} &= \sum_{s' \in \mathcal{S}, r \in \mathcal{R}}p(s',r \mid s,a)\left((r + c) + \gamma \left (\frac{c}{1 - \gamma} + \max_{a'\in\mathcal{A}(s')} q_*(s',a') \right) \right) \\ &= \sum_{s' \in \mathcal{S}, r \in \mathcal{R}}p(s',r \mid s,a)\left((r + c) + \frac{c \gamma}{1 - \gamma} + \gamma \max_{a'\in\mathcal{A}(s')} q_*(s',a') \right) \\ &= \sum_{s' \in \mathcal{S}, r \in \mathcal{R}}p(s',r \mid s,a)\left(r + \frac{c(1 - \gamma) + c \gamma}{1 - \gamma} + \gamma \max_{a'\in\mathcal{A}(s')} q_*(s',a') \right) \\ &= \sum_{s' \in \mathcal{S}, r \in \mathcal{R}}p(s',r \mid s,a)\left(r + \frac{c - c\gamma + c \gamma}{1 - \gamma} + \gamma \max_{a'\in\mathcal{A}(s')} q_*(s',a') \right) \\ &= \sum_{s' \in \mathcal{S}, r \in \mathcal{R}} \left ( p(s',r \mid s,a)\frac{c}{1 - \gamma} \right) + \\ & \sum_{s' \in \mathcal{S}, r \in \mathcal{R}} \left( p(s',r \mid s,a) \left(r + \gamma \max_{a'\in\mathcal{A}(s')} q_*(s',a') \right) \right) \tag{2}\label{2} \\ \end{align}

Given that $p(s',r \mid s,a)$ is a probability distribution, then the affine combination of $\frac{c}{1 - \gamma}$, where the affine weights are $p(s',r \mid s,a)$, is $\frac{c}{1 - \gamma}$. To see that this is true, suppose that we have the probability vector $[0.2, 0.5, 0.3]$ and let $c$ be a constant, then $0.2c + 0.5c + 0.3c = c$.

So, equation \ref{2} becomes

\begin{align} q_*(s,a) + \frac{c}{1 - \gamma} &= \frac{c}{1 - \gamma} + \sum_{s' \in \mathcal{S}, r \in \mathcal{R}} p(s',r \mid s,a) \left(r + \gamma \max_{a'\in\mathcal{A}(s')} q_*(s',a') \right)\\ q_*(s,a) &=\sum_{s' \in \mathcal{S}, r \in \mathcal{R}} p(s',r \mid s,a) \left(r + \gamma \max_{a'\in\mathcal{A}(s')} q_*(s',a') \right) \end{align} which is the Bellman optimality equation (see equation 3.20 of Sutton & Barto book, p. 64).

$\endgroup$
  • $\begingroup$ To make the proof even clearer, I should probably use a different version of the Bellman optimality equation that uses $r(s, a)$ directly (rather than $r$) or maybe formulate the question differently, but note that $r(s, a)$ can be expressed as a function of $p(s', r \mid r, a)$ as follows $r(s, a) = \sum_{r \in \mathcal{R}}r \sum_{s' \in \mathcal{S}}p(s', r \mid r, a)$. $\endgroup$ – nbro Nov 1 '20 at 0:43
  • $\begingroup$ I've just found out that this question is also asked in exercise 3.15 of the 2nd edition of Sutton & Barto's book (p. 61) and exercise 3.10 of the 1st edition of the same book, but they restrict themselves to the grid world. I'm trying to understand why. Moreover, the successive exercise (to the just mentioned exercises) asks about the episodic case. $\endgroup$ – nbro Nov 18 '20 at 21:22

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.