Annealed Softmax Greedy in Many-Armed Bayesian Bandits

• URL: http://arxiv.org/abs/2605.31034v1
• Date: Fri, 29 May 2026 09:05:29 GMT
• Title: Annealed Softmax Greedy in Many-Armed Bayesian Bandits
• Abstract summary: Reinforcement learning with rewards (RLVR) and group-based policy optimization methods such as GRPO update a verifiable policy by sampling multiple completions per prompt.<n>This paper studies a stylized explanation for why uncertainty-agnostic updates can nevertheless be effective.
• Score: 9.553819152637493
• License: http://creativecommons.org/licenses/by/4.0/
• 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$ case of $β$-regularity), 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 = Θ(\sqrt{T})$. This is the near-optimal Bayes regret rate in this regime, attained also by empirical-mean greedy. Under $β$-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. 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 $β$-regularity.

Related papers

• Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification? [11.223878908981725]
  $1/2$-Tsallis-INF is a canonical best-of-both-worlds FTRL algorithm.<n>It achieves logarithmic pseudo-regret in bandits while retaining minimax-optimal regret in adversarial bandits.<n>This raises a natural question: can the same algorithm, without additional exploration, also identify the best arm reliably?
  arXiv  Detail & Related papers  (2026-08-15T18:38:36Z)
• Finite-Time Regret Analysis of Retry-Aware Bandits [8.812244373657764]
  We study a bandit algorithm motivated by retry-aware objectives that value the best outcome among multiple attempts.<n>Given a posterior over arm values, ReMax chooses a sampling distribution that maximizes the posterior expected maximum reward over $M$ virtual draws.
  arXiv  Detail & Related papers  (2026-05-20T07:44:43Z)
• Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Bandits [6.402634424631123]
  We show that a natural finite-horizon LP-update policy with randomized rounding achieves an $O(log Nsqrt1/N)$ optimality gap in infinite time average reward problems.<n>Our results draw on techniques from the model predictive control literature by invoking the concept of emphdissipativity.
  arXiv  Detail & Related papers  (2025-11-11T10:53:49Z)
• Information Theoretic Guarantees For Policy Alignment In Large Language Models [19.315342870604113]
  We show that the $sqrtmathsfKL$ information theoretic upper bound holds if the reward under the reference policy has sub-gaussian tails. We also prove for the best of $n$ policy, that the $mathsfKL$ upper bound can be obtained for any $f$-divergence.
  arXiv  Detail & Related papers  (2024-06-09T18:41:50Z)
• Theoretical guarantees on the best-of-n alignment policy [110.21094183592358]
  We show that the KL divergence between the best-of-$n$ policy and the reference policy is an upper bound on the actual KL divergence.<n>We propose a new estimator for the KL divergence and empirically show that it provides a tight approximation.<n>We conclude with analyzing the tradeoffs between win rate and KL divergence of the best-of-$n$ alignment policy.
  arXiv  Detail & Related papers  (2024-01-03T18:39:13Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [59.02170783023547]
  We study the fixed-confidence best arm identification problem in the bandit framework.<n>We propose a novel policy that combines Thompson sampling with a computationally efficient approach known as the best challenger rule.
  arXiv  Detail & Related papers  (2023-10-01T01:37:02Z)
• Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
  This paper considers the best policy identification problem in online Constrained Markov Decision Processes (CMDPs) We are interested in algorithms that are model-free, have low regret, and identify an approximately optimal policy with a high probability. Existing model-free algorithms for online CMDPs with sublinear regret and constraint violation do not provide any convergence guarantee to an optimal policy.
  arXiv  Detail & Related papers  (2023-09-27T04:33:09Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  We study contextual bandits with probabilistically triggered arms (C$2$MAB-T) under a variety of smoothness conditions. Under the triggering modulated (TPM) condition, we devise the C$2$-UC-T algorithm and derive a regret bound $tildeO(dsqrtT)$.
  arXiv  Detail & Related papers  (2023-03-30T02:51:00Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  In many bandit problems, the maximal reward achievable by a policy is often unknown in advance. We consider the problem of estimating the optimal policy value in the sublinear data regime before the optimal policy is even learnable. We present a more practical, computationally efficient algorithm that estimates a problem-dependent upper bound on $V*$.
  arXiv  Detail & Related papers  (2023-02-19T01:09:24Z)
• Autoregressive Bandits [58.46584210388307]
  We propose a novel online learning setting, Autoregressive Bandits, in which the observed reward is governed by an autoregressive process of order $k$. We show that, under mild assumptions on the reward process, the optimal policy can be conveniently computed. We then devise a new optimistic regret minimization algorithm, namely, AutoRegressive Upper Confidence Bound (AR-UCB), that suffers sublinear regret of order $widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G
  arXiv  Detail & Related papers  (2022-12-12T21:37:36Z)
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
  The softmax policy gradient (PG) method is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. We demonstrate that softmax PG methods can take exponential time -- in terms of $mathcalS|$ and $frac11-gamma$ -- to converge.
  arXiv  Detail & Related papers  (2021-02-22T18:56:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.