This is the pre-proceedings for the RLC 2026. You may expect minor changes.

Annealed Softmax Greedy in Many-Armed Bayesian Bandits

By William Overman, and Mohsen Bayati

Reinforcement Learning Journal, vol. 7, 2026, pp. TBD.

Will be presented at the Reinforcement Learning Conference (RLC), Montréal, Quebec, Canada, August 15–17, 2026.

Download:

Keywords: Many-armed bandits, Bayesian bandits, exploration, Boltzmann exploration, RLVR.

Abstract:

Reinforcement learning with verifiable rewards (RLVR) and group-based policy optimization methods such as GRPO update a stochastic policy by sampling multiple completions per prompt and increasing the policy's probability on those with higher reward, regularized by a KL penalty toward a reference policy. These updates 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 (Boltzmann) policy that selects actions according to a softmax of empirical mean rewards in a many-armed Bayesian Bernoulli bandit. Under a $\beta$-regular 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 active arms scales as $m = \Theta(\sqrt{T})$, matching the rate that empirical-mean greedy achieves in the same regime. Under $\beta$-regularity, many arms maintain empirical means close to the optimum throughout learning, so when softmax samples an arm other than the empirically best, that arm tends to be another near-optimal one rather than a clearly inferior one. By contrast, with a small number of arms, the same kind of softmax policy can suffer linear regret \citep{cesabianchi2017boltzmann}. 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 $\beta$-regularity.

Citation Information:

William Overman and Mohsen Bayati. "Annealed Softmax Greedy in Many-Armed Bayesian Bandits." Reinforcement Learning Journal, vol. 7, 2026, pp. TBD.

BibTeX:
@article{overman2026annealed,
    title={Annealed Softmax Greedy in Many-Armed Bayesian Bandits},
    author={William Overman and Mohsen Bayati},
    journal={Reinforcement Learning Journal},
    volume={7},
    pages={},
    year={2026}
}