論文の概要: 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 Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - 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) - Typical and atypical solutions in non-convex neural networks with
discrete and continuous weights [2.7127628066830414]
ランダムな規則や関連を学習する単純な非拘束型ネットワークモデルとして、二項および連続負マージンパーセプトロンについて検討する。
どちらのモデルも、非常に平坦で幅の広い劣支配的な最小化器を示す。
両モデルにおいて、学習装置としての一般化性能は、広い平坦な最小化器の存在により大幅に向上することを示した。
論文 参考訳(メタデータ) (2023-04-26T23:34:40Z) - 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) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳(メタデータ) (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。