論文の概要: A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms

• arxiv url: http://arxiv.org/abs/2106.02126v1
• Date: Thu, 3 Jun 2021 20:52:26 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-07 15:20:24.132799
• Title: A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms
• Title（参考訳）: マルチアームバンディットアルゴリズムの最悪の動作をよく見る
• Authors: Anand Kalvit and Assaf Zeevi
• Abstract要約: アッパー信頼境界 (UCB) は楽観的なMABアルゴリズムである。 本稿では,UCBのアームサンプリング動作に関する新しい知見を提供する。 また、UPBの下でのMAB問題のプロセスレベルの特徴付けも提供する。
• 参考スコア（独自算出の注目度）: 8.099977107670918
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One of the key drivers of complexity in the classical (stochastic) multi-armed bandit (MAB) problem is the difference between mean rewards in the top two arms, also known as the instance gap. The celebrated Upper Confidence Bound (UCB) policy is among the simplest optimism-based MAB algorithms that naturally adapts to this gap: for a horizon of play n, it achieves optimal O(log n) regret in instances with "large" gaps, and a near-optimal O(\sqrt{n log n}) minimax regret when the gap can be arbitrarily "small." This paper provides new results on the arm-sampling behavior of UCB, leading to several important insights. Among these, it is shown that arm-sampling rates under UCB are asymptotically deterministic, regardless of the problem complexity. This discovery facilitates new sharp asymptotics and a novel alternative proof for the O(\sqrt{n log n}) minimax regret of UCB. Furthermore, the paper also provides the first complete process-level characterization of the MAB problem under UCB in the conventional diffusion scaling. Among other things, the "small" gap worst-case lens adopted in this paper also reveals profound distinctions between the behavior of UCB and Thompson Sampling, such as an "incomplete learning" phenomenon characteristic of the latter.
• Abstract（参考訳）: mab(classic (stochastic) multi-armed bandit)問題における複雑さの鍵となる要因の1つは、上位2つの腕の平均報酬(インスタンスギャップ)の違いである。 有名なuper confidence bound(ucb)ポリシーは、このギャップに自然に適応する最も単純なオプティミズムベースのmabアルゴリズムの1つである: プレイnの地平線に対して、"大きな"ギャップを持つインスタンスにおいて最適なo(log n)後悔を達成し、ギャップが任意に"小さい"場合に、至近のオプティミズムo(\sqrt{n log n})ミニマックス後悔を達成する。 本稿では,ucbのアームサンプリング動作に関する新たな結果について述べる。 これらのうち, UCB におけるアームサンプリング率は, 問題複雑性に関係なく, 漸近的に決定論的であることが示されている。 この発見は、新しい鋭い漸近と、 UCB の O(\sqrt{n log n}) ミニマックス後悔の新たな証明を促進する。 さらに,従来の拡散スケーリングにおけるUPBの下でのMAB問題の完全なプロセスレベル評価も提供する。 この論文で採用されている「小さな」ギャップの最悪ケースレンズは、後者の特徴である「不完全学習」のような、ucbとトンプソンサンプリングの挙動の明確な区別も明らかにしている。

関連論文リスト

• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Little Exploration is All You Need [1.9321472560290351]
  マルチアームバンディット問題において,標準 UCB アルゴリズムの新たな修正を導入する。 タスクの難易度を考慮に入れた$tau > 1/2$の調整付きボーナス項を提案する。 UCB$tau$と表記される提案アルゴリズムは,包括的後悔とリスク分析によって検証される。
  論文  参考訳（メタデータ） (2023-10-26T16:28:29Z)
• Simple Modification of the Upper Confidence Bound Algorithm by Generalized Weighted Averages [0.0]
  マルチアームバンディット問題(英: multi-armed bandit problem、MAB)は、強化学習の不確実性の下で連続的な意思決定をモデル化する古典的な問題である。 我々は,MAB問題の代表的なアルゴリズムである UCB1 を拡張して,新しい一般化された高信頼度境界(GWA-UCB1)アルゴリズムを提案する。 GWA-UCB1 は G-UCB1 や UCB1-Tuned 、Thompson よりも多くの問題設定で優れており、多くの状況で有用である。
  論文  参考訳（メタデータ） (2023-08-28T06:53:31Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Complexity Analysis of a Countable-armed Bandit Problem [9.163501953373068]
  遊びの地平線上で期待される累積的後悔を最小限に抑えるという古典的問題を考察する。 我々は、$K=2$のとき、$mathcalOleft(log n right)$の率最適有限時間インスタンス依存後悔を実現するアルゴリズムを提案する。 問題に対する後悔の順序と複雑さは、古典的MAB問題と非常に類似していることを示しているが、アルゴリズム設計における性能境界の特性と健全な側面は、後者とはかなり異なる。
  論文  参考訳（メタデータ） (2023-01-18T00:53:46Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms [10.662105162882526]
  本研究は,Emphmany-armed regimeにおける$k$-armed bandit問題について考察する。 以上の結果から,多腕の環境下での強欲なアルゴリズムには,新たなエフェフリー探索法が有用であることが示唆された。
  論文  参考訳（メタデータ） (2020-02-24T08:59:34Z)

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

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