論文の概要: 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})$のすべてのパラメータで下界と一致することを示す。
関連論文リスト
- Span-Based Optimal Sample Complexity for Average Reward MDPs [8.26485053800463]
平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。
我々は、$widetildeOleft(SAfracH (1-gamma)2varepsilon2 right)$, ここで、$H$は最適ポリシーのバイアス関数のスパンであり、$SA$は状態作用空間の濃度である。
論文 参考訳(メタデータ) (2023-11-22T15:34:44Z) - 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) - 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) - Reward-Free Model-Based Reinforcement Learning with Linear Function
Approximation [92.99933928528797]
エピソードマルコフ決定過程(MDP)に対する線形関数近似を用いたモデルに基づく無報酬強化学習について検討する。
計画段階では、特定の報酬関数が与えられ、探索フェーズから収集したサンプルを使用して良い政策を学ぶ。
任意の報酬関数に対して$epsilon$-optimal Policyを得るには,最大$tilde O(H4d(H + d)epsilon-2)$ episodesをサンプリングする必要がある。
論文 参考訳(メタデータ) (2021-10-12T23:03:58Z) - Towards Tight Bounds on the Sample Complexity of Average-reward MDPs [39.01663172393174]
生成モデルにアクセス可能な無限水平平均回帰マルコフ決定過程の最適方針を求める。
状態-作用対あたりのサンプルを$widetildeO(t_mathrmmix epsilon-3)$ (oblivious) で解決するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-06-13T17:18:11Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。