Annealed Softmax Greedy in Many-Armed Bayesian Bandits

William Overman, Mohsen Bayati · 2026

Read Annealed Softmax Greedy in Many-Armed Bayesian Bandits by William Overman, Mohsen Bayati (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-31034.txt.

Introduction

Overman and Bayati study why uncertainty-agnostic updates can work in verifiable learning. Such updates sample completions and raise probabilities on higher-reward ones, without tracking uncertainty like Thompson sampling or UCB. They analyze a softmax policy in a many-armed Bayesian bandit, proving near-optimal regret under a tail condition. With many, softmax probability away from the best falls on other near-optimal arms, while with few arms the policy can suffer linear regret. Simulations support the theory and motivate prior-based variants beating baselines for many arms.

Catalog record

CREATORWilliam Overman, Mohsen Bayati
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63066
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.31034

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Annealed Softmax Greedy in Many-Armed Bayesian Bandits William Overman, Mohsen Bayati 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 linear upper-tail condition on the prior (the β = 1 \beta=1 case of β \beta -regularity), which implies an abundance of near-optimal arms, we prove that annealed softmax greedy achieves Bayes regret O ~ ​ ( m + T / m ) \tilde{O}(m+T/m) , and in particular O ~ ​ ( T ) \tilde{O}(\sqrt{T}) when the number of arms scales as m = Θ ⁡ ( T ) m=\Theta(\sqrt{T}) . This is the near-optimal Bayes regret rate in this regime, attained also by empirical-mean greedy. 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 ( 11 ) . 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. † † footnotetext: Emails: [email protected] , [email protected] . 1 Introduction Reinforcement learning with verifiable rewards (RLVR) is now a common component of language-model post-training pipelines. In RLVR, a model is treated as a stochastic policy over candidate solutions and is trained using rewards that can be checked automatically, such as exact-match accuracy in mathematics or unit-test success in code. This makes it possible to optimize behavior at scale without relying on human preference labels. Group-based policy optimization methods such as Group Relative Policy Optimization (GRPO) are prominent examples of this paradigm ( 34 ) . RLVR sits somewhat outside the classical exploration picture in reinforcement learning and bandit theory. In those settings, performance is often tied to epistemic uncertainty : the learner must gather information to distinguish promising actions from poor ones. Group-based RLVR pipelines, by contrast, sample multiple completions per prompt, raise the policy probability of those with higher reward, and apply a KL penalty toward a reference policy; the randomness comes from repeated sampling rather than from an uncertainty-aware exploration rule. Under verifiable rewards, such updates can be viewed as iteratively amplifying the probability of already successful outputs, with the gain coming largely from redistribution within the model’s existing support ( 23 ) . This raises a basic question: when can uncertainty-agnostic reweighting work well in problems that seem to require exploration? A related discussion concerns the base model’s coverage of good solutions. Here pass@ k denotes the probability that at least one of k independent samples from the model is correct, with pass@1 being the per-sample success rate. One line of work reports that RLVR often improves pass@1 while making little progress on pass@ k for large k , suggesting that rewarded reasoning paths may already be present in the base model’s output distribution ( 41 ) . Other recent work reports settings where RLVR does extend reasoning performance, indicating that the empirical picture depends on training details and evaluation choices ( 14 ) . We do not try to resolve that broader debate. We instead study a simplified model that isolates one mechanism by which reweighting alone can be effective. 1.1 A stylized lens: many-armed bandits and annealed softmax We consider a stochastic many-armed bandit model with Bernoulli rewards and Beta priors, where each arm represents a “completion mode” and reward corresponds to a verifiable success event. Within this model, we analyze an annealed softmax policy that, at each time step t , selects an arm with probability proportional to \exp(\eta_{t}m_{i,t}) , where m_{i,t} is the empirical mean reward of arm i at time t and \eta_{t} is an inverse-temperature schedule that increases over time, a setup referred to as annealing . The policy does not use an optimism term, a posterior sample, or per-arm confidence intervals. A classical result of 11 shows that this type of exploration (also referred to as Boltzmann exploration) can suffer linear regret with a small number of arms under any monotone temperature schedule, and that strong guarantees in that regime typically require schedules that adapt to arm-specific information. The standard failure mode is “cooling too fast”: early noise gets amplified, causing premature concentration on suboptimal actions. At first glance, such results argue against exactly the kind of uncertainty-agnostic annealing that appears in RLVR practice. The many-armed Bayesian setting allows a different possibility. If the prior places enough mass near the optimum, the action space contains many arms whose rewards are already close to optimal. Even if the algorithm spreads probability across several arms, many of them are good enough that the regret cost remains small. This idea is studied in the many-armed bandit literature, where greedy-style procedures achieve Bayesian regret guarantees under upper-tail regularity conditions on the prior ( 6 ) . 1.2 Main results and contributions The question we study is therefore: can annealed softmax, despite ignoring epistemic uncertainty, inherit the regret behavior of greedy methods in the many-armed Bayesian regime? We answer this positively. The main contributions are: 1. Bayes regret guarantee. Under the linear upper-tail condition on the prior (the \beta=1 case of \beta -regularity), annealed softmax achieves Bayes regret \tilde{O}(m+T/m) , yielding \tilde{O}(\sqrt{T}) when m=\Theta(\sqrt{T}) . This is the near-optimal Bayes regret rate in this regime (also attained by empirical-mean greedy ( 6 ) ), achieved using only empirical-mean scores, with no optimism term, no posterior sample, and no per-arm confidence interval. The analysis extends to general \beta>0 , with optimized rate \tilde{O}(m+T(\log T/m)^{1/\beta}) (Remark 5.3 ). 2. Mechanism. Annealed softmax differs from greedy only by placing some probability mass on arms that are not currently empirically best. 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. This contrasts with the failure mode studied by 11 , where the same kind of policy can suffer linear regret with a small number of arms. 3. Structural analogue in RLVR. The \beta -regular prior condition has a direct analogue in RLVR: a base policy with non-negligible probability of producing a correct completion plays the role of \beta -regularity, with pass@ k probing the upper tail of the policy’s completion distribution. In that setting, repeated sampling surfaces correct completions reliably, and subsequent reweighting can improve pass@1 without an explicit uncertainty-aware exploration rule. We note that this is only a structural analogy and not a formal result about GRPO; the theorem lives in the non-contextual bandit model,

Read the complete text