論文の概要: The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis
- arxiv url: http://arxiv.org/abs/2410.07616v1
- Date: Thu, 10 Oct 2024 05:08:14 GMT
- ステータス: 処理完了
- システム内更新日: 2024-10-31 15:56:40.644285
- Title: The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis
- Title（参考訳）: 平均逆・非カウントMDPに対するプラグインアプローチ: 最適サンプル複雑度解析
- Authors: Matthew Zurek, Yudong Chen,
- Abstract要約: 平均回帰マルコフ決定過程において,$varepsilon$-optimal Policyを学習するためのプラグインアプローチのサンプル複雑性について検討した。
この問題の最も単純なアルゴリズムであるにもかかわらず、プラグインのアプローチは理論上は分析されていない。
- 参考スコア（独自算出の注目度）: 6.996002801232415
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the sample complexity of the plug-in approach for learning $\varepsilon$-optimal policies in average-reward Markov decision processes (MDPs) with a generative model. The plug-in approach constructs a model estimate then computes an average-reward optimal policy in the estimated model. Despite representing arguably the simplest algorithm for this problem, the plug-in approach has never been theoretically analyzed. Unlike the more well-studied discounted MDP reduction method, the plug-in approach requires no prior problem information or parameter tuning. Our results fill this gap and address the limitations of prior approaches, as we show that the plug-in approach is optimal in several well-studied settings without using prior knowledge. Specifically it achieves the optimal diameter- and mixing-based sample complexities of $\widetilde{O}\left(SA \frac{D}{\varepsilon^2}\right)$ and $\widetilde{O}\left(SA \frac{\tau_{\mathrm{unif}}}{\varepsilon^2}\right)$, respectively, without knowledge of the diameter $D$ or uniform mixing time $\tau_{\mathrm{unif}}$. We also obtain span-based bounds for the plug-in approach, and complement them with algorithm-specific lower bounds suggesting that they are unimprovable. Our results require novel techniques for analyzing long-horizon problems which may be broadly useful and which also improve results for the discounted plug-in approach, removing effective-horizon-related sample size restrictions and obtaining the first optimal complexity bounds for the full range of sample sizes without reward perturbation.
- Abstract（参考訳）: 平均回帰マルコフ決定過程(MDP)における$\varepsilon$-optimal Policyを生成モデルで学習するためのプラグインアプローチのサンプル複雑性について検討した。
プラグインアプローチはモデル推定を構築し、推定モデルにおける平均回帰最適ポリシーを計算する。
この問題の最も単純なアルゴリズムであるにもかかわらず、プラグインのアプローチは理論上は分析されていない。
よりよく研究された割引MDP削減手法とは異なり、プラグイン方式では事前の問題情報やパラメータチューニングは不要である。
このギャップを埋めて,事前の知識を使わずに,いくつかのよく研究された環境でプラグインアプローチが最適であることを示すため,従来のアプローチの限界に対処する。
具体的には、$\widetilde{O}\left(SA \frac{D}{\varepsilon^2}\right)$と$\widetilde{O}\left(SA \frac{\tau_{\mathrm{unif}}}{\varepsilon^2}\right)$の最適な直径と混合に基づくサンプル複合体を、直径の$D$または均一混合時間$\tau_{\mathrm{unif}}$の知識なしでそれぞれ達成する。
また、プラグインアプローチのスパンベースバウンダリを取得し、アルゴリズム固有の下限を補完することで、そのバウンダリが改善不可能であることを示唆する。
提案手法は, 広範に有用であり, かつ, ディスカウントされたプラグインアプローチの結果の改善, 有効水平関連サンプルサイズ制限の除去, および, 報奨を伴わない全サンプルサイズに対する最初の最適複雑性境界の獲得を必要とする。
関連論文リスト
- Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Sharper Rates and Flexible Framework for Nonconvex SGD with Client and
Data Sampling [64.31011847952006]
我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。
我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。
我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
論文 参考訳（メタデータ） (2022-06-05T21:32:33Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z) - Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with
Plug-in Solver [32.212146650873194]
報酬信号のガイダンスを使わずにRLモデルを効率的に学習するためのアプローチを提案する。
特に、私たちは、探索フェーズにおけるモデル学習に集中するプラグインソルバアプローチを採用しています。
新たな探索アルゴリズムを確立することで,プラグインアプローチは環境との相互作用を$tildeO(d2H3/epsilon2)$とすることでモデルを学習することを示す。
論文 参考訳（メタデータ） (2021-10-07T07:59:50Z) - Towards Tight Bounds on the Sample Complexity of Average-reward MDPs [39.01663172393174]
生成モデルにアクセス可能な無限水平平均回帰マルコフ決定過程の最適方針を求める。
状態-作用対あたりのサンプルを$widetildeO(t_mathrmmix epsilon-3)$ (oblivious) で解決するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-13T17:18:11Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement
Learning? [30.065091907118827]
本研究は,マルコフ決定過程(MDP)における$epsilon$-optimal Policyの発見の複雑さについて考察する。
実験モデルを構築し,任意のプラグインソルバを用いて実験モデルを計画するプラグインソルバ手法を用いてこの問題を解決する。
プラグインアプローチはサンプル効率も向上し,強化学習のためのモデルベースアルゴリズムを設計するための柔軟なアプローチを提供する。
論文 参考訳（メタデータ） (2020-10-12T13:13:01Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs
with Near-optimal Regret [44.374427255708135]
無限水平平均逆マルコフ決定過程(MDP)のモデルフリーアルゴリズムである探索強化Q-ラーニング(EE-QL)を提案する。
EE-QLは、最適平均報酬のオンライン集中近似が利用可能であると仮定する。
これは、エルゴード的な仮定なしに$O(sqrt T)$後悔を達成する最初のモデル自由学習アルゴリズムであり、対数的因子を除いて、下位境界の$T$と一致する。
論文 参考訳（メタデータ） (2020-06-08T05:09:32Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。