論文の概要: Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPs

• arxiv url: http://arxiv.org/abs/2605.01242v1
• Date: Sat, 02 May 2026 04:46:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-05 20:33:49.662575
• Title: Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPs
• Title（参考訳）: 計算障壁を破る:低ランクMDPにおけるアクター・クリティカルの可能性
• Authors: Ruiquan Huang, Donghao Li, Yingbin Liang, Jing Yang,
• Abstract要約: 低ランクマルコフ決定過程(MDPs)の下で広く採用されているRLオーラクルの階層を確立するために,教師付き学習を計算プロキシとして利用する。 本研究の目的は,政策評価にのみ依存する新しい楽観的アクター批判アルゴリズムを提案することである。 提案アルゴリズムは,従来の計算コストの高い計画や最適化オーラクルを回避しつつ,既存のサンプル複雑度保証よりも優れていることを示す。
• 参考スコア（独自算出の注目度）: 53.412166189410904
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reinforcement learning (RL) is a fundamental framework for sequential decision-making, in which an agent learns an optimal policy through interactions with an unknown environment. In settings with function approximation, many existing RL algorithms achieve favorable sample complexity, but often rely on computationally intractable oracles. In this paper, we use supervised learning as a computational proxy to establish a clear hierarchy of commonly adopted RL oracles under low-rank Markov Decision Processes (MDPs). This hierarchy shows that policy evaluation is the most computationally efficient oracle, provided that supervised learning can be efficiently solved. Motivated by this observation, we propose a novel optimistic actor-critic algorithm that relies solely on the policy evaluation oracle. We prove that our algorithm outperforms the existing sample complexity guarantees for low-rank MDPs while avoiding computationally expensive planning or optimization oracles commonly assumed in prior works. We further extend our theoretical results to approximately low-rank MDPs and demonstrate that this setting captures a broad class of real-world environments. Finally, we validate our theoretical results with experiments on several standard Gym environments.
• Abstract（参考訳）: 強化学習(Reinforcement Learning, RL)は、エージェントが未知の環境との相互作用を通じて最適な政策を学ぶための、シーケンシャルな意思決定のための基本的なフレームワークである。 関数近似を用いた設定では、多くの既存のRLアルゴリズムは好ましくサンプルの複雑さを達成するが、しばしば計算的に難解なオラクルに依存する。 本稿では、教師付き学習を計算プロキシとして使用し、低ランクマルコフ決定プロセス(MDP)の下で広く採用されているRLオーラクルの明確な階層を確立する。 この階層は、教師付き学習を効率的に解けることを前提として、ポリシー評価が最も計算効率のよいオラクルであることを示している。 本研究の目的は,政策評価にのみ依存する新しい楽観的アクター批判アルゴリズムを提案することである。 提案アルゴリズムは,従来の計算コストの高い計画や最適化オーラクルを回避しつつ,既存のサンプル複雑度保証よりも優れていることを示す。 我々はさらに、理論結果をおよそ低ランクのMDPにまで拡張し、この設定が現実世界の幅広い環境を捉えることを実証する。 最後に、いくつかの標準Gym環境における実験により、理論結果を検証した。

関連論文リスト

• Poly-EPO: Training Exploratory Reasoning Models [62.82992914206963]
  本稿では,学習後言語モデル(LM)の枠組みについて,楽観的な探索を明示的に奨励し,探索と搾取の相乗効果を促進する。 本稿では,この枠組みを探索と利用を明確に相乗化するための目的として,ポリクロミック探索政策最適化(Poly-EPO)を提案する。
  論文  参考訳（メタデータ） (2026-04-19T22:54:19Z)
• Agentic Reinforced Policy Optimization [66.96989268893932]
  検証可能な報酬付き大規模強化学習(RLVR)は,大規模言語モデル(LLM)を単一ターン推論タスクに活用する効果を実証している。 現在のRLアルゴリズムは、モデル固有のロングホライゾン推論能力と、マルチターンツールインタラクションにおけるその習熟性のバランスが不十分である。 エージェント強化ポリシー最適化(ARPO: Agentic Reinforced Policy Optimization)は,マルチターンLDMエージェントを学習するためのエージェントRLアルゴリズムである。
  論文  参考訳（メタデータ） (2025-07-26T07:53:11Z)
• Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions [10.225358400539719]
  本稿では,線形作用が特徴写像に一般化される決定法(MDP)の効率的な強化アルゴリズムを提案する。 具体的には、この設定において、最適に近いポリシーを効率的に見つける新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-07T14:38:05Z)
• Blending Imitation and Reinforcement Learning for Robust Policy Improvement [15.46204945792257]
  イミテーション学習(Imitation Learning, IL)は、オークルを用いてサンプル効率を向上させる。 RPIはILの強みを生かし、オラクルクエリを使って探索を容易にする。 RPIは多様なブラックボックスのオラクルから学習し、改善することができる。
  論文  参考訳（メタデータ） (2023-10-03T01:55:54Z)
• Provable Reward-Agnostic Preference-Based Reinforcement Learning [61.39541986848391]
  PbRL(Preference-based Reinforcement Learning)は、RLエージェントが、軌道上のペアワイドな嗜好に基づくフィードバックを用いてタスクを最適化することを学ぶパラダイムである。 本稿では,隠れた報酬関数の正確な学習を可能にする探索軌道を求める理論的報酬非依存PbRLフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-05-29T15:00:09Z)
• DEALIO: Data-Efficient Adversarial Learning for Imitation from Observation [57.358212277226315]
  観察ifoからの模倣学習において、学習エージェントは、実演者の生成した制御信号にアクセスせずに、実演行動の観察のみを用いて実演エージェントを模倣しようとする。 近年、逆模倣学習に基づく手法は、ifO問題に対する最先端のパフォーマンスをもたらすが、データ非効率でモデルなしの強化学習アルゴリズムに依存するため、サンプルの複雑さに悩まされることが多い。 この問題は、サンプルの収集が時間、エネルギー、およびリスクの面で高いコストを被る可能性がある現実世界の設定に展開することは非現実的です。 よりデータ効率の高いifOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-31T23:46:32Z)
• Reinforcement Learning with Algorithms from Probabilistic Structure Estimation [9.37335587960084]
  強化学習アルゴリズムは未知の環境で最適な決定を学習することを目的としている。 エージェントのアクションが環境に影響を及ぼすかどうかは、当初から不明である。 どのRLアルゴリズムが最も適しているかを決定することはしばしば不可能です。
  論文  参考訳（メタデータ） (2021-03-15T09:51:34Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。 そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2020-08-18T04:34:21Z)

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

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