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

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.

• You may want to have a look at this paper if you haven't yet.
– nbro
May 21, 2021 at 23:21

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., $$$$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],$$$$ 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: $$$$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].$$$$ Then, by linearity of expectation: $$$$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].$$$$ 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$$): $$$$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].$$$$ 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$$.
• Essentially you've proven $\forall \pi. V_\alpha^\pi = \alpha V_0^\pi + ( 1 - \alpha )V_1^\pi$ and then $\forall \pi. V_\alpha^\pi \leq \alpha V_0^{\pi_0^*} + ( 1 - \alpha )V_1^{\pi_0^*} = V_\alpha^{\pi_0^*}$. This makes sense. Thank you for looking into it. May 22, 2021 at 20:02
• Imagine you need to be able to quickly solve MDPs that differ only by $R$. E.g. a user set up his $R$ and wants the optimal policy. The statement shows the convexity of this kind of task: inputs inside the convex hull of previous equal solutions evaluated instantly to the same solution. May 23, 2021 at 13:48