論文の概要: Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2402.12711v2
• Date: Thu, 31 Oct 2024 08:13:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-01 16:59:13.520124
• Title: Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learning
• Title（参考訳）: バンドと強化学習のための一様最終保証
• Authors: Junyan Liu, Yunfan Li, Ruosong Wang, Lin F. Yang,
• Abstract要約: 本稿では,強化学習アルゴリズムの累積性能と即時性能を両立させる,より強力な測度,一様ラストイテレート(ULI)保証を提案する。 ほぼ最適のULI保証は、上記のメトリクス間で、直接的に、ほぼ最適の累積性能を意味するが、その逆ではないことを実証する。
• 参考スコア（独自算出の注目度）: 26.07010600520053
• License:
• Abstract: Existing metrics for reinforcement learning (RL) such as regret, PAC bounds, or uniform-PAC (Dann et al., 2017), typically evaluate the cumulative performance, while allowing the agent to play an arbitrarily bad policy at any finite time t. Such a behavior can be highly detrimental in high-stakes applications. This paper introduces a stronger metric, uniform last-iterate (ULI) guarantee, capturing both cumulative and instantaneous performance of RL algorithms. Specifically, ULI characterizes the instantaneous performance by ensuring that the per-round suboptimality of the played policy is bounded by a function, monotonically decreasing w.r.t. round t, preventing revisiting bad policies when sufficient samples are available. We demonstrate that a near-optimal ULI guarantee directly implies near-optimal cumulative performance across aforementioned metrics, but not the other way around. To examine the achievability of ULI, we first provide two positive results for bandit problems with finite arms, showing that elimination-based algorithms and high-probability adversarial algorithms with stronger analysis or additional designs, can attain near-optimal ULI guarantees. We also provide a negative result, indicating that optimistic algorithms cannot achieve near-optimal ULI guarantee. Furthermore, we propose an efficient algorithm for linear bandits with infinitely many arms, which achieves the ULI guarantee, given access to an optimization oracle. Finally, we propose an algorithm that achieves near-optimal ULI guarantee for the online reinforcement learning setting.
• Abstract（参考訳）: 後悔、PAC境界、均一PAC(Dann et al , 2017)のような既存の強化学習(RL)の指標は、一般に累積的性能を評価し、エージェントが任意の有限時間tで任意に悪いポリシーを実行できる。 このような振舞いは、高精細な応用において非常に有害である。 本稿では,RLアルゴリズムの累積性能と瞬時性能を両立させるため,より強力な測度,一様ラストイテレート(ULI)保証を提案する。 具体的には、ULIは、プレイポリシーのラウンドごとのサブ最適度が関数によって制限されることを保証し、ラウンドtを単調に減少させ、十分なサンプルが得られれば悪いポリシーの再検討を防止することにより、即時のパフォーマンスを特徴付ける。 ほぼ最適のULI保証は、上記のメトリクス間で、直接的に、ほぼ最適の累積性能を意味するが、その逆ではないことを実証する。 ULIの達成可能性を検討するために、まず、有限腕のバンドイット問題に対する2つの肯定的な結果を提供し、より強力な解析や追加設計による除去に基づくアルゴリズムと高確率逆アルゴリズムが、ほぼ最適のULI保証が得られることを示した。 また, 楽観的アルゴリズムでは, ほぼ最適ULI保証を達成できないという否定的な結果も提示する。 さらに、最適化オラクルへのアクセスを前提として、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)

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

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