提出一种高效敏捷的随机Q学习算法，理论可证且实测表现优越。
Provably Efficient and Agile Randomized Q-Learning
- 用采样探索结合每步更新策略，提升学习响应速度。
- 理论证明在$T$轮中误差上界为$ ilde{O}( oot{5}{H^5SAT})$。
- 适合追求理论保障与快速收敛的强化学习研究者。
尽管基于贝叶斯的探索在模型基础强化学习中常表现出优于奖励激励方法的实证性能，但其在无模型设定下的理论理解仍有限。现有可证明的算法要么计算不可行，要么依赖分阶段策略更新，降低响应性并减缓学习进程。本文提出一种新型Q-learning算法RandomizedQ，将采样式探索与敏捷的逐步策略更新相结合，适用于片状马尔可夫决策过程的强化学习。我们建立了$ ilde{O}( oot{5}{H^5SAT})$的遗憾上界，其中$S$为状态数，$A$为动作数，$H$为每回合长度，$T$为总回合数。此外，在最优Q函数存在轻微正次优性的条件下，还给出了对数级遗憾上界。实验表明，RandomizedQ在标准基准测试中显著优于现有基于奖励或贝叶斯探索的Q-learning变体。
原文摘要 · Abstract (English)
While Bayesian-based exploration often demonstrates superior empirical performance compared to bonus-based methods in model-based reinforcement learning (RL), its theoretical understanding remains limited for model-free settings. Existing provable algorithms either suffer from computational intractability or rely on stage-wise policy updates which reduce responsiveness and slow down the learning process. In this paper, we propose a novel variant of Q-learning algorithm, refereed to as RandomizedQ, which integrates sampling-based exploration with agile, step-wise, policy updates, for episodic tabular RL. We establish an $\widetilde{O}(\sqrt{H^5SAT})$ regret bound, where $S$ is the number of states, $A$ is the number of actions, $H$ is the episode length, and $T$ is the total number of episodes. In addition, we present a logarithmic regret bound under a mild positive sub-optimality condition on the optimal Q-function. Empirically, RandomizedQ exhibits outstanding performance compared to existing Q-learning variants with both bonus-based and Bayesian-based exploration on standard benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。