論文の概要: First-order Policy Optimization for Robust Markov Decision Process
- arxiv url: http://arxiv.org/abs/2209.10579v1
- Date: Wed, 21 Sep 2022 18:10:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-23 12:58:29.942789
- Title: First-order Policy Optimization for Robust Markov Decision Process
- Title(参考訳): ロバストマルコフ決定過程の1次政策最適化
- Authors: Yan Li, Tuo Zhao, Guanghui Lan
- Abstract要約: 我々は,安定なマルコフ決定過程 (MDP) の解法について考察する。これは,不確実な遷移カーネルを持つ,割引された有限状態有限作用空間 MDP の集合を含む。
$(mathbfs,mathbfa)$-矩形不確かさ集合に対して、ポリシーに基づく一階法、すなわちロバストポリシーミラー降下法(RPMD)を開発する。
一般のブレグマン発散に対して、$mathcalO(max 1/epsilon, 1/(eta epsilon2)$ complexityを確立する。
- 参考スコア(独自算出の注目度): 40.2022466644885
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of solving robust Markov decision process (MDP),
which involves a set of discounted, finite state, finite action space MDPs with
uncertain transition kernels. The goal of planning is to find a robust policy
that optimizes the worst-case values against the transition uncertainties, and
thus encompasses the standard MDP planning as a special case. For
$(\mathbf{s},\mathbf{a})$-rectangular uncertainty sets, we develop a
policy-based first-order method, namely the robust policy mirror descent
(RPMD), and establish an $\mathcal{O}(\log(1/\epsilon))$ and
$\mathcal{O}(1/\epsilon)$ iteration complexity for finding an
$\epsilon$-optimal policy, with two increasing-stepsize schemes. The prior
convergence of RPMD is applicable to any Bregman divergence, provided the
policy space has bounded radius measured by the divergence when centering at
the initial policy. Moreover, when the Bregman divergence corresponds to the
squared euclidean distance, we establish an $\mathcal{O}(\max \{1/\epsilon,
1/(\eta \epsilon^2)\})$ complexity of RPMD with any constant stepsize $\eta$.
For a general class of Bregman divergences, a similar complexity is also
established for RPMD with constant stepsizes, provided the uncertainty set
satisfies the relative strong convexity. We further develop a stochastic
variant, named SRPMD, when the first-order information is only available
through online interactions with the nominal environment. For general Bregman
divergences, we establish an $\mathcal{O}(1/\epsilon^2)$ and
$\mathcal{O}(1/\epsilon^3)$ sample complexity with two increasing-stepsize
schemes. For the euclidean Bregman divergence, we establish an
$\mathcal{O}(1/\epsilon^3)$ sample complexity with constant stepsizes. To the
best of our knowledge, all the aforementioned results appear to be new for
policy-based first-order methods applied to the robust MDP problem.
- Abstract(参考訳): 我々は,安定なマルコフ決定過程 (MDP) の解法について考察する。これは,不確実な遷移カーネルを持つ,割引された有限状態有限作用空間 MDP の集合を含む。
計画の目標は、移行の不確実性に対して最悪の場合の値を最適化し、そのため、特別のケースとして標準のMDP計画を包含する堅牢な政策を見つけることである。
例えば、$(\mathbf{s},\mathbf{a})$-rectangularの不確実性集合に対して、ポリシーベースの一階法、すなわちロバストなポリシーミラー降下 (rpmd) を開発し、$\mathcal{o}(\log(1/\epsilon))$ と $\mathcal{o}(1/\epsilon)$ という2つの段階的なスキームで$\epsilon$-optimalポリシーを見つけるための反復複雑性を確立する。
RPMDの先行収束は、ポリシー空間が初期ポリシーの中心となるときに発散によって測定される有界半径を持つならば、任意のブレグマン発散に適用できる。
さらに、ブレグマンの発散が二乗ユークリッド距離に対応するとき、任意の定数のステップを持つ rpmd の複雑性を $\eta$ とする $\mathcal{o}(\max \{1/\epsilon, 1/(\eta \epsilon^2)\}) を確立する。
ブレグマン発散の一般クラスに対しては、相対的な強い凸性を満たす不確実性集合が成立すれば、RPMD にも同様の複雑性が確立される。
SRPMDという名前の確率的変種をさらに発展させ、一階情報は名目環境とのオンラインインタラクションを通してのみ利用可能である。
一般的なブレグマンの発散に対して、$\mathcal{O}(1/\epsilon^2)$と$\mathcal{O}(1/\epsilon^3)$のサンプル複雑性を2つの増分スキームで確立する。
ユークリッドブレグマンの発散に対して、定数のステップ化を伴うサンプル複雑性の $\mathcal{o}(1/\epsilon^3)$ を確立する。
我々の知る限り、上記の結果はすべて、ロバストなMDP問題に適用されたポリシーベースの一階法に新しいものと思われる。
関連論文リスト
- First-order Policy Optimization for Robust Policy Evaluation [10.772560347950053]
我々は,ロバストなマルコフ決定プロセスに対する政策最適化の視点を,$mathrms$rectangular ambiguity Setで採用する。
The developed method, named first-order policy evaluation (FRPE) は、決定論的(オフライン)と線形(オンライン)の両方でロバストな政策評価のための最初の統一されたフレームワークを提供する。
論文 参考訳(メタデータ) (2023-07-29T05:22:43Z) - Last-Iterate Convergent Policy Gradient Primal-Dual Methods for
Constrained MDPs [107.28031292946774]
無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。
我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。
我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
論文 参考訳(メタデータ) (2023-06-20T17:27:31Z) - A Theoretical Analysis of Optimistic Proximal Policy Optimization in
Linear Markov Decision Processes [13.466249082564213]
本稿では,全情報フィードバックを用いた表層線形MDPに対するPPOの楽観的変種を提案する。
既存のポリシーベースのアルゴリズムと比較して, 線形MDPと逆線形MDPの双方において, 完全な情報付きで, 最先端の後悔点を達成している。
論文 参考訳(メタデータ) (2023-05-15T17:55:24Z) - Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted
Markov Decision Processes [18.35462792871242]
Policy Mirror Descentは、強化学習における様々な新しい基本的な手法を網羅するアルゴリズムのファミリーである。
不正確な政策評価を伴う政策反復の不安定性に動機づけられたPMDは、PIの政策改善ステップをアルゴリズム的に規則化する。
我々は,適応的なステップサイズの下で,非正規化PSDアルゴリズムの一般ファミリーによって,PIの次元自由な$gamma$-rateが達成可能であることを示す。
論文 参考訳(メタデータ) (2023-02-22T13:55:08Z) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。
シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
論文 参考訳(メタデータ) (2022-09-15T07:22:58Z) - Efficient Policy Iteration for Robust Markov Decision Processes via
Regularization [49.05403412954533]
ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。
最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。
本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
論文 参考訳(メタデータ) (2022-05-28T04:05:20Z) - Stochastic first-order methods for average-reward Markov decision
processes [10.483316336206903]
平均回帰マルコフ決定過程(AMDP)の問題点について検討する。
我々は,政策評価と最適化の両面において,強力な理論的保証を持つ新しい一階法を開発した。
論文 参考訳(メタデータ) (2022-05-11T23:02:46Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳(メタデータ) (2021-02-27T19:28:39Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。