Stochastic approximation with cone-contractive operators: Sharp ?∞-bounds for Q-learning
Stochastic approximation with cone-contractive operators: Sharp ?∞-bounds for Q-learning
复制标题
使用锥收缩算子的随机逼近：Q 学习的尖锐 ?∞ 边界
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
M. Wainwright
中科院分区：
文献类型：
--
作者：
M. Wainwright
受强化学习中$Q$ -学习算法研究的启发，我们研究了一类基于算子的随机逼近过程，这些算子满足底层锥体的单调性和拟收缩性条件。我们证明了每次迭代误差的一般夹心关系，并利用它导出了锥诱导规范范数的误差的非渐近界。这些结果是在确定性框架内得出的，不需要对噪声进行假设。我们将这些一般界应用于具有离散状态-动作空间的贴现马尔可夫决策过程的同步$Q$ -学习，特别是通过在一定步长范围内推导$\ell_\infty$ -范数的非渐近界。这些结果是迄今为止已知的最尖锐的，我们通过模拟表明，在最坏情况下，我们的边界的依赖性不能得到改善。这些结果表明，相对于基于模型的$Q$ -迭代，基于$\ell_\infty$的$Q$ -学习的样本复杂度在折现因子$\gamma$方面是次优的。
Motivated by the study of $Q$-learning algorithms in reinforcement learning, we study a class of stochastic approximation procedures based on operators that satisfy monotonicity and quasi-contractivity conditions with respect to an underlying cone. We prove a general sandwich relation on the iterate error at each time, and use it to derive non-asymptotic bounds on the error in terms of a cone-induced gauge norm. These results are derived within a deterministic framework, requiring no assumptions on the noise. We illustrate these general bounds in application to synchronous $Q$-learning for discounted Markov decision processes with discrete state-action spaces, in particular by deriving non-asymptotic bounds on the $\ell_\infty$-norm for a range of stepsizes. These results are the sharpest known to date, and we show via simulation that the dependence of our bounds cannot be improved in a worst-case sense. These results show that relative to a model-based $Q$-iteration, the $\ell_\infty$-based sample complexity of $Q$-learning is suboptimal in terms of the discount factor $\gamma$.