論文の概要: Optimal Sample Complexity for Average Reward Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2310.08833v2
• Date: Mon, 12 Feb 2024 19:06:53 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-14 19:19:13.523540
• 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_textmix2 epsilon-2)$で推定する。 これは文学の下位境界に到達した最初のアルゴリズムと分析である。
• 参考スコア（独自算出の注目度）: 1.0445957451908694
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We resolve the open question regarding the sample complexity of policy learning for maximizing 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 the development of an estimator for the optimal policy of average reward MDPs with a sample complexity of $\widetilde O(|S||A|t_{\text{mix}}\epsilon^{-2})$. This marks the first algorithm and analysis to reach the literature's lower bound. Our new algorithm draws inspiration from ideas in Li et al. (2020), Jin and Sidford (2021), and Wang et al. (2023). Additionally, we conduct numerical experiments to validate our theoretical findings.
• 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})$とする推定器の開発である。 これは文学の下位境界に到達した最初のアルゴリズムと分析である。 我々の新しいアルゴリズムは、Li et al. (2020)、Jin and Sidford (2021)、Wang et al. (2023)のアイデアからインスピレーションを得ている。 さらに,理論的結果を検証する数値実験を行った。

関連論文リスト

• 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)

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

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