强化学习（RL）的经典理论侧重于值函数的表格和线性表示。进一步的进展取决于将RL与现代函数逼近器（如核函数和深度神经网络）相结合，事实上，已经有许多经验成功在大规模应用中利用了这种结合。然而，在开发支持这一企业的理论方面存在着深刻的挑战，最值得注意的是需要结合现代基于函数近似的学习系统中出现的计算和统计权衡来考虑RL核心的探索开发权衡。我们通过研究最小平方值迭代算法的乐观修改，在由核函数或超参数神经网络表示的动作值函数的背景下，来解决这些挑战。我们为该算法建立了多项式运行时复杂度和多项式样本复杂度，而无需对数据生成模型进行额外假设。特别地，我们证明了该算法产生了Oe（FH2 p T）遗憾，其中F表征了函数类F的内在复杂性，H是每集的长度，T是总集数。我们的遗憾边界与状态数无关，这一结果清楚地显示了RL中函数近似的好处。
强化学习（RL）算法与现代函数逼近器（如核函数和深度神经网络）相结合，在各种应用问题中取得了经验成功[例如，27、60、61、72、70]。然而，理论已经落后，当使用这些强大的函数逼近器时，几乎没有关于RL算法设计的理论指导，这些算法在计算上或统计上是有效的，或者关于它们是否收敛。特别是，函数近似将统计估计问题与动态优化问题混合在一起，导致需要平衡统计估计中出现的偏差-方差权衡与RL中固有的勘探开发权衡。因此，完整的理论处理大多局限于表格设置，其中状态和动作空间都是离散的，并且值函数可以表示为表格[参见，例如，33、52、6、35、50、56]，并且理论与最引人注目的应用之间存在脱节。
