論文の概要: Online RL in Linearly $q^\pi$-Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore

• arxiv url: http://arxiv.org/abs/2310.07811v2
• Date: Wed, 20 Dec 2023 18:09:29 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-21 19:03:53.076578
• Title: Online RL in Linearly $q^\pi$-Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore
• Title（参考訳）: オンラインrl in linearly $q^\pi$-realizable mdps if you learn what to ignore. (英語)
• Authors: Gell\'ert Weisz and Andr\'as Gy\"orgy and Csaba Szepesv\'ari
• Abstract要約: エピソードマルコフ決定過程(MDP)におけるオンライン強化学習の検討 2つのクラスの違いは、線形に$qpi$-realizable MDPにおける状態の存在であることを示す。 線形$qpi$-realizable MDPのための新しい(計算非効率な)学習アルゴリズムを導出する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider online reinforcement learning (RL) in episodic Markov decision processes (MDPs) under the linear $q^\pi$-realizability assumption, where it is assumed that the action-values of all policies can be expressed as linear functions of state-action features. This class is known to be more general than linear MDPs, where the transition kernel and the reward function are assumed to be linear functions of the feature vectors. As our first contribution, we show that the difference between the two classes is the presence of states in linearly $q^\pi$-realizable MDPs where for any policy, all the actions have approximately equal values, and skipping over these states by following an arbitrarily fixed policy in those states transforms the problem to a linear MDP. Based on this observation, we derive a novel (computationally inefficient) learning algorithm for linearly $q^\pi$-realizable MDPs that simultaneously learns what states should be skipped over and runs another learning algorithm on the linear MDP hidden in the problem. The method returns an $\epsilon$-optimal policy after $\text{polylog}(H, d)/\epsilon^2$ interactions with the MDP, where $H$ is the time horizon and $d$ is the dimension of the feature vectors, giving the first polynomial-sample-complexity online RL algorithm for this setting. The results are proved for the misspecified case, where the sample complexity is shown to degrade gracefully with the misspecification error.
• Abstract（参考訳）: オンライン強化学習 (rl) は, 線形$q^\pi$-実現可能性仮定の下でのマルコフ決定過程 (mdps) において, 全てのポリシーの動作値が状態動作特徴の線形関数として表現できると仮定する。 このクラスは線型 MDP よりも一般であることが知られており、遷移核と報酬関数は特徴ベクトルの線型函数であると仮定される。 最初の貢献として、2つのクラスの違いは、すべてのアクションがほぼ等しい値を持つ線形$q^\pi$-実現可能なmdpにおける状態の存在を示し、これらの状態における任意に固定されたポリシーに従うことで、問題を線形mdpに変換する。 この結果をもとに,線形に$q^\pi$-realizable MDPを学習する新しい学習アルゴリズムを考案し,その問題に隠れた線形MDP上で,どの状態をスキップすべきかを同時に学習し,別の学習アルゴリズムを実行する。 このメソッドは、$\text{polylog}(H, d)/\epsilon^2$ と MDP との相互作用の後、$\epsilon$-optimal policy を返す。 誤特定の場合、サンプルの複雑さは、誤特定エラーによって優雅に劣化することが示される。

関連論文リスト

• Confident Natural Policy Gradient for Local Planning in $q_π$-realizable Constrained MDPs [44.69257217086967]
  制約付きマルコフ決定プロセス(CMDP)フレームワークは、安全性や他の重要な目的を課すための重要な強化学習アプローチとして出現する。 本稿では,線形関数近似が$q_pi$-realizabilityで与えられる学習問題に対処する。
  論文  参考訳（メタデータ） (2024-06-26T17:57:13Z)
• Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear $q^π$-Realizability and Concentrability [34.51093353030245]
  H$-horizon Markov decision process(MDPs)におけるオフライン強化学習(RL) トラジェクトリデータでは、$textpoly(d,H,C_textconc)/epsilon2$のデータセットは、$epsilon$-optimal Policyを導出するのに十分であることを示す。
  論文  参考訳（メタデータ） (2024-05-27T03:59:13Z)
• Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles [39.10180309328293]
  本稿では,特徴選択の観点から線形MDPを再考する。 我々の主な成果は、この問題に対する最初のアルゴリズムである。 コンベックスプログラミングによって効率よく計算できることを示す。
  論文  参考訳（メタデータ） (2023-09-18T03:35:48Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
  論文  参考訳（メタデータ） (2022-12-12T18:58:59Z)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-01-26T22:09:59Z)
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation [95.80683238546499]
  本論文では, 線形関数近似を用いた UCRL2 アルゴリズムの拡張として見ることのできる新しいアルゴリズム UCRL2-VTR を提案する。 Bernstein 型ボーナス付き UCRL2-VTR は $tildeO(dsqrtDT)$ の後悔を達成でき、$d$ は特徴写像の次元である。 また、一致した下界$tildeOmega(dsqrtDT)$を証明し、提案したUCRL2-VTRが対数係数の最小値であることを示す。
  論文  参考訳（メタデータ） (2021-02-15T02:08:39Z)
• RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
  後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討 LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。 鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
  論文  参考訳（メタデータ） (2021-02-09T16:49:58Z)
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation [99.59319332864129]
  最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。 我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
  論文  参考訳（メタデータ） (2020-11-23T17:25:00Z)
• Online learning in MDPs with linear function approximation and bandit feedback [13.32560004325655]
  我々は,学習者がマルコフ決定プロセスと一連のエピソードで対話するオンライン学習問題を考える。 我々は, MDP-LinExp3 が, この問題設定のための最初の証明可能なアルゴリズムであることを示す。
  論文  参考訳（メタデータ） (2020-07-03T11:06:38Z)
• 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)

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

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