論文の概要: Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process
- arxiv url: http://arxiv.org/abs/2606.16729v1
- Date: Mon, 15 Jun 2026 13:53:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-16 16:21:34.588673
- Title: Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process
- Title（参考訳）: 平均逆マルコフ決定過程における単一軌道からの学習方針
- Authors: Jongmin Lee, Ernest K. Ryu, Vaneet Aggarwal,
- Abstract要約: 弱通信型MDPにおける単一軌道のダイナミクスについて検討する。
問題依存量に関する事前知識を必要としない最初のモデルフリー手法を提案する。
- 参考スコア（独自算出の注目度）: 66.74725576150941
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: While there is an extensive body of work characterizing the sample complexity of discounted cumulative-reward MDPs, finite sample analyses for average-reward MDPs have been limited, and most existing works rely on restrictive assumptions such as ergodicity or access to a generative model. In this work, we establish the first finite sample complexity guarantees from a single trajectory for weakly communicating average-reward MDPs. To this end, we study the dynamics of a single trajectory in weakly communicating MDPs and based on this analysis, we develop novel model-free methods. Notably, our value-based and policy-based methods provide finite sample complexity guarantees of $\widetilde{O}(1/\varepsilon^2)$ and $\widetilde{O}(1/\varepsilon^4)$ from a single trajectory in weakly communicating MDPs, respectively. Furthermore, we introduce the first model-free method that requires no prior knowledge of problem-dependent quantities for communicating MDPs.
- Abstract（参考訳）: 縮小累積再帰型MDPのサンプル複雑性を特徴づける広範な研究は存在するが、平均再帰型MDPの有限サンプル分析は限定的であり、既存の研究の多くはエルゴード性や生成モデルへのアクセスといった制限的な仮定に依存している。
本研究では, 1 つの軌道から, 平均回帰 MDP を弱通信する最初の有限標本複雑性を保証する。
そこで本研究では,MDPの弱い通信における単一軌道のダイナミクスを考察し,その解析に基づいて,新しいモデルフリー手法を提案する。
特に、我々の値ベース法とポリシーベース法は、弱通信MDPの単一軌道から、それぞれ$\widetilde{O}(1/\varepsilon^2)$と$\widetilde{O}(1/\varepsilon^4)$の有限サンプル複雑性を保証する。
さらに,MDPの通信に問題依存量に関する事前知識を必要としない最初のモデルフリー手法を提案する。
関連論文リスト
- Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs [20.54731804867887]
We study the sample complexity of learning in average-reward weak-upupled Markov decision process (WCMDPs) and Restless Bandits (RBs)。
弱結合構造を利用することで、準最適ポリシーは、サンプルの複雑さと計算複雑性によって、$N$で学習できることが示される。
論文 参考訳（メタデータ） (2026-06-12T04:19:53Z) - Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs [8.784438985280092]
部分的に観測可能なマルコフ決定過程(POMDP)における有限ウィンドウポリシーのモデルに基づく学習について検討する。
部分的可観測性の下での学習の一般的なアプローチは、有限の行動観測窓を用いて履歴依存を近似することである。
この超状態 MDP のモデルが利用可能になると、標準的な MDP アルゴリズムを使って最適なポリシーを計算できる。
論文 参考訳（メタデータ） (2026-04-01T15:32:47Z) - Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum [62.691095807959215]
我々は,シングルタイムスケールアクター・クリティック(AC)アルゴリズムを用いて,$O(-2)$の最適なグローバルポリシを得るための最適なサンプル複雑性を確立する。
これらのメカニズムは、既存のディープラーニングアーキテクチャと互換性があり、実用的な適用性を損なうことなく、小さな修正しか必要としない。
論文 参考訳（メタデータ） (2026-02-02T00:35:42Z) - Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning [50.81240969750462]
我々は、ロバスト平均マルコフ決定過程(PMD)における政策評価の第1次有限サンプル解析を提案する。
頑健なベルマン作用素は、慎重に構築された半ノルムの下で収縮し、制御バイアスを持つフレームワークを開発することを示す。
本手法は,ロバストな政策評価とロバストな平均報酬推定のために,$tildemathcalO(epsilon-2)$のオーダー最適サンプル複雑性を実現する。
論文 参考訳（メタデータ） (2025-02-24T03:55:09Z) - A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。
我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。
この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
論文 参考訳（メタデータ） (2021-06-24T13:46:09Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。