技術要約：多腕ベイズ・バンディットにおけるアニールド・ソフトマックス・グリーディ

問題提起

本論文は、強化学習（RL）およびバンディット理論における根本的な問いを調査している。すなわち、**不確実性に無頓着な（uncertainty-agnostic）**方策更新が、明示的な探索を必要とすると思われる設定において、最適に近い性能を達成できるか？ という問いである。

具体的には、著者らは検証可能な報酬を伴う強化学習（RLVR）や、グループベースの方策最適化（例：GRPO）を分析している。これらのパイプラインでは、プロンプトごとに複数の補完（completion）をサンプリングし、より高い報酬を得たものの確率を高めつつ、参照方策に対するKLペナルティによって正則化することで、確率的な方策を更新する。決定的なことに、これらの更新にはエピステミックな不確実性（例：信頼区間や事後分布サンプリング）を追跡するための明示的なメカニズムが欠けている。

古典的なバンディット理論（Cesa-Bianchi et al., 2017など）によれば、このような「ボルツマン探索」（経験平均に基づくソフトマックス選択と単調な温度スケジュール）は、固定された腕の設定においては、線形リグレット（linear regret）に陥る可能性がある。これは、「冷却が早すぎる（cooling too fast）」ことによるものであり、初期のノイズが増幅され、劣悪な行動への早期のコミットメントを招く。本論文は、腕の数が多い（many-armed）ベイズ・レジームにおいて、作用空間が大きく、事前分布の「厚い」上部裾野（i.e., 最適に近い腕が豊富に存在する状態）を持つ場合でも、この負の結果が当てはまるのかを問うている。

手法

モデルの設定

著者らは、問題を多腕ベイズ・ベルヌーイ・バンディットとして定式化している：

• ホライゾン: $T$ ステップ。
• 腕: $m$ 個の腕、インデックス $i \in [m]$。
• 事前分布: 各腕の平均報酬 $\mu_i$ は、$[0, 1]$ 上の事前分布 $\Gamma$ から独立同一に（i.i.d.）抽出される。
• 報酬: Bernoulli($\mu_i$)。
• 正則性条件: 事前分布 $\Gamma$ は 1 の近傍で $\beta$-正則性を満たす。具体的には、小さな $\epsilon$ に対して $\Gamma([1-\epsilon, 1]) \asymp \epsilon^\beta$ である。主要な分析は線形裾野のケース（$\beta=1$）に焦点を当てており、これは最適に近い腕の多項式的な密度を意味する。

分析対象とするアルゴリズム

1. 経験平均グリーディ（Empirical-Mean Greedy、ベースライン）: 初期化フェーズで各腕を一度ずつ引いた後、最も高い経験平均 $\hat{\mu}_{i,t}$ を持つ腕を決定論的に選択する。これは、このレジームにおいてほぼ最適なベイズ・リグレットを達成することが知られているベンチマークである（Bayati et al., 2020）。
2. アニールド・ソフトマックス・グリーディ（Annealed Softmax Greedy, ASG）: 提案手法。
   • 初期化: 各腕を一度ずつ引く。
   • 選択: 各ステップ $t$ において、$\exp(\eta_t \hat{\mu}_{i,t})$ に比例する確率で腕 $i$ を選択する。
   • アニーリング: 非減少の逆温度スケジュール $\eta_t$ を使用する（例：$\eta_t \propto \log t$）。
   • 重要な相違点: ASG は楽観的ボーナス、事後分布サンプリング、または腕ごとの信頼区間を使用しない。それは、経験平均とグローバルな温度スケジュールのみに依存する。

主な貢献

1. 理論的なリグレット保証

本論文は、線形上部裾野条件（$\beta=1$）の下で、ASG が以下のベイズ・リグレットを達成することを証明している：
$$\tilde{O}\left(m + \frac{T}{m}\right)$$
$m = \Theta(\sqrt{T})$ となるように腕の数 $m$ をスケールさせた場合、これは $\tilde{O}(\sqrt{T})$ のリグレットをもたらす。これは、決定論的な経験平均グリーディ・アルゴリズムによって達成されるほぼ最適なレートと一致する。

この分析は、一般的な $\beta > 0$ にも拡張可能であり、$\tilde{O}(m + T(\log T/m)^{1/\beta})$ のレートを与える。

2. 成功のメカニズム：「ソフトマックス・リーク（漏れ）」の制御

