平均奖励强化学习的有限常数前沿与可审计遗憾证书

# 平均奖励强化学习的有限常数前沿与可审计遗憾证书

Source: https://arxiv.org/html/2608.07725

Ibne Farabi Shihab¹, Abu Sa-Adat Mohamed Moon-Im Al Ahsan², Md Najmus Swaqeeb²

¹ 爱荷华州立大学计算机科学系  
² BRAC大学计算机科学与工程系  

[email protected], [email protected], [email protected]

###### 摘要

平均奖励强化学习的遗憾已知到对数因子，但由于概率模式、结构参数、对数归一化、先验信息和规划假设各不相同，已发表保证的数值内容难以比较。我们引入了一个常数感知的比较协议，并为通信MDP导出了一个显式的有限下界证书。该构造是一个由二态块构成的二叉树；其证明使用精确的轨迹级Bernoulli KL散度，并保持动作预算、直径、占用率、导航成本和终端偏差均为显式。一个公共闭式包络在一个有限前沿上改进了已发表的系数 \(0.015\)：在中等场景下为 \(0.0200\)，在更强的动作、直径和时间范围条件下最高达 \(0.0291\)，提升了 \(94\%\)。极限系数为 \(\frac{1}{32}\sqrt{(A-3)/A}\)。对于上界，我们为跨距受限的乐观学习器给出一个可审计的复合规则，但在自适应方向方差和规划证书仍然开放的情况下，我们不声称系数。我们还形式化了有效的期望转换和常数可比性。受控诊断测试了直径依赖性、加成与宽度的交互、跨距错误设定，以及在其精确族上的有限下界证书。

## 引言

平均奖励强化学习是持续型任务的自然模型，例如推荐、排队控制、库存管理和投资组合再平衡，这些任务没有情节式重置(Mahadevan1996 (https://arxiv.org/html/2608.07725#bib.bib45); Puterman1994 (https://arxiv.org/html/2608.07725#bib.bib14); Sutton and Barto2018 (https://arxiv.org/html/2608.07725#bib.bib15))。对于直径为 \(D\)、状态数为 \(S\)、动作数为 \(A\)、时间范围为 \(T\) 的通信MDP，经典极小极大尺度是 \(\sqrt{DSAT}\) (Jakschet al.2010 (https://arxiv.org/html/2608.07725#bib.bib1))。后续工作发展了偏差跨距正则化、KL或经验Bernstein置信区域、无模型方法，以及易处理的极小极大最优规划(Bartlett and Tewari2009 (https://arxiv.org/html/2608.07725#bib.bib2); Fruitet al.2018 (https://arxiv.org/html/2608.07725#bib.bib4); Zhang and Ji2019 (https://arxiv.org/html/2608.07725#bib.bib6); Fruitet al.2020 (https://arxiv.org/html/2608.07725#bib.bib5); Boone and Zhang2024 (https://arxiv.org/html/2608.07725#bib.bib49))。这些论文锐化了速率和结构依赖性，但诸如 \(\widetilde{O}(\sqrt{DSAT})\) 这样的速率并不能揭示被证明的乘数是 \(3\)、\(30\)，还是 \(300\)。“前导常数”只有在归一化固定之后才有意义。一个乘以 \(\sqrt{\log(SAT/\delta)}\) 的系数与一个乘以 \(\log(SAT/\delta)\) 的系数并不直接可比；而一个高概率上界系数本身也并不是与无对数的期望下界构成常数因子匹配。这一区别至关重要：Jakschet al.(2010 (https://arxiv.org/html/2608.07725#bib.bib1)) 在有限条件下给出了显式的下界系数 \(0.015\)，而他们的UCRL2系数 \(34\) 乘以的是不同的形式 \(DS\sqrt{AT\log(T/\delta)}\)。我们做出四项贡献。第一，我们为每个常数记录概率模式、结构项、对数项、时间范围阈值和辅助信息。第二，我们导出了一个精确KL下界证书，其中检验、占用、导航和几何项保持显式，并将其转化为从 \(0.0152\) 到 \(0.0291\) 的一致有限前沿。第三，我们规定了一个可审计的上界账本，并指出在数值系数有效之前必须完成的统计与规划义务。第四，我们围绕修正后的主张重新设计了实证检验：零跨距直径平坦性、加成与宽度的交互、宽度错误设定，以及在已证明的困难族上的直接评估。完整证明和扩展实验见补充材料。

## 设置、相关工作与比较协议

一个平均奖励MDP是 \(M=(\mathcal{S},\mathcal{A},p,\nu)\)，其中奖励位于 \([0,1]\)。在时刻 \(t\)，学习器观测 \(s_t\)，选择 \(a_t\)，接收 \(R_t\sim\nu(\cdot\mid s_t,a_t)\)，并观测 \(s_{t+1}\sim p(\cdot\mid s_t,a_t)\)。我们保留显式奖励模型，因为随机奖励不确定性通常不能吸收到转移加成中。对于通信MDP，最优增益 \(\rho^{\star}\) 与起始状态无关，且最优偏差 \(h^{\star}\) 满足
\[
\rho^{\star}+h^{\star}(s)=\max_{a\in\mathcal{A}(s)}\left\{r(s,a)+\sum_{s^{\prime}}p(s^{\prime}\mid s,a)h^{\star}(s^{\prime})\right\}.
\tag{1}
\]
直径为 \(D=\max_{s\neq s^{\prime}}\min_{\pi}\mathbb{E}_{s}^{\pi}[\tau_{s^{\prime}}]\)，跨距复杂度为 \(H=1\vee\operatorname{sp}(h^{\star})\)，遗憾为
\[
\mathcal{R}_{T}=T\rho^{\star}-\sum_{t=1}^{T}R_t.
\]
下界取 \(1\) 是必要的：一个通信MDP可以具有常数最优偏差，同时仍包含一个具有 \(\Omega(\sqrt{SAT})\) 遗憾的随机bandit学习问题。我们研究 \(\mathbb{E}[\mathcal{R}_T]\)；实现遗憾可以为负，但总是至多 \(T\)，这在将尾部保证转换为期望时很重要。

相关的平均奖励文献包括UCRL2及其下界构造(Jakschet al.2010 (https://arxiv.org/html/2608.07725#bib.bib1))、REGAL/SCAL(Bartlett and Tewari2009 (https://arxiv.org/html/2608.07725#bib.bib2); Fruitet al.2018 (https://arxiv.org/html/2608.07725#bib.bib4))、EBF(Zhang and Ji2019 (https://arxiv.org/html/2608.07725#bib.bib6))、经验Bernstein改进(Talebi and Maillard2018 (https://arxiv.org/html/2608.07725#bib.bib10);