DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees¶

会议: NeurIPS 2026
arXiv: 2604.16684
领域: 强化学习
关键词: 非平稳强化学习, 分段平稳 MDP, 变化点检测, 探测集与重启, 极小极大下界

一句话总结¶

本文针对无环境变化先验知识的分段平稳有限时域马尔可夫决策过程，确立了首个表格与线性 MDP 动态遗憾的极小极大下界，并提出了通用模块化包装框架 DARLING，通过周期性均匀探测显式监控奖励与转移分布变点，在表格与线性设定下均首次实现了匹配理论下界的近最优动态遗憾。

研究背景与动机¶

现实世界中应用强化学习（如动态定价、库存调度、交通控制与自适应医疗方案等）的核心痛点之一，在于外部环境的转移概率与奖励函数并非一成不变，而是随着外界条件发生动态演化。传统假设环境平稳的理论保证在此类场景下彻底失效，智能体若固守历史经验将面临灾难性的性能退化。现有非平稳强化学习主要分为渐变漂移与突变（分段平稳，Piecewise Stationary, PS）两类机制。在分段平稳设定中，虽然环境在离散时间点发生突变而在区间内保持平稳，但大多数主流算法（包括滑窗法、折扣更新与预算定期重启）都严重依赖于对环境非平稳程度的先验知识（如变化次数 $N_T$ 或变异总预算），若超参数配置脱靶，算法将陷入过早遗忘导致高方差或迟钝适应导致大偏差的困境。

无需先验知识的“检测-重启”（Detection-Restart）范式是破解上述难题的理想路径，然而该方向长期面临着理论与实用性的严重脱节。作为此前宣称无需先验的代表性基线，MASTER 框架通过检验平稳算法的累积遗憾是否违背理论界来触发告警与重启；但深入剖析其理论推导后发现，其核心引理对多实例调度的伯努利随机变量条件概率存在严重逻辑漏洞，使得其遗憾上界在数学上失效。在实际数值实验中，MASTER 极度保守的统计检验要求高达 $10^{19}$ 量级的轮次才可能触发一次检测，导致其在常规样本预算下几乎退化为纯平稳算法。更关键的是，领域内此前甚至缺乏分段平稳有限时域 MDP 的极小极大（Minimax）动态遗憾下界，致使现有方法到底能达到何种理论极限长期缺乏衡量坐标。

本文的切入角度是打破以“遗憾违规”作为间接告警信号的旧范式，转向直接对环境模型（奖励与状态转移）分布偏移进行轻量级显式监控，同时将探测数据流与主策略学习彻底解耦。核心 idea：构建模块化检测包装器 DARLING，通过定期插入解耦的强制均匀探测轮次显式监控奖励与转移核的均值漂移，不仅建立了分段平稳 MDP 的第一个极小极大下界，还在表格与线性 MDP 中均首次达成了近乎匹配下界的无先验最优动态遗憾。

方法详解¶

整体框架¶

DARLING 是一个即插即用的模块化外层包装器（Wrapper）。它以任意在平稳环境下具有阶最优静态遗憾的基学习器 $\mathcal{L}$ 为核心，在不破坏 $\mathcal{L}$ 内部机制的前提下，为其赋予应对突变非平稳性的敏捷自适应能力。整个框架的核心运转逻辑可以概括为两套交替运行的模式与一个终极重置闭环：

在绝大多数轮次中，算法处于平稳学习模式，由基学习器 $\mathcal{L}$ 自主控制动作选择并根据环境反馈更新策略或 $Q$ 值网络；而每隔固定的自适应周期 $\lceil 1/\alpha_k \rceil$，框架强制切入探测模式，完全挂起基学习器 $\mathcal{L}$，改用均匀随机策略在关键探针集合（Probe Set）上采样。探测轮次收集的所有奖励与转移样本绝对不回传给基学习器 $\mathcal{L}$（从而完全保护平稳算法的数据分布假设不受污染），仅被喂入专门构建的检测历史统计流。一旦序贯变化点检测器在任何一个流中捕捉到显著的分布均值漂移，框架立即拉响警报并触发重置，将基学习器 $\mathcal{L}$ 与全部检测历史清空，进入下一个平稳区间的极速重新学习。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["环境交互开始 Episode t"] --> B["判断轮次类型<br/>(t - τ - 1) mod ⌈1/α_k⌉"]
    B -->|非探测轮次| C["基学习器平稳学习<br/>执行策略并更新 L"]
    B -->|探测轮次| D["强制探测与样本解耦<br/>均匀采样且不更新基算法 L"]
    D --> E["模型漂移双重检测<br/>奖励检验 Test 1 + 转移检验 Test 2"]
    E -->|未触发阈值| F["继续当前区间学习"]
    E -->|触发变点告警| G["全局重启与历史清空<br/>重置 L 并清空历史 H"]
    G --> H["自适应探测频率更新<br/>递增阶段计数器 k 并重置基准点 τ"]