中心となる理論的洞察は、多くの腕が存在し、厚い裾野を持つ事前分布の下では、最良の腕から劣悪な腕への確率質量の「リーク（漏れ）」が、無害であるということである。

• 標準的な失敗モード: 腕の数が少ない設定では、ソフトマックスが最良ではない腕をサンプリングすると、明らかに劣悪な腕を選択してしまい、高いリグレットを招く。
• 多腕設定での成功: $\beta$-正則性の下では、経験平均が最適値に近い腕が多数存在する。ASG が現在の経験上の最良ではない腕をサンプリングする場合でも、その腕は別の最適に近い腕である可能性が非常に高く、明らかに劣悪な腕である可能性は低い。
• 結果: ランダム化のコスト（リーク）は、最適に近い腕に対して支払われるため、総リグレットは低く抑えられる。証明では、この「リーク項」がアニーリング・スケジュールによって制御されており、和が収束すること、および主要なオーダーのリグレット・スケーリングを変化させないことを示している。

3. RLVR への構造的アナロジー

論文は、理論的条件と RLVR の実践との間に構造的なアナロジーがあることを提示している：

• $\beta$-正則性 は、RLVR におけるベース・ポリシー（正しい補完を生み出す非ゼロの確率を持つ $pass@k$）に対応する。
• ベースモデルがすでに解空間を十分にカバーしている場合（多くの「最適に近い」補完が存在する場合）、反復的な重み付け（ソフトマックス更新）は、明示的な不確実性認識型の探索を必要とせずに成功を増幅させることができる。

実験結果

著者らは、ベルヌーイ・バンディットを用いたシミュレーションを通じて理論を検証している：

1. 小規模腕レジーム ($m=10$): Thompson Sampling (TS) がグリーディ法やソフトマックス法を凌駕すること、および一定温度のソフトマックスは $\eta$ が非常に高い（グリーディに近づく）場合を除き、線形リグレットを被るという古典的な結果を確認した。
2. 多腕レジーム ($m$ 最大 1000): 「性能の逆転」を示している。$m$ が増加するにつれ、経験平均グリーディおよび高 $\eta$ のソフトマックスが TS を上回る。TS のリグメントは $m$ に対して線形に増加する（明らかに劣悪な腕にサンプルを浪費する）一方で、グリーディ/ソフトマックス手法は最適に近い腕の豊富さを利用し、劣線形のリグレットを達成する。
3. 事前分布の誤設定: 事前分布が誤設定（ノイズを含む）されている場合、搾取型アルゴリズムはリグレットが増大することを示しており、このメカニズムが事前分布（または初期信号）が腕の質の妥当な順序を提供していることに依存していることを浮き彫りにしている。
4. KL ペナルティ: GRPO（ソフトマックス + KL）を模倣した実験では、情報量の多い事前分布への KL アンカーが、事前平均と経験平均の両方の信号を合成することで、リグレットをさらに減少させる。

意義と主張

本論文は、なぜ不確実性認識のない再重み付け手法（RLVR/GR포におけるものなど）が、エピステミックな不確実性を無視しているにもかかわらず効果的なのかについて、**定型的な説明（stylized explanation）**を提供していると主張している。

• 古典的理論との矛盾ではない: 著者らは、自らの結果が Cesa-Bianchi et al. (2017) と矛盾しないことを強調している。ボルツマン探索に対する負の結果は、固定された $K$ の設定において成立する。ここでの成功は、作用空間の幾何学的構造、すなわち多腕かつ厚い裾野を持つ事前分布に特有のものである。
• 限定的な範囲: 著者らは、これは構造的なアナロジーであり、LLM における GRPO が機能することの形式的な証明ではないことを明示している。定理は非文脈的（non-contextual）バンディット・モデルに限定されている。GRPO が動作する文脈的（contextual）または逐次的（sequential）な設定への拡張は、未解決の課題として特定されている。
• 有効性の境界: 本論文は、この手法が機能する領域を明確にしている。すなわち、事前分布が最適に近い腕の豊富さを保証している場合である。最適に近い腕が稀である（裾野が薄い）場合、このメカニズムは弱まり、古典的な探索の失敗が再び現れる。

要約すると、本論文は、最適に近い行動が豊富に存在する環境においては、明示的な不確実性の追跡は必ずしも必要ではなく、経験平均に対する単純なアニールド・ソフトマックスで十分であることを示している。