epsilon-greedy policy improvement?

Question

I am learning reinforcement learning from David Silver's open course and Richard Sutton's book. While I enjoy the course and the book much, I am currently confused in $\epsilon$-greedy policy improvement.

Both the book and the open course have a theorem saying that

For any $\epsilon$-greedy policy $\pi$, the $\epsilon$-greedy policy $\pi'$ with respect to $q_\pi$ is an improvement, i.e., $v_{\pi'}(s)\ge v_{\pi}(s)$

which is proved by

where the inequality holds because the $\max$ operation is greater than equal to an arbitrary weighted sum. (m is the number of actions.)

However, the theorem does not make sense to me, because if $\epsilon\approx 1$, what the theorem implies is that an (almost) random policy would be better than the current one.

When I was walking through the proof, I found that the weights should be nonnegative, i.e., $\pi(a|s)-\epsilon/m\ge 0$ indicating that $\epsilon$ is bounded by $\epsilon \le \min_a m \pi(a|s)$.

Further, in determinsitic (e.g., greedy) policies, $\pi(a|s)=0$ for $a\ne\arg\max_a q_\pi(s,a)$. Then the theorem tells little.

Could anyone verify my understanding or shed more light in the theorem?

Answer 1

Ok! If you remember generalized policy iteration, the idea is a policy $\pi$ is first evaluated $v_\pi(s)$ and then improved, into $\pi'$, by acting greedily with respect to our original policy evaluation: $\pi' \rightarrow greedy(v_\pi(s))$. The theorem basically states that acting $\varepsilon$-greedy $still$ will result in policy improvement i.e. a policy with greater reward $v_{\pi'}(s) \geq v_\pi(s)$. The theorem works this out in reverse.

Line 1 left-side: we evaluate our improved policy, $\pi'$, by an action-value function (instead of a value function) with respect to our original policy: $q_\pi(s,\pi'(s)).$

Line 1 right-side: $\sum_{a \in A}\pi'(a|s)q_\pi(s,a) \approx v_{\pi'}(s)$

Line 2: we expand $\pi'(a|s)$, which is the probability of taking an action in a given state, to conform to our definition of being $\varepsilon$-greedy: we choose the max action with $1-\varepsilon$ probability or a random action (which could include the max action) with $\varepsilon/m$ probability where $m$ is the total number of actions.

Line 3: This is by far the most fun part of the proof. $max_{a \in A}q_\pi(s,a)$ is replaced by $\sum_{a \in A}\frac{\pi(a|s)-\varepsilon/m}{1-\varepsilon}q_\pi(s,a).$ The claim is that the max action under $\pi'$ is greater than or equal to a weighted sum of actions under $\pi$ for any arbitrarily chosen max action. To see this, imagine there's two actions we can choose from $A = \{a_1,a_2\}$ where $a_2$ is arbitrarily selected as the max under $\pi$: $\sum_{a \in A}\frac{\pi(a|s)-\varepsilon/2}{1-\varepsilon}q_\pi(s,a) = \frac{(\varepsilon/2 -\varepsilon/2)q_\pi(s,a_1) + ((1-\varepsilon) + \varepsilon/2 -\varepsilon/2)q_\pi(s,a_2)}{1-\varepsilon} = \frac{(1-\varepsilon)q_\pi(s,a_2)}{1-\varepsilon} = q_\pi(s,a_2).$ The equality is satisfied when the max action under $\pi'$ is the same as $\pi$, namely $a_2$: $ max_{a \in A}q_\pi(s,a) = q_\pi(s,a_2)$. The inequality is satisfied when the max action under $\pi'$ is not $a_2$ in which case: $max_{a \in A}q_\pi(s,a) > q_\pi(s,a_2)$.

Line 4: cancel terms and simplify.

What is crucial to understand is that generalized policy iteration has multiple iterations of evaluation and improvement. The policy under $\pi$ can be different from $\pi'$(hence the difference in selecting $a_2$ as max) because each were improved under different evaluations. This theorem is essentially saying, "Hey, greedily selecting actions after looking at my last choice of greedily selecting actions will either improve my overall reward or just keep it the same." One subtlety (for understanding line 2) is actually (not approximately) $\sum_{a \in A}\pi'(a|s)q_{\pi'}(s,a) = v_{\pi'}(s).$

Answer 2

Reinforcement learning is fairly new to me, but hopefully this is helpful. Firstly, some general remarks.

1. The theorem states that the new policy will not be worse than the previous policy, not that it has to be better.

2. There is a slight difference in the formulation of the theorem between the book and the slides. The book specifies the first policy to be $\epsilon$-soft, whereas the slides specify $\epsilon$-greedy.

3. An $\epsilon$-greedy policy is $\epsilon$-greedy with respect to an action-value function, it's useful to think about which action-value function a policy is greedy/$\epsilon$-greedy with respect to.

