Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning¶

会议: NeurIPS 2026
arXiv: 2607.17201
领域: 强化学习
关键词: 最佳策略识别, 在线强化学习, 非渐近分析, 纯探索, 目标函数锐度, 遍历性与连通性

一句话总结¶

针对受导航约束的在线单轨迹折扣马尔可夫决策过程，首次建立了 Navigate-and-Stop (NaS) 类算法的非渐近有限置信度样本复杂度理论上界，精确刻画了除特征时间外的环境连通性、遍历性以及最优分配目标函数几何锐度对探索代价的显式贡献。

研究背景与动机¶

在强化学习理论中，大量经典文献聚焦于累积遗憾最小化。然而在诸如机器人原型测试、模拟决策支持、系统设计验证以及离线规划的模型选择等场景中，学习过程本身收集的即时奖励往往并不重要；智能体的核心诉求是以尽可能少的交互步数收集足够环境信息，并在达到给定置信度 $1-\delta$ 时主动终止，输出一个确定的最优控制策略。这一范式被称为定置信度下的最佳策略识别（Best Policy Identification, BPI）或纯探索强化学习。

传统的纯探索研究往往假设存在生成模型（Generative Model），允许算法在任意时刻对任意状态-动作对进行自由采样。然而在真实的在线强化学习环境中，智能体只能沿着单一的时间演化轨迹与未知的马尔可夫决策过程交互，其观测与转移必然受到马尔可夫转移规律的物理导航约束（Navigation Constraints）。虽然先驱工作（如 Al Marjani 等人提出的 Navigate and Stop 算法，简称 NaS）建立了基于博弈论的实例相关特征时间下界并在渐近极限 $\delta \to 0$ 下证明了渐近最优性，但现有关于在线 BPI 的理论分析完全停留在渐近层面。这种渐近保障隐藏了有限样本阶段的所有关键风险：在数据匮乏的初期阶段，经验转移核的不稳定波动、强制探索机制的耗时以及经验访问频率向遍历平稳分布逼近的瞬态动态，都可能对实际样本复杂度产生决定性影响。

在纯探索多臂老虎机（Best-Arm Identification, BAI）领域，Track-and-Stop 类算法的有限样本分析已被证明极其关键且具有高度挑战性。将该挑战拓展至在线强化学习则更为艰巨，不仅需要应对测度变换论证，还必须在非平稳自适应策略下控制非齐次马尔可夫链的遍历收敛性与受限流平衡条件。核心 idea：通过解构自适应策略下的非齐次马尔可夫链瞬态浓度偏离，结合最优状态-动作分配解集的几何锐度分析，为在线导航纯探索算法建立首个隐式与显式非渐近有限置信度样本复杂度上界。

方法详解¶

整体框架¶

在受导航约束的在线折扣马尔可夫决策过程 $\mathcal{M} = (\mathcal{S}, \mathcal{A}, P, r, \gamma)$ 中，智能体通过单一在线轨迹推进状态交互。BPI 的目标是在满足 $\mathbb{P}(\hat{\pi}_{\tau} \in \Pi^\star(\mathcal{M})) \geq 1 - \delta$ 的 $\delta$-Probably-Correct ($\delta$-PC) 准则下，最小化期望停止步数 $\mathbb{E}[\tau_\delta]$。

算法采用 Navigate-and-Stop (NaS) 框架的扩展机制，整体分为三层联动闭环：首先，在每一个交互步骤维护经验转移核并投影至有界测度空间；其次，基于当前估计模型求解最优驻留分配游戏的最优解，并与自适应强制探索策略加权混合以生成当前动作分布；最后，基于广义似然比（GLR）停止统计量检验当前收集的信息是否足以区分所有具有不同最优策略的混淆备择 MDP，一旦通过检验即触发停止并输出经验最优策略。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    Env["环境轨迹交互<br/>执行动作 a_t 观察 s_{t+1}"] --> Update["经验模型与投影更新<br/>更新计数 N_t 并投影到 G_μ(L)"]
    Update --> Plan["最优分配求解与最小二乘选择<br/>求解极小极大博弈得最优分配 ω_t*"]

    subgraph Sampling ["自适应混合导航策略"]
        direction TB
        Force["自适应欠采样强制探索策略<br/>Softmax 抑制高频并向低频倾斜"]
        Mix["动态凸组合策略<br/>π_t = (1-ε_t)π_t* + ε_t π_{f,t}"]
    end

    Plan --> Mix
    Force --> Mix
    Mix --> Env

    Update --> StopCheck{"广义似然比停止检验<br/>t · T(N_t/t; M_t)⁻¹ ≥ b(N_t, δ) ?"}
    StopCheck -->|否：继续探索| Plan
    StopCheck -->|是：停止探索| Output["输出经验最优策略<br/>基于 M_τ 运行策略迭代输出 π̂_τ*"]

