論文の概要: Quantitative Analysis of $ω$-Regular Robust MDPs

• arxiv url: http://arxiv.org/abs/2608.25968v1
• Date: Wed, 26 Aug 2026 16:26:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-27 14:15:15.908143
• Title: Quantitative Analysis of $ω$-Regular Robust MDPs
• Title（参考訳）: $ω$-regular Robust MDPの定量的解析
• Abstract要約: 直交的に定義された不確実性集合を持つ$(s,a)$-矩形RMDPについて検討し、パリティ目的について検討する。 定量的な値は、すべてのエージェントポリシーの上限であり、敵環境に対して保証される満足度確率である。 エージェントと環境の両方が、純粋なメモリレス最適ポリシーを受け入れていることを示す。
• 参考スコア（独自算出の注目度）: 8.858048243097203
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Robust Markov Decision Processes (RMDPs) generalize classical MDPs by allowing uncertainty in transition probabilities and optimizing against their worst-case realization. We consider $(s,a)$-rectangular RMDPs with \emph{linearly defined} uncertainty sets and study parity objectives, which are a canonical representation of $ω$-regular objectives. An uncertainty set is linearly defined if it is described by linear inequalities over the transition distribution together with auxiliary variables, which capture the standard $L_1$ and $L_\infty$ balls as well as general polytopic uncertainty sets. The quantitative value is the supremum, over all agent policies, of the satisfaction probability guaranteed against the adversarial environment. Previous work studied the qualitative analysis, namely the almost-sure (resp. positive) problem that asks whether a single agent policy guarantees satisfaction with probability one (resp. positive probability) against every environment policy. In this work, we solve the exact quantitative problem. Our contributions are threefold. First, we show that both the agent and the environment admit pure memoryless optimal policies. Second, we give a polynomial-time algorithm for quantitative parity on linearly defined robust Markov chains and use it as a subroutine in a policy-iteration algorithm for RMDPs. The algorithm combines quantitative one-step improvements with qualitative almost-sure improvements. Finally, we report experiments comparing our approach with the explicit reduction to stochastic games.
• Abstract（参考訳）: ロバストマルコフ決定過程(RMDP)は、遷移確率の不確実性を許容し、最悪のケースの実現に対して最適化することにより、古典的なMDPを一般化する。 我々は、$(s,a)$-正方形 RMDP と \emph{linearly defined} の不確かさ集合とパリティ目的について検討し、これは$ω$-正則目的の正準表現である。 不確かさ集合は、遷移分布上の線型不等式によって補助変数とともに記述され、標準の$L_1$と$L_\infty$の球と一般的なポリトープの不確かさ集合をキャプチャするときに線型的に定義される。 定量的な値は、すべてのエージェントポリシーの上限であり、敵環境に対して保証される満足度確率である。 以前の研究は質的な分析、すなわち、一つのエージェントポリシーが全ての環境ポリシーに対して確率1(resp. 正の確率)で満足を保証しているかどうかを問うほぼ正の問題を研究した。 この研究では、正確な量的問題を解く。 私たちの貢献は3倍です。 まず、エージェントと環境の両方が純粋なメモリレス最適ポリシーを受け入れていることを示す。 第二に、線形に定義されたロバストなマルコフ連鎖上での定量的パリティの多項式時間アルゴリズムを与え、RMDPのポリシーイテレーションアルゴリズムのサブルーチンとして利用する。 このアルゴリズムは定量的なワンステップ改善と質的な準音質改善を組み合わせたものである。 最後に,我々のアプローチと,確率ゲームへの明示的な還元との比較実験を報告する。

関連論文リスト

• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• Bayesian Risk-Sensitive Policy Optimization For MDPs With General Loss Functions [8.16996766356341]
  我々は、一般的な損失関数と未知のパラメータを持つマルコフ決定過程(MDP)を考察する。 我々はベイズ的手法を用いてデータからパラメータを推定し、損失にコヒーレントなリスク関数を課す。 本稿では,コヒーレントリスク尺度の二重表現を利用した政策勾配最適化手法を提案する。
  論文  参考訳（メタデータ） (2025-09-19T01:16:59Z)
• Best-Effort Policies for Robust Markov Decision Processes [69.60742680559788]
  我々は、ロバスト MDP (RMDPs) として知られる遷移確率の組によるマルコフ決定過程(MDPs)の共通一般化について研究する。 このような政策を最適な堅牢なベストプラクティス(ORBE)政策と呼ぶ。 我々はORBEポリシーが常に存在することを証明し、その構造を特徴付け、標準的なロバストな値反復よりも小さなオーバヘッドで計算するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-08-11T09:18:34Z)
• A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding [61.86327960322782]
  本稿では,各項目の品質の間隔推定に基づくランダム化意思決定の枠組みを提案する。 最適化に基づく最適化手法であるMERITを導入する。 MERITが既存のアプローチで保証されていない望ましい公理特性を満たすことを証明している。
  論文  参考訳（メタデータ） (2025-06-23T19:59:30Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• First-order Policy Optimization for Robust Markov Decision Process [40.2022466644885]
  我々はロバストマルコフ決定過程(MDP)の解法を考える。 MDPは、不確実な遷移カーネルを持つ割引状態、有限状態、有限作用空間 MDP の集合を含む。 $(mathbfs,mathbfa)$-矩形不確かさ集合に対して、ロバストな目的に関するいくつかの構造的な観察を確立する。
  論文  参考訳（メタデータ） (2022-09-21T18:10:28Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。 最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。 本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
  論文  参考訳（メタデータ） (2022-05-28T04:05:20Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)

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

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