論文の概要: 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の解法においてはるかに効率的であることが示された。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。