論文の概要: Span-Based Optimal Sample Complexity for Average Reward MDPs
- arxiv url: http://arxiv.org/abs/2311.13469v1
- Date: Wed, 22 Nov 2023 15:34:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-23 14:40:01.543900
- Title: Span-Based Optimal Sample Complexity for Average Reward MDPs
- Title(参考訳): 平均報酬mdpのためのスパンベース最適サンプル複雑性
- Authors: Matthew Zurek, Yudong Chen
- Abstract要約: 平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。
我々は、$widetildeOleft(SAfracH (1-gamma)2varepsilon2 right)$, ここで、$H$は最適ポリシーのバイアス関数のスパンであり、$SA$は状態作用空間の濃度である。
- 参考スコア(独自算出の注目度): 8.26485053800463
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the sample complexity of learning an $\varepsilon$-optimal policy in
an average-reward Markov decision process (MDP) under a generative model. We
establish the complexity bound $\widetilde{O}\left(SA\frac{H}{\varepsilon^2}
\right)$, where $H$ is the span of the bias function of the optimal policy and
$SA$ is the cardinality of the state-action space. Our result is the first that
is minimax optimal (up to log factors) in all parameters $S,A,H$ and
$\varepsilon$, improving on existing work that either assumes uniformly bounded
mixing times for all policies or has suboptimal dependence on the parameters.
Our result is based on reducing the average-reward MDP to a discounted MDP.
To establish the optimality of this reduction, we develop improved bounds for
$\gamma$-discounted MDPs, showing that
$\widetilde{O}\left(SA\frac{H}{(1-\gamma)^2\varepsilon^2} \right)$ samples
suffice to learn a $\varepsilon$-optimal policy in weakly communicating MDPs
under the regime that $\gamma \geq 1 - \frac{1}{H}$, circumventing the
well-known lower bound of
$\widetilde{\Omega}\left(SA\frac{1}{(1-\gamma)^3\varepsilon^2} \right)$ for
general $\gamma$-discounted MDPs. Our analysis develops upper bounds on certain
instance-dependent variance parameters in terms of the span parameter. These
bounds are tighter than those based on the mixing time or diameter of the MDP
and may be of broader use.
- Abstract(参考訳): 平均回帰マルコフ決定過程 (mdp) において,$\varepsilon$-optimal ポリシーを生成モデルで学習するサンプル複雑性について検討した。
我々は、$\widetilde{O}\left(SA\frac{H}{\varepsilon^2} \right)$, ここで、$H$は最適ポリシーのバイアス関数のスパンであり、$SA$は状態-作用空間の濃度である。
我々の結果は、すべてのパラメータにおいて(ログファクタまで)最小値の最大値である$S,A,H$および$\varepsilon$で、すべてのポリシーに対して一様に有界な混合時間を仮定する既存の作業を改善するか、パラメータに最適に依存するかのいずれかである。
本結果は, 平均再帰型MDPを, 割引型MDPに還元することに基づく。
この削減の最適性を確立するために、$\widetilde{O}\left(SA\frac{H}{(1-\gamma)^2\varepsilon^2} \right)$サンプルが$\varepsilon$-optimal policyを学習するのに十分であることを示す$\gamma$-discounted MDPsに対する改善されたバウンダリを開発し、$\widetilde{\Omega}\left(SA\frac{1}{(1-\gamma)^3\varepsilon^2} \right)のよく知られた下限を回避した。
分析では,スパンパラメータの観点から,特定のインスタンス依存分散パラメータの上限を求める。
これらの境界は、MDPの混合時間や直径に基づくものよりも厳密であり、より広い用途がある可能性がある。
関連論文リスト
- Sharper Model-free Reinforcement Learning for Average-reward Markov
Decision Processes [21.77276136591518]
我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。
シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
論文 参考訳(メタデータ) (2023-06-28T17:43:19Z) - 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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs
with a Generative Model [3.749193647980305]
本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。
モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
論文 参考訳(メタデータ) (2021-05-28T17:49:39Z) - 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) - Efficiently Solving MDPs with Stochastic Mirror Descent [38.30919646721354]
線形モデルに与えられた無限水平マルコフ決定過程(MDP)を近似的に解くための統一的な枠組みを提案する。
これらの結果は、より一般的なミラー降下フレームワークを用いて、単純なドメインとボックスドメインで大域的なサドルポイント問題を解くことによって達成される。
論文 参考訳(メタデータ) (2020-08-28T17:58:40Z) - Provably Efficient Reinforcement Learning for Discounted MDPs with
Feature Mapping [99.59319332864129]
本稿では,割引決定(MDP)のための強化学習について検討する。
本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。
以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-23T17:08:54Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。