論文の概要: 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})$にさらに改善することができる。
我々の理論上の利点は数値実験によって裏付けられる。
関連論文リスト
- Randomized Policy Optimization for Optimal Stopping [0.0]
本稿では,ランダム化線形ポリシーに基づく最適停止手法を提案する。
提案手法は最先端手法を著しく上回り得ることを示す。
論文 参考訳（メタデータ） (2022-03-25T04:33:15Z) - Block Policy Mirror Descent [40.2022466644885]
ブロックポリシミラー降下(BPMD)という新しいポリシークラス(PG)手法を提案する。
BPMDは、強い凸正則化を伴う正規化強化学習(RL)のクラスを解決するために用いられる。
強化学習におけるポリシー最適化のために,ブロック座標降下法が開発され,解析されたのはこれが初めてである。
論文 参考訳（メタデータ） (2022-01-15T04:42:02Z) - MDPGT: Momentum-based Decentralized Policy Gradient Tracking [29.22173174168708]
マルチエージェント強化学習のための運動量に基づく分散型ポリシー勾配追跡(MDPGT)を提案する。
MDPGTは、グローバル平均の$N$ローカルパフォーマンス関数の$epsilon-stationaryポイントに収束するために$mathcalO(N-1epsilon-3)$の最良のサンプル複雑性を実現する。
これは、分散モデルレス強化学習における最先端のサンプル複雑さよりも優れています。
論文 参考訳（メタデータ） (2021-12-06T06:55:51Z) - Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。
次に,政策最適化におけるコミット率の概念を紹介する。
第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文 参考訳（メタデータ） (2021-10-29T06:35:44Z) - Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy
Gradient Methods with Entropy Regularization [9.622367651590878]
古典的エントロピー正規化政策勾配法をソフトマックス政策パラメトリゼーションで再検討する。
エントロピー項によって導入された対数的ポリシー報酬により、推定子自身は一般に非有界であることが証明されるが、分散は一様有界である。
これにより、定常点と大域的最適ポリシーの両方に対するエントロピー正規化ポリシー勾配法の最初の収束結果の開発が可能となる。
論文 参考訳（メタデータ） (2021-10-19T17:21:09Z) - A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。
PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
論文 参考訳（メタデータ） (2021-07-23T19:38:17Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。
その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
論文 参考訳（メタデータ） (2021-04-09T14:50:59Z) - Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
Softmax Policy gradient(PG)メソッドは、現代の強化学習におけるポリシー最適化の事実上の実装の1つです。
ソフトマックス PG 法は、$mathcalS|$ および $frac11-gamma$ の観点から指数時間で収束できることを実証する。
論文 参考訳（メタデータ） (2021-02-22T18:56:26Z) - On the Convergence and Sample Efficiency of Variance-Reduced Policy
Gradient Method [38.34416337932712]
政策は、例えばREINFORCEのようなリッチな強化学習(RL)手法を生み出します。
しかし、そのようなメソッドが$epsilon$-optimal Policyを見つけるための最もよく知られたサンプルの複雑さは$mathcalO(epsilon-3)$である。
第一次政策最適化法の基本収束特性とサンプル効率について検討する。
論文 参考訳（メタデータ） (2021-02-17T07:06:19Z) - Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
平均報酬MDPの関数近似によるオフポリシ政策評価を検討する。
ブートストラップは必要であり、オフポリシ学習とFAと一緒に、致命的なトライアドをもたらす。
そこで本研究では,勾配型tdアルゴリズムの成功を再現する2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-08T00:43:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。