关键设计¶

1. 极小极大最优分配追踪与投影模型估计：解决未知环境下的最优采样规划

根据信息论下界，任意 $\delta$-PC 算法的期望停止时间下界由特征时间 $T(\mathcal{M})$ 决定，其倒数等于以下零和博弈的最优值： $$T(\mathcal{M})^{-1} = \sup_{\omega \in \Omega(\mathcal{M})} \inf_{\mathcal{M}' \in \text{Alt}(\mathcal{M})} \sum_{s,a} \omega(s,a) \text{KL}\big(P(\cdot|s,a) \,\big\|\, P'(\cdot|s,a)\big)$$ 其中 $\Omega(\mathcal{M})$ 为马尔可夫转移约束下的可行平稳分布集合，$\text{Alt}(\mathcal{M})$ 为所有最优策略与原模型相异的备择 MDP 集合。由于真实环境未知，算法在时刻 $t$ 依据经验计数构造经验转移核并投影至先验测度球 $\mathcal{G}_\mu(L)$ 得到 $M_t$。针对最优分配集合 $\Omega^\star_t(M_t)$ 可能不是单点集的问题，算法显式引入最小 2-范数选择器 $\omega^\star_t = \arg\min_{\omega \in \Omega^\star_t(M_t)} \|\omega\|_2^2$，从而严格消除多最优解导致的策略跳跃抖动，并诱导导航策略 $\pi_t^\star(a|s) = \omega_t^\star(s,a) / \sum_{a'} \omega_t^\star(s,a')$。

2. 状态访问依赖的自适应强制探索机制：保障有限时间内全局状态动作充分覆盖

单纯追踪估计的最优分配可能导致采样陷入部分局部状态而忽略未被充分估计的边缘动作，从而无法保证经验核一致收敛。本文设计了无需先验估计环境连通度参数的自适应强制探索策略 $\pi_{f,t}(\cdot|s) = \text{softmax}\big(-\beta_t(s) N_t(s, \cdot)\big)$，其中温度调节系数为： $$\beta_t(s) = \frac{\beta \log(N_t(s))}{\max_a [N_t(s,a)] - \min_b [N_t(s,b)]}, \quad \beta \in (0,1)$$ 该设计对访问频次显著滞后的动作施加指数级选择偏好。随后以依赖于单点状态访问计数的衰减率 $\varepsilon_t = 1 / \max(1+\nu, N_t(s_t))^\alpha$ 将导航策略与强制策略进行凸组合：$\pi_t(a|s_t) = (1-\varepsilon_t)\pi_t^\star(a|s_t) + \varepsilon_t \pi_{f,t}(a|s_t)$。只要满足超参数约束 $\alpha + \beta < 1$，便可确保各状态动作对以严格可控的多项式下界被访问，避免状态空间坍缩。

3. 广义似然比停止规则与目标函数几何锐度控制：界定有限样本收敛阶数

算法采用基于鞅论与 Doob 不等式推导的时变置信阈值函数 $b(t,\delta) = \log(1/\delta) + (S-1)\sum_{s,a} \log\big(e[1 + \frac{N_t(s,a)}{S-1}]\big)$，在停止准则 $t \, T(N_t/t; M_t)^{-1} \geq b(t,\delta)$ 达成时触发终止。有限置信度分析的核心瓶颈在于：经验分配逼近最优分配时，目标函数 $J_M(\omega) = T(\omega, M)^{-1}$ 在最优解集周围的局部几何弯曲程度（即锐度，Sharpness）。定义锐度函数 $\varphi$ 满足 $\varphi\big(J_M^\star - J_M(\omega)\big) \geq \text{dist}_\infty(\omega, \Omega^\star(M))$。当目标函数极度平坦时，微弱的模型转移估计误差可能诱导巨大的分配偏差。论文严格论证了即使在离散有限 MDP 集合下锐度函数为线性，但在连续参数族中多项式锐度阶数可达任意有理指数，并在此基础上将集中性误差精准传递至样本复杂度的高阶修正项。

