論文の概要: 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)アルゴリズムの広いファミリーへと一般還元する。 我々は,コンテキストバンディット,グラフバンディット,表型マルコフ決定プロセスにおいて,最善の両世界保証を持つ新たなアルゴリズムに,最悪の保証を達成するためにのみ知られている既存のアルゴリズムを変換することで,この削減の能力を示す。

関連論文リスト

• Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback [34.7178680288326]
  Stradi et al.(2024) は、マルコフ決定過程に制約のある最初のベスト・オブ・ボス・ワールドズ・アルゴリズムを提案した。 本稿では,CMDPにおける帯域幅フィードバックを用いたベスト・オブ・ワールドズ・アルゴリズムを提案する。 本アルゴリズムは政策最適化手法に基づいており, 占有率に基づく手法よりも効率的である。
  論文  参考訳（メタデータ） (2024-10-03T07:44:40Z)
• Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits [6.7310264583128445]
  FTRL (Follow-The-Regularized-Leader) アルゴリズムは、しばしば敵対的問題や盗賊問題に対して最適な後悔を味わう。 本稿では,逆方向と多重方向の両方の帯域に対して最適なポリシを生成する新しいFTPLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-30T16:00:23Z)
• 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)
• 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)

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

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