論文の概要: Optimal Sample Complexity of Reinforcement Learning for Uniformly
Ergodic Discounted Markov Decision Processes
- arxiv url: http://arxiv.org/abs/2302.07477v2
- Date: Thu, 16 Feb 2023 07:28:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-17 16:13:55.374879
- Title: Optimal Sample Complexity of Reinforcement Learning for Uniformly
Ergodic Discounted Markov Decision Processes
- Title(参考訳): 一様エルゴード割引マルコフ決定過程に対する強化学習の最適サンプル複雑性
- Authors: Shengbo Wang, Jose Blanchet, and Peter Glynn
- Abstract要約: マルコフ決定過程(MDP)における無限地平線割引報酬を制御するための最適なサンプル複雑性理論を考える。
多くの興味ある応用において、最適政策(または全ての政策)は混合を誘導する。
我々の分析は、一般状態空間 MDP の関連問題の研究に使用できるため、独立した関心を持つ再生型アイデアに基づいている。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the optimal sample complexity theory of tabular reinforcement
learning (RL) for controlling the infinite horizon discounted reward in a
Markov decision process (MDP). Optimal min-max complexity results have been
developed for tabular RL in this setting, leading to a sample complexity
dependence on $\gamma$ and $\epsilon$ of the form $\tilde
\Theta((1-\gamma)^{-3}\epsilon^{-2})$, where $\gamma$ is the discount factor
and $\epsilon$ is the tolerance solution error. However, in many applications
of interest, the optimal policy (or all policies) will induce mixing. We show
that in these settings the optimal min-max complexity is $\tilde
\Theta(t_{\text{minorize}}(1-\gamma)^{-2}\epsilon^{-2})$, where
$t_{\text{minorize}}$ is a measure of mixing that is within an equivalent
factor of the total variation mixing time. Our analysis is based on
regeneration-type ideas, that, we believe are of independent interest since
they can be used to study related problems for general state space MDPs.
- Abstract(参考訳): マルコフ決定過程(MDP)において,無限地平面割引報酬を制御するための表型強化学習(RL)の最適サンプル複雑性理論を考察する。
この設定において、表形式 RL に対して最適な min-max 複雑性の結果が開発され、$\gamma$ と $\epsilon$ の形での複雑さ依存のサンプルが $\tilde \Theta((1-\gamma)^{-3}\epsilon^{-2})$ となり、$\gamma$ は割引係数、$\epsilon$ は許容解誤差となる。
しかし、多くの応用において、最適政策(または全ての政策)は混合を引き起こす。
これらの設定において、最適なmin-max複雑性は$\tilde \theta(t_{\text{minorize}}(1-\gamma)^{-2}\epsilon^{-2})$であり、ここで$t_{\text{minorize}}$ は全変分混合時間の等価な係数である。
本分析は, 一般状態空間mdpにおける関連する問題の研究に使用できるため, 個別の関心を持つ再生型アイデアに基づくものである。
関連論文リスト
- 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) - Optimal Sample Complexity for Average Reward Markov Decision Processes [1.0445957451908694]
平均報酬 MDP の最適ポリシを$widetilde O(|S||A|t_textmix2 epsilon-2)$で推定する。
これは文学の下位境界に到達した最初のアルゴリズムと分析である。
論文 参考訳(メタデータ) (2023-10-13T03:08:59Z) - A Finite Sample Complexity Bound for Distributionally Robust Q-learning [16.88062487980405]
我々は,展開環境が訓練環境と異なる強化学習環境を考える。
ロバストなマルコフ決定プロセスの定式化を適用することで、Liuらで研究されている分布的にロバストな$Q$ラーニングフレームワークを拡張します。
これはモデルのないロバストなRL問題に対する最初のサンプル複雑性結果である。
論文 参考訳(メタデータ) (2023-02-26T01:15:32Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳(メタデータ) (2022-04-11T17:26:19Z) - 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) - Settling the Horizon-Dependence of Sample Complexity in Reinforcement
Learning [82.31436758872715]
我々は,環境相互作用の$O(1)$のエピソードのみを用いて,同一のPAC保証を実現するアルゴリズムを開発した。
値関数と有限水平マルコフ決定過程の接続を確立する。
論文 参考訳(メタデータ) (2021-11-01T00:21:24Z) - Policy Mirror Descent for Reinforcement Learning: Linear Convergence,
New Sampling Complexity, and Generalized Problem Classes [6.240369435223]
本稿では,強い凸あるいは一般凸正規化器を用いた強化学習問題の解法として,PMD法を提案する。
私たちの知る限りでは、これらの開発は最適化と柔軟性の両面で新しくなっています。
論文 参考訳(メタデータ) (2021-01-30T02:30:45Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳(メタデータ) (2020-07-15T03:25:24Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。