How can policies be ordered in reinforcement learning?

Question

Following Sutton, Barto "Reinforcement Learning: An Introduction", in 3.6 Optimal Policies and Optimal Value Functions they define an ordering between 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}$.

This involves the definition for the state-value function $v(s)$:

$$ v_{\pi}(s) = \mathbb{E}_{\pi}\left[G_t | S_t = s\right] $$

where $G_t$ is the return and

$\mathbb{E}_{\pi}[\cdot]$ denotes the expected value of a random variable given that the agent follows policy $\pi$, and $t$ is any time step.

In 3.5 Policies and Value Functions they also define a policy $\pi$ as

a mapping from states to probabilities of selecting each possible action. If the agent is following policy $\pi$ at time $t$, then $\pi(a|s)$ is the probability that $A_t = a$ if $S_t = s$.

Question

From above definition it appears that a policy is (in a general sense) a set of rules that maps state-action pairs $(s, a)$ to probabilities by using the same set of rules for all states $s$. Now it could happen that policy $\pi$ has a greater state-value function for state $s_0$ but $\pi'$ has a greater one for $s_1$, i.e. $v_{\pi}(s_0) > v_{\pi'}(s_0)$ but $v_{\pi}(s_1) < v_{\pi'}(s_1)$ for some states $s_0, s_1$. According to the above definition of ordering none of the policies would be superior to the other one (because it requires $>$ for all states $s\in\mathcal{S}$). Then, again in 3.6 Optimal Policies and Optimal Value Functions, they make the statement

There is always at least one policy that is better than or equal to all other policies. This is an optimal policy.

Based on the above concerns about policy ordering it's not clear that such an optimal policy exists. However this is quite an important result as the following Bellman optimality equations are based on it.

Can someone resolve these concerns about how policies can be ordered?

Answer 1

It is a partial ordering, if you check back in the reference, just above your quote:

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.

So your two policy can't be ordered with respect to each other. so neither is better than the other, that does not prove that there can't be an optimal one.

I think that the partial ordering may be all they needed to infer existence. There are threads here, I think, asking for details on that proof. I have not yet been able to read them.

It just occurred to me, that you could construct a better policy from patching the two non-ordered ones. Axiom of choice (something like that): partition the action-state space according to what ails, and choose the best of the two policies in every such subset, adding quantifiers to cover A X S defined support for such mapping. Maybe then we are both more inclined to accept that optimal policy...

Would that patched new mapping be a policy? I don't recall a policy definition, but if mapping from A X S to space of "conditional" probabilities is enough qualification, then you just have to worry about your partition sub-sets be measurable, I would think.

The quotes on conditional were a remark that when probability notation becomes frequent, I have experienced that set notation tends to get fuzzy, makes the Bayesian juggling faster... (that was a joke).

Answer 2

Suppose we have two policies that are incomparable: the first on is $p_1 = argmax(Q_1)$ that is better in one states and the second one is $p_2 = argmax(Q_2)$ that is better in another. We can always design a better policy which will be better both $p_1$ and $p_2$ which is equal to $p^* = argmax[max(Q1, Q2)]$

We need to consider optimality in terms of cumulative reward - calculating policy in each step is a bit meaningful.