Provably Efficient Q𝑄Q-learning with Function Approximation via Distribution Shift Error Checking Oracle
Simon S. Du Institute for Advanced Study, Email: Yuping Luo Princeton University, Email: Ruosong Wang Carnegie Mellon University, Email: Hanrui Zhang Duke University, Email:
Abstract
$Q$ -learning with function approximation is one of the most popular methods in reinforcement learning. Though the idea of using function approximation was proposed at least $60$ years ago [28], even in the simplest setup, i.e, approximating $Q$ -functions with linear functions, it is still an open problem how to design a provably efficient algorithm that learns a near-optimal policy. The key challenges are how to efficiently explore the state space and how to decide when to stop exploring in conjunction with the function approximation scheme.
中文速览
用函数逼近来估计Q函数是强化学习中最核心的方法之一，但哪怕只用最简单的线性函数，如何设计一个有理论保证的高效算法，六十年来始终是悬而未决的难题。这篇论文提出了一种名为"差异最大化Q学习"（Difference Maximization Q-learning，DMQ）的算法，核心创新是引入了"分布偏移误差检测"（Distribution Shift Error Checking，DSEC）机制——它能自动判断当前的探索是否还能带来新信息：若某个策略诱导的状态分布上存在模型预测好但另一分布上预测差的函数，就说明还有值得继续探索的区域，否则便可停止。对于线性函数类，这一检测等价于求矩阵的最大特征值问题，且可以证明触发探索的次数至多为多项式次，从而保证整体样本复杂度也是多项式级别。在合理的正则性假设下，DMQ能以多项式条数的轨迹找到近最优策略，适用于一般随机转移的情形，填补了线性函数逼近Q学习缺乏可证明高效算法这一长期空白。
原文 arXiv:1906.06321;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1906.06321v2