Interpolating Between Softmax Policy Gradient and Neural Replicator Dynamics with Capped Implicit Exploration
Neural replicator dynamics (NeuRD) is an alternative to the foundational
softmax policy gradient (SPG) algorithm motivated by online learning and
evolutionary game theory. The NeuRD expected update is designed to be nearly
identical to that of SPG, however, we show that the Monte Carlo updates differ
in a substantial way: the importance correction accounting for a sampled action
is nullified in the SPG update, but not in the NeuRD update. Naturally, this
causes the NeuRD update to have higher variance than its SPG counterpart.
Building on implicit exploration algorithms in the adversarial bandit setting,
we introduce capped implicit exploration (CIX) estimates that allow us to
construct NeuRD-CIX, which interpolates between this aspect of NeuRD and SPG.
We show how CIX estimates can be used in a black-box reduction to construct
bandit algorithms with regret bounds that hold with high probability and the
benefits this entails for NeuRD-CIX in sequential decision-making settings. Our
analysis reveals a bias--variance tradeoff between SPG and NeuRD, and shows how
theory predicts that NeuRD-CIX will perform well more consistently than NeuRD
while retaining NeuRD's advantages over SPG in non-stationary environments.