Annealed Softmax Greedy Achieves Near-Optimal Regret in Many-Armed Bandits

A new paper on arXiv (2605.31034) studies why uncertainty-agnostic policy updates in reinforcement learning with verifiable rewards (RLVR) and group-based methods like GRPO can still be effective. The authors analyze an annealed softmax (Boltzmann) policy in a many-armed Bayesian Bernoulli bandit setting. Under a linear upper-tail condition on the prior (β=1 case of β-regularity), which implies many near-optimal arms, they prove that annealed softmax greedy achieves Bayes regret of Õ(m + T/m), and in particular Õ(√T) when the number of arms m is chosen appropriately. The work provides a theoretical explanation for the empirical success of such updates without explicit epistemic uncertainty tracking.