Fugu-MT 論文翻訳(概要): Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP

論文の概要: Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP

arxiv url: http://arxiv.org/abs/2212.00603v1
Date: Thu, 1 Dec 2022 15:57:58 GMT
ステータス: 処理完了
システム内更新日: 2022-12-02 15:11:36.615849
Title: Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP
Title（参考訳）: 平均リワードMDPのための準最適還元型政策学習
Authors: Jinghan Wang, Mengdi Wang, Lin F. Yang
Abstract要約: この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
参考スコア（独自算出の注目度）: 58.13930707612128
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This work considers the sample complexity of obtaining an $\varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP), given access to a generative model (simulator). When the ground-truth MDP is weakly communicating, we prove an upper bound of $\widetilde O(H \varepsilon^{-3} \ln \frac{1}{\delta})$ samples per state-action pair, where $H := sp(h^*)$ is the span of bias of any optimal policy, $\varepsilon$ is the accuracy and $\delta$ is the failure probability. This bound improves the best-known mixing-time-based approaches in [Jin & Sidford 2021], which assume the mixing-time of every deterministic policy is bounded. The core of our analysis is a proper reduction bound from AMDP problems to discounted MDP (DMDP) problems, which may be of independent interests since it allows the application of DMDP algorithms for AMDP in other settings. We complement our upper bound by proving a minimax lower bound of $\Omega(|\mathcal S| |\mathcal A| H \varepsilon^{-2} \ln \frac{1}{\delta})$ total samples, showing that a linear dependent on $H$ is necessary and that our upper bound matches the lower bound in all parameters of $(|\mathcal S|, |\mathcal A|, H, \ln \frac{1}{\delta})$ up to some logarithmic factors.
Abstract（参考訳）: この研究は、生成モデル(シミュレータ)にアクセス可能な平均報酬マルコフ決定過程(AMDP)において、$\varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。基底構造 MDP が弱通信の場合、上界の$\widetilde O(H \varepsilon^{-3} \ln \frac{1}{\delta})$ 状態-作用ペアあたりのサンプルを証明し、$H := sp(h^*)$ は任意の最適ポリシーのバイアスのスパンであり、$\varepsilon$ は精度、$\delta$ は失敗確率である。この境界は[jin & sidford 2021]における最もよく知られた混合時間に基づくアプローチを改善する。本分析の核となるのは,AMDP 問題から割引 MDP (DMDP) 問題への適切なリダクションであり,他の設定で DMDP アルゴリズムを適用できるため,独立した関心を持つ可能性がある。上界は、$\Omega(|\mathcal S| |\mathcal A| H \varepsilon^{-2} \ln \frac{1}{\delta})$の全サンプルを証明し、$H$への線形依存が必要であり、上界が$(|\mathcal S|, |\mathcal A|, H, \ln \frac{1}{\delta})$のすべてのパラメータで下界と一致することを示す。

関連論文リスト

Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs [35.22742439337603]
Proposed Primal-Dual based Regularized Accelerated Natural Policy Gradient (PDR-ANPG) algorithm using entropy and quadratic regularizers to reach this goal。 PDR-ANPGは、パラメータ化されたポリシークラスに変換互換性の近似誤差を持たせるため、最終値の$epsilon$Optimity gapを達成できる。これは、汎用パラメータ化CMDPの最先端最終保証の大幅な改善である。
論文参考訳（メタデータ） (2024-08-21T10:44:57Z)
Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
論文参考訳（メタデータ） (2024-06-10T17:48:36Z)
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)
Span-Based Optimal Sample Complexity for Average Reward MDPs [6.996002801232415]
平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。我々は、$widetildeOleft(SAfracH (1-gamma)2varepsilon2 right)$, ここで、$H$は最適ポリシーのバイアス関数のスパンであり、$SA$は状態作用空間の濃度である。
論文参考訳（メタデータ） (2023-11-22T15:34:44Z)
Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文参考訳（メタデータ） (2022-10-05T22:52:00Z)
Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文参考訳（メタデータ） (2022-08-11T04:12:50Z)
SDP Achieves Exact Minimax Optimality in Phase Synchronization [19.909352968029584]
我々は、ノイズ測定$Y=z*z*+sigma WinmathbbCntimes ntimes nで位相同期問題を研究する。 SDPが誤差境界$ (1+o)fracnp22np$を2乗の$ell$損失で達成することを証明する。
論文参考訳（メタデータ） (2021-01-07T03:14:05Z)
Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文参考訳（メタデータ） (2020-12-15T18:56:46Z)
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)

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

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