6
$\begingroup$

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.

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

1 Answer 1

4
$\begingroup$

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

$\endgroup$
3
  • 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
    Commented May 22, 2021 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
    Commented May 23, 2021 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
    Commented May 23, 2021 at 13:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .