論文の概要: Policy Mirror Descent Inherently Explores Action Space
- arxiv url: http://arxiv.org/abs/2303.04386v1
- Date: Wed, 8 Mar 2023 05:19:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-09 15:01:02.939788
- Title: Policy Mirror Descent Inherently Explores Action Space
- Title（参考訳）: 政策鏡「Descent」がアクションスペースを探索
- Authors: Yan Li, Guanghui Lan
- Abstract要約: MDP構造によって,国家空間の探査が示唆される場合,高度な探査戦略の必要性はほとんどないと考えられる。
ポリシーミラー降下と呼ばれるポリシー勾配法を無限地平線に適用する。
我々は$mathcalH_mathcalD$を有効地平線と作用空間の大きさの発散依存関数として特徴づける。
- 参考スコア（独自算出の注目度）: 10.772560347950053
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Designing computationally efficient exploration strategies for on-policy
first-order methods that attain optimal $\mathcal{O}(1/\epsilon^2)$ sample
complexity remains open for solving Markov decision processes (MDP). This
manuscript provides an answer to this question from a perspective of
simplicity, by showing that whenever exploration over the state space is
implied by the MDP structure, there seems to be little need for sophisticated
exploration strategies. We revisit a stochastic policy gradient method, named
stochastic policy mirror descent, applied to the infinite horizon, discounted
MDP with finite state and action spaces. Accompanying SPMD we present two
on-policy evaluation operators, both simply following the policy for trajectory
collection with no explicit exploration, or any form of intervention. SPMD with
the first evaluation operator, named value-based estimation, tailors to the
Kullback-Leibler (KL) divergence. Provided the Markov chains on the state space
of generated policies are uniformly mixing with non-diminishing minimal
visitation measure, an $\tilde{\mathcal{O}}( 1 / \epsilon^2)$ sample complexity
is obtained with a linear dependence on the size of the action space. SPMD with
the second evaluation operator, named truncated on-policy Monte Carlo, attains
an $\tilde{\mathcal{O}}(\mathcal{H}_{\mathcal{D}} / \epsilon^2)$ sample
complexity, with the same assumption on the state chains of generated policies.
We characterize $\mathcal{H}_{\mathcal{D}}$ as a divergence-dependent function
of the effective horizon and the size of the action space, which leads to an
exponential dependence of the latter two quantities for the KL divergence, and
a polynomial dependence for the divergence induced by negative Tsallis entropy.
These obtained sample complexities seem to be new among on-policy stochastic
policy gradient methods without explicit explorations.
- Abstract（参考訳）: 最適$\mathcal{O}(1/\epsilon^2)$サンプルの複雑さはマルコフ決定過程(MDP)の解法として未解決のままである。
本書は, 国家空間の探査がMDP構造によって示唆される場合, 高度な探査戦略の必要性はほとんどないことを示すことによって, 単純性の観点から, この疑問に対する回答を提供するものである。
本研究では,有限状態と作用空間を有するMDPを割引した確率的ポリシー勾配法である確率的ポリシーミラー降下法を再検討する。
SPMDを伴って2つのオン・ポリティクス評価演算子を提示する。どちらも、明示的な探索のない軌跡収集の方針に従うか、いかなる形での介入を行うかのどちらかである。
SPMDは、値ベース推定と呼ばれる最初の評価演算子で、KL(Kulback-Leibler)の発散を補う。
生成したポリシの状態空間上のマルコフ連鎖が非最小訪問測度と均一に混合されている場合、$\tilde{\mathcal{O}}(1 / \epsilon^2)$サンプル複雑性は、アクション空間のサイズに線形に依存する。
2番目の評価演算子である truncated on-policy monte carlo で spmd は、生成したポリシーの状態連鎖と同じ仮定で、$\tilde{\mathcal{o}}(\mathcal{h}_{\mathcal{d}} / \epsilon^2)$ のサンプル複雑性を達成する。
我々は$\mathcal{H}_{\mathcal{D}}$を、有効地平線と作用空間の大きさの発散依存性関数として特徴づけ、KL の発散に対する後者の 2 量の指数関数依存と、負の Tsallis エントロピーによって引き起こされる発散に対する多項式依存を導く。
これらの試料複合体は, 明示的な探索を行わず, 政治上の確率的政策勾配法の中で新しいものと考えられる。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with
General Utilities [12.104551746465932]
安全マルチエージェント強化学習について検討し、エージェントはそれぞれの安全制約を満たしつつ、局所的な目的の総和をまとめて最大化しようとする。
我々のアルゴリズムは、$mathcalOleft(T-2/3right)$のレートで1次定常点(FOSP)に収束する。
サンプルベースの設定では、高い確率で、我々のアルゴリズムは、$epsilon$-FOSPを達成するために$widetildemathcalOleft(epsilon-3.5right)$サンプルが必要です。
論文 参考訳（メタデータ） (2023-05-27T20:08:35Z) - Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。
我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。
我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
論文 参考訳（メタデータ） (2023-03-17T17:53:28Z) - First-order Policy Optimization for Robust Markov Decision Process [40.2022466644885]
我々はロバストマルコフ決定過程(MDP)の解法を考える。
MDPは、不確実な遷移カーネルを持つ割引状態、有限状態、有限作用空間 MDP の集合を含む。
$(mathbfs,mathbfa)$-矩形不確かさ集合に対して、ロバストな目的に関するいくつかの構造的な観察を確立する。
論文 参考訳（メタデータ） (2022-09-21T18:10:28Z) - Sample Complexity of Nonparametric Off-Policy Evaluation on
Low-Dimensional Manifolds using Deep Networks [71.95722100511627]
深層ニューラルネットワークを用いた強化学習における非政治的評価問題について考察する。
ネットワークサイズを適切に選択することにより、マルコフ決定過程において低次元多様体構造を利用することができることを示す。
論文 参考訳（メタデータ） (2022-06-06T20:25:20Z) - Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov
Decision Processes [61.11090361892306]
Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。
この分離は線形MDPの設定には存在しないことを示す。
我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-01-26T22:09:59Z) - Homotopic Policy Mirror Descent: Policy Convergence, Implicit
Regularization, and Improved Sample Complexity [40.2022466644885]
有限状態と作用空間を持つ割引・無限水平型MDPを解くホモトピーポリシーミラー降下法(HPMD)法。
政策勾配法に関する文献では, 新たな3つの特性が報告されている。
論文 参考訳（メタデータ） (2022-01-24T04:54:58Z) - MDPGT: Momentum-based Decentralized Policy Gradient Tracking [29.22173174168708]
マルチエージェント強化学習のための運動量に基づく分散型ポリシー勾配追跡(MDPGT)を提案する。
MDPGTは、グローバル平均の$N$ローカルパフォーマンス関数の$epsilon-stationaryポイントに収束するために$mathcalO(N-1epsilon-3)$の最良のサンプル複雑性を実現する。
これは、分散モデルレス強化学習における最先端のサンプル複雑さよりも優れています。
論文 参考訳（メタデータ） (2021-12-06T06:55:51Z) - Settling the Horizon-Dependence of Sample Complexity in Reinforcement
Learning [82.31436758872715]
我々は,環境相互作用の$O(1)$のエピソードのみを用いて,同一のPAC保証を実現するアルゴリズムを開発した。
値関数と有限水平マルコフ決定過程の接続を確立する。
論文 参考訳（メタデータ） (2021-11-01T00:21:24Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。