损失函数 / 训练策略¶

本算法为主动纯探索在线学习算法，无参数梯度优化步骤。其在线采样与更新流程由超参数三元组 $(\alpha, \beta, \nu)$ 调控，其中 $\alpha \in (0,1), \beta \in (0,1)$ 满足 $\alpha + \beta < 1$ 且 $\nu \in (0,1)$。在每个时间步 $t$，经验转移核在凸多面体空间 $\mathcal{G}_\mu(L)$ 上的 $L_1$ 投影可转化为标准凸二次/线性规划，而经验最优特征时间与目标分配的计算则依托于凸凹极大极小鞍点求解器；在满足停止不等式时，调用单调策略迭代（Policy Iteration）从 $M_{\tau_\delta}$ 中求解最终最优策略 $\hat{\pi}_{\tau_\delta}^\star$。

实验关键数据¶

主实验¶

论文对理论提出的非渐近上界展开了系统性的数值实验验证。由于本文是一篇核心纯理论工作，实验核心针对两个关键维度开展：其一是验证定理 4 提出的多项式锐度对样本复杂度曲线的实际影响；其二是对比不同算法在单轨迹导航约束 MDP 下的有限置信度期望停止样本数 $\mathbb{E}[\tau_\delta]$。基准算法包含 Navigate-and-Stop (NaS)、均匀强制探索基线 (Uniform-Forcing NaS) 以及启发式探索算法。

环境配置 / 评估设定	评估指标	本文 NaS 变体	原 NaS (Al Marjani et al.)	均匀探索基线	理论下界 $T(M)\log(1/\delta)$
4状态双动作可连通 MDP ($\delta = 10^{-2}$)	经验停止步数 $\mathbb{E}[\tau]$	$1.84 \times 10^4$	$2.91 \times 10^4$	$5.42 \times 10^4$	$1.21 \times 10^4$
4状态双动作可连通 MDP ($\delta = 10^{-4}$)	经验停止步数 $\mathbb{E}[\tau]$	$3.92 \times 10^4$	$5.68 \times 10^4$	$1.15 \times 10^5$	$2.73 \times 10^4$
4状态双动作可连通 MDP ($\delta = 10^{-6}$)	经验停止步数 $\mathbb{E}[\tau]$	$6.01 \times 10^4$	$8.45 \times 10^4$	$1.76 \times 10^5$	$4.25 \times 10^4$
目标函数曲率收敛斜率 (Log-Log)	经验锐度拟合斜率	匹配理论阶数	未提供非渐近分析	无自适应调节	渐近极限无界

消融实验¶

消融实验重点验证了构造族 $\mathcal{M}_{m,n}$ 中不同参数对 $(m,n)$ 下目标函数间隙 $J^\star - J(\omega^{(d)})$ 随距离 $d = \text{dist}_\infty(\omega, \Omega^\star)$ 的幂律衰减特性，直接支撑了定理 4 与推论 10 中的理论曲率阶数。

锐度构造阶数 $(m, n)$	理论间隙指数 $\frac{m}{m-n}$	理论锐度指数 $p = \frac{m-n}{m}$	对数斜率拟合值 (Empirical Slope)	相对误差
$(m=2, n=1)$	$2.000$	$0.500$	$1.994 \pm 0.012$	$< 0.3\%$
$(m=3, n=1)$	$1.500$	$0.667$	$1.498 \pm 0.009$	$< 0.2\%$
$(m=3, n=2)$	$3.000$	$0.333$	$2.987 \pm 0.021$	$< 0.5\%$
$(m=4, n=1)$	$1.333$	$0.750$	$1.331 \pm 0.011$	$< 0.2\%$
$(m=5, n=2)$	$1.667$	$0.600$	$1.662 \pm 0.015$	$< 0.3\%$

关键发现¶

经验验证充分印证了理论构造：在 log-log 坐标系下，目标间隙曲线的实测拟合斜率精确逼近理论推导的 $m/(m-n)$，表明在受导航约束的强化学习中，最优分配目标函数确实存在任意扁平的多项式曲率。
在有限置信度区域（如 $\delta = 10^{-2} \sim 10^{-4}$），高阶项 $\mathcal{O}(\sum A_i B_\delta^{r_i})$ 对实际交互步数具有实质性制约，原先渐近理论无法解释的样本延迟主要源自转移核估计误差与状态遍历混洗时间 $m, \kappa_M, 1/\eta_m$ 的耦合。
所提出的平滑 Softmax 强制探索机制显著优于纯均匀强制探索，使得算法在保证充分覆盖的同时尽可能贴合最优追踪方向，有效压低了前序瞬态误差 $A_4 B_\delta^{r_4}$。

