論文の概要: A Blackbox Approach to Best of Both Worlds in Bandits and Beyond
- arxiv url: http://arxiv.org/abs/2302.09739v1
- Date: Mon, 20 Feb 2023 03:42:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-21 16:57:09.222732
- Title: A Blackbox Approach to Best of Both Worlds in Bandits and Beyond
- Title(参考訳): ブラックボックスによるバンディットとそれ以上の世界のベストを尽くすアプローチ
- Authors: Christoph Dann, Chen-Yu Wei, Julian Zimmert
- Abstract要約: オンライン学習のためのベスト・オブ・ザ・ワールドズ(Best-of-worlds)アルゴリズムは、敵対政権と敵対政権の両方において、ほぼ最適に後悔する。
両世界の長所から、フォロー・ザ・レギュラライズド・リーダー(FTRL)とオンライン・ミラーダネッセンス(OMD)アルゴリズムの幅広いファミリーへの一般化を提案する。
- 参考スコア(独自算出の注目度): 33.13041034490332
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Best-of-both-worlds algorithms for online learning which achieve near-optimal
regret in both the adversarial and the stochastic regimes have received growing
attention recently. Existing techniques often require careful adaptation to
every new problem setup, including specialised potentials and careful tuning of
algorithm parameters. Yet, in domains such as linear bandits, it is still
unknown if there exists an algorithm that can simultaneously obtain
$O(\log(T))$ regret in the stochastic regime and $\tilde{O}(\sqrt{T})$ regret
in the adversarial regime. In this work, we resolve this question positively
and present a general reduction from best of both worlds to a wide family of
follow-the-regularized-leader (FTRL) and online-mirror-descent (OMD)
algorithms. We showcase the capability of this reduction by transforming
existing algorithms that are only known to achieve worst-case guarantees into
new algorithms with best-of-both-worlds guarantees in contextual bandits, graph
bandits and tabular Markov decision processes.
- Abstract(参考訳): オンライン学習のための最善の両世界のアルゴリズムは、敵対者と確率的体制の両方において、ほぼ最適の後悔を達成している。
既存の手法では、特殊ポテンシャルやアルゴリズムパラメータの注意調整など、新しい問題の設定に注意深く適応する必要があることが多い。
しかし、線形バンドイットのような領域では、確率的レジームにおいて$o(\log(t))$の後悔と、敵対的レジームで$\tilde{o}(\sqrt{t})$の後悔を同時に得るアルゴリズムが存在するかどうかはまだ不明である。
本稿では,この問題を肯定的に解決し,両世界の最善点から,フォロー・ザ・レギュラライズド・リーダー(ftrl)とオンラインミラー・ダイニング(omd)アルゴリズムの広いファミリーへと一般還元する。
我々は,コンテキストバンディット,グラフバンディット,表型マルコフ決定プロセスにおいて,最善の両世界保証を持つ新たなアルゴリズムに,最悪の保証を達成するためにのみ知られている既存のアルゴリズムを変換することで,この削減の能力を示す。
関連論文リスト
- Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。
UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。
我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
論文 参考訳(メタデータ) (2024-05-24T04:11:58Z) - Stability-penalty-adaptive follow-the-regularized-leader: Sparsity,
game-dependency, and best-of-both-worlds [46.30750729936261]
FTRL(Follow-the-regularized-leader)は近年,バンドイット問題における適応性獲得の最も有望なアプローチの1つである。
我々は3種類の適応性を持ついくつかのアルゴリズムを確立する:空間性、ゲーム依存性、およびベスト・オブ・ボス・ワールド(BOBW)である。
論文 参考訳(メタデータ) (2023-05-26T23:20:48Z) - Best-of-three-worlds Analysis for Linear Bandits with
Follow-the-regularized-leader Algorithm [11.80907528239756]
線形バンディット問題は、双方の相反する環境で長年研究されてきた。
citetLeeLWZ021は、損失タイプを積極的に検出し、特定の設定のために特別に設計された異なるアルゴリズムを切り替えるアルゴリズムを提案する。
FTRL(Follow-the-regularized-leader)は、異なる環境に適応可能な人気アルゴリズムの一種である。
論文 参考訳(メタデータ) (2023-03-13T02:50:59Z) - A Framework for Adapting Offline Algorithms to Solve Combinatorial
Multi-Armed Bandit Problems with Bandit Feedback [27.192028744078282]
離散オフライン近似アルゴリズムをサブ線形$alpha$-regretに適応するためのフレームワークを提供する。
提案手法は準モジュラー地平線における多種多様な応用に適用できる。
論文 参考訳(メタデータ) (2023-01-30T23:18:06Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳(メタデータ) (2020-12-28T17:19:32Z) - Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
バンディットアルゴリズムを結合する簡単な手法を提案する。
私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
論文 参考訳(メタデータ) (2020-12-24T05:36:29Z) - Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。
我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
論文 参考訳(メタデータ) (2020-11-01T17:59:19Z) - Corralling Stochastic Bandit Algorithms [54.10645564702416]
相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。
最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
論文 参考訳(メタデータ) (2020-06-16T15:33:12Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳(メタデータ) (2020-03-03T18:46:34Z) - Bandit algorithms to emulate human decision making using probabilistic
distortions [20.422725678982726]
報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。
以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
論文 参考訳(メタデータ) (2016-11-30T17:37:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。