Given two optimal policies, is an affine combination of them also optimal?

Question

If there are two different optimal policies $\pi_1, \pi_2$ in a reinforcement learning task, will the linear combination (or 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.

Answer 1

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];

  • 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, 2], 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 (i.e. policies that always take the same action in a given state, i.e. they give probability $1$ to one action) and stochastic (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, 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).

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