Why does Q-Learning use epsilon-greedy during testing?

Question

In DeepMind's paper on Deep Q-Learning for Atari video games (here), they use an epsilon-greedy method for exploration during training. This means that when an action is selected in training, it is either chosen as the action with the highest q-value, or a random action. Choosing between these two is random and based on the value of epsilon, and epsilon is annealed during training such that initially, lots of random actions are taken (exploration), but as training progresses, lots of actions with the maximum q-values are taken (exploitation).

Then, during testing, they also use this epsilon-greedy method, but with epsilon at a very low value, such that there is a strong bias towards exploitation over exploration, favouring choosing the action with the highest q-value over a random action. However, random actions are still sometimes chosen (5 % of the time).

My questions are:

1. Why is any exploration necessary at all at this point, given that training has already been done?

2. If the system has learned the optimal policy, then why can't the action always be chosen as the one with the highest q-value?

3. Shouldn't exploration be done only in training, and then once the optimal policy is learned, the agent can just repeatedly choose the optimal action?

Answer 1

In the nature paper they mention:

The trained agents were evaluated by playing each game 30 times for up to 5 min each time with different initial random conditions (‘noop’;see Extended Data Table 1) and an e-greedy policy with epsilon 0.05. This procedure is adopted to minimize the possibility of overfitting during evaluation.

I think what they mean is 'to nullify the negative effects of over / under fitting'. Using epsilon of 0 is a fully exploitative (as you point out) choice and makes a strong statement.

For instance, consider a labyrinth game where the agent’s current Q-estimates are converged to the optimal policy except for one grid, where it greedily chooses to move toward a boundary that results in it remaining in the same grid. If the agent reaches any such state, and it is choosing the Max Q action, it will be stuck there for eternity. However, keeping a vaguely explorative / stochastic element in its policy (like a tiny amount of epsilon) allows it to get out of such states.

Having said that, from the code implementations I have looked at (and coded myself) in practice performance is often times measured with greedy policy for the exact reasons you list in your question.

Answer 2

The answer is there in the paper itself. They used $\epsilon\ = 0.05$ to avoid overfitting. This model is used as a baseline. And yobibyte mentioned in the comment they do random starts for the same reason. And then the algorithm is evaluated for performance against a human expert. The algorithm has no model of its opponent, so the tiny epsilon. If you have the model of your opponent your problem will be deterministic instead of being stochastic. I hope this answers your question

Answer 3

I think the purpose of testing is to get a sense of how the system responds in real-world situations.

Option 1:
They might actually put some noise in the real world play - making truly random moves. This could make $\epsilon$-policy switching perfectly reflective of actual play.

Option 2:
If they are worried about being brittle, playing against a less "pristinely rational" player, then they might be "annealing" their training scores in order to not over-estimate them.

Option 3:
This is their magic smoke. There are going to be pieces of it they can't and don't want to share. They could be publishing this in order to obscure something proprietary or exceptionally relevant for their business that they don't want to share.

Option 4:
They could use repeated tests, and various values of epsilon to test how much "fat" is left in the system. If they had weak randomization, or so many samples that even a fair randomization starts repeating itself, then the method could "learn" an untrue behavior do to pseudo-random bias. This might allow checking of that in the testing phase.

I'm sure there are a half-dozen other meaningful reasons, but these were what I could think of.

EDIT: note to self, I really like the "brittle" thought. I think it may be an existential weakness of first-gen intermediate AI.

Answer 4

The reason for using $\epsilon$-greedy during testing is that, unlike in supervised machine learning (for example image classification), in reinforcement learning there is no unseen, held-out data set available for the test phase. This means the algorithm is tested on the very same setup that it has been trained on. Now the paper mentions (section Methods, Evaluation procedure):

The trained agents were evaluated by playing each game 30 times for up to 5 min each time with different initial random conditions (‘no- op’; see Extended Data Table 1) and an $\epsilon$-greedy policy with $\epsilon = 0.05$. This procedure is adopted to minimize the possibility of overfitting during evaluation.

Especially since the preprocessed input contains a history of previously encountered states the concern is that, instead of generalizing to the underlying gameplay, the agent just memorizes optimal trajectories for that specific game and replays them during the testing phase; this is what is meant by "the possibility of overfitting during evaluation". For deterministic environments this is obvious but also for stochastic state transitions memorization (i.e. overfitting) can occur. Using randomization during the test phase, in form of no-op starts of random length as well as a portion of random actions during the game, forces the algorithm to deal with unforeseen states and hence requires some degree of generalization.

On the other hand $\epsilon$-greedy is not used for potentially improving the performance of the algorithm by helping it get unstuck in poorly trained regions of the observation space. Although a given policy can always only be considered an approximate of the optimal policy (for these kind of tasks at least), they have trained well beyond the point where the algorithm would perform nonsensical actions. Using $\epsilon = 0$ during testing would potentially improve the performance but the point here is to show the ability to generalize. Furthermore in most of the Atari games the state also evolves on a no-op and so the agent would naturally get "unstuck" if that ever happened. Considering the elsewhere mentioned labyrinth example where the environment doesn't evolve on no-ops, the agent would quickly learn that running into a wall isn't a good idea if the reward is shaped properly (-1 for each step for example); especially when using optimistic initial values the required exploration happens naturally. In case you still find find your algorithm ever getting stuck in some situations then this means you need to increase the training time (i.e. run more episodes), instead of introducing some auxiliary randomization with respect to the actions.

If you are however running in an environment with evolving system dynamics (that is the underlying state transitions or rewards change over time) then you must retain some degree of exploration and update your policy accordingly in order to keep up with the changes.