RL Policy Churn

I have a good theory about this now.

The Phenomenon of Policy Churn https://arxiv.org/pdf/2206.00730

The classic exploration method in RL is “epsilon greedy”, where the agent normally takes the “greedy” action with the highest predicted value, but on a small fraction of the frames a completely random action will be taken.

Surprisingly, in deep RL, setting epsilon to 0.0 often produces no change in agent performance. It still learns fine, even with “no exploration”.

This is because standard network architectures already cause the “best action” to change semi-randomly as training proceeds, giving an implicit form of exploration. This is dubbed “policy churn”.

I read this paper a while ago, but I was still shocked when I visualized the amount of policy churn happening in my agent recently. I logged eight sample points, each 100 frames before a point is scored in Breakout, which means they are about to return the ball and already doing the right thing. I reevaluated those samples after each of the next 30,000 optimizer steps and found that most of them wound up jumping between all 18 possible actions solely due to policy churn.

Because it is an implicit effect there isn’t a clear knob to adjust it, but the paper does a lot of good experiments to test various hypotheses.

The magnitude of policy churn implies two uncomfortable things for research:

Schemes designed to improve exploration are likely completely swamped by the implicit exploration due to policy churn. Agents are almost certainly already over-exploring in some parts of their life cycle.

Algorithmic changes that would otherwise be beneficial, like improvements in generalization, may be returning false-negative results if they implicitly reduce the policy churn exploration too much.

This ties in with another surprising measurement I made recently that I think nicely explains the phenomenon.

If you train a deep value function to correct for a TD error, and reevaluating the sample after training shows that it has moved by +10, what do you think the distribution of changes across all the other samples will be? Intuitively, you would like samples very similar to the trained one to change by similar amounts, maybe +8 or so, ramping down to no change in most samples that aren’t at all similar.

What actually happens in my particular network is that every sample has changed by +9 or more, with only a small gap of less than 1.0 between the sample that changed the most and the one that changed the least. Averaging over batches and multiple training steps damps this down, but there is still a lot of harmful over-generalization happening that will be jerking the policy around.

This is fundamental to standard dense network training with ReLU activations, and you can see it in a single layer network. Because all activations are >= 0, the backprop gradient will have the same sign as the error everywhere, and the resulting output change will have the same sign everywhere. On average half of your activations will be > 0 on each sample, and half of the weights will have moved due to the gradient, so the more activation channels, the more of a bias the values get.

If you addressed this with, say network sparsity, then you would likely collapse the policy churn, and agent performance would go down if you didn’t add in more explicit exploration strategies.