技术摘要：基于非齐次马尔可夫链随机逼近集中性的在线 Q 学习 regret 与样本复杂度

1. 问题陈述

本工作针对无限时域折扣马尔可夫决策过程（MDP）中经典、无模型在线 Q 学习的理论分析。尽管 Q 学习是强化学习（RL）中的基础算法，并为深度 Q 网络（DQN）等现代方法提供了支撑，但现有的有限时间分析存在显著局限：

• 离线偏差：大多数样本复杂度结果集中于离线设定，即数据由固定的行为策略生成。这些分析控制了估计误差（$\|Q_n - Q^\star\|_\infty$），但无法保证学习过程中的性能（regret）。
• 对乐观主义的依赖：现有的在线 Q 学习 regret 界通常依赖于“面对不确定性时的乐观”（例如奖励项）或基于模型的方法。
• 探索缺口：对于标准探索策略（如 $\epsilon$-greedy 或 Boltzmann/softmax 探索）在未修改的在线 Q 学习更新中使用时，缺乏理论保证。

核心挑战在于，在不添加乐观项的情况下，利用标准探索策略为在线 Q 学习建立regret和样本复杂度保证，同时考虑到策略（从而数据分布）随时间演化，形成非齐次马尔可夫噪声结构这一事实。

2. 方法论

作者开发了一个基于**随机逼近（SA）**的新颖分析框架，用于分析 Q 学习的收敛性与 regret。

2.1 基于非齐次链的随机逼近框架

Q 学习更新被表述为收缩型 SA 迭代：
$$x_{n+1} = x_n + \beta_n (F(x_n, y_n) - x_n + M_{n+1})$$
其中 $x_n$ 代表 Q 值，$y_n = (s_n, a_n)$ 是由当前策略生成的状态 - 动作对，$M_{n+1}$ 是鞅噪声。

关键创新在于处理非齐次马尔可夫链 $\{y_n\}$。与假设时间齐次链或均匀混合时间的先前工作不同，该框架允许：

1. 时变转移动力学：转移核 $p(\zeta_n, x_n)$ 依赖于迭代值 $x_n$ 和外部控制序列 $\zeta_n$（例如温度 $\lambda_n$ 或探索率 $\epsilon_n$）。
2. 渐近消失的收缩：收缩因子 $\alpha(\zeta_n)$ 被允许在 $n \to \infty$ 时收敛于 1。这模拟了次优动作以消失概率被选中的场景，导致诱导马尔可夫链的混合时间发散。
3. Lipschitz 敏感性：转移核对迭代值 $x$ 变化的敏感性被允许增长（例如，当温度 $\lambda_n \to 0$ 时，softmax 策略对 Q 值差异的敏感性日益增强）。

2.2 高概率集中界

作者推导了 SA 迭代值的高概率集中界。证明技术涉及：

• 泊松方程分解：利用与时变转移核相关的泊松方程的解，将马尔可夫噪声转换为鞅差序列加上残差项。
• 噪声平均：开发一种新颖的论证，以在收缩减弱和转移核变化的情况下界定噪声的衰减。
• 结果：该界表明 $\|x_n - x^\star\|$ 的衰减速率取决于步长调度、收缩因子趋近于 1 的速率以及转移核变化的速率。

2.3 分析的探索方案

该框架应用于两种具体的探索策略：

1. Boltzmann Q 学习：动作通过带有衰减温度 $\lambda_n$ 的 softmax 分布 $\sigma(Q_n/\lambda_n)$ 进行选择。
2. 平滑 $\epsilon_n$-Greedy (S$\epsilon$G)：均匀策略与 softmax 策略的凸组合。引入这种平滑是为了确保转移核相对于 Q 值保持平滑，从而促进分析，同时有效地模拟标准的 $\epsilon$-greedy 行为。

3. 主要贡献与结果

3.1 经典在线 Q 学习的首个 regret 界

本文提供了首个针对经典、完全无模型且不含乐观项的 Q 学习的 regret 界。

• Boltzmann Q 学习：regret 关键性地依赖于 MDP 的次优性间隙（$\text{gap}(M)$）。
  • 对于大间隙，regret 是次线性的。
  • 对于小间隙，regret 可能恶化并趋近于线性增长（$O(N)$），这与带臂赌博机中 Boltzmann 探索的已知局限性一致。
• 平滑 $\epsilon_n$-Greedy (S$\epsilon$G)：该方案实现了接近 $\tilde{O}(N^{9/10})$ 的间隙鲁棒 regret 界。虽然这比基于乐观主义的方法实现的 $\tilde{O}(\sqrt{N})$ 要差，但它证明了未修改的在线 Q 学习可以实现次线性 regret。

3.2 样本复杂度保证

作者建立了表现出亚高斯尾部行为的高概率样本复杂度界：

• Boltzmann：在特定参数选择下，样本复杂度为 $\tilde{O}((1-\gamma)^{-4}\epsilon^{-2})$，随着温度衰减参数 $b \to 0$，趋近于最优离线速率。
• S$\epsilon$G：样本复杂度为 $\tilde{O}((1-\gamma)^{-5}\epsilon^{-2})$，与通过 SA 技术导出的离线 Q 学习已知界相匹配，但将其扩展到了在线设定。

3.3 针对 SA 的新颖集中界

主要的技术贡献是针对具有非齐次动力学的收缩型马尔可夫 SA的集中界。

• 该界以高概率成立，并允许收缩因子渐近地趋近于 1。
• 它处理了混合时间发散且转移核随迭代值变化的情况。
• 该结果被提出可能对于涉及受控马尔可夫噪声的 RL 和优化算法具有独立的兴趣。

4. 意义与主张

本文声称通过为标准 Q 学习算法提供严格的有限时间保证，填补了 RL 理论中的一个关键空白。这些算法在实践中被广泛使用（例如带有 $\epsilon$-greedy 或 Boltzmann 探索的 DQN），但此前缺乏在线设定下的理论依据。

• 实际相关性：结果适用于不需要基于模型的组件或复杂乐观奖励的算法，这与许多成功的现代 RL 系统的“无模型”性质相一致。
• 理论局限性：作者承认实现的 regret 速率（$\tilde{O}(N^{9/10})$）与基于乐观主义的方法（$\tilde{O}(\sqrt{N})$）相比是次优的。他们将此归因于无乐观探索的根本局限性，并类比多臂赌博机结果，其中 $\epsilon$-greedy 和 Boltzmann 策略产生的速率比 UCB 更差。
• 未来方向：本文指出了潜在的扩展方向，包括将 regret 速率提高到与赌博机结果相匹配（$\tilde{O}(N^{2/3})$），将分析扩展到函数近似，以及将这些界应用于平均奖励 RL。

总之，这项工作表明，通过利用针对非齐次随机逼近的新分析工具，只要仔细调整探索参数，经典在线 Q 学习即可在不进行算法修改的情况下实现次线性 regret 和高概率收敛。