Answers.Body: <p>Yes, in general any linear combination of probability distributions between optimal policies is also an optimal policy. In fact <em>any</em> combination with each state treated separately will also be an optimal policy.</p>
  <p>This can be seen using the equation for optimal deterministic policy in terms of optimal value function:</p>
  <p><span class="math-container">$$\pi^*(s) = \text{argmax}_a [\sum_{r,s'}p(r,s'|s,a)(r + \gamma v^*(s'))] = \text{argmax}_a [q^*(s,a)]$$</span></p>
  <p>The only way to have multiple equivalent optimal policies is when there are two or more actions tied for <span class="math-container">$\text{max}_a [q^*(s,a)]$</span>. If that is the case, then it does not matter - in terms of expected future reward - which of those actions is taken in the affected state. It is possible to take one or the other action.</p>
  <p>You can use any rule you wish to decide which of the tied-for-max actions to take, including a random choice. Creating a new policy that is a linear combination of optimal policies is one way to make that random choice. You could equally say that you would make one action choice on a Monday and another on Tuesday - in terms of being optimal choices it does not matter at all how you break ties.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-18T09:06:01.383Z
Answers.LastActivityDate: 2020-11-18T09:06:01.383Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <h3>Short answer</h3>
  <p>Two policies are different if they take different actions in a specific state <span class="math-container">$s$</span> (or they give different probabilities of taking those actions in <span class="math-container">$s$</span>). There can be more than one optimal policy for a given value function: this only happens when two actions have the same value in a given state. Nevertheless, both policies lead to the same <strong>expected return</strong>. So, although they take different actions, those actions lead to the same <strong>expected return</strong>, so it doesn't matter which one you take: both actions are optimal.</p>
  <h3>Long answer</h3>
  <p>There are a few important points that need to be understood before understanding that an affine combination of optimal policies is also optimal.</p>
  <ul>
  <li><p>A policy <span class="math-container">$\pi$</span> is optimal if and only if <span class="math-container">$v_\pi(s) \geq v_{\pi'}(s)$</span>, for all states <span class="math-container">$s \in S$</span> and <span class="math-container">$\pi' \neq \pi \in \Pi$</span> [<a href="http://incompleteideas.net/book/RLbook2020.pdf#page=84" rel="nofollow noreferrer">1</a>];</p>
  <ul>
  <li><p>In that case, we denote <span class="math-container">$\pi$</span> as <span class="math-container">$\pi_*$</span> and <span class="math-container">$\pi_* = \pi \geq \pi'$</span>, for all <span class="math-container">$\pi' \neq \pi \in \Pi$</span>.</p>
  </li>
  <li><p>In simple words, a policy is optimal if it leads to more or equal <strong>expected return</strong>, in all states, with respect to all other policies</p>
  </li>
  </ul>
  </li>
  <li><p>Optimal policies share the same state and state-action value functions [<a href="http://incompleteideas.net/book/RLbook2020.pdf#page=85" rel="nofollow noreferrer">1</a>, <a href="https://papers.nips.cc/paper/2017/file/453fadbd8a1a3af50a9df4df899537b5-Paper.pdf" rel="nofollow noreferrer">2</a>], i.e. <span class="math-container">$v_*$</span> and <span class="math-container">$q_*$</span>, respectively</p>
  <ul>
  <li>In other words, if <span class="math-container">$\pi_1$</span> and <span class="math-container">$\pi_2$</span> are optimal policies, then <span class="math-container">$v_{\pi_1}(s) = v_{\pi_2}(s) = v_{\pi_*}(s)$</span> and  <span class="math-container">$q_{\pi_1}(s, a) = q_{\pi_2}(s, a) = q_{\pi_*}(s, a)$</span>, for all <span class="math-container">$s \in S$</span> and <span class="math-container">$a \in A$</span></li>
  </ul>
  </li>
  <li><p>Consequently, two optimal policies <span class="math-container">$\pi_1$</span> and <span class="math-container">$\pi_2$</span> can differ in state <span class="math-container">$s$</span> (i.e. <span class="math-container">$\pi_1$</span> takes action <span class="math-container">$a_1$</span> and <span class="math-container">$\pi_2$</span> takes action <span class="math-container">$a_2$</span> and <span class="math-container">$a_1 \neq a_2$</span>) if and only if there exist actions <span class="math-container">$a_1$</span> and <span class="math-container">$a_2$</span> in <span class="math-container">$s$</span> such that
  <span class="math-container">\begin{align}
  v_{*}(s) 
  &amp;= q_{\pi_1}(s, a_1) \\ 
  &amp;= q_{\pi_1}(s, a_2) \\ 
  &amp;= q_{\pi_2}(s, a_2) \\
  &amp;= q_{\pi_2}(s, a_1) \\
  &amp;= \max _{a \in \mathcal{A}(s)} q_{\pi_{*}}(s, a) \\
  &amp;= \max _{a \in \mathcal{A}(s)} q_{\pi_1}(s, a) \\
  &amp;= \max _{a \in \mathcal{A}(s)} q_{\pi_2}(s, a) \tag{1} \label{1}
  \end{align}</span></p>
  </li>
  <li><p>This holds for <a href="https://ai.stackexchange.com/a/12275/2444">deterministic</a> (i.e. policies that always take the same action in a given state, i.e. they give probability <span class="math-container">$1$</span> to one action) and <a href="https://ai.stackexchange.com/a/12275/2444">stochastic</a> (give <strong>non-zero</strong> probability only to <strong>optimal</strong> actions) optimal policies</p>
  </li>
  </ul>
  <p>So, two different optimal policies <span class="math-container">$\pi_1$</span> and <span class="math-container">$\pi_2$</span> lead to the same expected return, for all states. Given that optimality is defined in terms of expected return, then, if <span class="math-container">$a_1 = \pi_1(s) \neq \pi_2(s) = a_2$</span>, for some state <span class="math-container">$s$</span>, then, it doesn't matter whether you take <span class="math-container">$a_1$</span> or <span class="math-container">$a_2$</span>, because both lead to the same expected return. So, as written in <a href="https://ai.stackexchange.com/a/24689/2444">this answer</a>, you can either take action <span class="math-container">$a_1$</span> or <span class="math-container">$a_2$</span>: both are optimal in terms of expected returns and this follows from equation \ref{1} above.</p>
  <blockquote>
  <p>In this simple demo task, we can first derive two different optimal policy <span class="math-container">$\pi_1$</span>, <span class="math-container">$\pi_2$</span>, where <span class="math-container">$\pi_1(a_1|s_0) = 1$</span>, <span class="math-container">$\pi_2(a_2 | s_0) = 1$</span>. The combination of <span class="math-container">$\pi_1$</span> and<span class="math-container">$\pi_2$</span> is
  <span class="math-container">$\pi: \pi(a_1|s_0) = \alpha, \pi(a_2|s_0) = \beta$</span>. <span class="math-container">$\pi$</span> is an optimal policy, too. Because any policy in this task is an optimal policy.</p>
  </blockquote>
  <p>Yes, correct. The reason is simple. In your case, <span class="math-container">$\pi_1$</span> and <span class="math-container">$\pi_2$</span> give probability <span class="math-container">$1$</span> to one action, <span class="math-container">$a_1$</span> and <span class="math-container">$a_2$</span> respectively, so they must give probability <span class="math-container">$0$</span> to any other actions. <span class="math-container">$\pi$</span> will give a probability <span class="math-container">$\alpha$</span> to action <span class="math-container">$a_2$</span> and probability <span class="math-container">$\beta$</span> to action <span class="math-container">$a_1$</span>, but, given that <span class="math-container">$a_1$</span> and <span class="math-container">$a_2$</span> lead to the same expected return (i.e. they are both optimal), it doesn't matter whether you take <span class="math-container">$a_1$</span> or <span class="math-container">$a_2$</span>, even if <span class="math-container">$\alpha \ll \beta$</span> (or vice-versa).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-19T11:04:29.557Z
Answers.Text: @yangliu You're welcome! The only thing I would like to prove (that I didn't in this answer yet) is that _two optimal policies share the state-action value function_ (because, right now and after my last edit, I am only stating it without proving it based on Sutton & Barto's book). I was thinking that maybe two optimal policies with the same state value function could have, in principle, different state-action value functions. If that was the case, then some parts of this answer could not be correct.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-18T12:13:49.753Z
Answers.LastActivityDate: 2020-11-20T14:13:48.603Z
Answers.LastEditDate: 2020-11-20T14:13:48.603Z
Answers.UserDisplayName: nbro
Body: <p>If there are two different optimal policies <span class="math-container">$\pi_1, \pi_2$</span> in a reinforcement learning task, will the linear combination (or <a href="https://en.wikipedia.org/wiki/Affine_combination" rel="nofollow noreferrer">affine combination</a>) of the two policies <span class="math-container">$\alpha \pi_1 + \beta \pi_2, \alpha + \beta = 1$</span> also be an optimal policy?</p>
  <p>Here I give a simple demo:</p>
  <p>In a task, there are three states <span class="math-container">$s_0, s_1, s_2$</span>, where <span class="math-container">$s_1, s_2$</span> are both terminal states. The action space contains two actions <span class="math-container">$a_1, a_2$</span>.</p>
  <p>An agent will start from <span class="math-container">$s_0$</span>, it can choose <span class="math-container">$a_1$</span>, then it will arrive <span class="math-container">$s_1$</span>，and receive a reward of <span class="math-container">$+1$</span>. In <span class="math-container">$s_0$</span>, it can also choose
  <span class="math-container">$a_2$</span>, then it will arrive <span class="math-container">$s_2$</span>, and receive a reward of <span class="math-container">$+1$</span>.</p>
  <p>In this simple demo task, we can first derive two different optimal policy <span class="math-container">$\pi_1$</span>, <span class="math-container">$\pi_2$</span>, where <span class="math-container">$\pi_1(a_1|s_0) = 1$</span>, <span class="math-container">$\pi_2(a_2 | s_0) = 1$</span>. The combination of <span class="math-container">$\pi_1$</span> and<span class="math-container">$\pi_2$</span> is
  <span class="math-container">$\pi: \pi(a_1|s_0) = \alpha, \pi(a_2|s_0) = \beta$</span>. <span class="math-container">$\pi$</span> is an optimal policy, too. Because any policy in this task is an optimal policy.</p>
  
Tags: <reinforcement-learning><proofs><policies><optimal-policy><optimality>
Title: Given two optimal policies, is an affine combination of them also optimal?
UserDisplayName: yang liu
ThreadText: # Given two optimal policies, is an affine combination of them also optimal?
  
  (Asked by: username_0 on 2020-11-18)
  
  If there are two different optimal policies $\pi\_1, \pi\_2$ in a reinforcement learning task, will the linear combination (or [affine combination](https://en.wikipedia.org/wiki/Affine_combination)) of the two policies $\alpha \pi\_1 + \beta \pi\_2, \alpha + \beta = 1$ also be an optimal policy?
  
  Here I give a simple demo:
  
  In a task, there are three states $s\_0, s\_1, s\_2$, where $s\_1, s\_2$ are both terminal states. The action space contains two actions $a\_1, a\_2$.
  
  An agent will start from $s\_0$, it can choose $a\_1$, then it will arrive $s\_1$，and receive a reward of $+1$. In $s\_0$, it can also choose
  $a\_2$, then it will arrive $s\_2$, and receive a reward of $+1$.
  
  In this simple demo task, we can first derive two different optimal policy $\pi\_1$, $\pi\_2$, where $\pi\_1(a\_1|s\_0) = 1$, $\pi\_2(a\_2 | s\_0) = 1$. The combination of $\pi\_1$ and$\pi\_2$ is
  $\pi: \pi(a\_1|s\_0) = \alpha, \pi(a\_2|s\_0) = \beta$. $\pi$ is an optimal policy, too. Because any policy in this task is an optimal policy.
  
  **Tags:** reinforcement-learning, proofs, policies, optimal-policy, optimality
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2020-11-18. Score: 2 | Accepted answer
  
  ### Short answer
  
  Two policies are different if they take different actions in a specific state $s$ (or they give different probabilities of taking those actions in $s$). There can be more than one optimal policy for a given value function: this only happens when two actions have the same value in a given state. Nevertheless, both policies lead to the same **expected return**. So, although they take different actions, those actions lead to the same **expected return**, so it doesn't matter which one you take: both actions are optimal.
  
  ### Long answer
  
  There are a few important points that need to be understood before understanding that an affine combination of optimal policies is also optimal.
  
  * A policy $\pi$ is optimal if and only if $v\_\pi(s) \geq v\_{\pi'}(s)$, for all states $s \in S$ and $\pi' \neq \pi \in \Pi$ [[1](http://incompleteideas.net/book/RLbook2020.pdf#page=84)];
  
    + In that case, we denote $\pi$ as $\pi\_\*$ and $\pi\_\* = \pi \geq \pi'$, for all $\pi' \neq \pi \in \Pi$.
    + In simple words, a policy is optimal if it leads to more or equal **expected return**, in all states, with respect to all other policies
  * Optimal policies share the same state and state-action value functions [[1](http://incompleteideas.net/book/RLbook2020.pdf#page=85), [2](https://papers.nips.cc/paper/2017/file/453fadbd8a1a3af50a9df4df899537b5-Paper.pdf)], i.e. $v\_\*$ and $q\_\*$, respectively
  
    + In other words, if $\pi\_1$ and $\pi\_2$ are optimal policies, then $v\_{\pi\_1}(s) = v\_{\pi\_2}(s) = v\_{\pi\_\*}(s)$ and $q\_{\pi\_1}(s, a) = q\_{\pi\_2}(s, a) = q\_{\pi\_\*}(s, a)$, for all $s \in S$ and $a \in A$
  * Consequently, two optimal policies $\pi\_1$ and $\pi\_2$ can differ in state $s$ (i.e. $\pi\_1$ takes action $a\_1$ and $\pi\_2$ takes action $a\_2$ and $a\_1 \neq a\_2$) if and only if there exist actions $a\_1$ and $a\_2$ in $s$ such that
    \begin{align}
    v\_{\*}(s)
    &= q\_{\pi\_1}(s, a\_1) \\
    &= q\_{\pi\_1}(s, a\_2) \\
    &= q\_{\pi\_2}(s, a\_2) \\
    &= q\_{\pi\_2}(s, a\_1) \\
    &= \max \_{a \in \mathcal{A}(s)} q\_{\pi\_{\*}}(s, a) \\
    &= \max \_{a \in \mathcal{A}(s)} q\_{\pi\_1}(s, a) \\
    &= \max \_{a \in \mathcal{A}(s)} q\_{\pi\_2}(s, a) \tag{1} \label{1}
    \end{align}
  * This holds for [deterministic](https://ai.stackexchange.com/a/12275/2444) (i.e. policies that always take the same action in a given state, i.e. they give probability $1$ to one action) and [stochastic](https://ai.stackexchange.com/a/12275/2444) (give **non-zero** probability only to **optimal** actions) optimal policies
  
  So, two different optimal policies $\pi\_1$ and $\pi\_2$ lead to the same expected return, for all states. Given that optimality is defined in terms of expected return, then, if $a\_1 = \pi\_1(s) \neq \pi\_2(s) = a\_2$, for some state $s$, then, it doesn't matter whether you take $a\_1$ or $a\_2$, because both lead to the same expected return. So, as written in [this answer](https://ai.stackexchange.com/a/24689/2444), you can either take action $a\_1$ or $a\_2$: both are optimal in terms of expected returns and this follows from equation \ref{1} above.
  
  > In this simple demo task, we can first derive two different optimal policy $\pi\_1$, $\pi\_2$, where $\pi\_1(a\_1|s\_0) = 1$, $\pi\_2(a\_2 | s\_0) = 1$. The combination of $\pi\_1$ and$\pi\_2$ is
  > $\pi: \pi(a\_1|s\_0) = \alpha, \pi(a\_2|s\_0) = \beta$. $\pi$ is an optimal policy, too. Because any policy in this task is an optimal policy.
  
  Yes, correct. The reason is simple. In your case, $\pi\_1$ and $\pi\_2$ give probability $1$ to one action, $a\_1$ and $a\_2$ respectively, so they must give probability $0$ to any other actions. $\pi$ will give a probability $\alpha$ to action $a\_2$ and probability $\beta$ to action $a\_1$, but, given that $a\_1$ and $a\_2$ lead to the same expected return (i.e. they are both optimal), it doesn't matter whether you take $a\_1$ or $a\_2$, even if $\alpha \ll \beta$ (or vice-versa).
  
  > **Comments:**
  > **username_2**: @yangliu You're welcome! The only thing I would like to prove (that I didn't in this answer yet) is that _two optimal policies share the state-action value function_ (because, right now and after my last edit, I am only stating it without proving it based on Sutton & Barto's book). I was thinking that maybe two optimal policies with the same state value function could have, in principle, different state-action value functions. If that was the case, then some parts of this answer could not be correct.  
  
  ---
  
  ### Answer by username_1 on 2020-11-18. Score: 2
  
  Yes, in general any linear combination of probability distributions between optimal policies is also an optimal policy. In fact *any* combination with each state treated separately will also be an optimal policy.
  
  This can be seen using the equation for optimal deterministic policy in terms of optimal value function:
  
  $$\pi^\*(s) = \text{argmax}\_a [\sum\_{r,s'}p(r,s'|s,a)(r + \gamma v^\*(s'))] = \text{argmax}\_a [q^\*(s,a)]$$
  
  The only way to have multiple equivalent optimal policies is when there are two or more actions tied for $\text{max}\_a [q^\*(s,a)]$. If that is the case, then it does not matter - in terms of expected future reward - which of those actions is taken in the affected state. It is possible to take one or the other action.
  
  You can use any rule you wish to decide which of the tied-for-max actions to take, including a random choice. Creating a new policy that is a linear combination of optimal policies is one way to make that random choice. You could equally say that you would make one action choice on a Monday and another on Tuesday - in terms of being optimal choices it does not matter at all how you break ties.
  
  
  ---
  
  