0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.