論文の概要: The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms

• arxiv url: http://arxiv.org/abs/2002.10121v3
• Date: Wed, 23 Mar 2022 00:44:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-29 03:02:27.485829
• Title: The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms
• Title（参考訳）: 多数の腕を持つマルチアーメッドバンドにおけるグリーディアルゴリズムの妥当な有効性
• Authors: Mohsen Bayati, Nima Hamidi, Ramesh Johari, Khashayar Khosravi
• Abstract要約: 我々は、サブサンプルのグリードアルゴリズムが、多くの武装政権におけるベルヌーイの盗賊に対するレート最適化であることを示している。 これらの結果は、欲求アルゴリズムの恩恵を受ける多腕体制における新たな自由探索形態を示唆している。
• 参考スコア（独自算出の注目度）: 14.834625066344584
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a Bayesian $k$-armed bandit problem in many-armed regime, when $k \geq \sqrt{T}$, with $T$ the time horizon. We first show that subsampling is critical for designing optimal policies. Specifically, the standard UCB algorithm is sub-optimal while a subsampled UCB (SS-UCB), which samples $\Theta(\sqrt{T})$ arms and executes UCB on that subset, is rate-optimal. Despite theoretically optimal regret, SS-UCB numerically performs worse than a greedy algorithm that pulls the current empirically best arm each time. These empirical insights hold in a contextual setting as well, using simulations on real data. These results suggest a new form of free exploration in the many-armed regime that benefits greedy algorithms. We theoretically show that this source of free exploration is deeply connected to the distribution of a tail event for the prior distribution of arm rewards. This is a fundamentally distinct phenomenon from free exploration due to variation in covariates, as discussed in the recent literature on contextual bandits. Building on this result, we prove that the subsampled greedy algorithm is rate-optimal for Bernoulli bandits in many armed regime, and achieves sublinear regret with more general distributions. Taken together, our results suggest that practitioners may benefit from using greedy algorithms in the many-armed regime.
• Abstract（参考訳）: 我々は、多くの武器を持つ状態におけるベイズ的$k$武装バンディット問題を、$k \geq \sqrt{T}$, $T$で検討する。 まず、最適なポリシーを設計するためにサブサンプリングが重要であることを示す。 具体的には、標準 UCB アルゴリズムは準最適であり、サブサンプル UCB (SS-UCB) は $\Theta(\sqrt{T})$ arms をサンプリングし、そのサブセット上で UCB を実行する。 理論的に最適な後悔にもかかわらず、SS-UCBは、現在の最高の腕を毎回引っ張る欲張りアルゴリズムよりも数値的に劣る。 これらの経験的洞察は、実データ上のシミュレーションを使用して、文脈的にも保持される。 これらの結果は,多武装体制における新たな自由探索形態を示唆する。 理論的には、この自由探索の源泉は、腕の報酬の事前分布のための尾イベントの分布と深く関係していることが示される。 これは、文脈的包帯に関する最近の文献で論じられているように、共変量の変化による自由探索とは根本的に異なる現象である。 この結果に基づいて, サブサンプルグリードアルゴリズムが, 多くの武装体制におけるベルヌーイの盗賊に対するレート最適化であることを証明し, より一般的な分布でサブ線形後悔を実現する。 以上の結果から,多武器体制における欲求的アルゴリズムの活用のメリットが示唆された。

関連論文リスト

• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Multi-armed Bandit Algorithm against Strategic Replication [5.235979896921492]
  我々は,各エージェントが一組のアームを登録する多腕バンディット問題を考慮し,各エージェントがそのアームを選択すると報酬を受け取る。 エージェントは、より多くの武器を複製で戦略的に送信し、バンディットアルゴリズムの探索と探索のバランスを悪用することで、より多くの報酬をもたらす可能性がある。 本稿では,複製の復号化と,最小限の累積後悔を実現するバンディットアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-23T07:38:44Z)
• The Fragility of Optimized Bandit Algorithms [4.390757904176221]
  帯域幅アルゴリズムの最適設計に関する文献の多くは、期待される後悔の脆弱さに基づいている。 最適化された UCB バンディットの設計は,問題をわずかに誤定義した場合に脆弱であることを示す。 提案手法は, 誤り特定に対する強靭性を確保するために, UCBアルゴリズムを改良可能であることを示す。
  論文  参考訳（メタデータ） (2021-09-28T10:11:06Z)
• Be Greedy in Multi-Armed Bandits [22.301793734117805]
  グレディアルゴリズムは、各ラウンドで局所最適選択を行う、シーケンシャルな決定問題の最も単純なものである。 We provide a generic worst-case bound on the regret of the Greedy algorithm。 連続・無限・多武装バンディット問題において,ほぼ最適の最悪の後悔境界を検証できることを証明した。
  論文  参考訳（メタデータ） (2021-01-04T16:47:02Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits [61.490254407420906]
  我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。 本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
  論文  参考訳（メタデータ） (2020-11-05T05:16:04Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。 以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
  論文  参考訳（メタデータ） (2016-11-30T17:37:51Z)

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

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