論文の概要: Stochastic first-order methods for average-reward Markov decision
processes
- arxiv url: http://arxiv.org/abs/2205.05800v1
- Date: Wed, 11 May 2022 23:02:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2022-05-14 02:31:55.491422
- Title: Stochastic first-order methods for average-reward Markov decision
processes
- Title（参考訳）: 平均回帰マルコフ決定過程に対する確率的一階法
- Authors: Tianjiao Li, Feiyang Wu and Guanghui Lan
- Abstract要約: 平均回帰マルコフ決定過程(AMDP)の問題点について検討する。
我々は,政策評価と最適化の両面において,強力な理論的保証を持つ新しい一階法を開発した。
- 参考スコア（独自算出の注目度）: 10.483316336206903
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of average-reward Markov decision processes (AMDPs) and
develop novel first-order methods with strong theoretical guarantees for both
policy evaluation and optimization. Existing on-policy evaluation methods
suffer from sub-optimal convergence rates as well as failure in handling
insufficiently random policies, e.g., deterministic policies, for lack of
exploration. To remedy these issues, we develop a novel variance-reduced
temporal difference (VRTD) method with linear function approximation for
randomized policies along with optimal convergence guarantees, and an
exploratory variance-reduced temporal difference (EVRTD) method for
insufficiently random policies with comparable convergence guarantees. We
further establish linear convergence rate on the bias of policy evaluation,
which is essential for improving the overall sample complexity of policy
optimization. On the other hand, compared with intensive research interest in
finite sample analysis of policy gradient methods for discounted MDPs, existing
studies on policy gradient methods for AMDPs mostly focus on regret bounds
under restrictive assumptions on the underlying Markov processes (see, e.g.,
Abbasi-Yadkori et al., 2019), and they often lack guarantees on the overall
sample complexities. Towards this end, we develop an average-reward variant of
the stochastic policy mirror descent (SPMD) (Lan, 2022). We establish the first
$\widetilde{\mathcal{O}}(\epsilon^{-2})$ sample complexity for solving AMDPs
with policy gradient method under both the generative model (with unichain
assumption) and Markovian noise model (with ergodic assumption). This bound can
be further improved to $\widetilde{\mathcal{O}}(\epsilon^{-1})$ for solving
regularized AMDPs. Our theoretical advantages are corroborated by numerical
experiments.
- Abstract（参考訳）: 平均回帰マルコフ決定過程 (amdps) の問題を調査し, 政策評価と最適化に強い理論的保証を持つ新しい一階法を開発した。
既存のオン・ポリティクス評価手法は、最適化されていない収束率と、不十分なランダムな政策、例えば決定論的政策、探査の欠如に苦しむ。
そこで本研究では,ランダム化ポリシーに対する線形関数近似と最適収束保証を併用した新しい分散分散分散時間差法(vrtd)と,同等の収束保証を満たさない不完全分散時間差法(evrtd)を開発した。
さらに,政策最適化の全体的サンプル複雑性を改善する上で不可欠な,政策評価のバイアスに基づく線形収束率を確立する。
一方、割引MDPの政策勾配法に関する有限サンプル分析における集中的な研究と比較して、AMDPの政策勾配法に関する既存の研究は、基礎となるマルコフ過程(例えば、Abbasi-Yadkori et al., 2019)の制約的な仮定の下での後悔境界に主に焦点を絞っている。
この目的に向けて,確率的政策ミラー降下 (spmd) の平均回帰型 (lan, 2022) を開発した。
我々は、生成モデル(ユニチェーン仮定)とマルコフ雑音モデル(エルゴード仮定)の両方の下でポリシー勾配法を用いてAMDPを解くために、最初の$\widetilde{\mathcal{O}}(\epsilon^{-2})$サンプル複雑性を確立する。
この境界は正規化AMDPを解くために$\widetilde{\mathcal{O}}(\epsilon^{-1})$にさらに改善することができる。
我々の理論上の利点は数値実験によって裏付けられる。
関連論文リスト
- Achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ Regret in Average-Reward POMDPs with Known Observation Models [56.92178753201331]
平均逆無限水平POMDPを未知の遷移モデルで扱う。
この障壁を克服する斬新でシンプルな推定器を提示する。
論文 参考訳（メタデータ） (2025-01-30T22:29:41Z) - Policy Gradient for Robust Markov Decision Processes [16.281897051782863]
本稿では、ロバストなマルコフ決定過程(MDP)を解くために、新しいポリシー勾配法であるダブルループロバストポリシーミラーDescent(MD)を提案する。
MDは、イテレーション毎の適応耐性を持つポリシー最適化に一般的なミラー降下更新ルールを採用し、グローバルな最適ポリシーへの収束を保証する。
我々は,直接パラメータ化とソフトマックスパラメータ化の両方の下での新しい収束結果を含むMDの包括的解析を行い,トランジションミラー・アセンション(TMA)による内部問題の解に対する新たな洞察を提供する。
論文 参考訳（メタデータ） (2024-10-29T15:16:02Z) - Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
我々は,POMDPパラメータを信念に基づくポリシを用いて収集したサンプルから学習することのできる観測・認識スペクトル(OAS)推定手法を提案する。
提案するOAS-UCRLアルゴリズムに対して,OASプロシージャの整合性を示し,$mathcalO(sqrtT log(T)$の残差保証を証明した。
論文 参考訳（メタデータ） (2024-10-02T08:46:34Z) - Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs [82.34567890576423]
我々は,非漸近収束を伴う最適決定主義政策を求めるための決定主義的政策勾配原始双対法を開発した。
D-PGPDの一次-双対反復は、最適正則化原始-双対にサブ線形速度で収束することが証明された。
我々の知る限り、これは連続空間制約型MDPに対する決定論的ポリシー探索法を提案する最初の研究であると思われる。
論文 参考訳（メタデータ） (2024-08-19T14:11:04Z) - Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning [62.81324245896717]
我々はC-PGと呼ばれる探索非依存のアルゴリズムを導入し、このアルゴリズムは(弱)勾配支配仮定の下でのグローバルな最終点収束を保証する。
制約付き制御問題に対して,我々のアルゴリズムを数値的に検証し,それらを最先端のベースラインと比較する。
論文 参考訳（メタデータ） (2024-07-15T14:54:57Z) - Score-Aware Policy-Gradient Methods and Performance Guarantees using Local Lyapunov Conditions: Applications to Product-Form Stochastic Networks and Queueing Systems [1.747623282473278]
本稿では,ネットワーク上の決定過程(MDP)から得られる定常分布のタイプを利用したモデル強化学習(RL)のポリシー段階的手法を提案する。
具体的には、政策パラメータによってMDPの定常分布がパラメータ化されている場合、平均回帰推定のための既存の政策手法を改善することができる。
論文 参考訳（メタデータ） (2023-12-05T14:44:58Z) - A safe exploration approach to constrained Markov decision processes [7.036452261968767]
無限水平制限マルコフ決定過程(CMDP)について考察する。
目標は、期待される累積的制約の対象となる累積的報酬を最大化する最適なポリシーを見つけることである。
安全クリティカルなシステムのオンライン学習におけるCMDPの適用により、モデルフリーでシミュレータフリーなアルゴリズムの開発に焦点をあてる。
論文 参考訳（メタデータ） (2023-12-01T13:16:39Z) - Last-Iterate Convergent Policy Gradient Primal-Dual Methods for
Constrained MDPs [107.28031292946774]
無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。
我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。
我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
論文 参考訳（メタデータ） (2023-06-20T17:27:31Z) - High-probability sample complexities for policy evaluation with linear function approximation [88.87036653258977]
本研究では,2つの広く利用されている政策評価アルゴリズムに対して,最適線形係数の予め定義された推定誤差を保証するために必要なサンプル複素量について検討する。
高確率収束保証に縛られた最初のサンプル複雑性を確立し、許容レベルへの最適依存を実現する。
論文 参考訳（メタデータ） (2023-05-30T12:58:39Z) - First-order Policy Optimization for Robust Markov Decision Process [40.2022466644885]
我々はロバストマルコフ決定過程(MDP)の解法を考える。
MDPは、不確実な遷移カーネルを持つ割引状態、有限状態、有限作用空間 MDP の集合を含む。
$(mathbfs,mathbfa)$-矩形不確かさ集合に対して、ロバストな目的に関するいくつかの構造的な観察を確立する。
論文 参考訳（メタデータ） (2022-09-21T18:10:28Z) - Variance-Reduced Off-Policy Memory-Efficient Policy Search [61.23789485979057]
政治政策の最適化は強化学習において難しい問題である。
オフポリシーアルゴリズムはメモリ効率が高く、オフポリシーサンプルから学ぶことができる。
論文 参考訳（メタデータ） (2020-09-14T16:22:46Z) - Fast Global Convergence of Natural Policy Gradient Methods with Entropy
Regularization [44.24881971917951]
自然政策勾配法(NPG)は、最も広く使われている政策最適化アルゴリズムの一つである。
我々は,ソフトマックスパラメータ化の下で,エントロピー規則化NPG法に対する収束保証を開発する。
この結果から, エントロピー正則化の役割を浮き彫りにした。
論文 参考訳（メタデータ） (2020-07-13T17:58:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。