論文の概要: Achieving Near-Optimal Regret for Bandit Algorithms with Uniform Last-Iterate Guarantee

• arxiv url: http://arxiv.org/abs/2402.12711v1
• Date: Tue, 20 Feb 2024 04:21:13 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-21 17:11:37.933307
• Title: Achieving Near-Optimal Regret for Bandit Algorithms with Uniform Last-Iterate Guarantee
• Title（参考訳）: 一様最終保証付き帯域アルゴリズムの準最適レグレを得る
• Authors: Junyan Liu, Yunfan Li, Lin Yang
• Abstract要約: 本稿では,バンドレートアルゴリズムの累積性能と即時性能を両立させる,より強力な性能尺度,ULI(Universal Last-iterate)の保証を提案する。 以上の結果から, ほぼ最適なULI保証は, 上記の性能指標にまたがって, ほぼ最適な累積性能を直接的に示唆することを示す。
• 参考スコア（独自算出の注目度）: 10.159410396698929
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Existing performance measures for bandit algorithms such as regret, PAC bounds, or uniform-PAC (Dann et al., 2017), typically evaluate the cumulative performance, while allowing the play of an arbitrarily bad arm at any finite time t. Such a behavior can be highly detrimental in high-stakes applications. This paper introduces a stronger performance measure, the uniform last-iterate (ULI) guarantee, capturing both cumulative and instantaneous performance of bandit algorithms. Specifically, ULI characterizes the instantaneous performance since it ensures that the per-round regret of the played arm is bounded by a function, monotonically decreasing w.r.t. (large) round t, preventing revisits to bad arms when sufficient samples are available. We demonstrate that a near-optimal ULI guarantee directly implies near-optimal cumulative performance across aforementioned performance measures. To examine the achievability of ULI in the finite arm setting, we first provide two positive results that some elimination-based algorithms and high-probability adversarial algorithms with stronger analysis or additional designs, can attain near-optimal ULI guarantees. Then, we also provide a negative result, indicating that optimistic algorithms cannot achieve a near-optimal ULI guarantee. Finally, we propose an efficient algorithm for linear bandits with infinitely many arms, which achieves the ULI guarantee, given access to an optimization oracle.
• Abstract（参考訳）: 後悔、PACバウンダリ、均一PAC(Dann et al., 2017)のような既存のバンディットアルゴリズムのパフォーマンス測定は、一般に累積性能を評価し、任意の有限時間tでの任意に悪い腕の演奏を可能にする。 このような振る舞いは、高スループットアプリケーションでは極めて有害である。 本稿では,バンドレートアルゴリズムの累積性能と即時性能を両立させる,より強力な性能尺度,ULI保証を提案する。 特に、ULIは、演奏腕の丸ごとの後悔が機能によって束縛されていることを保証し、w.r.t.(大きな)ラウンドtを単調に減少させ、十分なサンプルが得られれば、悪い腕への再訪を防止するため、即時のパフォーマンスを特徴付ける。 以上の結果から, ほぼ最適ULI保証は, 上記の性能指標のほぼ最適累積性能を直接意味することを示す。 有限アーム設定におけるuliの到達可能性を調べるために,まず,削除に基づくアルゴリズムと,より強力な解析や追加設計を持つ高確率逆アルゴリズムの2つの正の結果を提示する。 さらに,楽観的アルゴリズムでは至近距離 uli 保証が達成できないことを示す負の結果も提示する。 最後に,最適化オラクルへのアクセスによってuli保証を実現する,無限個のアームを持つ線形バンディットに対する効率的なアルゴリズムを提案する。

関連論文リスト

• Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization [37.24692425018]
  Emphconstrained MDPs(CMDPs)におけるオンライン学習の研究 提案アルゴリズムは, 対向型MDPに対して, 最先端のポリシー最適化アプローチを採用するプリミティブ・デュアル・スキームを実装している。
  論文  参考訳（メタデータ） (2024-10-03T07:54:04Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• Iteratively Refined Behavior Regularization for Offline Reinforcement Learning [57.10922880400715]
  本稿では,保守的政策反復に基づく行動規則化を大幅に強化する新しいアルゴリズムを提案する。 行動規則化に使用される基準ポリシーを反復的に洗練することにより、保守的な政策更新は徐々に改善される。 D4RLベンチマークの実験結果から,本手法は従来のタスクのベースラインよりも優れていたことが示唆された。
  論文  参考訳（メタデータ） (2023-06-09T07:46:24Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。 IRLの多くのアルゴリズムは本質的にネスト構造を持つ。 我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T17:13:45Z)
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation [92.3161051419884]
  線形関数近似を用いた強化学習について検討する。 既存のアルゴリズムは、高い確率的後悔と/またはおよそ正当性(PAC)サンプルの複雑さの保証しか持たない。 我々はFLUTEと呼ばれる新しいアルゴリズムを提案し、高い確率で最適ポリシーへの均一PAC収束を享受する。
  論文  参考訳（メタデータ） (2021-06-22T08:48:56Z)
• Provably Efficient Algorithms for Multi-Objective Competitive RL [54.22598924633369]
  エージェントの報酬がベクトルとして表現される多目的強化学習(RL)について検討する。 エージェントが相手と競合する設定では、その平均戻りベクトルから目標セットまでの距離によってその性能を測定する。 統計的および計算学的に効率的なアルゴリズムを開発し、関連するターゲットセットにアプローチする。
  論文  参考訳（メタデータ） (2021-02-05T14:26:00Z)
• Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
  オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。 我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-01T17:59:19Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。 そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2020-08-18T04:34:21Z)

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

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