Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning
Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning
复制标题
打破样本复杂性障碍，实现后悔最优无模型强化学习
DOI：
10.1093/imaiai/iaac034
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Chi, Yuejie
中科院分区：
文献类型：
--
作者：
Li, Gen;Shi, Laixi;Chen, Yuxin;Chi, Yuejie
在在线情景强化学习 (RL) 中实现样本效率需要最佳地平衡探索和利用。当涉及到具有状态、动作和视野长度的有限视野情景马尔可夫决策过程时，在描述极小极大最优后悔方面已经取得了实质性进展，它与样本总数按（模对数因子）的顺序缩放。虽然已经提出了几种相互竞争的解决方案范式来最大限度地减少遗憾，但除非样本量超过巨大的阈值（例如，对于现有的无模型方法），否则它们要么内存效率低下，要么达不到最优性。为了克服如此大的样本量对高效强化学习的障碍，我们设计了一种新颖的无模型算法，具有空间复杂性，一旦样本量超过了数量级，就可以实现接近最优的遗憾。就样本大小要求（也称为初始老化成本）而言，我们的方法比任何现有渐近遗憾最优的内存高效算法至少提高了一倍。利用最近引入的方差减少策略（也称为参考优势分解），所提出的算法采用了早期确定的参考更新规则，并借助两个具有上下置信界的 Q 学习序列。我们早期确定的方差减少方法的设计原则可能与其他涉及复杂的探索-利用权衡的强化学习设置无关。
Achieving sample efficiency in online episodic reinforcement learning (RL) requires optimally balancing exploration and exploitation. When it comes to a finite-horizon episodic Markov decision process withstates,actions and horizon length, substantial progress has been achieved toward characterizing the minimax-optimal regret, which scales on the order of(modulo log factors) withthe total number of samples. While several competing solution paradigms have been proposed to minimize regret, they are either memory-inefficient, or fall short of optimality unless the sample size exceeds an enormous threshold (e.g.for existing model-free methods).To overcome such a large sample size barrier to efficient RL, we design a novel model-free algorithm, with space complexity, that achieves near-optimal regret as soon as the sample size exceeds the order of. In terms of this sample size requirement (also referred to the initial burn-in cost), our method improves—by at least a factor of—upon any prior memory-efficient algorithm that is asymptotically regret-optimal. Leveraging the recently introduced variance reduction strategy (also calledreference-advantage decomposition), the proposed algorithm employs anearly-settledreference update rule, with the aid of two Q-learning sequences with upper and lower confidence bounds. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings that involve intricate exploration–exploitation trade-offs.