2
$\begingroup$

Consider the reward function $r(s, a)$ with optimal state-action value function $q_*(s, a)$. What would be the optimal state-action value function of $c r(s, a)$, for $c \in \mathbb{R}$? Would it be $c q_*(s, a)$?

$\endgroup$
2
$\begingroup$

The Bellman optimality equation is given by

$$q_*(s,a) = \sum_{s' \in \mathcal{S}, r \in \mathcal{R}}p(s',r \mid s,a)(r + \gamma \max_{a'\in\mathcal{A}(s')}q_*(s',a')) \tag{1}\label{1}.$$

If the reward is multiplied by a constant $c > 0 \in \mathbb{R}$, then the new optimal action-value function is given by $cq_*(s, a)$.

To prove this, we just need to show that equation \ref{1} holds when the reward is $cr$ and the action-value is $c q_*(s, a)$.

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

Given that $c > 0$, then $\max_{a'\in\mathcal{A}(s')} c q_*(s',a') = c\max_{a'\in\mathcal{A}(s')}q_*(s',a')$, so $c$ can be taken out of the $\operatorname{max}$ operator. Therefore, the equation \ref{2} becomes

\begin{align} c q_*(s,a) &= \sum_{s' \in \mathcal{S}, r \in \mathcal{R}}p(s',r \mid s,a)(c r + \gamma c \max_{a'\in\mathcal{A}(s')} q_*(s',a')) \\ &= \sum_{s' \in \mathcal{S}, r \in \mathcal{R}}c p(s',r \mid s,a)(r + \gamma \max_{a'\in\mathcal{A}(s')} q_*(s',a')) \\ &= c \sum_{s' \in \mathcal{S}, r \in \mathcal{R}} p(s',r \mid s,a)(r + \gamma \max_{a'\in\mathcal{A}(s')} q_*(s',a')) \\ q_*(s,a) &= \sum_{s' \in \mathcal{S}, r \in \mathcal{R}} p(s',r \mid s,a)(r + \gamma \max_{a'\in\mathcal{A}(s')} q_*(s',a')) \tag{3}\label{3} \end{align} which is equal to the the Bellman optimality in \ref{1}, which implies that, when the reward is given by $cr$, $c q_*(s,a)$ is the solution to the Bellman optimality equation. Consequently, in this case, the set of optimal policies does not change.

If $c=0$, then \ref{2} becomes $0=0$, which is true.

If $c < 0$, then $\max_{a'\in\mathcal{A}(s')} c q_*(s',a') = c\min_{a'\in\mathcal{A}(s')}q_*(s',a')$, so equation \ref{3} becomes

\begin{align} q_*(s,a) &= \sum_{s' \in \mathcal{S}, r \in \mathcal{R}} p(s',r \mid s,a)(r + \gamma \min_{a'\in\mathcal{A}(s')} q_*(s',a')) \end{align}

which is not equal to the Bellman optimality equation in \ref{1}.

$\endgroup$

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.