提出高效算法求解带状态独立模糊集的鲁棒MDP问题
Efficient Algorithms for Robust Markov Decision Processes with $s$-Rectangular Ambiguity Sets
- 针对状态独立模糊集设计统一求解框架，提升计算效率
- 在多种模糊集下求解速度比商用求解器快数个数量级
- 适用于需应对不确定性但追求高效率的强化学习场景
鲁棒马尔可夫决策过程（MDP）因其能缓解因模糊性导致的样本外性能下降而受到广泛关注。与经典MDP通过已知转移核建模随机性不同，鲁棒MDP通过历史数据构建模糊集，并优化最坏情况下的转移核以增强鲁棒性。本文针对具有s-矩形模糊集的广义鲁棒MDP，提出统一求解框架，其中各状态的最坏转移概率可独立处理。实验表明，该方法在1-范数、2-范数及ϕ-散度模糊集下，求解速度比当前最优商业求解器快数个数量级，且通常仅比经典MDP慢对数因子。在合成数据及标准基准实例上均验证了良好的可扩展性。
原文摘要 · Abstract (English)
Robust Markov decision processes (MDPs) have attracted significant interest due to their ability to protect MDPs from poor out-of-sample performance in the presence of ambiguity. In contrast to classical MDPs, which account for stochasticity by modeling the dynamics through a stochastic process with a known transition kernel, a robust MDP additionally accounts for ambiguity by optimizing against the most adverse transition kernel from an ambiguity set constructed via historical data. In this paper, we develop a unified solution framework for a broad class of robust MDPs with $s$-rectangular ambiguity sets, where the most adverse transition probabilities are considered independently for each state. Using our algorithms, we show that $s$-rectangular robust MDPs with $1$- and $2$-norm as well as $ϕ$-divergence ambiguity sets can be solved several orders of magnitude faster than with state-of-the-art commercial solvers, and often only a logarithmic factor slower than classical MDPs. We demonstrate the favorable scaling properties of our algorithms on a range of synthetically generated as well as standard benchmark instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。