关键设计¶

1. 极小极大动态遗憾下界构建：确立分段平稳强化学术界理论极限

针对此前分段平稳有限时域 MDP 缺乏理论下界的问题，本文分别针对表格 MDP 与线性 MDP 建立了严格的信息论极小极大动态遗憾下界。在表格设定中，论文构造了一组规模为 $2^{N_T+1}$ 的对抗 MDP 族。每个 MDP 包含一个根状态、一棵深度为 $D-1$ 的 $A$ 叉树以及好/坏两个吸收状态；在第 $k$ 个平稳区间上，依据二进制索引位动态调整叶节点转移概率，使得一个 MDP 中的最优动作-状态三元组在配对的另一个 MDP 中被访问期望最低。利用测度变换与 Bretagnole-Huber 不等式计算策略诱导概率分布间的 KL 散度，推导出任何算法的动态遗憾必然满足下界： $$ \mathcal{R}(\pi, T) = \Omega\left(\sqrt{S A H^3 N_T T}\right) $$ 在线性 MDP 设定下，论文将困难实例推广为包含 $H+2$ 个状态与动作空间为 $\{\pm 1\}^{d-2}$ 的线性结构，利用超立方体参数构造转移偏差，借助 Pinsker 不等式与多区间累积 KL 散度积分，严格证明了线性 MDP 的动态遗憾下界为 $\Omega(d\sqrt{H^3 N_T T})$。这两大下界为检验非平稳算法的理论终局提供了唯一定量基准。

2. 探测集构建与解耦采样机制：消除学习偏差与覆盖死角

如果完全依赖基学习器在探索过程中的自然轨迹来检测环境突变，会导致严重的覆盖缺陷：表现优异的学习器会迅速收敛于当前环境的最优路径，而极少探索次优分支；一旦环境在那些次优分支上发生剧烈突变并反转成为全局最优，依赖被动数据的检测器将完全失明。为了彻底解决这一矛盾，DARLING 显式定义了探测集合 $\mathcal{P}$：在表格设定下，探针集合覆盖全体可能的三元组 $\mathcal{S} \times \mathcal{A} \times [H]$；在状态空间可能无限的线性 MDP 中，探针集合收敛为在特征空间 $\mathbb{R}^d$ 中具有极大线性无关性的特征动作组 $\mathcal{P}_h$。

在探测调度上，DARLING 在第 $k$ 个重启区间内以周期 $\lceil 1/\alpha_k \rceil$ 强制介入执行均匀随机动作。探测收集到的样本完全与基学习器 $\mathcal{L}$ 的经验缓存隔离，不参与任何策略评估或梯度回传。此设计不仅在理论上确保了基学习器的样本独立性，还在无需假设行为策略具备全空间覆盖度的前提下，为检测统计量提供了严格的高概率样本到达率下界。

3. 双重模型变点检验：将非平稳探测规约至独立标量均值漂移

