利用转移矩阵预测提升折扣MDP求解效率
Efficiently Solving Discounted MDPs with Predictions on Transition Matrices
- 基于极小极大优化设计新算法，利用转移矩阵预测信息
- 样本复杂度随预测误差降低，优于此前最优结果
- 理论与实验结合，适合强化学习高效算法研究者
我们研究在生成模型下的无限时域折扣马尔可夫决策过程（DMDPs）。受Mitzenmacher和Vassilvitskii（2022）提出的带建议算法框架启发，提出新框架以探究对转移矩阵的预测如何提升求解DMDPs的样本效率并改进样本复杂度界。针对具有$N$个状态-动作对和折扣因子$γ$的DMDPs，首先证明一个不可能性结果：在无预测精度先验知识下，任何采样策略都无法获得优于$ ilde{O}((1-γ)^{-3} Nε^{-2})$的样本复杂度界，该界与无预测时的最优极小极大样本复杂度一致。在此基础上，提出一种基于极小极大优化技术的新算法，有效利用转移矩阵预测。该算法的样本复杂度依赖于预测误差，且统一优于$ ilde{O}((1-γ)^{-4} N ε^{-2})$，即此前由凸优化方法获得的最佳结果。理论结论得到数值实验进一步支持。
原文摘要 · Abstract (English)
We study infinite-horizon Discounted Markov Decision Processes (DMDPs) under a generative model. Motivated by the Algorithm with Advice framework Mitzenmacher and Vassilvitskii 2022, we propose a novel framework to investigate how a prediction on the transition matrix can enhance the sample efficiency in solving DMDPs and improve sample complexity bounds. We focus on the DMDPs with $N$ state-action pairs and discounted factor $γ$. Firstly, we provide an impossibility result that, without prior knowledge of the prediction accuracy, no sampling policy can compute an $ε$-optimal policy with a sample complexity bound better than $\tilde{O}((1-γ)^{-3} Nε^{-2})$, which matches the state-of-the-art minimax sample complexity bound with no prediction. In complement, we propose an algorithm based on minimax optimization techniques that leverages the prediction on the transition matrix. Our algorithm achieves a sample complexity bound depending on the prediction error, and the bound is uniformly better than $\tilde{O}((1-γ)^{-4} N ε^{-2})$, the previous best result derived from convex optimization methods. These theoretical findings are further supported by our numerical experiments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。