論文の概要: An Adaptive State Aggregation Algorithm for Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2107.11053v1
• Date: Fri, 23 Jul 2021 07:19:43 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-26 14:12:30.381619
• Title: An Adaptive State Aggregation Algorithm for Markov Decision Processes
• Title（参考訳）: マルコフ決定過程に対する適応的状態集約アルゴリズム
• Authors: Guanting Chen, Johann Demetrio Gaebler, Matt Peng, Chunlin Sun, Yinyu Ye
• Abstract要約: 同様のコスト・ツー・ゴー値の状態を動的にグループ化することで、価値反復更新のコストを削減できるMDPを解くための直感的なアルゴリズムを提案する。 我々のアルゴリズムはほぼ確実に(2varepsilon / (1 - gamma) に収束し、(γ) は割引係数であり、集約された状態は最大で (varepsilon) 異なる。
• 参考スコア（独自算出の注目度）: 10.494611365482028
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Value iteration is a well-known method of solving Markov Decision Processes (MDPs) that is simple to implement and boasts strong theoretical convergence guarantees. However, the computational cost of value iteration quickly becomes infeasible as the size of the state space increases. Various methods have been proposed to overcome this issue for value iteration in large state and action space MDPs, often at the price, however, of generalizability and algorithmic simplicity. In this paper, we propose an intuitive algorithm for solving MDPs that reduces the cost of value iteration updates by dynamically grouping together states with similar cost-to-go values. We also prove that our algorithm converges almost surely to within \(2\varepsilon / (1 - \gamma)\) of the true optimal value in the \(\ell^\infty\) norm, where \(\gamma\) is the discount factor and aggregated states differ by at most \(\varepsilon\). Numerical experiments on a variety of simulated environments confirm the robustness of our algorithm and its ability to solve MDPs with much cheaper updates especially as the scale of the MDP problem increases.
• Abstract（参考訳）: 値反復はマルコフ決定過程(MDP)を解く方法としてよく知られている。 しかし、状態空間のサイズが大きくなるにつれて、価値反復の計算コストは急速に高くなる。 大規模状態と動作空間のmdpにおける価値反復に関するこの問題を克服するために、様々な方法が提案されているが、多くの場合、一般化可能性とアルゴリズムの単純さである。 本稿では,同様のコスト対ゴー値の状態を動的にグループ化することで,価値反復更新のコストを削減できるMDPの直感的解法を提案する。 また、このアルゴリズムは \(\ell^\infty\) ノルムにおける真の最適値の \(2\varepsilon / (1 - \gamma)\) 内でほぼ確実に収束することを証明し、ここで \(\gamma\) は割引係数であり、集約状態は少なくとも \(\varepsilon\) で異なることを証明する。 各種シミュレーション環境における数値実験により,提案アルゴリズムのロバスト性と,特にMDP問題の規模が大きくなるにつれて,より安価にMDPを解く能力が確認された。

関連論文リスト

• Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
  一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。 最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。 我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
  論文  参考訳（メタデータ） (2024-04-19T06:24:22Z)
• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching [53.91395791840179]
  我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。 USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
  論文  参考訳（メタデータ） (2023-12-19T02:27:22Z)
• Non-stationary Reinforcement Learning under General Function Approximation [60.430936031067006]
  まず,非定常MDPに対する動的ベルマンエルダー次元(DBE)と呼ばれる新しい複雑性指標を提案する。 提案する複雑性指標に基づいて,SW-OPEAと呼ばれる新しい信頼度セットに基づくモデルフリーアルゴリズムを提案する。 SW-OPEAは,変動予算がそれほど大きくない限り,有効に有効であることを示す。
  論文  参考訳（メタデータ） (2023-06-01T16:19:37Z)
• Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularization [64.60253456266872]
  マルコフ決定プロセス(MDP)は、変化または部分的に知られているシステムのダイナミクスを扱うことを目的としている。 規則化されたMDPは、時間的複雑さを損なうことなく、ポリシー学習の安定性を高める。 ベルマン作用素は、収束と一般化を保証する計画と学習スキームを導出することができる。
  論文  参考訳（メタデータ） (2023-03-12T13:03:28Z)
• Structural Estimation of Markov Decision Processes in High-Dimensional State Space with Finite-Time Guarantees [39.287388288477096]
  本研究では,実施行動と訪問状態の観測可能な履歴に基づいて,人間エージェントによる動的決定の構造モデルの推定作業を検討する。 この問題には固有のネスト構造があり、内部問題では与えられた報酬関数に対する最適ポリシーが特定され、外部問題では適合度の測定が最大化される。 本研究では,高次元状態空間を扱うための有限時間保証付き単一ループ推定アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-04T00:11:38Z)
• Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes [22.07834608976826]
  そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。 本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
  論文  参考訳（メタデータ） (2021-10-21T18:05:40Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Partial Policy Iteration for L1-Robust Markov Decision Processes [13.555107578858307]
  本稿では、ロバストなMDPの共通クラスを解くための新しい効率的なアルゴリズムについて述べる。 我々は、ロバストなMDPのための部分ポリシーイテレーション、新しい、効率的で柔軟な、一般的なポリシーイテレーションスキームを提案する。 実験結果から,提案手法は最先端手法よりも桁違いに高速であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-16T19:50:14Z)
• Scalable First-Order Methods for Robust MDPs [31.29341288414507]
  本稿では、ロバストなMDPを解くための第1次フレームワークを提案する。 値イテレーション更新の精度とコストのトレードオフを慎重に制御することで、O left(A2 S3log(S)log(epsilon-1) epsilon-1 right)$のエルゴード収束率を達成する。
  論文  参考訳（メタデータ） (2020-05-11T21:06:22Z)

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

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