論文の概要: Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs

• arxiv url: http://arxiv.org/abs/2410.24071v1
• Date: Thu, 31 Oct 2024 16:07:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-01 17:00:58.235446
• Title: Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs
• Title（参考訳）: 局所線形性:連続MDPにおける非回帰強化学習の鍵
• Authors: Davide Maran, Alberto Maria Metelli, Matteo Papini, Marcello Restelli,
• Abstract要約: 既存の解は非常に特定の仮定の下で機能するか、いくつかの状態において空でない境界を達成するかのいずれかである。 多くの構造的仮定は、残念なことに、時間的地平線上の必然的に避けられない指数的依存に悩まされていることが知られている。 局所線形化可能な MDP を適切な表現選択により, 軽度に滑らかな MDP をどのように表現できるかを示す。
• 参考スコア（独自算出の注目度）: 56.237917407785545
• License:
• Abstract: Achieving the no-regret property for Reinforcement Learning (RL) problems in continuous state and action-space environments is one of the major open problems in the field. Existing solutions either work under very specific assumptions or achieve bounds that are vacuous in some regimes. Furthermore, many structural assumptions are known to suffer from a provably unavoidable exponential dependence on the time horizon $H$ in the regret, which makes any possible solution unfeasible in practice. In this paper, we identify local linearity as the feature that makes Markov Decision Processes (MDPs) both learnable (sublinear regret) and feasible (regret that is polynomial in $H$). We define a novel MDP representation class, namely Locally Linearizable MDPs, generalizing other representation classes like Linear MDPs and MDPS with low inherent Belmman error. Then, i) we introduce Cinderella, a no-regret algorithm for this general representation class, and ii) we show that all known learnable and feasible MDP families are representable in this class. We first show that all known feasible MDPs belong to a family that we call Mildly Smooth MDPs. Then, we show how any mildly smooth MDP can be represented as a Locally Linearizable MDP by an appropriate choice of representation. This way, Cinderella is shown to achieve state-of-the-art regret bounds for all previously known (and some new) continuous MDPs for which RL is learnable and feasible.
• Abstract（参考訳）: 連続状態および行動空間環境における強化学習(RL)問題に対する非Regret性を達成することは、この分野における主要なオープン問題の一つである。 既存の解は非常に特定の仮定の下で機能するか、いくつかの状態において空でない境界を達成するかのいずれかである。 さらに、多くの構造的仮定は、時間の地平線上の証明不可能な指数依存に悩まされることが知られている。 本稿では局所線型性を,マルコフ決定過程(MDP)を学習可能(サブリニア後悔)かつ実現可能($H$の多項式)にする特徴として認識する。 局所線形化可能な MDP という新しい MDP 表現クラスを定義し,線形 MDP や MDPS などの表現クラスを固有なベルマン誤差で一般化する。 そして i) この汎用表現クラスのための非regretアルゴリズムであるCinderellaを導入し、 ii) このクラスでは, 学習可能な, 実現可能なMPPファミリーがすべて表現可能であることを示す。 まず,Mildly Smooth MDPs と呼ばれる家族に属する,既知のすべての MDP について述べる。 次に, 局所線形化可能なMDPを適切な表現選択により, 軽度に滑らかなMDPを表現できることを示す。 このように、シンデレラは、RLが学習可能で実現可能なすべての既知(およびいくつかの新しい)連続 MDPに対して、最先端の後悔境界を達成することが示されている。

関連論文リスト

• No-Regret Reinforcement Learning in Smooth MDPs [24.249446550171307]
  本稿では,これまで提案されてきたほとんどの設定を一般化した,決定プロセス(MDP)に関する新たな構造仮定を提案する。 本稿では,2つのアルゴリズムを用いて,$nu-$smoothnessにおける後悔の最小化を提案する。 結果とRL理論の最先端技術を比較し,アルゴリズムが最高の保証を達成することを示す。
  論文  参考訳（メタデータ） (2024-02-06T08:18:14Z)
• Online RL in Linearly $q^\pi$-Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore [0.0]
  エピソードマルコフ決定過程(MDP)におけるオンライン強化学習の検討 2つのクラスの違いは、線形に$qpi$-realizable MDPにおける状態の存在であることを示す。 線形$qpi$-realizable MDPのための新しい(計算非効率な)学習アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2023-10-11T18:50:25Z)
• Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection [136.4014229319618]
  線形構造を持つ有限水平マルコフ決定過程(MDPs)における後悔最小化における状態-作用値関数の表現の役割について検討する。 まず,線形報酬関数を持つ任意のMDPにおいて,一貫した後悔を実現するために,Universally spaning optimal features (UNISOFT) と呼ばれる表現に必要条件を導出する。
  論文  参考訳（メタデータ） (2021-10-27T22:07:08Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• 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)
• Reward is enough for convex MDPs [30.478950691312715]
  静止分布の凸関数として目標が表現される凸MDPについて検討する。 本稿では,この問題を解決するメタアルゴリズムを提案し,文献における既存のアルゴリズムを統一することを示す。
  論文  参考訳（メタデータ） (2021-06-01T17:46:25Z)
• RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
  後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討 LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。 鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
  論文  参考訳（メタデータ） (2021-02-09T16:49:58Z)
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs [53.710405006523274]
  この研究は、表現学習の問題に焦点を当てている。 基礎となる(未知の)力学が低階遷移行列に対応するという仮定の下で、表現学習問題と特定の非線形行列分解問題との関連性を示す。 低階遷移モデルにおけるRLの探索と表現学習を行うFLAMBEを開発した。
  論文  参考訳（メタデータ） (2020-06-18T19:11:18Z)

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

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