論文の概要: Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits

• arxiv url: http://arxiv.org/abs/2505.20268v1
• Date: Mon, 26 May 2025 17:44:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-28 14:37:20.360902
• Title: Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits
• Title（参考訳）: アウトカムベースオンライン強化学習:アルゴリズムと基本限界
• Authors: Fan Chen, Zeyu Jia, Alexander Rakhlin, Tengyang Xie,
• Abstract要約: 結果に基づくフィードバックによる強化学習は、根本的な課題に直面します。 適切なアクションにクレジットを割り当てるには? 本稿では,一般関数近似を用いたオンラインRLにおけるこの問題の包括的解析を行う。
• 参考スコア（独自算出の注目度）: 58.63897489864948
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reinforcement learning with outcome-based feedback faces a fundamental challenge: when rewards are only observed at trajectory endpoints, how do we assign credit to the right actions? This paper provides the first comprehensive analysis of this problem in online RL with general function approximation. We develop a provably sample-efficient algorithm achieving $\widetilde{O}({C_{\rm cov} H^3}/{\epsilon^2})$ sample complexity, where $C_{\rm cov}$ is the coverability coefficient of the underlying MDP. By leveraging general function approximation, our approach works effectively in large or infinite state spaces where tabular methods fail, requiring only that value functions and reward functions can be represented by appropriate function classes. Our results also characterize when outcome-based feedback is statistically separated from per-step rewards, revealing an unavoidable exponential separation for certain MDPs. For deterministic MDPs, we show how to eliminate the completeness assumption, dramatically simplifying the algorithm. We further extend our approach to preference-based feedback settings, proving that equivalent statistical efficiency can be achieved even under more limited information. Together, these results constitute a theoretical foundation for understanding the statistical properties of outcome-based reinforcement learning.
• Abstract（参考訳）: 結果に基づくフィードバックによる強化学習は、基本的な課題に直面している。 本稿では,一般関数近似を用いたオンラインRLにおけるこの問題の包括的解析を行う。 C_{\rm cov}/{\epsilon^2}) $\widetilde{O}({C_{\rm cov} H^3}/{\epsilon^2})$ sample complexity, where $C_{\rm cov}$ is the coverability coefficient of the underlying MDP。 一般関数近似の活用により,表型メソッドが失敗する大あるいは無限の状態空間で効果的に機能し,値関数と報酬関数を適切な関数クラスで表す必要がある。 また,結果に基づくフィードバックがステップごとの報酬から統計的に切り離された場合にも特徴的であり,特定のMDPに対して避けられない指数的分離が明らかとなった。 決定論的 MDP に対して,完全性仮定の除去方法を示し,アルゴリズムを劇的に単純化する。 我々は、より限られた情報の下でも等価な統計的効率が達成できることを証明し、嗜好に基づくフィードバック設定へのアプローチをさらに拡張する。 これらの結果は、結果に基づく強化学習の統計的性質を理解するための理論的基盤となっている。

関連論文リスト

• Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation [8.378137704007038]
  有限エピソードマルコフ決定過程における一般値関数近似を用いた分布強化学習の後悔の解析を行った。 証明可能なアルゴリズムである$textttSF-LSVI$を提案し、$tildeO(d_E Hfrac32sqrtK)$で、$H$は地平線、$K$はエピソード数、$d_E$は関数クラスの退化次元である。
  論文  参考訳（メタデータ） (2024-07-31T00:43:51Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• Offline Reinforcement Learning with Additional Covering Distributions [0.0]
  我々は,関数近似を用いて,ログ化されたデータセット,すなわちオフラインRLから最適ポリシーを学習する。 一般のMDPに対するサンプル効率のよいオフラインRLは、部分的カバレッジデータセットと弱い実現可能な関数クラスだけで実現可能であることを示す。
  論文  参考訳（メタデータ） (2023-05-22T03:31:03Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。 このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
  論文  参考訳（メタデータ） (2022-06-01T23:26:51Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。 そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2020-08-18T04:34:21Z)

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

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