論文の概要: Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation

• arxiv url: http://arxiv.org/abs/2605.00393v1
• Date: Fri, 01 May 2026 04:32:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-04 17:43:28.844296
• Title: Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation
• Title（参考訳）: 政策最適化とオフライン推定における二重Oracle効率を用いたモデルベース強化学習
• Authors: Haichen Hu, Jian Qian, David Simchi-Levi,
• Abstract要約: 大規模環境での強化学習(RL)は、しばしば深刻な計算ボトルネックに悩まされる。 我々は,$O(Hloglog T)$呼び出しのみを必要としながら,最適な$tildeO(sqrtT)$後悔境界を達成する新しいアルゴリズムを提案する。 このオラクルの複雑さは状態空間と作用空間のサイズとは全く無関係である。
• 参考スコア（独自算出の注目度）: 21.36054923028733
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reinforcement learning (RL) in large environments often suffers from severe computational bottlenecks, as conventional regret minimization algorithms require repeated, costly calls to planning and statistical estimation oracles. While recent advances have explored offline oracle-efficient algorithms, their computational complexity typically scales with the cardinality of the state and action spaces, rendering them intractable for large-scale or continuous environments. In this paper, we address this fundamental limitation by studying offline oracle-efficient episodic RL through the lens of log-barrier and log-determinant regularization. Specifically, for tabular Markov Decision Processes (MDPs), we propose a novel algorithm that achieves the optimal $\tilde{O}(\sqrt{T})$ regret bound while requiring only $O(H\log\log T)$ calls to both the offline statistical estimation and planning oracles when $T$ is known and $O(H\log T)$ calls when $T$ is unknown. Crucially, this oracle complexity is entirely independent of the size of the state and action spaces. This strict independence drastically reduces the planning oracle complexity, representing a substantial improvement over existing offline oracle-efficient algorithms (Qian et al., 2024). Furthermore, we demonstrate the versatility of our framework by generalizing the algorithm to linear MDPs featuring infinite state spaces and arbitrary action spaces. We prove that this generalized approach successfully attains meaningful sub-linear regret. Consequently, our work yields the first doubly oracle-efficient (i.e., efficient with respect to both statistical estimation and policy optimization) regret minimization algorithm capable of solving MDPs with infinite state and action spaces, significantly expanding the boundaries of computationally tractable RL.
• Abstract（参考訳）: 大規模環境における強化学習(RL)は、しばしば深刻な計算ボトルネックに悩まされる。 最近の進歩はオフラインのオラクル効率のアルゴリズムを探索しているが、それらの計算複雑性は一般に状態空間や行動空間の濃度とともにスケールし、大規模または連続的な環境においてそれらを引き付けることができる。 本稿では、対数バリアと対数行列正則化のレンズを用いて、オフラインオラクル効率のエピソードRLを研究することにより、この基本的な制限に対処する。 具体的には、表形式のマルコフ決定プロセス(MDP)に対して、$O(H\log\log T)と$O(H\log T)と$T$が未知の場合に、オフラインの統計的推定と計画のオーラクルの両方を呼び出しながら、最適な$\tilde{O}(\sqrt{T})$後悔境界を達成する新しいアルゴリズムを提案する。 重要なことに、このオラクルの複雑さは状態空間と作用空間のサイズとは全く独立である。 この厳格な独立は、計画オラクルの複雑さを大幅に減らし、既存のオフラインオラクル効率アルゴリズム(Qian et al , 2024)よりも大幅に改善されている。 さらに,無限の状態空間と任意の行動空間を特徴とする線形MDPにアルゴリズムを一般化することにより,フレームワークの汎用性を実証する。 この一般化されたアプローチが有意義なサブ線形後悔を達成できたことを証明している。 その結果, 2次オラクル効率(すなわち, 統計的推定と政策最適化の両面での効率)の最小化アルゴリズムは, MDPを無限の状態と作用空間で解くことができ, 計算処理可能なRLの境界を大きく広げることができる。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions [66.17960480460185]
  決定過程(MDP)における線形関数近似を用いた強化学習の研究 本稿では, 線形ベルマン完全オラクルに対して, 決定論的遷移, 初期状態, 報奨を伴う計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-24T17:32:29Z)
• Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation [32.74649239695449]
  制約決定過程(CMDP)における強化学習問題について検討する。 本稿では,リニアCMDPに対するRLアルゴリズムを提案する。 その結果,近年の線形CMDPアルゴリズムでは,制約に違反するか,指数計算コストに悪影響を及ぼす結果が得られた。
  論文  参考訳（メタデータ） (2025-02-14T13:07:25Z)
• Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions [10.225358400539719]
  本稿では,線形作用が特徴写像に一般化される決定法(MDP)の効率的な強化アルゴリズムを提案する。 具体的には、この設定において、最適に近いポリシーを効率的に見つける新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-07T14:38:05Z)
• Tractable Offline Learning of Regular Decision Processes [50.11277112628193]
  この研究は、正則決定過程(RDP)と呼ばれる非マルコフ環境のクラスにおけるオフライン強化学習(RL)を研究する。 インスは、未来の観測と過去の相互作用からの報酬の未知の依存を実験的に捉えることができる。 多くのアルゴリズムは、まずこの未知の依存関係を自動学習技術を用いて再構築する。
  論文  参考訳（メタデータ） (2024-09-04T14:26:58Z)
• RL in Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Model [15.596599935486534]
  シミュレータへの局所アクセスを伴う粗相関平衡(CCE)を学習するための新しいアルゴリズムLin-Confident-FTRLを導入する。 状態空間のサイズに対数的依存がある限り、Lin-Confident-FTRLは証明可能な最適精度で$O(epsilon-2)$で$epsilon$-CCEを学ぶ。 本分析は,単一エージェントのローカルプランニング文献における仮想ポリシー境界を一般化する。
  論文  参考訳（メタデータ） (2024-03-18T07:54:11Z)
• Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration [87.53543137162488]
  我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。 textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。 様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
  論文  参考訳（メタデータ） (2023-05-29T17:25:26Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)

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

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