論文の概要: 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は、現在の最高の腕を毎回引っ張る欲張りアルゴリズムよりも数値的に劣る。
これらの経験的洞察は、実データ上のシミュレーションを使用して、文脈的にも保持される。
これらの結果は,多武装体制における新たな自由探索形態を示唆する。
理論的には、この自由探索の源泉は、腕の報酬の事前分布のための尾イベントの分布と深く関係していることが示される。
これは、文脈的包帯に関する最近の文献で論じられているように、共変量の変化による自由探索とは根本的に異なる現象である。
この結果に基づいて, サブサンプルグリードアルゴリズムが, 多くの武装体制におけるベルヌーイの盗賊に対するレート最適化であることを証明し, より一般的な分布でサブ線形後悔を実現する。
以上の結果から,多武器体制における欲求的アルゴリズムの活用のメリットが示唆された。
関連論文リスト
- Zero-Inflated Bandits [12.675908271908048]
ゼロ膨らんだ帯状地について検討し、報酬をゼロ膨らんだ分布と呼ばれる古典的な半パラメトリック分布としてモデル化する。
我々のアルゴリズムは、非常に一般的な報酬分布のクラスに適合し、典型的なガウス以下の要件よりもかなり厳密な尾仮定の下で機能する。
理論的には、多武装バンディットに対するUTBアルゴリズムとTSアルゴリズムの両方の後悔境界を導出し、報酬分布がガウス以下の場合、その確率-最適後悔を達成できることを示す。
論文 参考訳(メタデータ) (2023-12-25T03:13:21Z) - 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) - Contextual Combinatorial Volatile Bandits via Gaussian Processes [10.312968200748116]
利用可能なベースアームのセットとそのコンテキストによるコンテキスト的バンディット問題を考える。
我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。
両アルゴリズムが従来のUTBベースのアルゴリズムを現実的な設定で大幅に上回っていることを実験的に示す。
論文 参考訳(メタデータ) (2021-10-05T18:02:10Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳(メタデータ) (2021-03-03T23:08:59Z) - 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) - Restless-UCB, an Efficient and Low-complexity Algorithm for Online
Restless Bandits [61.490254407420906]
我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。
本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
論文 参考訳(メタデータ) (2020-11-05T05:16:04Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳(メタデータ) (2020-07-07T09:00:57Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z) - Bandit algorithms to emulate human decision making using probabilistic
distortions [20.422725678982726]
報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。
以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
論文 参考訳(メタデータ) (2016-11-30T17:37:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。