論文の概要: Annealed Softmax Greedy in Many-Armed Bayesian Bandits

• arxiv url: http://arxiv.org/abs/2605.31034v1
• Date: Fri, 29 May 2026 09:05:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-01 20:56:50.494176
• Title: Annealed Softmax Greedy in Many-Armed Bayesian Bandits
• Title（参考訳）: 多元ベイズバンドにおけるAnnealed Softmax Greedy
• Authors: William Overman, Mohsen Bayati,
• Abstract要約: 報奨付き強化学習(RLVR)とGRPOのようなグループベースのポリシー最適化手法は、プロンプト毎に複数の完了をサンプリングすることで検証可能なポリシーを更新する。 本稿では,不確実性に依存しない更新が有効である理由について,スタイリングした説明を行う。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 検証可能な報酬付き強化学習(RLVR)とGRPOのようなグループベースの政策最適化手法は、各プロンプトごとに複数の完了をサンプリングし、より高い報酬を持つ者に対する政策の確率を高めることで確率的政策を更新し、基準政策に向けてKLペナルティによって正規化される。 これらの更新には、てんかんの不確実性を追跡する明確なメカニズムが含まれていない。 本稿では,このような不確実性に依存しない更新が有効である理由について,スタイリングした説明を行う。 我々は,ベイズ平均報酬のソフトマックスに基づいて行動を選択するアニール型ソフトマックス (ボルツマン) ポリシーを,多腕のベイズ平均ベルヌーイバンディットで解析する。 前者の線形上尾条件($β=1$の$β$-regularityの場合)では、アニールされたソフトマックスグリーディがベイズ後悔の$\tilde{O}(m + T/m)$、特に$\tilde{O}(\sqrt{T})$が$m = >(\sqrt{T})$とスケールするときに、アニールされたソフトマックスグリーディがベイズ後悔することを示す。 これは、この政権で最も近いベイズ後悔率であり、経験的な平均的な欲求によっても達成された。 β$-regularityの下では、多くの腕は学習を通して最適に近い経験的手段を維持しているため、ソフトマックスが経験的に最も良い腕以外の腕をサンプリングする場合、その腕は明らかに劣る腕というよりは、もう1つの最適に近い傾向にある。 対照的に、少数の腕では、同じ種類のソフトマックスポリシーが線形後悔に苦しむことがある。 この結果はRLVRと構造的な類似性ももたらし、正しい完備化を生み出す確率が無視できない基本方針が$β$-regularity(英語版)(英語版)(英語版)(英語版)(英語版)(英語版)(英語版)(英語版))(英語版)(英語版)(英語版))(英語版)(英語版))(英語版)(英語版))(英語版)(英語版))(英語版)(英語版))(英語版)(英語版))(英語版)(英語版))(英語版)(英語版))の役割を果たす。

関連論文リスト

• Finite-Time Regret Analysis of Retry-Aware Bandits [8.812244373657764]
  複数の試行において最良の結果を評価するために,再試行を意識した目的によって動機付けられた帯域幅アルゴリズムについて検討する。 後部の腕の値が与えられた場合、ReMaxはサンプリング分布を選択し、後部の最大報酬を$M$仮想引き数で最大化する。
  論文  参考訳（メタデータ） (2026-05-20T07:44:43Z)
• Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Bandits [6.402634424631123]
  ランダムなラウンドリングを持つ自然な有限水平LP更新ポリシーは、無限時間平均報酬問題において$O(log Nsqrt1/N)$Optimity gapを達成することを示す。 本研究は, 共分散性の概念を提唱し, 予測制御文学の手法を取り入れたものである。
  論文  参考訳（メタデータ） (2025-11-11T10:53:49Z)
• Theoretical guarantees on the best-of-n alignment policy [110.21094183592358]
  我々は、KLの最良のn$ポリシーと参照ポリシーのKL分岐が、実際のKL分岐の上限であることを示す。 そこで本研究では,KLの発散に対する新しい推定器を提案し,その近似が厳密であることを実証的に示す。 我々は、利益率とKLの最良のn$アライメントポリシーの相違点を分析することで締めくくった。
  論文  参考訳（メタデータ） (2024-01-03T18:39:13Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [59.02170783023547]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-19T01:09:24Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。