論文の概要: RL for Latent MDPs: Regret Guarantees and a Lower Bound
- arxiv url: http://arxiv.org/abs/2102.04939v1
- Date: Tue, 9 Feb 2021 16:49:58 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-10 14:57:29.925733
- Title: RL for Latent MDPs: Regret Guarantees and a Lower Bound
- Title（参考訳）: RL for Latent MDPs: Regret Guarantees and a Lower Bounds (英語)
- Authors: Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, Shie Mannor
- Abstract要約: 後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討
LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。
鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
- 参考スコア（独自算出の注目度）: 74.41782017817808
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we consider the regret minimization problem for reinforcement
learning in latent Markov Decision Processes (LMDP). In an LMDP, an MDP is
randomly drawn from a set of $M$ possible MDPs at the beginning of the
interaction, but the identity of the chosen MDP is not revealed to the agent.
We first show that a general instance of LMDPs requires at least
$\Omega((SA)^M)$ episodes to even approximate the optimal policy. Then, we
consider sufficient assumptions under which learning good policies requires
polynomial number of episodes. We show that the key link is a notion of
separation between the MDP system dynamics. With sufficient separation, we
provide an efficient algorithm with local guarantee, {\it i.e.,} providing a
sublinear regret guarantee when we are given a good initialization. Finally, if
we are given standard statistical sufficiency assumptions common in the
Predictive State Representation (PSR) literature (e.g., Boots et al.) and a
reachability assumption, we show that the need for initialization can be
removed.
- Abstract（参考訳）: 本研究では,潜在マルコフ決定過程(LMDP)における強化学習における後悔最小化問題を検討する。
LMDPでは、MDPは相互作用の開始時に$M$可能なMDPのセットからランダムに引き出されるが、選択したMDPのアイデンティティはエージェントに明らかにされない。
まず、LMDPの一般的な例は、最適ポリシーを近似するために少なくとも$\Omega((SA)^M)$のエピソードを必要とすることを示す。
そこで,良質な政策を学ぶためには,エピソード数を多項式数とする十分な仮定を考える。
鍵となるリンクはmdpシステムダイナミクス間の分離の概念であることを示す。
十分な分離で、我々は局所的な保証を持つ効率的なアルゴリズム、すなわち、良い初期化が与えられたときのサブ線形後悔保証を提供する。
最後に、予測状態表現(psr)の文献(例えばbootsなど)に共通する標準的な統計十分性仮定が与えられた場合。
そして到達可能性の仮定は、初期化の必要性が取り除かれることを示します。
関連論文リスト
- Achieving $\tilde{O}(1/ε)$ Sample Complexity for Constrained Markov Decision Process [4.685121820790546]
マルコフ決定過程(CMDP)の強化学習問題について考察する。
これは$O(frac1Deltacdotepscdotlog2(1/eps))$ sample complexity boundとなる。
本アルゴリズムは一次空間で動作し,CMDP問題に対する一次LPを各期間にオンライン的に解決する。
論文 参考訳（メタデータ） (2024-02-26T06:08:25Z) - Provably Efficient CVaR RL in Low-rank MDPs [58.58570425202862]
リスクに敏感な強化学習(RL)について検討する。
本稿では, CVaR RLにおける探索, 搾取, 表現学習の相互作用のバランスをとるための, 新たなアッパー信頼境界(UCB)ボーナス駆動アルゴリズムを提案する。
提案アルゴリズムは,各エピソードの長さが$H$,アクション空間が$A$,表現の次元が$d$であるような,エプシロン$最適CVaRのサンプル複雑性を実現する。
論文 参考訳（メタデータ） (2023-11-20T17:44:40Z) - Prospective Side Information for Latent MDPs [80.00842638151558]
本報告では,各エピソードの開始時に,エージェントが付加的,弱く露呈する情報を受信した場合に,予測側情報を用いたLMDPのクラスについて検討する。
驚くべきことに、この問題は、部分的に観察された環境のために設計された現代の設定やアルゴリズムによって捉えられていない。
すると、サンプル効率の良いアルゴリズムは、標準の$Omega(K2/3)$-regretとは対照的に、少なくとも$Omega(K2/3)$-regretを被ることを確立し、一致する上限を持つアルゴリズムを設計する。
論文 参考訳（メタデータ） (2023-10-11T15:37:31Z) - A Theoretical Analysis of Optimistic Proximal Policy Optimization in
Linear Markov Decision Processes [13.466249082564213]
本稿では,全情報フィードバックを用いた表層線形MDPに対するPPOの楽観的変種を提案する。
既存のポリシーベースのアルゴリズムと比較して, 線形MDPと逆線形MDPの双方において, 完全な情報付きで, 最先端の後悔点を達成している。
論文 参考訳（メタデータ） (2023-05-15T17:55:24Z) - PAC Statistical Model Checking of Mean Payoff in Discrete- and
Continuous-Time MDP [0.34410212782758043]
我々は,未知のMDPにおいて,平均ペイオフをほぼ正確に計算する最初のアルゴリズムを提供する。
状態空間に関する知識は一切必要とせず、最小遷移確率の低い境界のみである。
提案アルゴリズムは, ほぼ正しいPAC境界を提供するだけでなく, 標準ベンチマークで実験を行うことにより, その実用性を実証する。
論文 参考訳（メタデータ） (2022-06-03T09:13:27Z) - Semi-Markov Offline Reinforcement Learning for Healthcare [57.15307499843254]
本稿では,SDQN,SDDQN,SBCQという3つのオフラインRLアルゴリズムを紹介する。
変動時間環境において,これらのアルゴリズムのみが最適ポリシーを学習できることを実験的に実証した。
我々は,脳卒中予防のためのウォーファリン投与に関連する実世界のオフラインデータセットに,我々の新しいアルゴリズムを適用した。
論文 参考訳（メタデータ） (2022-03-17T14:51:21Z) - Safe Exploration by Solving Early Terminated MDP [77.10563395197045]
我々は、Early TerminatedP(ET-MDP)の枠組みの下で、安全なRL問題に対処する新しいアプローチを導入する。
まず、ET-MDPを対応するCMDPと同じ最適値関数を持つ非制約アルゴリズムとして定義する。
そこで,文脈モデルに基づく非政治アルゴリズムを提案し,ET-MDPを解き,それに対応するCMDPをより良い性能で解き,学習効率を向上する。
論文 参考訳（メタデータ） (2021-07-09T04:24:40Z) - A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。
我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。
この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
論文 参考訳（メタデータ） (2021-06-24T13:46:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。