The $\epsilon$-Greedy policy improvement theorem is the stochastic extension of the policy improvement theorem discussed earlier in Sutton (section 4.2) and in David Silver's lecture. The motivation for the theorem is that we want to find a way of improving policies while ensuring that we explore the environment. Deterministic policies are no good now as there may be state-action pairs that are never encountered under them. One way to ensure exploration is via so called $\epsilon$-soft policies. A policy is $\epsilon$-soft if all actions $a$ have probability of being taken $p(a) \ge \epsilon/N_{a}$, where $\epsilon > 0$ and $N_{a}$ is the number of possible actions.

In both cases of policy improvement the aim is to find a policy $\pi'$ that satisfies $q(s,\pi'(s)) \ge q(s,\pi(s)) = v^{\pi}(s)$, as this implies that $v^{\pi'}(s) \ge v^{\pi}(s)$ and thus we have a better policy. In the deterministic case it was straightforward to arrive at such a policy by construction so it was not necessary to demonstrate that the condition was satisfied. In the stochastic case it is less obvious, and the solution to constructing such a new policy needs to be shown to satisfy the required condition.

In the deterministic limit ($\epsilon = 0$) of a full greedy policy, we are just back at the case of deterministic policy improvement. Our new policy $\pi'$ is the greedy policy with respect to the action value function of $\pi$, this is exactly the policy constructed to meet the condition in the deterministic case. You're right to say the theorem doesn't say much in this case, it says exactly as much as we already know from the deterministic case, which didn't require proof. We already know how things work in this case and we want to generalise to non-deterministic policies. Hopefully that resolves your second area of confusion.

How do we find a better stochastic policy?

The theorem (according to the book) tells us that given an $\epsilon$-soft policy, $\pi$, we can find a better policy, $\pi'$, by taking the $\epsilon$-greedy policy with respect to the action-value function of $\pi$. Note that $\pi'$ is $\epsilon$-greedy with respect to the action-value function of the previous policy $\pi$, not (in general) its own action-value function. Any policy that is $\epsilon$-greedy with respect to any action-value function is $\epsilon$-soft, i.e. the new policy is still $\epsilon$-soft. Hence we can find another new policy, $\pi''$, this time taking it to be $\epsilon$-greedy with respect to the action-value function of $\pi'$, and this will be better again. We are aiming at the optimal $\epsilon$-soft policy. When we arrive at a policy that is $\epsilon$-greedy with respect to its own action-value function then we are done.

Clearly if a policy is e-greedy, then it is $\epsilon$-soft, giving the formulation on the slide. I think the discussion of $\epsilon$-soft policies in the book helps to illuminate the theorem. Potentially they have avoided introducing $\epsilon$-soft in the slides to reduce the amount of new terminology being presented.

In the case that $\epsilon$ $\approx$ 1, remember that the original policy is also $\epsilon$-greedy so will be almost random. In this case we're essentially saying that we can find an almost random policy that is (occasionally) greedy in a better way than a previous almost random policy. Specifically, we make it "greedy in a better way" by making it $\epsilon$-greedy with respect to the action-value function of the previous policy.

Answer 3

Epsilon is defined as the probability of exploration. Exploration is equivalent to picking a random action in action space. This is so that the agent will try out new actions during training, in case these lead to better (future discounted) rewards. If epsilon = 1, the agent will always explore, and never act greedily with respect to the action-value function. Therefore, epsilon < 1 in practice, so that there is a good balance between exploration and exploitation.

Answer 4

Sutton RL book says

"Among epsilon-soft policies, epsilon-greedy policies are in some sense those that are closest to greedy."

The theorem assumes that given policy is epsilon soft policy and shows that epsilon greedy on value function obtained by following an epsilon soft policy is optimal.

The fact that policy is episolon soft ensures that weights are non negative. Note that inequality won't hold if weights can be negative.

David silver slides are bit misleading here as they fail to mention that universe of policies considered here are epsilon soft.

Answer 5

I am going through the lectures and the book as well, and had the same confusion as you.

I realize that David does not highlight that the original policy $\pi$ is $\epsilon$-soft in the lecture, meaning every action has probability at least $\epsilon / |\mathcal{A}|$. This is crucial to the proof. This is emphasized in the book (sec 5.4).

However, the theorem does not make sense to me, because if ≈1, what the theorem implies is that an (almost) random policy would be better than the current one.

You are right. Note that if $\epsilon \approx 1$, then the constraint that the policy $\pi$ must be $\epsilon$-soft implies that $\pi$ too is almost random. All you are saying here is that your new almost random policy will be better than your original almost random policy.

Further, in determinsitic (e.g., greedy) policies, (|)=0 for ≠argmax(,). Then the theorem tells little.

You are right again. The theorem does not apply to deterministic policies since they are not $\epsilon$-soft.