与 MASTER 基于抽象遗憾违规测试的隐式检测不同，DARLING 采用直观、高灵敏度且计算轻量的“模型级均值检测”（Detect-the-Model）。检测系统由两套并行的流式检验器组成： - 奖励检测流（Test 1）：针对每个监控的三元组 $(s,a,h) \in \mathcal{P}$，维护观测奖励历史 $\mathcal{H}_{(s,a,h)}^{(r)}$。由于奖励有界在 $[0, 1]$，该流为独立的有界随机变量序列，环境发生突变直接体现为经验均值的跳变。 - 状态转移检测流（Test 2）：在表格设定下，论文巧妙地将后继状态编码为 One-Hot 伯努利向量。对于每个目标状态 $\tilde{s} \in \mathcal{S}$，转移到 $\tilde{s}$ 记为 1，转移到其余状态记为 0，从而将多项式转移核的检验彻底拆解为 $|\mathcal{S}|$ 个独立的伯努利序列 $\mathcal{H}_{(s,a,h,\tilde{s})}^{(P)}$。在线性 MDP 中，由于状态无限，算法转向监控后继状态特征向量在各个基方向上的投影期望 $[\phi(s_{h+1}, a')]_j$，将其转化为 $d \times A$ 个标量连续流。

检测器 $\mathcal{D}$ 采用通用序贯广义似然比检验（GLR）。在历史长度为 $n$、候选分割点为 $t \in [n-1]$ 时，其对数似然比统计量闭式为： $$ \mathrm{GLR}t = t\,\mathrm{kl}(\hat{\mu}}, \hat{\mu{1:n}) + (n-t)\,\mathrm{kl}(\hat{\mu}) $$ 配合随样本量动态收缩的高概率安全阈值 }, \hat{\mu}_{1:n$\beta_{\mathrm{GLR}}(n, \delta_{\mathrm{F}})$，既将误报概率严格压制在 $\mathcal{O}(T^{-\gamma})$，又将检测延迟控制在 $\tilde{\mathcal{O}}(1)$ 样本阶。

4. 自适应重启与频率退火：动态遗憾阶最优性的闭环达成

重启机制连接了检测统计与学习性能。当 Test 1 或 Test 2 的统计量逾越阈值时，算法确认非平稳突变发生，立即重置基学习器并抹除历史记录。为了在无先验（不知道未来还会突变多少次）的前提下达成全局最优的遗憾权衡，探测频率 $\alpha_k$ 必须随重启计数器 $k$ 进行精细退火。在第 $k$ 个重启周期内，表格与线性设定的探测频率分别设定为： $$ \alpha_k^{\text{tabular}} = \frac{\sqrt{k S A H}}{2\sqrt{T}\log^2 T}, \qquad \alpha_k^{\text{linear}} = \frac{\sqrt{k d}}{2\sqrt{T}\log^2 T} $$ 由于探测轮次导致的遗憾代价为 $\sum_k \alpha_k (\nu_k - \nu_{k-1}) H \approx \tilde{\mathcal{O}}(\sqrt{S A H^3 N_T T})$，而检测延迟导致的失控步数在平稳区间隔离假设下被严格限制在高概率极小范围内，整体累积遗憾完全被基学习器在各个平稳子区间的上界之和支配。通过琴生不等式合并各区间的上凸遗憾函数，DARLING 成功在表格 MDP 达到 $\tilde{\mathcal{O}}(\sqrt{S A H^3 N_T T})$、在线性 MDP 达到 $\tilde{\mathcal{O}}(d\sqrt{H^3 N_T T})$，双双在主阶上精确匹配本文提出的极小极大下界。

损失函数 / 训练策略¶

DARLING 框架本身作为非侵入式的算法包装器，不引入额外的参数化神经网络损失函数，其学习行为完全由内部的基算法（表格下为 UCB-MQ，线性下为 LSVI-UCB++）驱动。框架的核心计算开销全部来自于 GLR 统计量的流式增量计算。在工程实现中，通过维护前缀和与滑动计数，单步经验均值计算复杂度降为常数级；检测器仅在探测轮次且历史命中更新时触发求值，使得单轮平摊运行时开销在毫秒级以内（表格场景仅 0.83 ms/episode，线性场景仅 1.67 ms/episode）。

实验关键数据¶

主实验¶

实验涵盖 5 个表格 MDP 环境（Bidirectional Diabolical Combination Lock、DeepSea、FourRoom、NRoom、Forked RiverSwim）与 5 个线性 MDP 环境（Synthetic Chain Lock、Simplex、Linear GARNET、Anchor、Block Low-Rank）。测试总轮次均为 $T = 50,000$ episodes。在突变分段平稳（PS）设定下，采用几何变点模型，平均包含多达 659 次环境变化（参数 $\xi \in \{0.4, 0.6, 0.8\}$）；同时评测了连续渐变漂移场景。

各算法理论性能保证与特性对比如下表所示：

设定	算法	动态遗憾上界	匹配下界	先验依赖 (Prior-Free)
表格 MDP	RestartQ-UCB	$\tilde{\mathcal{O}}(S^{3/4}A^{3/4}H^{5/3}N_T^{1/3}T^{2/3})$	✗	依赖变化先验 $N_T$
	Double-Restart Q-UCB	$\tilde{\mathcal{O}}(S^{1/3}A^{1/3}H^{5/3}N_T^{1/3}T^{2/3} + H^{6/4}T^{3/4})$	✗	无需先验 (Prior-Free)
	MASTER	理论证明失效 (原宣称 $\tilde{\mathcal{O}}(\sqrt{SAH^5 N_T T})$)	✗	无需先验 (但实际无法触发)
	DARLING + UCB-MQ (本文)	$\tilde{\mathcal{O}}(\sqrt{S A H^3 N_T T})$	严格匹配	无需先验 (Prior-Free)
	理论极小极大下界	$\Omega(\sqrt{S A H^3 N_T T})$	—	—
线性 MDP	OPT-WLSVI	$\tilde{\mathcal{O}}(d^{5/4}H^2 N_T^{1/4}T^{3/4})$	✗	依赖变化先验 $N_T$
	LSVI-UCB-Restart	$\tilde{\mathcal{O}}(d^{4/3}H^2 N_T^{1/3}T^{2/3})$	✗	依赖变化先验 $N_T$
	ADA-LSVI-UCB-Restart	$\tilde{\mathcal{O}}(d^{5/4}H^2 N_T^{1/4}T^{3/4})$	✗	无需先验 (Prior-Free)
	MASTER	理论证明失效 (原宣称 $\tilde{\mathcal{O}}(d^{3/2}\sqrt{H^4 N_T T})$)	✗	无需先验 (但实际无法触发)
	DARLING + LSVI-UCB++ (本文)	$\tilde{\mathcal{O}}(d\sqrt{H^3 N_T T})$	严格匹配	无需先验 (Prior-Free)
	理论极小极大下界	$\Omega(d\sqrt{H^3 N_T T})$	—	—

消融实验¶

论文针对各算法的平均单轮耗时（计算效率分析）以及在不同非平稳模式下的实际表现进行了系统对比测试：

环境类别	算法配置	每轮平均耗时 (ms/ep.)	相对 MASTER 速度提升	突变检测与适应表现
表格 MDP	DARLING (完整)	0.825	1.99× 更快	能够即时响应频繁变点，累积回报全场景第一
	Double-RestartQ	0.224	7.34× 更快	盲目定期重启，非平稳区间后期性能退化明显
	MASTER	1.644	1.00× (基准)	理论阈值过宽导致检测从未触发，表现垫底
	RestartQ-UCB	0.403	4.08× 更快	依赖已知 $N_T$ 超参数，调优敏感且泛化差
线性 MDP	DARLING (完整)	1.672	2.07× 更快	特征空间贪婪基选择鲁棒，极高累积回报
	MASTER	3.464	1.00× (基准)	计算开销大且无法捕捉多维隐式特征偏移
	LSVI-UCB-Restart	1.064	3.26× 更快	依赖区间长度先验，面对随机变点频繁失准
	ADA-LSVI-UCB	1.271	2.73× 更快	遗憾界次优，深层探索环境累计回报差距大
	OPT-WLSVI	1.136	3.05× 更快	滑窗衰减权重引起高估计方差

关键发现¶

直接检测模型彻底击溃隐式遗憾检测：在所有 10 项复杂基准中，MASTER 因其判别条件严重受制于极端保守的理论置信界，在 $T=50,000$ 轮次内近乎无法触发任何重启，累积回报显著落后；DARLING 通过流式均值检验，能够在变点发生后的极短延迟内迅速重启，性能大幅领先。
面对渐变漂移展现惊人跨域鲁棒性：虽然 DARLING 的理论保证建立在分段平稳假设之上，但在平滑连续漂移的实验场景下，DARLING 的累积回报不仅未发生崩溃，甚至全面战胜了专为漂移设计的强基线（如 RestartQ-UCB 与 OPT-WLSVI），印证了快速响应局部大偏差的重启策略对累积微弱漂移具有极佳的实际鲁棒性。
探针集几何构造对实际性能影响极小：在线性 MDP 实验中，消融测试表明无论是严格按照理论标定搜寻探针，还是仅以贪婪方式挑选使特征向量满秩的活跃状态-动作对，最终策略回报与检测响应灵敏度几乎无统计差异，极大减轻了实际落地部署的标定门槛。

亮点与洞察¶

首创分段平稳强化学习极小极大下界：论文首次推导出有限时域非平稳 MDP 在表格和线性场景下的信息论下界，不仅填补了理论空白，更为整个非平稳强化学习领域树立了金标基准。
数据解耦的探测-学习隔离范式：巧妙地将环境探测样本限定于独立历史流中，严禁其掺杂入基学习器的更新过程，既彻底保证了基学习器的平稳假设成立，又消除了自适应策略带来的采样选择性偏误。
多项式转移核向伯努利流的升维降解技巧：将高维或多状态转移概率通过 One-Hot 指示变量与特征投影拆解为并行的独立标量序列，使经典的流式检验算法（如 GLR/GSR）能够直接无缝赋能复杂强化学习系统。

局限与展望¶

理论证明依赖变点分离与可达性假设：为了在数学上证明高概率检测，理论推导要求任意两个变点之间的平稳区间长度必须大于检测器延迟与采样累积所需的最小轮次（Assumption 5.4 和 6.2），且状态需具备均匀可达性下界 $p_{\mathrm{m}}$；如果环境发生高频连续微小抖动，理论最优性将不再严格成立。
动作空间受限于离散有限集：由于状态转移检测需要遍历或枚举动作以维持特征投影历史，当前算法结构尚无法直接无损拓展至连续或无限维动作空间。
向无限时域与深度强化学习拓展：未来的重要改进方向在于将该显式模型监控机制推进至无限时域平均奖励 MDP，并探索与隐空间对比学习（Representational Learning）相结合，在纯图像输入的深度非平稳端到端控制中实现通用变点自适应。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次确立分段平稳 MDP 理论极小极大下界，并首创基于解耦探测的流式模型变点检测包装框架。
实验充分度: ⭐⭐⭐⭐⭐ 覆盖 10 个代表性表格与线性 MDP 测试集，囊括高达数百次突变及连续漂移环境，对比全面且包含深入的理论除错剖析。
写作质量: ⭐⭐⭐⭐⭐ 论证极其扎实严谨，从理论漏洞指正、下界推导到算法模块设计层层递进，数学逻辑无懈可击。
价值: ⭐⭐⭐⭐⭐ 为非平稳在线决策与强化学习提供了一套兼具最优理论保证与工程实用价值的坚实范式。

设定	算法	动态遗憾上界	匹配下界	先验依赖 (Prior-Free)
表格 MDP	RestartQ-UCB	\(\tilde{\mathcal{O}}(S^{3/4}A^{3/4}H^{5/3}N_T^{1/3}T^{2/3})\)	✗	依赖变化先验 \(N_T\)
	Double-Restart Q-UCB	\(\tilde{\mathcal{O}}(S^{1/3}A^{1/3}H^{5/3}N_T^{1/3}T^{2/3} + H^{6/4}T^{3/4})\)	✗	无需先验 (Prior-Free)
	MASTER	理论证明失效 (原宣称 \(\tilde{\mathcal{O}}(\sqrt{SAH^5 N_T T})\))	✗	无需先验 (但实际无法触发)
	DARLING + UCB-MQ (本文)	\(\tilde{\mathcal{O}}(\sqrt{S A H^3 N_T T})\)	严格匹配	无需先验 (Prior-Free)
	理论极小极大下界	\(\Omega(\sqrt{S A H^3 N_T T})\)	—	—
线性 MDP	OPT-WLSVI	\(\tilde{\mathcal{O}}(d^{5/4}H^2 N_T^{1/4}T^{3/4})\)	✗	依赖变化先验 \(N_T\)
	LSVI-UCB-Restart	\(\tilde{\mathcal{O}}(d^{4/3}H^2 N_T^{1/3}T^{2/3})\)	✗	依赖变化先验 \(N_T\)
	ADA-LSVI-UCB-Restart	\(\tilde{\mathcal{O}}(d^{5/4}H^2 N_T^{1/4}T^{3/4})\)	✗	无需先验 (Prior-Free)
	MASTER	理论证明失效 (原宣称 \(\tilde{\mathcal{O}}(d^{3/2}\sqrt{H^4 N_T T})\))	✗	无需先验 (但实际无法触发)
	DARLING + LSVI-UCB++ (本文)	\(\tilde{\mathcal{O}}(d\sqrt{H^3 N_T T})\)	严格匹配	无需先验 (Prior-Free)
	理论极小极大下界	\(\Omega(d\sqrt{H^3 N_T T})\)	—	—