論文の概要: Frozen Policy Iteration: Computationally Efficient RL under Linear $Q^π$ Realizability for Deterministic Dynamics
- arxiv url: http://arxiv.org/abs/2603.00716v1
- Date: Sat, 28 Feb 2026 15:41:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-03 19:50:56.336124
- Title: Frozen Policy Iteration: Computationally Efficient RL under Linear $Q^π$ Realizability for Deterministic Dynamics
- Title（参考訳）: 凍結政策反復:決定論的ダイナミクスに対する線形$Q^π$実現可能性の下での計算効率の良いRL
- Authors: Yijing Ke, Zihan Zhang, Ruosong Wang,
- Abstract要約: 線形な$Q$実現可能性仮定の下で,計算的および統計的に効率的な強化学習について検討する。
我々のアルゴリズムは、$widetildeO(sqrtd2H6T)$で、$d$は特徴空間の次元、$H$は地平線長、$T$はエピソードの総数である。
- 参考スコア（独自算出の注目度）: 23.744125839429415
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study computationally and statistically efficient reinforcement learning under the linear $Q^π$ realizability assumption, where any policy's $Q$-function is linear in a given state-action feature representation. Prior methods in this setting are either computationally intractable, or require (local) access to a simulator. In this paper, we propose a computationally efficient online RL algorithm, named Frozen Policy Iteration, under the linear $Q^π$ realizability setting that works for Markov Decision Processes (MDPs) with stochastic initial states, stochastic rewards and deterministic transitions. Our algorithm achieves a regret bound of $\widetilde{O}(\sqrt{d^2H^6T})$, where $d$ is the dimensionality of the feature space, $H$ is the horizon length, and $T$ is the total number of episodes. Our regret bound is optimal for linear (contextual) bandits which is a special case of our setting with $H = 1$. Existing policy iteration algorithms under the same setting heavily rely on repeatedly sampling the same state by access to the simulator, which is not implementable in the online setting with stochastic initial states studied in this paper. In contrast, our new algorithm circumvents this limitation by strategically using only high-confidence part of the trajectory data and freezing the policy for well-explored states, which ensures that all data used by our algorithm remains effectively on-policy during the whole course of learning. We further demonstrate the versatility of our approach by extending it to the Uniform-PAC setting and to function classes with bounded eluder dimension.
- Abstract（参考訳）: 線形な$Q^π$実現可能性仮定の下で、任意のポリシーの$Q$-函数が与えられた状態-作用特徴表現において線形であるような、計算的かつ統計的に効率的な強化学習について検討する。
この設定の以前の手法は、計算的に抽出可能であるか、シミュレータへの(局所的な)アクセスを必要とする。
本稿では,確率的初期状態,確率的報酬,決定論的遷移を伴うマルコフ決定プロセス(MDP)で動作する線形$Q^π$実現可能性設定の下で,凍結ポリシーイテレーション(Frozen Policy Iteration)という計算効率のよいオンラインRLアルゴリズムを提案する。
我々のアルゴリズムは、$\widetilde{O}(\sqrt{d^2H^6T})$, $d$は特徴空間の次元、$H$は地平線長、$T$はエピソードの総数である。
我々の後悔境界は線型(コンテキスト的)バンディットに対して最適であり、これは$H = 1$ の設定の特別な場合である。
同条件下での既存のポリシー反復アルゴリズムは、シミュレータへのアクセスによって同じ状態を繰り返しサンプリングすることに大きく依存しており、これは、確率的初期状態を持つオンライン設定では実装できない。
対照的に、我々の新しいアルゴリズムは、トラジェクトリデータの高信頼部分のみを戦略的に利用し、よく探索された状態に対するポリシーを凍結することにより、この制限を回避する。
さらに、Uniform-PAC設定に拡張し、有界なエリダー次元を持つクラスを機能させることにより、我々のアプローチの汎用性を実証する。
関連論文リスト
- Confident Natural Policy Gradient for Local Planning in $q_π$-realizable Constrained MDPs [44.69257217086967]
制約付きマルコフ決定プロセス(CMDP)フレームワークは、安全性や他の重要な目的を課すための重要な強化学習アプローチとして出現する。
本稿では,線形関数近似が$q_pi$-realizabilityで与えられる学習問題に対処する。
論文 参考訳（メタデータ） (2024-06-26T17:57:13Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
論文 参考訳（メタデータ） (2021-12-21T01:54:17Z) - Implicitly Regularized RL with Implicit Q-Values [42.87920755961722]
Q$関数は多くの強化学習(RL)アルゴリズムにおいて中心的な量であり、RLエージェントは(ソフト)グレーディポリシーに従って振る舞う。
対数政治と値関数の和として、暗黙的に$Q$-関数をパラメータ化することを提案する。
我々は,大規模アクション空間に適した実用的な非政治的深部RLアルゴリズムを導出し,ポリシーと$Q$値とのソフトマックス関係を強制する。
論文 参考訳（メタデータ） (2021-08-16T12:20:47Z) - Efficient Local Planning with Linear Function Approximation [27.90696655434707]
線形関数近似とシミュレータを用いたクエリと計算効率のよい計画アルゴリズムについて検討する。
本稿では,モンテカルロ最小二乗政策反復(MC-LSPI)というアルゴリズムを提案する。
我々の研究の技術的貢献の1つは、仮想ポリシーアルゴリズムを利用した新しい証明手法の導入である。
論文 参考訳（メタデータ） (2021-08-12T04:56:33Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Online Sub-Sampling for Reinforcement Learning with General Function
Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。
複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。
少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文 参考訳（メタデータ） (2021-06-14T07:36:25Z) - Improved Regret Bound and Experience Replay in Regularized Policy
Iteration [22.621710838468097]
無限ホライゾンマルコフ決定過程(mdps)における学習アルゴリズムを関数近似を用いて検討する。
まず、ほぼ同一の仮定の下で、Politexアルゴリズムの後悔解析を$O(T3/4)$から$O(sqrtT)$にシャープできることを示す。
その結果、計算効率の良いアルゴリズムに対して、最初の高い確率の$o(sqrtt)$ regretバウンドが得られる。
論文 参考訳（メタデータ） (2021-02-25T00:55:07Z) - On Query-efficient Planning in MDPs under Linear Realizability of the
Optimal State-value Function [14.205660708980988]
固定水平マルコフ決定過程(MDP)における局所的計画の問題点を生成モデルを用いて考察する。
最近の下界は、最適ポリシーの作用値関数が線形に実現可能である場合の関連する問題は指数的なクエリ数を必要とすることを証明している。
本研究では,アクションセットが小さい場合,ポリ$(H, d)$学習が(状態値関数の実現可能性を持つ)可能であることを確かめる。
論文 参考訳（メタデータ） (2021-02-03T13:23:15Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。