Answers.Body: <p>I believe the claim is true. Here is my attempt at a proof.</p>
  <p>Let us consider the optimal infinite horizon value function <span class="math-container">$V_\alpha^*$</span> of <span class="math-container">$\mathcal{M}_\alpha$</span> at an arbitrary state <span class="math-container">$s \in S$</span>.
  The value <span class="math-container">$V_\alpha^*(s)$</span> is the expected sum of discounted rewards under an optimal policy <span class="math-container">$\pi_\alpha^*$</span>, i.e.,
  <span class="math-container">\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}</span>
  with the expectation taken with respect to the steady state distribution <span class="math-container">$\rho_\alpha$</span> of states under <span class="math-container">$\pi_\alpha^*$</span>.
  In the following, I drop the condition <span class="math-container">$s_0=s$</span> for conciseness, but you can assume it's in each expectation.
  Now, break up the sum:
  <span class="math-container">\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}</span>
  Then, by linearity of expectation:
  <span class="math-container">\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}</span>
  Note that the first expectation term is the value of <span class="math-container">$\pi_\alpha^*$</span> in <span class="math-container">$\mathcal{M}_0$</span>, and the second expectation term is the value of <span class="math-container">$\pi_\alpha^*$</span> in <span class="math-container">$\mathcal{M}_1$</span>.
  We already know that <span class="math-container">$\pi_0^*(s)$</span> is optimal in <span class="math-container">$\mathcal{M}_0$</span> with reward function <span class="math-container">$R_0$</span>, and <span class="math-container">$\pi_1^*(s)$</span> is likewise optimal in <span class="math-container">$\mathcal{M}_1$</span> with <span class="math-container">$R_1$</span>. Further, as per your assumption, <span class="math-container">$\pi_0^*(s) = \pi_1^*(s)$</span>.
  So <span class="math-container">$\pi_\alpha^*$</span> can be at most as good as <span class="math-container">$\pi_0^*$</span> with reward function <span class="math-container">$R_0$</span> (resp., with <span class="math-container">$R_1$</span>):
  <span class="math-container">\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}</span>
  Note that we know take the expectation under the steady state distribution <span class="math-container">$\rho_0$</span> of <span class="math-container">$\pi_0^*$</span> instead.
  Thus, we have shown that <span class="math-container">$V_\alpha^*(s) \leq \alpha V_0^*(s) + (1-\alpha)V_1^*(s)$</span>.
  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 <span class="math-container">$V_\alpha^*(s) &lt; \alpha V_0^*(s) + (1-\alpha)V_1^*(s)$</span>.
  But then <span class="math-container">$\pi_0^*$</span> would attain a higher value than <span class="math-container">$\pi_\alpha^*$</span> in <span class="math-container">$\mathcal{M}_\alpha$</span>, which is a contradiction (because we assumed that <span class="math-container">$\pi_\alpha^*$</span> is an optimal policy for <span class="math-container">$\mathcal{M}_\alpha$</span>).</p>
  <p>Thus, <span class="math-container">$V_\alpha^*(s) = \alpha V_0^*(s) + (1-\alpha)V_1^*(s)$</span> and furthermore, acting according to <span class="math-container">$\pi_0^*$</span> is optimal also in <span class="math-container">$\mathcal{M}_\alpha$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-22T20:02:07.490Z
Answers.Text: 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.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-23T09:53:47.933Z
Answers.Text: @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?
Answers.UserDisplayName: mikkola
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-23T13:48:38.097Z
Answers.Text: 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.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-22T09:52:29.153Z
Answers.LastActivityDate: 2021-05-22T10:00:28.820Z
Answers.LastEditDate: 2021-05-22T10:00:28.820Z
Answers.UserDisplayName: mikkola
Body: <p>Say I've got two Markov Decision Processes (MDPs):
  <span class="math-container">$$\mathcal{M_0} = (\mathcal{S}, \mathcal{A}, P, R_0),\quad\text{and}\quad\mathcal{M}_1 = (\mathcal{S}, \mathcal{A}, P, R_1)$$</span>
  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 <span class="math-container">$R_0$</span> and <span class="math-container">$R_1$</span>. Suppose that we've found an optimal deterministic policy <span class="math-container">$\pi^*_0$</span> for the problem <span class="math-container">$\mathcal{M}_0$</span> and we've checked that this policy is also optimal for <span class="math-container">$\mathcal{M}_1$</span>
  <span class="math-container">$$\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)$$</span></p>
  <p>Now, given the two MDPs one can build a whole family of MDPs interpolating between them:
  <span class="math-container">$$\mathcal{M}_\alpha = (\mathcal{S}, \mathcal{A}, P, \alpha R_0 + (1-\alpha) R_1)$$</span>
  Where <span class="math-container">$\alpha\in[0,1]$</span> is the interpolation parameter between the two problems - the rewards are linearly changing from <span class="math-container">$R_0$</span> to <span class="math-container">$R_1$</span> with this parameter. My question is - in general. will <span class="math-container">$\pi_0^*$</span> be optimal for all MDPs in the middle of interpolation interval?</p>
  <p><span class="math-container">$$Q_\alpha(s,\pi_0^*(s))\stackrel{?}{=}\max\limits_aQ^*_\alpha(s,a),\; \forall\alpha\in[0,1]$$</span></p>
  <p>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.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-21T23:21:49.177Z
Comments.Text: You may want to have a look at [this paper](https://people.eecs.berkeley.edu/~pabbeel/cs287-fa09/readings/NgHaradaRussell-shaping-ICML1999.pdf) if you haven't yet.
Comments.UserDisplayName: nbro
Tags: <markov-decision-process><rewards><reward-shaping><interpolation>
Title: Reward interpolation between MDPs. Will an optimal policy on both ends stay optimal inside the interval?
UserDisplayName: Kostya
ThreadText: # Reward interpolation between MDPs. Will an optimal policy on both ends stay optimal inside the interval?
  
  (Asked by: username_0 on 2021-05-21)
  
  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.
  
  **Tags:** markov-decision-process, rewards, reward-shaping, interpolation
  > **Comments:**
  > **username_1**: You may want to have a look at [this paper](https://people.eecs.berkeley.edu/~pabbeel/cs287-fa09/readings/NgHaradaRussell-shaping-ICML1999.pdf) if you haven't yet.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-05-22. Score: 4 | Accepted answer
  
  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$.
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_2**: @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?  
  > **username_0**: 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.  
  
  ---
  
  