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.

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

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$.

  • 1
    $\begingroup$ 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. $\endgroup$
    – Kostya
    May 22 '21 at 20:02
  • $\begingroup$ @Kostya That's a nice way to phrase it, the decomposition of the value function holds for any policy. I am curious how you came about asking this question - I could not think of any practical examples where one might have the property you start with. Any comment? $\endgroup$
    – mikkola
    May 23 '21 at 9:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kostya
    May 23 '21 at 13:48

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.