# Annealed Softmax Greedy in Many-Armed Bayesian Bandits

arXiv: https://arxiv.org/abs/2605.31034 · HTML: https://mlsanity.com/paper/2605.31034/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 42 references that are in the map.
- First posted on arXiv 29 May 2026.

## Builds on (most cited first, 27 of 27)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?](https://mlsanity.com/paper/2504.13837/) (2025)
- [The Entropy Mechanism of Reinforcement Learning for Reasoning Language Models](https://mlsanity.com/paper/2505.22617/) (2025)
- [Reinforcement Learning with Verifiable Rewards Implicitly Incentivizes Correct Reasoning in Base LLMs](https://mlsanity.com/paper/2506.14245/) (2025)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [A Survey of Reinforcement Learning for Large Reasoning Models](https://mlsanity.com/paper/2509.08827/) (2025)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [REASONING GYM: Reasoning Environments for Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2505.24760/) (2025)
- [Reinforcement Learning with Verifiable Rewards: GRPO's Effective Loss, Dynamics, and Success Amplification](https://mlsanity.com/paper/2503.06639/) (2025)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Boltzmann Exploration Done Right](https://mlsanity.com/paper/1705.10257/) (2017)
- [Adaptive Exploration in Linear Contextual Bandit](https://mlsanity.com/paper/1910.06996/) (2019)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [Satisficing in Time-Sensitive Bandit Learning](https://mlsanity.com/paper/1803.02855/) (2018)
- [Sharp Analysis for KL-Regularized Contextual Bandits and RLHF](https://mlsanity.com/paper/2411.04625/) (2024)
- [The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms](https://mlsanity.com/paper/2002.10121/) (2020)
- [The Externalities of Exploration and How Data Diversity Helps Exploitation](https://mlsanity.com/paper/1806.00543/) (2018)
- [On Bayesian index policies for sequential resource allocation](https://mlsanity.com/paper/1601.01190/) (2016)
- [Shrinking the Variance: Shrinkage Baselines for Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2511.03710/) (2025)
- [Pass@k Metric for RLVR: A Diagnostic Tool of Exploration, But Not an Objective](https://mlsanity.com/paper/2511.16231/) (2025)

## Abstract (arXiv)

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 tildeO(m + T/m), and in particular tildeO(√T) when the number of arms scales as m = Theta(√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.