Reward interpolation between MDPs. Will an optimal policy on both ends stay optimal inside the interval?

Question

Say I've got two Markov Decision Processes (MDPs): $$\mathcal{M_0} = (\mathcal{S}, \mathcal{A}, P, R_0),\quad\text{and}\quad\mathcal{M}_1 = (\mathcal{S}, \mathcal{A}, P, R_1)$$ Both have the same set of states and actions, and the transition probabilities are also the same. The only difference is in the reward functions $R_0$ and $R_1$. Suppose that we've found an optimal deterministic policy $\pi^*_0$ for the problem $\mathcal{M}_0$ and we've checked that this policy is also optimal for $\mathcal{M}_1$ $$\pi_0^*(s) = \arg\max\limits_a Q^*_0(s,a)\qquad Q_1^*(s,\pi_0^*(s)) = \max\limits_a Q^*_1(s,a)$$

Now, given the two MDPs one can build a whole family of MDPs interpolating between them: $$\mathcal{M}_\alpha = (\mathcal{S}, \mathcal{A}, P, \alpha R_0 + (1-\alpha) R_1)$$ Where $\alpha\in[0,1]$ is the interpolation parameter between the two problems - the rewards are linearly changing from $R_0$ to $R_1$ with this parameter. My question is - in general. will $\pi_0^*$ be optimal for all MDPs in the middle of interpolation interval?

$$Q_\alpha(s,\pi_0^*(s))\stackrel{?}{=}\max\limits_aQ^*_\alpha(s,a),\; \forall\alpha\in[0,1]$$

I feel like this could be generally true due to linearity of the dependence and convexity of the optimization problem. But I cannot neither prove it, nor find a counterexample.

Answer 1

I believe the claim is true. Here is my attempt at a proof.

Let us consider the optimal infinite horizon value function $V_\alpha^*$ of $\mathcal{M}_\alpha$ at an arbitrary state $s \in S$. The value $V_\alpha^*(s)$ is the expected sum of discounted rewards under an optimal policy $\pi_\alpha^*$, i.e., \begin{equation} V_\alpha^*(s) = \mathbb{E}_{\rho_\alpha}\left[\sum\limits_{t=0}^{\infty}\gamma^t\left( \alpha R_0(s_t,\pi_\alpha^*(s_t)) + (1-\alpha)R_1(s_t, \pi_\alpha^*(s_t)) \right)\middle| s_0 = s, \right], \end{equation} with the expectation taken with respect to the steady state distribution $\rho_\alpha$ of states under $\pi_\alpha^*$. In the following, I drop the condition $s_0=s$ for conciseness, but you can assume it's in each expectation. Now, break up the sum: \begin{equation} V_\alpha^*(s) = \mathbb{E}_{\rho_\alpha}\left[ \alpha\sum\limits_{t=0}^{\infty}\gamma^t R_0(s_t,\pi_\alpha^*(s_t)) + (1-\alpha)\sum\limits_{t=0}^{\infty}\gamma^t R_1(s_t,\pi_\alpha^*(s_t)) \right]. \end{equation} Then, by linearity of expectation: \begin{equation} V_\alpha^*(s) = \alpha\mathbb{E}_{\rho_\alpha}\left[ \sum\limits_{t=0}^{\infty}\gamma^t R_0(s_t,\pi_\alpha^*(s_t)) \right] + (1-\alpha)\mathbb{E}_{\rho_\alpha}\left[ \sum\limits_{t=0}^{\infty}\gamma^t R_1(s_t,\pi_\alpha^*(s_t)) \right]. \end{equation} Note that the first expectation term is the value of $\pi_\alpha^*$ in $\mathcal{M}_0$, and the second expectation term is the value of $\pi_\alpha^*$ in $\mathcal{M}_1$. We already know that $\pi_0^*(s)$ is optimal in $\mathcal{M}_0$ with reward function $R_0$, and $\pi_1^*(s)$ is likewise optimal in $\mathcal{M}_1$ with $R_1$. Further, as per your assumption, $\pi_0^*(s) = \pi_1^*(s)$. So $\pi_\alpha^*$ can be at most as good as $\pi_0^*$ with reward function $R_0$ (resp., with $R_1$): \begin{equation} V_\alpha^*(s) \leq \alpha\mathbb{E}_{\rho_0}\left[ \sum\limits_{t=0}^{\infty}\gamma^t R_0(s_t,\pi_0^*(s_t)) \right] + (1-\alpha)\mathbb{E}_{\rho_0}\left[ \sum\limits_{t=0}^{\infty}\gamma^t R_1(s_t,\pi_0^*(s_t)) \right]. \end{equation} Note that we know take the expectation under the steady state distribution $\rho_0$ of $\pi_0^*$ instead. Thus, we have shown that $V_\alpha^*(s) \leq \alpha V_0^*(s) + (1-\alpha)V_1^*(s)$. Now it remains to argue that the case with a strict less than relation is not possible. Suppose this were the case, and we would have $V_\alpha^*(s) < \alpha V_0^*(s) + (1-\alpha)V_1^*(s)$. But then $\pi_0^*$ would attain a higher value than $\pi_\alpha^*$ in $\mathcal{M}_\alpha$, which is a contradiction (because we assumed that $\pi_\alpha^*$ is an optimal policy for $\mathcal{M}_\alpha$).

Thus, $V_\alpha^*(s) = \alpha V_0^*(s) + (1-\alpha)V_1^*(s)$ and furthermore, acting according to $\pi_0^*$ is optimal also in $\mathcal{M}_\alpha$.