Why is there always at least one policy that is better than or equal to all other policies?

Question

Reinforcement Learning: An Introduction. Second edition, in progress., Richard S. Sutton and Andrew G. Barto (c) 2012, pp. 67-68.

Solving a reinforcement learning task means, roughly, finding a policy that achieves a lot of reward over the long run. For finite MDPs, we can precisely define an optimal policy in the following way. Value functions define a partial ordering over policies. A policy $\pi$ is defined to be better than or equal to a policy $\pi'$ if its expected return is greater than or equal to that of $\pi'$, for all states. In other words, $\pi \geq \pi'$ if and only if $v_\pi(s) \geq v_{\pi'}(s)$, for all $s \in \mathcal{S}$. There is always at least one policy that is better than or equal to all other policies. This is an optimal policy.

Why is there always at least one policy that is better than or equal to all other policies?

Answer 1

Just past the quoted part, the same paragraph actually tells you what this policy is: it is the one that takes the best action in every state. In an MDP, the action we take in one state does not affect rewards for actions taken in others, so we can simply maximize the policy state-by-state.

Answer 2

The existence of an optimal policy is not obvious. To see why, note that the value function provides only a partial ordering over the space of policies. This means:

$$\pi' \geq \pi \iff v_{\pi'}(s) \geq v_{\pi}(s), \forall s \in S $$

Since this is only a partial ordering, there could be a case where two policies, $\pi_1$ and $\pi_2$, are not comparable. In other words, there are subsets of the state space, $S_1$ and $S_2$ such that:

$$v_{\pi'}(s) \geq v_{\pi}(s), \forall s \in S_1$$

$$v_{\pi}(s) \geq v_{\pi'}(s),\forall s \in S_2$$

In this case, we can't say that one policy is better than the other. But if we are dealing with finite MDPs with bounded value functions, then such a scenario never occurs. There is exactly one optimal value functions, though there might be multiple optimal policies.

For a proof of this, you need to understand the Banach Fixed Point theorem. For a detailed analysis, please refer.

Answer 3

$\newcommand{\mc}{\mathcal} \newcommand{\mb}{\mathbb}$

Setting

We are considering in the setting of:

• Discrete actions
• Discrete states
• Bounded rewards
• Stationary policy
• Infinite horizon

The optimal policy is defined as: $$ \pi^\ast \in \arg \max_\pi V^\pi(s), \forall s \in \mc{S} \tag{1} $$ and the optimal value function is: $$ V^\ast = \max_\pi V^\pi (s), \forall s \in \mc S \tag{2} $$ There can be a set of policies which achieve the maximum. But there is only one optimal value function: $$ V^\ast = V^{\pi^\ast} \tag{3} $$

The question

How to prove that there exists at least one $\pi^\ast$ which satisfies (1) simultaneously for all $s \in \mc{S}$ ?

Outline of proof

1. Construct the optimal equation to be used as a temporary surrogate definition of optimal value function, which we will prove in step 2 that it is equivalent to the definition via Eq.(2). $$ V^\ast(s) = \max_{a \in \mc A} [ R(s, a) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) V^\ast(s^\prime)] \tag{4} $$

2. Derive the equivalency of defining optimal value function via Eq.(4) and via Eq.(2).

   (Note in fact we only need the necessity direction in the proof, because the sufficiency is obvious since we constructed Eq.(4) from Eq.(2).)

3. Prove that there is a unique solution to Eq.(4).

4. By step 2, we know that the solution obtained in step 3 is also a solution to Eq.(2), so it is an optimal value function.

5. From an optimal value function, we can recover an optimal policy by choosing the maximizer action in Eq.(4) for each state.

Details of the steps

1

Since $V^\ast(s) = V^{\pi^\ast}(s) = \mb E_a [Q^{\pi^\ast}(s, a)]$, we have $V^{\pi^\ast}(s) \le \max_{a \in \mc A} Q^{\pi^\ast} (s, a)$. And if there is any $\tilde{s}$ such that $V^{\pi^\ast} \neq \max_{a \in \mc A} Q^{\pi^\ast} (s, a)$, we can choose a better policy by maximizing $Q^{\ast} (s, a) = Q^{\pi^\ast} (s, a)$ over $a$.

2

(=>)

Follows by step 1.

(<=)

i.e. If $\tilde V$ satisfies $\tilde V(s) = \max_{a \in \mc A} [ R(s, a) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) \tilde V(s^\prime)]$, then $\tilde V(s) = V^\ast(s) = \max_\pi V^\pi(s), \forall s \in \mc S$.

