論文の概要: Solving Long-run Average Reward Robust MDPs via Stochastic Games
- arxiv url: http://arxiv.org/abs/2312.13912v2
- Date: Tue, 30 Apr 2024 17:05:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-01 19:28:13.213440
- 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ý, Đorđe Žikelić,
- Abstract要約: ロバストマルコフ決定過程(RMDP)は、各遷移に単一の確率値ではなく不確実性集合を割り当てる。
我々は、有限状態およびアクション空間を持つ長期平均報酬ターンベースのゲームに還元可能であることを示す。
本稿では、長期平均ポリトピックRMDPを解くための新しいポリシー反復アルゴリズムであるRobust Polytopic Policy Iteration(RPPI)を提案する。
- 参考スコア（独自算出の注目度）: 6.183091173390457
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Markov decision processes (MDPs) provide a standard framework for sequential decision making under uncertainty. However, MDPs do not take uncertainty in transition probabilities 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. 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. 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 \cap 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（参考訳）: マルコフ決定プロセス(MDP)は、不確実性の下でのシーケンシャルな意思決定のための標準フレームワークを提供する。
しかし、MDPは遷移確率の不確実性を考慮していない。
ロバスト・マルコフ決定プロセス(RMDP)は、各遷移に単一の確率値ではなく不確実性セットを割り当てることで、MDPのこの欠点に対処する。
本研究では,全ての不確実集合がポリトープであるポリトープ RMDP について考察し,長期平均報酬 RMDP の解法について考察する。
この問題に対する新たな視点を提示し、有限状態およびアクション空間を持つ長期平均報酬型確率ゲームに還元可能であることを示す。
この減少により,ポリトピックRMDPを保有することが分かっていなかったいくつかの重要な結果が導出される。
まず,長期平均報酬 RMDP を解くための新しい計算複雑性境界を導出し,そのしきい値決定問題は$NP \cap coNP$ であり,サブ指数予測実行時のランダム化アルゴリズムを許容することを示す。
第2に,ロバスト・ポリトピック・ポリシー・イテレーション(RPPI)を提案する。
実験により、RPPIは、値反復に基づく最先端手法と比較して、長期平均ポリトピー的RMDPの解法においてはるかに効率的であることが示された。
関連論文リスト
- RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation [73.2390735383842]
付加的な構造仮定を伴わずにLMDPのサンプル効率アルゴリズムを初めて導入する。
楽観的な探索アルゴリズムのほぼ最適保証を導出するためにどのように使用できるかを示す。
これらの結果は、LMDP以外の幅広い対話型学習問題、特に部分的に観察された環境において有用である。
論文 参考訳（メタデータ） (2024-06-03T14:51:27Z) - 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) - The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model [61.87673435273466]
本稿では,強化学習(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) - 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) - Stochastic first-order methods for average-reward Markov decision processes [10.023632561462712]
平均回帰マルコフ決定過程(AMDP)について検討し,政策最適化と政策評価の両面において理論的確証が強い新しい一階法を開発した。
政策評価と政策最適化の部分を組み合わせることで、生成的およびマルコフ的ノイズモデルの両方の下で、AMDPを解くためのサンプル複雑性結果を確立する。
論文 参考訳（メタデータ） (2022-05-11T23:02:46Z) - Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。
我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-01-21T16:43:03Z) - 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) - Model-Free Algorithm and Regret Analysis for MDPs with Long-Term
Constraints [38.2783003051101]
本稿では,制約付き最適化とQ-ラーニングの概念を用いて,長期制約付きCMDPのアルゴリズムを提案する。
本研究は, 長期的制約を伴うMDPの遺残分析における最初の結果であり, 遷移確率はアプリオリではないことに留意する。
論文 参考訳（メタデータ） (2020-06-10T17:19:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。