analiza aiqbench
This paper provides a theoretical justification for why uncertainty-agnostic optimization methods, like annealed softmax greedy, remain effective in large-scale reinforcement learning settings with verifiable rewards. By demonstrating near-optimal regret bounds when an abundance of near-optimal actions exists, the work clarifies that explicit epistemic tracking is not strictly necessary if the action space contains many high-performing candidates. The findings offer valuable insights for scaling group-based policy optimization techniques used in modern AI alignment and reward modeling pipelines.
Annealed Softmax Greedy in Many-Armed Bayesian Bandits
arXiv:2605.31034v3 Announce Type: replace 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.
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.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2605.31034 [cs.LG]
(or arXiv:2605.31034v3 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2605.31034 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 368 cuvinte
Subiecte conexe
The Greedy Advantage in Finite-Horizon Bandits
arXiv · 3 aug. 2026
Structured Neuron Pruning in Deep Neural Networks Using Multi-Armed Bandits
arXiv · 9 iun. 2026
Information-Directed Sampling for Causal Bandits
arXiv · 22 sept. 2026
Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits
arXiv · 26 sept. 2026