Exploration under Softmax Policy Gradients in Bandits: An Empirical Study

How do policy-gradient design choices shape exploration under a softmax parameterization? We investigate this question empirically in stochastic multi-armed bandits, studying baseline subtraction, reward standard-deviation normalization, and arm-dependent learning rates. We compare variants incorporating these mechanisms with KL-UCB on Bernoulli bandits and UCB on Gaussian bandits. Appropriately tuned variants achieve competitive finite-horizon regret on the studied instances, but the benefits of normalization depend on the reward distribution and instance. Some comparisons use oracle information, including reward gaps, or variances. Our findings highlight the importance of separating the effects of baselines, normalization, and learning-rate selection when evaluating policy-gradient exploration.