Annealed Softmax Greedy in Many-Armed Bayesian Bandits

Abstract

Reinforcement learning with verifiable rewards and group-based policy optimization methods update a stochastic policy by sampling multiple completions per prompt and increasing the policy's probability on those with higher reward. These updates, unline the exploration mechanism in Thompson sampling and UCB, do not include explicit mechanisms that track epistemic uncertainty. This paper studies a stylized explanation for why such uncertainty-agnostic updates can nevertheless be effective. We analyze an annealed softmax policy that selects actions according to a softmax of empirical mean rewards in a many-armed Bayesian Bernoulli bandit. Under a linear upper-tail condition on the prior, which implies an abundance of near-optimal arms, we prove that annealed softmax greedy achieves Bayes regret $\tilde{O}(m+T/m)$, and in particular $\tilde{O}(\sqrt{T})$ when the number of arms scales as $m=\Theta (\sqrt{T})$. This is the near-optimal Bayes regret rate in this regime, attained also by empirical-mean greedy. Under the upper-tail condition, many arms keep empirical means near the optimum throughout learning, so the probability that softmax places away from the empirical best falls mostly on other near-optimal arms. By contrast, with a small number of arms, the same kind of softmax policy can suffer linear regret (Cesa-Bianchi et al., 2017). The result also provides a structural analogy to RLVR, where a base policy with a non-negligible probability of producing a correct completion plays the role of the tail condition. Simulations support the theory and motivate prior-anchored variants of greedy and annealed softmax that score arms by the Beta posterior mean and skip the forced initialization; with an arm-specific prior, accurate or noisy, these variants outperform baselines, including Thompson Sampling, when the number of arms is large.

Appeared in Reinforcement Learning Conference, 2026