亮点与洞察¶

首次攻克了受导航约束下强化学习纯探索的有限时间分析壁垒：克服了自适应策略导致非齐次马尔可夫链无固定谱隙的难题，借助鞅不等式与扰动分析完成了经验访问频率对最优分配的非渐近集中性证明。
深刻揭示了最优分配博弈的几何锐度（Sharpness）对 BPI 样本复杂度的本质影响：不仅证明了离散模型下的线性锐度，更构造了能产生任意有理多项式平坦度的反例族，填补了强化学习优化几何领域的基础理论空白。
理论上界结构清晰解构了各类物理量的贡献：显式分离出基础特征时间 $B_\delta$、环境遍历时间 $m$、状态混洗常数 $\kappa_M$、最小分配概率 $\underline{\rho}_M$ 以及多面体扰动敏感度 $\kappa_\Omega$，为未来面向实际部署的高效纯探索算法设计提供了明确的优化目标。

局限与展望¶

算法依然需要在线求解连续极小极大优化与可行多面体投影，对于大规模状态-动作空间或连续状态环境在计算复杂度上存在明显瓶颈。
当前非渐近理论假设奖励函数已知且确定，若扩展至随机未知奖励，上界将进一步叠加奖励方差诱导的置信半径，但核心导航挑战一致。
理论上界中出现的最小分配权重倒数 $1/\underline{\rho}_M$ 导致当最优分配极度偏向某单一动作时界限较宽，未来工作亟需探索该依赖性是否属于信息论不可避免项。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次打破在线 MDP 最佳策略识别长期仅有渐近保证的理论局限。
实验充分度: ⭐⭐⭐⭐ 理论构造与曲率实验验证极为严密，提供了清晰的数值模拟验证。
写作质量: ⭐⭐⭐⭐⭐ 数学推导层层递进，概念定义严密，实例物理意义解释极为透彻。
价值: ⭐⭐⭐⭐⭐ 填补了在线强化学习纯探索与顺序假设检验领域的基础理论空白。

环境配置 / 评估设定	评估指标	本文 NaS 变体	原 NaS (Al Marjani et al.)	均匀探索基线	理论下界 \(T(M)\log(1/\delta)\)
4状态双动作可连通 MDP (\(\delta = 10^{-2}\))	经验停止步数 \(\mathbb{E}[\tau]\)	\(1.84 \times 10^4\)	\(2.91 \times 10^4\)	\(5.42 \times 10^4\)	\(1.21 \times 10^4\)
4状态双动作可连通 MDP (\(\delta = 10^{-4}\))	经验停止步数 \(\mathbb{E}[\tau]\)	\(3.92 \times 10^4\)	\(5.68 \times 10^4\)	\(1.15 \times 10^5\)	\(2.73 \times 10^4\)
4状态双动作可连通 MDP (\(\delta = 10^{-6}\))	经验停止步数 \(\mathbb{E}[\tau]\)	\(6.01 \times 10^4\)	\(8.45 \times 10^4\)	\(1.76 \times 10^5\)	\(4.25 \times 10^4\)
目标函数曲率收敛斜率 (Log-Log)	经验锐度拟合斜率	匹配理论阶数	未提供非渐近分析	无自适应调节	渐近极限无界

锐度构造阶数 \((m, n)\)	理论间隙指数 \(\frac{m}{m-n}\)	理论锐度指数 \(p = \frac{m-n}{m}\)	对数斜率拟合值 (Empirical Slope)	相对误差
\((m=2, n=1)\)	\(2.000\)	\(0.500\)	\(1.994 \pm 0.012\)	\(< 0.3\%\)
\((m=3, n=1)\)	\(1.500\)	\(0.667\)	\(1.498 \pm 0.009\)	\(< 0.2\%\)
\((m=3, n=2)\)	\(3.000\)	\(0.333\)	\(2.987 \pm 0.021\)	\(< 0.5\%\)
\((m=4, n=1)\)	\(1.333\)	\(0.750\)	\(1.331 \pm 0.011\)	\(< 0.2\%\)
\((m=5, n=2)\)	\(1.667\)	\(0.600\)	\(1.662 \pm 0.015\)	\(< 0.3\%\)