論文の概要: Demystifying Linear MDPs and Novel Dynamics Aggregation Framework

• arxiv url: http://arxiv.org/abs/2410.24089v1
• Date: Thu, 31 Oct 2024 16:21:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-01 17:03:19.165220
• Title: Demystifying Linear MDPs and Novel Dynamics Aggregation Framework
• Title（参考訳）: 線形MDPのデミスティファイションと新しいダイナミクス集約フレームワーク
• Authors: Joongkyu Lee, Min-hwan Oh,
• Abstract要約: 線型 MDP において、$d$ は遷移確率を適切に表すために$S/U$ で制限される。 動的アグリゲーション(dynamics aggregate, 動的アグリゲーション)と呼ばれる動的に基づく新しい構造アグリゲーションフレームワークを提案する。 提案アルゴリズムは統計的効率を示し,$ tildeO (d_psi3/2 H3/2sqrt T)$, $d_psi$は集約されたサブMDPの特徴次元を表す。
• 参考スコア（独自算出の注目度）: 8.087699764574788
• License:
• Abstract: In this work, we prove that, in linear MDPs, the feature dimension $d$ is lower bounded by $S/U$ in order to aptly represent transition probabilities, where $S$ is the size of the state space and $U$ is the maximum size of directly reachable states. Hence, $d$ can still scale with $S$ depending on the direct reachability of the environment. To address this limitation of linear MDPs, we propose a novel structural aggregation framework based on dynamics, named as the "dynamics aggregation". For this newly proposed framework, we design a provably efficient hierarchical reinforcement learning algorithm in linear function approximation that leverages aggregated sub-structures. Our proposed algorithm exhibits statistical efficiency, achieving a regret of $ \tilde{O} ( d_{\psi}^{3/2} H^{3/2}\sqrt{ N T} )$, where $d_{\psi}$ represents the feature dimension of aggregated subMDPs and $N$ signifies the number of aggregated subMDPs. We establish that the condition $d_{\psi}^3 N \ll d^{3}$ is readily met in most real-world environments with hierarchical structures, enabling a substantial improvement in the regret bound compared to LSVI-UCB, which enjoys a regret of $ \tilde{O} (d^{3/2} H^{3/2} \sqrt{ T})$. To the best of our knowledge, this work presents the first HRL algorithm with linear function approximation that offers provable guarantees.
• Abstract（参考訳）: この研究において、線形 MDP において、$d$ は遷移確率を適切に表すために$S/U$ で有界であり、$S$ は状態空間のサイズであり、$U$ は直接到達可能な状態の最大サイズであることを示す。 したがって、$d$は環境の直接的な到達性に応じて$S$でスケールすることができる。 線形MDPのこの制限に対処するために,力学に基づく新しい構造集約フレームワークを提案し,これを「力学集約」と呼ぶ。 新たに提案したフレームワークでは, 集約されたサブ構造を利用する線形関数近似において, 効率の良い階層的強化学習アルゴリズムを設計する。 提案アルゴリズムは統計的効率を示し,$ \tilde{O} (d_{\psi}^{3/2} H^{3/2}\sqrt{NT} )$, $d_{\psi}$は集約されたサブMDPの特徴次元を表し,$N$は集約されたサブMDPの数を表す。 条件 $d_{\psi}^3 N \ll d^{3}$ は、階層構造を持つほとんどの実世界の環境で容易に満たされ、LSVI-UCB と比較して、後悔の大幅な改善が可能であり、これは $ \tilde{O} (d^{3/2} H^{3/2} \sqrt{T})$ の後悔を享受するものである。 我々の知る限り、この研究は証明可能な保証を提供する線形関数近似を用いた最初のHRLアルゴリズムを示す。

関連論文リスト

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。 我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-07T15:03:50Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation [25.60689712525918]
  本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。 本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
  論文  参考訳（メタデータ） (2022-06-23T06:04:21Z)
• Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure [9.759209713196718]
  我々は、対応する最適$Q*$関数が低ランクであるMDPのクラスを考える。 より強い低階構造仮定の下では、生成モデル(LR-MCPI)と低階経験値イテレーション(LR-EVI)が、ランクに対して$tildeOleft((|S|+|A|)mathrmpoly(d,H)/epsilon2right)$の所望のサンプル複雑性を実現することが示されている。
  論文  参考訳（メタデータ） (2022-06-07T20:39:51Z)
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation [92.99933928528797]
  エピソードマルコフ決定過程(MDP)に対する線形関数近似を用いたモデルに基づく無報酬強化学習について検討する。 計画段階では、特定の報酬関数が与えられ、探索フェーズから収集したサンプルを使用して良い政策を学ぶ。 任意の報酬関数に対して$epsilon$-optimal Policyを得るには,最大$tilde O(H4d(H + d)epsilon-2)$ episodesをサンプリングする必要がある。
  論文  参考訳（メタデータ） (2021-10-12T23:03:58Z)
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model [3.749193647980305]
  本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。 モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
  論文  参考訳（メタデータ） (2021-05-28T17:49:39Z)
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation [99.59319332864129]
  最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。 我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
  論文  参考訳（メタデータ） (2020-11-23T17:25:00Z)
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
  本稿では,割引決定(MDP)のための強化学習について検討する。 本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。 以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-23T17:08:54Z)

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

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