Faster saddle-point optimization for solving large-scale Markov decision processes
\Name[Joan Bas-Serrano]Joan Bas-Serrano \addrUniversitat Pompeu Fabra Barcelona Spain \Name[Gergely Neu]Gergely Neu \addrUniversitat Pompeu Fabra Barcelona Spain
Abstract
We consider the problem of computing optimal policies in average-reward Markov decision processes. This classical problem can be formulated as a linear program directly amenable to saddle-point optimization methods, albeit with a number of variables that is linear in the number of states. To address this issue, recent work has considered a linearly relaxed version of the resulting saddle-point problem. Our work aims at achieving a better understanding of this relaxed optimization problem by characterizing the conditions necessary for convergence to the optimal policy, and designing an optimization algorithm enjoying fast convergence rates that are independent of the size of the state space. Notably, our characterization points out some potential issues with previous work.
中文速览
平均奖励马尔可夫决策过程（average-reward MDP）的最优策略求解是序列决策领域的核心难题，传统线性规划方法因变量数量随状态空间线性增长而面临严重的可扩展性瓶颈。本文从LP的双线性鞍点（saddle-point）形式出发，通过引入线性特征映射对原始变量降维，研究这一"松弛鞍点问题"的理论基础：明确指出收敛到最优策略所必需的两个条件——可实现性假设与一个新发现的"相干性（coherence）假设"，并证明后者不可或缺（违反它会导致松弛问题的最优解反而对应次优策略）。在此基础上，作者设计了基于Mirror Prox算法的优化方案，将找到ε-最优策略的运行时复杂度压缩至Õ(τ²_mix · N³/ε)，其中N为松弛问题的特征维数，与原始状态空间大小无关，同时将前人工作中对ε的依赖从1/ε²改善至1/ε，并消除了依赖状态空间大小的不利因子α²。这一工作不仅为大规模MDP优化提供了理论严格且计算高效的路径，还指出了已有相关文献中因忽略相干性假设而存在的潜在错误。
原文 arXiv:1909.10904;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1909.10904v2