Fugu-MT 論文翻訳(概要): Polynomial Time Reinforcement Learning in Correlated FMDPs with Linear Value Functions

論文の概要: Polynomial Time Reinforcement Learning in Correlated FMDPs with Linear Value Functions

arxiv url: http://arxiv.org/abs/2107.05187v1
Date: Mon, 12 Jul 2021 04:13:18 GMT
ステータス: 処理完了
システム内更新日: 2021-07-13 15:52:13.482903
Title: Polynomial Time Reinforcement Learning in Correlated FMDPs with Linear Value Functions
Title（参考訳）: 相関fmdpsと線形値関数における多項式時間強化学習
Authors: Siddartha Devic, Zihao Deng, Brendan Juba
Abstract要約: 因子マルコフ決定過程(FMDP)を用いた強化学習のための最初のアルゴリズムを提案する。様々な要因の遷移が独立したものではないと仮定する。従来の作業とは対照的に、さまざまな要因の遷移が独立したものであるとは考えません。
参考スコア（独自算出の注目度）: 25.621280373733605
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Many reinforcement learning (RL) environments in practice feature enormous state spaces that may be described compactly by a "factored" structure, that may be modeled by Factored Markov Decision Processes (FMDPs). We present the first polynomial-time algorithm for RL with FMDPs that does not rely on an oracle planner, and instead of requiring a linear transition model, only requires a linear value function with a suitable local basis with respect to the factorization. With this assumption, we can solve FMDPs in polynomial time by constructing an efficient separation oracle for convex optimization. Importantly, and in contrast to prior work, we do not assume that the transitions on various factors are independent.
Abstract（参考訳）: 多くの強化学習(RL)環境は、有限マルコフ決定過程(FMDP)によってモデル化される「リファクタリングされた」構造によってコンパクトに記述できる巨大な状態空間を特徴としている。本稿では, 線形遷移モデルを必要とする代わりに, 因数分解に関して適切な局所基底を持つ線形値関数のみを必要とするFMDPを用いたRLの最初の多項式時間アルゴリズムを提案する。この仮定により、凸最適化のための効率的な分離オラクルを構築することにより、FMDPを多項式時間で解くことができる。重要なことは、以前の作業とは対照的に、さまざまな要因の遷移が独立しているとは考えません。

関連論文リスト

Horizon-Free Regret for Linear Markov Decision Processes [92.02082223856479]
最近の一連の研究は、強化学習における残念な境界が(ほぼ)計画的地平から独立していることを示している。我々は、人気のある線形マルコフ決定過程(MDP)設定に対して、最初の地平面自由境界を与える。遷移モデルを明示的に推定し、不均一な値関数を計算する先行研究とは対照的に、直接値関数と信頼集合を推定する。
論文参考訳（メタデータ） (2024-03-15T23:50:58Z)
Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning [53.97335841137496]
非線形関数近似を用いたオフラインRLにおけるPNLSVI(Pessimistic Least-Square Value Iteration)と呼ばれるオラクル効率のアルゴリズムを提案する。本アルゴリズムは,関数クラスの複雑性に強く依存する後悔境界を享受し,線形関数近似に特化して最小限のインスタンス依存後悔を実現する。
論文参考訳（メタデータ） (2023-10-02T17:42:01Z)
Provably Efficient Algorithm for Nonstationary Low-Rank MDPs [48.92657638730582]
我々は,非定常RLを,遷移カーネルと報酬の両方が時間とともに変化するような,エピソードな低ランクMDPで調査する最初の試みを行っている。本稿では,パラメータ依存型ポリシ最適化アルゴリズムである Portal を提案し,パラメータフリー版である Ada-Portal の Portal をさらに改良する。両アルゴリズムとも,非定常性が著しく大きくない限り, Portal と Ada-PortAL はサンプリング効率が良く,サンプリング複雑性を伴う平均的動的準最適ギャップを任意に小さく得ることを示す。
論文参考訳（メタデータ） (2023-08-10T09:52:44Z)
Revisiting the Linear-Programming Framework for Offline RL with General Function Approximation [24.577243536475233]
オフライン強化学習(RL)は、事前に収集されたデータセットからシーケンシャルな意思決定のための最適なポリシーを追求する。近年の理論的進歩は、データカバレッジと関数近似器に関する様々な緩和された仮定を持つサンプル効率の良いオフラインRLアルゴリズムの開発に焦点が当てられている。オフラインRLのための線形プログラミングフレームワークを再検討し、いくつかの面で既存の結果を前進させます。
論文参考訳（メタデータ） (2022-12-28T15:28:12Z)
Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
論文参考訳（メタデータ） (2022-12-12T18:58:59Z)
Computational-Statistical Gaps in Reinforcement Learning [23.517741855454044]
そこでは,CNF式を決定論的遷移,動作の定数数,低次元線形最適値関数を備えたMDP仮説に変換する。この結果は線形関数近似を用いた強化学習における最初の計算統計的ギャップを示す。
論文参考訳（メタデータ） (2022-02-11T04:48:35Z)
Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearity [50.38337893712897]
線形性を仮定しないMDP上の構造条件であるEPW(Effective Planning Window)条件を導入する。 EPW条件は、この条件を満たすMDPを確実に解くアルゴリズムを提供することで、サンプル効率のよいRLを許容することを示した。また, EPW のような条件の必要性も示し, わずかに非線形な単純な MDP を効率的にサンプリングできないことを示した。
論文参考訳（メタデータ） (2021-06-15T00:06:59Z)
Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting [60.98700344526674]
線形関数表現のような低複雑度モデルがサンプル効率のよい強化学習を可能にする上で重要な役割を果たしている。本稿では,オンライン/探索的な方法でサンプルを描画するが,制御不能な方法で以前の状態をバックトラックし,再訪することができる新しいサンプリングプロトコルについて検討する。この設定に合わせたアルゴリズムを開発し、特徴次元、地平線、逆の準最適ギャップと実際にスケールするサンプル複雑性を実現するが、状態/作用空間のサイズではない。
論文参考訳（メタデータ） (2021-05-17T17:22:07Z)
Local Function Complexity for Active Learning via Mixture of Gaussian Processes [5.382740428160009]
実世界のデータにおける不均一性は、観測ノイズレベルの変化や源関数の構造的複雑さの変化により、統計的推測に固有の課題が生じる。本稿では,局所関数複雑性(LFC)の推定に関する最近の理論的結果について述べる。我々は、LPSベースのLFCのガウスプロセス回帰(GPR)に基づくアナログを導出、推定し、上記のフレームワークの代用として使用し、堅牢でスケーラブルにする。
論文参考訳（メタデータ） (2019-02-27T17:55:06Z)

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