論文の概要: End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions

• arxiv url: http://arxiv.org/abs/2603.23461v1
• Date: Tue, 24 Mar 2026 17:32:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-25 19:53:37.612485
• Title: End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions
• Title（参考訳）: 決定論的遷移を持つ線形ベルマン完全MDPの終端終端効率RL
• Authors: Zakaria Mhammedi, Alexander Rakhlin, Nneka Okolo,
• Abstract要約: 決定過程(MDP)における線形関数近似を用いた強化学習の研究 本稿では, 線形ベルマン完全オラクルに対して, 決定論的遷移, 初期状態, 報奨を伴う計算効率のよいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 66.17960480460185
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study reinforcement learning (RL) with linear function approximation in Markov Decision Processes (MDPs) satisfying \emph{linear Bellman completeness} -- a fundamental setting where the Bellman backup of any linear value function remains linear. While statistically tractable, prior computationally efficient algorithms are either limited to small action spaces or require strong oracle assumptions over the feature space. We provide a computationally efficient algorithm for linear Bellman complete MDPs with \emph{deterministic transitions}, stochastic initial states, and stochastic rewards. For finite action spaces, our algorithm is end-to-end efficient; for large or infinite action spaces, we require only a standard argmax oracle over actions. Our algorithm learns an $\varepsilon$-optimal policy with sample and computational complexity polynomial in the horizon, feature dimension, and $1/\varepsilon$.
• Abstract（参考訳）: 本稿では,任意の線形値関数のベルマンバックアップが線形である基本的条件である 'emph{linear Bellman completeness} を満たすマルコフ決定過程 (MDP) において,線形関数近似を用いた強化学習 (RL) について検討する。 統計的に抽出可能であるが、事前の計算効率のよいアルゴリズムは小さな作用空間に限られるか、特徴空間上で強いオラクル仮定を必要とする。 本稿では, 線形ベルマン完全MDPに対して, 確率的初期状態, 確率的報酬を用いた計算効率の良いアルゴリズムを提案する。 有限作用空間の場合、我々のアルゴリズムはエンドツーエンドで効率的であり、大または無限の作用空間の場合、作用上の標準的なargmaxオラクルしか必要としない。 我々のアルゴリズムは、水平線、特徴次元、および1/\varepsilon$のサンプルおよび計算複雑性多項式を持つ、$\varepsilon$-optimal Policyを学習する。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics [39.07258580928359]
  線形ベルマン完全設定に対する計算的および統計的に効率的な強化学習アルゴリズムについて検討する。 この設定では線形関数近似を用いて値関数をキャプチャし、線形マルコフ決定プロセス(MDP)や線形二次レギュレータ(LQR)のような既存のモデルを統一する。 我々の研究は、線形ベルマン完全設定のための計算効率の良いアルゴリズムを提供し、大きなアクション空間、ランダムな初期状態、ランダムな報酬を持つMDPに対して機能するが、決定論的となる基礎となる力学に依存している。
  論文  参考訳（メタデータ） (2024-06-17T17:52:38Z)
• Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions [29.69428894587431]
  ベルマンが成り立つと仮定し、これらの回帰問題が十分に特定されていることを保証している。 数作用が定数であるとき、線形ベルマンの下でRLの最初の特別なアルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-06-17T15:24:49Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
  論文  参考訳（メタデータ） (2022-12-12T18:58:59Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
  我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。 我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。 また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
  論文  参考訳（メタデータ） (2021-02-17T18:54:08Z)

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

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