提出非矩形鲁棒MDP的新对偶解法，突破复杂度瓶颈。
Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes
- 基于Lp有界不确定集构造可分解的对偶形式
- 首次实现非矩形鲁棒策略评估的高效算法
- 适合研究鲁棒强化学习与不确定性建模的学者
研究具有非矩形不确定集的鲁棒马尔可夫决策过程（RMDPs），此类模型能捕捉状态间的依赖关系，优于传统矩形模型。尽管非矩形鲁棒策略评估通常为NP难问题，甚至难以近似，但本文识别出一类结构简单的Lp有界不确定集，可避免复杂性障碍。该类集合可分解为无限多个sa-矩形的Lp有界子集，并利用其结构特性推导出Lp RMDPs的新型对偶公式。该公式揭示了对抗者的策略机制，推动了首个针对非矩形RMDPs的鲁棒策略评估算法的发展。实验表明，该方法显著优于暴力搜索，为未来非矩形鲁棒MDP研究奠定坚实基础。
原文摘要 · Abstract (English)
We study robust Markov decision processes (RMDPs) with non-rectangular uncertainty sets, which capture interdependencies across states unlike traditional rectangular models. While non-rectangular robust policy evaluation is generally NP-hard, even in approximation, we identify a powerful class of $L_p$-bounded uncertainty sets that avoid these complexity barriers due to their structural simplicity. We further show that this class can be decomposed into infinitely many \texttt{sa}-rectangular $L_p$-bounded sets and leverage its structural properties to derive a novel dual formulation for $L_p$ RMDPs. This formulation provides key insights into the adversary's strategy and enables the development of the first robust policy evaluation algorithms for non-rectangular RMDPs. Empirical results demonstrate that our approach significantly outperforms brute-force methods, establishing a promising foundation for future investigation into non-rectangular robust MDPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。