論文の概要: Optimal Sample Complexity for Average Reward Markov Decision Processes
- arxiv url: http://arxiv.org/abs/2310.08833v1
- Date: Fri, 13 Oct 2023 03:08:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-16 14:31:02.646021
- Title: Optimal Sample Complexity for Average Reward Markov Decision Processes
- Title（参考訳）: 平均報酬マルコフ決定過程における最適サンプル複雑性
- Authors: Shengbo Wang, Jose Blanchet, and Peter Glynn
- Abstract要約: 平均報酬 MDP の最適ポリシを$widetilde O(|S||A|t_textmixepsilon-2)$で推定する。
我々の主な貢献は、平均報酬MDPの最適政策を$widetilde O(|S||A|t_textmixepsilon-2)$で推定し、文献の下位境界に効果的に到達することである。
- 参考スコア（独自算出の注目度）: 1.0445957451908694
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We settle the sample complexity of policy learning for the maximization of
the long run average reward associated with a uniformly ergodic Markov decision
process (MDP), assuming a generative model. In this context, the existing
literature provides a sample complexity upper bound of $\widetilde
O(|S||A|t_{\text{mix}}^2 \epsilon^{-2})$ and a lower bound of
$\Omega(|S||A|t_{\text{mix}} \epsilon^{-2})$. In these expressions, $|S|$ and
$|A|$ denote the cardinalities of the state and action spaces respectively,
$t_{\text{mix}}$ serves as a uniform upper limit for the total variation mixing
times, and $\epsilon$ signifies the error tolerance. Therefore, a notable gap
of $t_{\text{mix}}$ still remains to be bridged. Our primary contribution is to
establish an estimator for the optimal policy of average reward MDPs with a
sample complexity of $\widetilde O(|S||A|t_{\text{mix}}\epsilon^{-2})$,
effectively reaching the lower bound in the literature. This is achieved by
combining algorithmic ideas in Jin and Sidford (2021) with those of Li et al.
(2020).
- Abstract（参考訳）: 我々は,一様エルゴード的マルコフ決定過程(MDP)に関連する長期平均報酬の最大化のための政策学習のサンプル複雑性を,生成モデルとして解決する。
この文脈では、既存の文献は、$\widetilde O(|S||A|t_{\text{mix}}^2 \epsilon^{-2})$と$\Omega(|S||A|t_{\text{mix}} \epsilon^{-2})$のサンプル複雑性上限を提供する。
これらの式では、$|S|$ と $|A|$ はそれぞれ状態と作用空間の濃度を表し、$t_{\text{mix}}$ は全変動混合時間の均一な上限として機能し、$\epsilon$ はエラー耐性を表す。
したがって、$t_{\text{mix}}$の注目すべきギャップは依然としてブリッジされている。
我々の主な貢献は、平均報酬 MDP の最適ポリシを$\widetilde O(|S||A|t_{\text{mix}}\epsilon^{-2})$で推定し、文献の下位境界に効果的に到達することである。
これは、jin と sidford (2021) のアルゴリズム的アイデアと li et al. (2020) のアイデアを組み合わせたものである。
関連論文リスト
- Finding good policies in average-reward Markov Decision Processes without prior knowledge [19.89784209009327]
平均回帰決定(MDP)における$varepsilon$-Optimal Policyの同定を再考する。
直径推定法を用いて,$(varepsilon,delta)$-PAC-PACポリシー識別のための最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-27T12:24:14Z) - 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) - Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs [6.996002801232415]
平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。
MDP を弱通信するためには、$widetildeO(SAfracHvarepsilon2 )$, $H$ は最適ポリシーのバイアス関数のスパンであり、$SA$ は状態作用空間の濃度である。
論文 参考訳（メタデータ） (2024-03-18T04:52:11Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
仮説選択問題に対する最適2ドルの近似学習戦略を導出する。
これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
論文 参考訳（メタデータ） (2021-08-17T21:11:20Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。