論文の概要: Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping
- arxiv url: http://arxiv.org/abs/2609.22690v1
- Date: Sat, 19 Sep 2026 01:48:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-22 20:29:00.52024
- Title: Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping
- Title（参考訳）: ミニマックスシングルアームストッピングによるマルチアームベルヌーイ帯域
- Abstract要約: 有限ホライゾンベルヌーイ多武装バンディットの指数ポリシを開発する。
SAB問題に対する最悪の後悔を最小限に抑えることは、予測できないすべてのポリシーが、完全に半無限線形プログラミングの定式化を許していることを示す。
- 参考スコア（独自算出の注目度）: 9.05633129427177
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We develop an index policy for finite-horizon Bernoulli multi-armed bandits from minimax solutions to single-arm bandit (SAB) problems. Each SAB problem involves choosing between an unknown Bernoulli arm and a known reward. We show that minimizing worst-case regret of SAB problems over all non-anticipative policies admits an exact semi-infinite linear programming formulation. The resulting stopping policies offer a natural way to compare arms: the higher the known reward against which a policy continues sampling, the more promising the unknown arm. We turn this intuition into indices based on cumulative continuation probabilities, with a monotone adjustment and a reward-shortfall cap. By relating index errors to the regret of single-arm stopping policies, we establish a distribution-free regret bound of $4.45\sqrt{KT}+10.75K$ for $K$ arms and horizon $T$. This bound matches the minimax-optimal regret order established in the literature. The guarantee extends to rewards supported on $[0,1]$ through Bernoulli randomization. We also provide a finite-grid implementation with quantified approximation loss. In numerical experiments, the SAB-based index policy achieves lower worst-case regret than every tested benchmark policy across all evaluated numbers of arms and horizons, while closely matching the grid-based MAB minimax policy in the two-arm setting.
- Abstract（参考訳）: 我々は,ミニマックス解から単一アーム・バンディット(SAB)問題まで,有限水平ベルヌーイマルチアーム・バンディットの指数ポリシを開発する。
それぞれのSAB問題は、未知のベルヌーイの腕と既知の報酬を選択することである。
SAB問題に対する最悪の後悔を最小限に抑えることは、予測できないすべてのポリシーが、完全に半無限線形プログラミングの定式化を許していることを示す。
結果として引き起こされる政策は、武器を比較する自然な方法を提供する: 政策がサンプリングを続ける既知の報酬が高くなるほど、未知の武器はより有望になる。
我々はこの直感を、単調な調整と報酬-ショートフォールキャップを備えた累積継続確率に基づく指標に変換する。
単発停止ポリシーの後悔に指数誤差を関連付けることで、$K$アームと水平線$T$に対して4.45\sqrt{KT}+10.75K$の分布自由後悔境界を確立する。
この境界は、文学で確立されたミニマックス最適後悔の順序と一致する。
この保証はベルヌーイランダム化を通じて$[0,1]$でサポートされている報酬にまで拡張される。
また、近似損失を定量化した有限グリッドの実装も提供する。
数値実験では、SABベースのインデックスポリシは、評価されたすべての腕と地平線数でテストされたベンチマークポリシよりも、最悪のケースの後悔を減らし、グリッドベースのMABミニマックスポリシを両腕設定で密にマッチングする。
関連論文リスト
- Annealed Softmax Greedy in Many-Armed Bayesian Bandits [9.553819152637493]
報奨付き強化学習(RLVR)とGRPOのようなグループベースのポリシー最適化手法は、プロンプト毎に複数の完了をサンプリングすることで検証可能なポリシーを更新する。
本稿では,不確実性に依存しない更新が有効である理由について,スタイリングした説明を行う。
論文 参考訳（メタデータ） (2026-05-29T09:05:29Z) - Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Arms [80.05851139852311]
本稿では,ガウス的手法を用いて連続空間上の報酬環境を学習するための新しいポリシーを提案する。
提案手法は,$mathcalO*(sqrtT)$ cumulative regret を用いて連続リプシッツ報酬関数を効率よく学習することを示す。
論文 参考訳（メタデータ） (2025-05-30T15:15:18Z) - Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits [31.212504858546232]
ヘビーテールの片側定常バンディット問題に対処する。
重み付き分布に適した新しいカタニスタイル変化点検出戦略を提案する。
本稿では,この変化点検出戦略と楽観的アルゴリズムを組み合わせたロバストCPD-UCBを提案する。
論文 参考訳（メタデータ） (2025-05-26T14:40:47Z) - Optimal Regret of Bernoulli Bandits under Global Differential Privacy [44.25744563135375]
エプシロン$-global Differential Privacy (DP) による包帯のレグレット最小化が広く研究されている。
我々はベルヌーイのバンディットに対する$epsilon-global DPアルゴリズムの残酷な下限と上限を再検討し、両者を改善した。
論文 参考訳（メタデータ） (2025-05-08T19:48:58Z) - Continuous K-Max Bandits [54.21533414838677]
我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。
この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。
我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
論文 参考訳（メタデータ） (2025-02-19T06:37:37Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals [0.9831489366502302]
予算的マルチアーマッド・バンドイット(MAB)問題について検討し、プレイヤーが期待できない報酬とコストでK$アームから選択する。
非対称な信頼区間を用いた新しいアッパー信頼境界(UCB)サンプリングポリシーである$omega$-UCBを提案する。
これらの間隔は、サンプル平均とランダム変数の境界との間の距離でスケールし、報酬コスト比をより正確かつ厳密に推定する。
論文 参考訳（メタデータ） (2023-06-12T12:35:16Z) - Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。
決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。
このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
論文 参考訳（メタデータ） (2022-03-29T04:58:04Z) - Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax
Regret [5.1398743023989555]
我々は、各腕に関連する報酬の分布が時間変動であると仮定する非定常的マルチアーミングバンディット(MAB)問題を研究する。
提案手法は, 変動予算を満たした報酬分配系列の組に対する後悔の前提となる, 最悪の場合の後悔という観点から, 提案手法の性能を特徴付ける。
論文 参考訳（メタデータ） (2021-01-22T07:34:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。