論文の概要: Geometric Policy Iteration for Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2206.05809v1
• Date: Sun, 12 Jun 2022 18:15:24 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-15 05:20:21.704649
• Title: Geometric Policy Iteration for Markov Decision Processes
• Title（参考訳）: マルコフ決定過程の幾何学的政策反復
• Authors: Yue Wu and Jes\'us A. De Loera
• Abstract要約: 最近発見された有限状態作用割引マルコフ決定過程(MDP)の値関数の多面構造は、強化学習の成功を理解することに光を当てた。 ディスカウントされたMDPを解決するために,新しいアルゴリズムであるemphGeometric Policy Iterationを提案する。
• 参考スコア（独自算出の注目度）: 4.746723775952672
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently discovered polyhedral structures of the value function for finite state-action discounted Markov decision processes (MDP) shed light on understanding the success of reinforcement learning. We investigate the value function polytope in greater detail and characterize the polytope boundary using a hyperplane arrangement. We further show that the value space is a union of finitely many cells of the same hyperplane arrangement and relate it to the polytope of the classical linear programming formulation for MDPs. Inspired by these geometric properties, we propose a new algorithm, \emph{Geometric Policy Iteration} (GPI), to solve discounted MDPs. GPI updates the policy of a single state by switching to an action that is mapped to the boundary of the value function polytope, followed by an immediate update of the value function. This new update rule aims at a faster value improvement without compromising computational efficiency. Moreover, our algorithm allows asynchronous updates of state values which is more flexible and advantageous compared to traditional policy iteration when the state set is large. We prove that the complexity of GPI achieves the best known bound $\bigO{\frac{|\actions|}{1 - \gamma}\log \frac{1}{1-\gamma}}$ of policy iteration and empirically demonstrate the strength of GPI on MDPs of various sizes.
• Abstract（参考訳）: 近年,有限状態作用割引マルコフ決定過程(mdp)における値関数の多面体構造が,強化学習の成功に光を当てている。 我々は,ポリトープの値関数を詳細に検討し,超平面配置を用いてポリトープ境界を特徴付ける。 さらに、値空間は、同じ超平面配置の有限個のセルの和であり、MDPの古典線形計画法(英語版)のポリトープと関係していることを示す。 これらの幾何学的性質に触発されて、割引されたMDPを解決するために、新しいアルゴリズム \emph{Geometric Policy Iteration} (GPI) を提案する。 GPIは、値関数ポリトープの境界にマッピングされたアクションに切り替えて単一の状態のポリシーを更新し、その後、値関数の即時更新を行う。 この新しい更新ルールは、計算効率を損なうことなく、より高速な価値改善を目指している。 さらに,提案アルゴリズムは,状態集合が大きい場合の従来のポリシーの繰り返しよりも柔軟で有利な状態値の非同期更新を可能にする。 GPIの複雑さは、最もよく知られた有界な$\bigO{\frac{|\actions|}{1 - \gamma}\log \frac{1}{1-\gamma}}$のポリシー反復を実現し、様々な大きさのMDP上のGPIの強さを実証的に示す。

関連論文リスト

• Confident Natural Policy Gradient for Local Planning in $q_π$-realizable Constrained MDPs [44.69257217086967]
  制約付きマルコフ決定プロセス(CMDP)フレームワークは、安全性や他の重要な目的を課すための重要な強化学習アプローチとして出現する。 本稿では,線形関数近似が$q_pi$-realizabilityで与えられる学習問題に対処する。
  論文  参考訳（メタデータ） (2024-06-26T17:57:13Z)
• On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes [50.68789924454235]
  我々は、平均報酬マルコフ決定過程(MDP)の文脈における政策勾配の最初の有限時間大域収束解析を示す。 我々の分析によると、ポリシー勾配は、$Oleft(frac1Tright)$のサブリニアレートで最適ポリシーに収束し、$Oleft(log(T)right)$ regretに変換され、$T$は反復数を表す。
  論文  参考訳（メタデータ） (2024-03-11T15:25:03Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。 我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。 我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
  論文  参考訳（メタデータ） (2023-06-20T17:27:31Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。 最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。 本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
  論文  参考訳（メタデータ） (2022-05-28T04:05:20Z)
• Robust and Adaptive Temporal-Difference Learning Using An Ensemble of Gaussian Processes [70.80716221080118]
  本稿では、時間差学習(TD)による政策評価の世代的視点について考察する。 OS-GPTDアプローチは、状態-逆ペアのシーケンスを観測することにより、与えられたポリシーの値関数を推定するために開発された。 1つの固定カーネルに関連する限られた表現性を緩和するために、GP前の重み付けアンサンブル(E)を用いて代替のスキームを生成する。
  論文  参考訳（メタデータ） (2021-12-01T23:15:09Z)
• 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 Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function [14.205660708980988]
  固定水平マルコフ決定過程(MDP)における局所的計画の問題点を生成モデルを用いて考察する。 最近の下界は、最適ポリシーの作用値関数が線形に実現可能である場合の関連する問題は指数的なクエリ数を必要とすることを証明している。 本研究では,アクションセットが小さい場合,ポリ$(H, d)$学習が(状態値関数の実現可能性を持つ)可能であることを確かめる。
  論文  参考訳（メタデータ） (2021-02-03T13:23:15Z)
• Queueing Network Controls via Deep Reinforcement Learning [0.0]
  待ち行列ネットワークのためのポリシ最適化アルゴリズムを開発した。 このアルゴリズムは、文学における最先端よりも優れた制御ポリシーを一貫して生成する。 PPOアルゴリズムの成功の鍵は、相対値関数を推定するために3つの分散還元技術を使用することである。
  論文  参考訳（メタデータ） (2020-07-31T01:02:57Z)
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization [44.24881971917951]
  自然政策勾配法(NPG)は、最も広く使われている政策最適化アルゴリズムの一つである。 我々は,ソフトマックスパラメータ化の下で,エントロピー規則化NPG法に対する収束保証を開発する。 この結果から, エントロピー正則化の役割を浮き彫りにした。
  論文  参考訳（メタデータ） (2020-07-13T17:58:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。