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


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?

  • $\begingroup$ The actions at s1 is different to the action at s2 in a given policy, you dont just apply the same actions to all states. the pii for all states is the combination of arrangement of what action you commit for all states (if i see a tree I walk aound, policy at state 1, if I see a hole I jump, policy at state 2). And one of such arrangement of actions, (the policy) is greater than or equal to all other arrangements. $\endgroup$ – lzl Sep 28 '19 at 20:01

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.