(二) 1. Q-learning的遗憾界分析-高效的Q-learning算法

无模型（Model-free）强化学习算法（如 Q-learning）无需显式地对环境进行建模，而是直接对价值函数或策略进行参数化和更新。与基于模型（Model-based）的方法相比，这类算法通常更简单、更灵活，因此在现代深度强化学习中更为普遍。然而，实证研究表明，无模型算法在学习过程中可能需要更多的样本。

“无模型算法能否实现样本高效（sample efficient）”这一理论问题是强化学习中最根本的问题之一，即使在状态数和动作数有限的基础场景下，该问题也尚未得到解决。

我们证明了在分幕式（episodic）MDP 环境中，带有 UCB（置信上限）探索策略的 Q-learning 可以达到O ~ ( H 3 S A T ) \tilde{O}(\sqrt{H^3SAT})