論文の概要: Solving Long-run Average Reward Robust MDPs via Stochastic Games
- arxiv url: http://arxiv.org/abs/2312.13912v1
- Date: Thu, 21 Dec 2023 15:00:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-22 14:30:12.796096
- Title: Solving Long-run Average Reward Robust MDPs via Stochastic Games
- Title(参考訳): 確率ゲームによるLong-run Average Reward Robust MDPの解法
- Authors: Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Mehrdad Karrabi,
Petr Novotn\'y, {\DJ}or{\dj}e \v{Z}ikeli\'c
- Abstract要約: 本稿では,長期平均ポリトピック RMDP を解くための新しいポリシーアルゴリズムである Robust Polytopic Policy Iteration (RPPI) を紹介する。
RPPIは、値反復に基づく最先端手法と比較して、長期平均報酬ポリトピー的RMDPerationの解法においてはるかに効率的である。
- 参考スコア(独自算出の注目度): 4.833571004087541
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Markov decision processes (MDPs) provide a standard framework for sequential
decision making under uncertainty. However, transition probabilities in MDPs
are often estimated from data and MDPs do not take data uncertainty into
account. Robust Markov decision processes (RMDPs) address this shortcoming of
MDPs by assigning to each transition an uncertainty set rather than a single
probability value. The goal of solving RMDPs is then to find a policy which
maximizes the worst-case performance over the uncertainty sets. In this work,
we consider polytopic RMDPs in which all uncertainty sets are polytopes and
study the problem of solving long-run average reward polytopic RMDPs. Our focus
is on computational complexity aspects and efficient algorithms. We present a
novel perspective on this problem and show that it can be reduced to solving
long-run average reward turn-based stochastic games with finite state and
action spaces. This reduction allows us to derive several important
consequences that were hitherto not known to hold for polytopic RMDPs. First,
we derive new computational complexity bounds for solving long-run average
reward polytopic RMDPs, showing for the first time that the threshold decision
problem for them is in NP coNP and that they admit a randomized algorithm with
sub-exponential expected runtime. Second, we present Robust Polytopic Policy
Iteration (RPPI), a novel policy iteration algorithm for solving long-run
average reward polytopic RMDPs. Our experimental evaluation shows that RPPI is
much more efficient in solving long-run average reward polytopic RMDPs compared
to state-of-the-art methods based on value iteration.
- Abstract(参考訳): markov decision process (mdps) は不確実性下での逐次意思決定のための標準フレームワークを提供する。
しかし、MDPの遷移確率はしばしばデータから推定され、MDPはデータの不確実性を考慮していない。
ロバスト・マルコフ決定プロセス(RMDP)は、各遷移に単一の確率値ではなく不確実性セットを割り当てることで、MDPのこの欠点に対処する。
RMDPの解決の目標は、不確実性セットに対する最悪のパフォーマンスを最大化するポリシーを見つけることである。
本研究では,全ての不確実性集合がポリトープであるポリトープRMDPについて考察し,長期平均ポリトープRMDPの解法について考察する。
我々の焦点は計算複雑性の側面と効率的なアルゴリズムです。
本稿では,この問題に対する新しい視点を示し,有限状態と作用空間を持つ長ラン平均報酬ターンベースの確率ゲームに還元できることを示す。
この減少により,ポリトピックRMDPを保有することが分かっていなかったいくつかの重要な結果が導出される。
まず,長期平均報酬 RMDP を解くための計算複雑性境界を導出し,そのしきい値決定問題が NP coNP に含まれることを初めて示し,非指数的予測実行時を含むランダム化アルゴリズムを認めた。
第2に, 長期平均報奨ポリトピーrmdpsの解法として, ロバスト・ポリトピー・ポリシー・イテレーション (rppi) を提案する。
実験により、RPPIは、値反復に基づく最先端手法と比較して、長期平均ポリトピー的RMDPの解法においてはるかに効率的であることが示された。
関連論文リスト
- The Curious Price of Distributional Robustness in Reinforcement Learning
with a Generative Model [63.11179754372823]
本稿では,強化学習(RL)におけるモデルロバスト性を検討した。
我々は,デプロイ環境が,名目MDPに規定された不確実性に陥る場合に,最悪の場合のパフォーマンスを最適化する政策を学習することを目的とした,分布的に堅牢なマルコフ決定プロセス(RMDP)の枠組みを採用する。
論文 参考訳(メタデータ) (2023-05-26T02:32:03Z) - Twice Regularized Markov Decision Processes: The Equivalence between
Robustness and Regularization [64.60253456266872]
マルコフ決定プロセス(MDP)は、変化または部分的に知られているシステムのダイナミクスを扱うことを目的としている。
規則化されたMDPは、時間的複雑さを損なうことなく、ポリシー学習の安定性を高める。
ベルマン作用素は、収束と一般化を保証する計画と学習スキームを導出することができる。
論文 参考訳(メタデータ) (2023-03-12T13:03:28Z) - Robust Average-Reward Markov Decision Processes [25.125481838479256]
我々は,不確実なセットに対して最悪の平均報酬を最適化する政策を見出すことを目標とする,堅牢な平均リワードMDPに焦点を当てる。
我々は, ディスカウント型MDPを用いて, 平均回帰MDPを近似するアプローチを採っている。
我々は、ロバスト平均逆 MDP に対するロバストなベルマン方程式を導出し、最適ポリシーがその解から導出できることを証明し、さらに、その解を確実に見つけ出すロバストな相対値アルゴリズムを設計する。
論文 参考訳(メタデータ) (2023-01-02T19:51:55Z) - Policy Gradient in Robust MDPs with Global Convergence Guarantee [13.40471012593073]
Robust Markov決定プロセス(RMDP)は、モデルエラーに直面した信頼性の高いポリシーを計算するための有望なフレームワークを提供する。
本稿では、RMDPの汎用的ポリシー勾配法であるDRPG(Double-Loop Robust Policy Gradient)を提案する。
従来のロバストなポリシー勾配アルゴリズムとは対照的に、DRPGはグローバルな最適ポリシーへの収束を保証するために近似誤差を単調に削減する。
論文 参考訳(メタデータ) (2022-12-20T17:14:14Z) - First-order Policy Optimization for Robust Markov Decision Process [40.2022466644885]
我々はロバストマルコフ決定過程(MDP)の解法を考える。
MDPは、不確実な遷移カーネルを持つ割引状態、有限状態、有限作用空間 MDP の集合を含む。
$(mathbfs,mathbfa)$-矩形不確かさ集合に対して、ロバストな目的に関するいくつかの構造的な観察を確立する。
論文 参考訳(メタデータ) (2022-09-21T18:10:28Z) - Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。
まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。
次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文 参考訳(メタデータ) (2022-08-17T18:49:53Z) - Robust Entropy-regularized Markov Decision Processes [23.719568076996662]
本稿では,ER-MDPモデルのロバストバージョンについて検討する。
我々は, ER-MDPと頑健な非正規化MDPモデルに係わる重要な特性も設定に保たれることを示す。
私たちは、我々のフレームワークと結果を、価値や(修正された)ポリシーを含む異なるアルゴリズムのスキームに統合する方法を示します。
論文 参考訳(メタデータ) (2021-12-31T09:50:46Z) - Twice regularized MDPs and the equivalence between robustness and
regularization [65.58188361659073]
報酬を損なうMDPのポリシーイテレーションは、正規化MDPと同じ時間複雑性を持つことを示す。
正規化MDPを2倍の正規化MDPに一般化する。
論文 参考訳(メタデータ) (2021-10-12T18:33:45Z) - Reinforcement Learning for Finite-Horizon Restless Multi-Armed
Multi-Action Bandits [8.136957953239254]
本稿では、R(MA)2Bと呼ばれる複数の動作を持つ有限ホライゾンレス・マルチアームバンディット問題について検討する。
各アームの状態は、制御されたマルコフ決定プロセス(MDP)に従って進化し、アームを引く報酬は、対応するMDPの現在の状態と、取られたアクションの両方に依存する。
最適政策の発見は典型的には難解であるため,我々はOccupancy-Measured-Reward Index Policyと呼ぶ,計算に訴える指標ポリシーを提案する。
論文 参考訳(メタデータ) (2021-09-20T21:40:12Z) - Safe Exploration by Solving Early Terminated MDP [77.10563395197045]
我々は、Early TerminatedP(ET-MDP)の枠組みの下で、安全なRL問題に対処する新しいアプローチを導入する。
まず、ET-MDPを対応するCMDPと同じ最適値関数を持つ非制約アルゴリズムとして定義する。
そこで,文脈モデルに基づく非政治アルゴリズムを提案し,ET-MDPを解き,それに対応するCMDPをより良い性能で解き,学習効率を向上する。
論文 参考訳(メタデータ) (2021-07-09T04:24:40Z) - Exploration-Exploitation in Constrained MDPs [79.23623305214275]
拘束マルコフ決定過程(CMDP)における探索・探索ジレンマについて検討する。
未知のCMDPで学習している間、エージェントは、MDPに関する新しい情報を見つけるために、トレードオフ探索を行う必要がある。
エージェントは最終的に良い方針や最適な方針を学習するが、学習プロセス中にエージェントが制約に過度に違反することを望まない。
論文 参考訳(メタデータ) (2020-03-04T17:03:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。