Define the optimal Bellman operator as $$ \mc T V(s) = \max_{a \in \mc A} [ R(s, a) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) V(s^\prime)] \tag{5} $$ So our goal is to prove that if $\tilde V = \mc T \tilde V$, then $\tilde V = V^\ast$. We show this by combining two results, following Puterman[1]:

a) If $\tilde V \ge \mc T \tilde V$, then $\tilde V \ge V^\ast$.

b) If $\tilde V \le \mc T \tilde V$, then $\tilde V \le V^\ast$.

Proof:

a)

For any $\pi = (d_1, d_2, ...)$, $$ \begin{align} \tilde V &\ge \mc T \tilde V = \max_{d} [ R_d + \gamma \, P_d \tilde V] \\ &\ge R_{d_1} + \gamma \, P_{d_1} \tilde V \\ \end{align} $$ Here $d$ is the decision rule(action profile at specific time), $R_d$ is the vector representation of immediate reward induced from $d$ and $P_d$ is transition matrix induced from $d$.

By induction, for any $n$, $$ \tilde V \ge R_{d_1} + \sum_{i=1}^{n-1} \gamma^i P_\pi^i R_{d_{i+1}} + \gamma^n P_\pi^n \tilde V $$ where $P_\pi^j$ represents the $j$-step transition matrix under $\pi$.

Since $$ V^\pi = R_{d_1} + \sum_{i=1}^{\infty}\gamma^i P_\pi^i R_{d_{i+1}} $$ we have $$ \tilde V - V^\pi \ge \underbrace{\gamma^n P_\pi^n \tilde V -\sum_{i=n}^{\infty}\gamma^i P_\pi^i R_{d_{i+1}}}_{\rightarrow 0 \ \text{as}\ n\rightarrow \infty} $$ So we have $\tilde V \ge V^\pi$. And since this holds for any $\pi$, we conclude that $$ \tilde V \ge \max_\pi V^\pi = V^\ast $$ b)

Follows from step 1.

3

The optimal Bellman operator is a contraction in $L_\infty$ norm, cf. [2].

Proof: For any $s$, $$ \begin{align} \left\vert \mc T V_1(s) - \mc TV_2(s) \right\vert &= \left\vert \max_{a \in \mc A} [ R(s, a) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) V_1(s^\prime)] -\max_{a^\prime \in \mc A} [ R(s, a^\prime) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a^\prime, s^\prime) V(s^\prime)]\right\vert \\ &\overset{(*)}{\le} \left\vert \max_{a \in \mc A} [\gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) (V_1(s^\prime) - V_2(s^\prime))] \right\vert \\ &\le \gamma \Vert V_1 - V_2 \Vert_\infty \end{align} $$ where in (*) we used the fact that $$ \max_a f(a) - \max_{a^\prime} g(a^\prime) \le \max_a [f(a) - g(a)] $$

Thus by Banach fixed point theorum it follows that $\mc T$ has a unique fixed point.

References

[1] Puterman, Martin L.. “Markov Decision Processes : Discrete Stochastic Dynamic Programming.” (2016).

[2] A. Lazaric. http://researchers.lille.inria.fr/~lazaric/Webpage/MVA-RL_Course14_files/slides-lecture-02-handout.pdf

Answer 4

I spent a bit of time researching on this for my master thesis. Even though this question is a bit old, I've decided to share my findings anyway since it would have helped me earlier when I ran into this page and didn't think the answers so far gave a full picture.

The short story: The question is non-trivial for general state and action spaces. Here are a couple of results:

Let $A(s) \subseteq \mathcal{A}$ denote the set of available actions at a state $s \in \mathcal{S}$.

Thm: If

1. $\mathcal{S}$ is countable and $\mathcal{A}$ is standard Borel

2. $A(s)$ is compact for all $s \in \mathcal{S}$

3. For every $s \in \mathcal{S}$ the reward function $r(s, \cdot)$ is upper semicontinuous.

Then there exists a deterministic optimal policy $\pi^*$.

Thm: If

1. $\mathcal{S}$ is standard Borel

2. $A(s)$ is finite for all $s \in \mathcal{S}$

Then there exists a deterministic optimal policy $\pi^*$.

The long story: Here are some references that I found useful: A good source for an overview, and basis for the short story above: Feinberg: Total Expected Discounted Reward MDPs: Existence of Optimal Policies. The most 'deep' of the results comes, as far as I can see, from this article Schäl: On dynamic programming: Compactness of the space of policies. Another good source giving its own comprehensive account is Bertsekas & Shreve: Stochastic Optimal Control: Discrete time case chapters 7,8 and 9.

Cheers.