Online Prediction of Stochastic Sequences with High Probability Regret Bounds¶

会议: ICLR 2026
arXiv: 2602.16236
代码: 无
领域: 强化学习 / 在线学习理论
关键词: 在线预测, 随机序列, 高概率遗憾界, 通用预测, 可数字母表

一句话总结¶

重新审视有限时间范围 \(T\) 下随机序列的通用预测经典问题，首次给出以高概率成立的消退遗憾界（形式为 \(O(T^{-1/2}\delta^{-1/2})\)），与已有的期望遗憾界 \(O(T^{-1/2})\) 形式高度一致，并证明在不附加额外假设时 \(\delta\) 的指数无法改进。

研究背景与动机¶

通用预测（Universal Prediction）是信息论和在线学习的经典问题：给定一个由未知随机过程生成的序列，学习者的目标是对每一步的下一观测进行最优预测，使其累积损失（遗憾/regret）尽可能逼近"知道真实分布的先知"策略。

在已有文献中，通用预测的遗憾界主要以期望形式给出。例如，对于可数字母表上的随机过程，经典结果给出的期望遗憾收敛率为 \(O(T^{-1/2})\)。然而，期望界存在本质局限：

尾部风险不可控：期望界只保证"平均"表现良好，但不排除在某些（可能概率不低的）实现路径上遗憾极大

不适合风险敏感场景：在安全关键、金融风控等应用中，需要的是"除了极小概率事件外，遗憾一定不超过某个阈值"这类更强的高概率保证

理论空白：是否能在不显著牺牲收敛率的情况下，将期望界提升为高概率界，这一问题此前尚未解决

本文的核心贡献就是回答了这个问题：可以——并给出了形式上与期望界高度一致的高概率界，代价仅是多一个 \(\delta^{-1/2}\) 因子。

方法详解¶

整体框架¶

考虑如下在线预测场景： - 字母表：可数集 \(\mathcal{X}\)（可以是无限可数的） - 时间范围：有限 \(T\)，且学习者已知 \(T\) - 随机过程：序列 \(X_1, X_2, \ldots, X_T\) 由某个未知的平稳可遍历过程 \(P\) 生成 - 目标：设计预测器 \(\hat{q}_t(\cdot | X^{t-1})\)，使得对真实条件分布 \(p_t(\cdot | X^{t-1})\) 的累积 KL 散度（遗憾）尽可能小 - 遗憾定义：\(R_T = \sum_{t=1}^T D_{\text{KL}}(p_t \| \hat{q}_t)\) 或等价的对数损失形式

关键设计¶

从期望到高概率的提升：
- 已知的期望界：\(E[R_T] = O(\sqrt{T})\)，即 \(E[R_T / T] = O(T^{-1/2})\)
- 本文的高概率界：\(P(R_T / T \geq \epsilon) \leq \delta\)，其中 \(\epsilon = O(T^{-1/2} \delta^{-1/2})\)
- 换言之，以至少 \(1 - \delta\) 的概率，遗憾率不超过 \(O(T^{-1/2}\delta^{-1/2})\)
技术路线：
- 传统的 Markov 不等式直接将期望界转为高概率界会得到 \(O(T^{-1/2}\delta^{-1})\)，其中 \(\delta\) 的指数为 -1
- 本文通过更精细的分析（可能利用随机过程的混合性质、集中不等式的改进或 Azuma-Hoeffding 类型的鞅不等式），将 \(\delta\) 的指数改进为 \(-1/2\)
- 这一改进虽然看似微小，但在理论上具有本质性意义
不可能性结果（Impossibility Result）：
- 证明在不附加额外假设（如更强的混合条件、指数矩条件等）的情况下，\(\delta^{-1/2}\) 的指数是最优的，不可能进一步改进
- 通过构造对抗性（adversarial）实例来证明下界
- 这使得本文的上界和下界在 \(\delta\) 依赖性上实现了匹配，给出了完整的刻画
可数字母表的处理：
- 可数字母表上的通用预测比有限字母表更具挑战性，因为模型类更丰富
- 需要处理无限维分布空间上的一致收敛问题
- 本文的结果适用于这一更一般的设定

损失函数 / 训练策略¶

本文为纯理论工作，无训练过程。关键数学工具包括： - 对数损失（Log-loss）作为标准预测损失函数 - KL 散度作为遗憾的度量 - 鞅集中不等式进行高概率分析 - 信息论工具（互信息、条件熵等）处理随机过程预测

实验关键数据¶

主实验¶

本文为纯理论贡献，主要结果为定理和命题形式：

结果类型	界的形式	概率保证	字母表	备注
已有期望界	\(E[R_T/T] = O(T^{-1/2})\)	期望	可数	文献已知
本文高概率界	\(R_T/T \leq O(T^{-1/2}\delta^{-1/2})\)	\(\geq 1-\delta\)	可数	新结果
Markov 不等式转换	\(R_T/T \leq O(T^{-1/2}\delta^{-1})\)	\(\geq 1-\delta\)	—	平凡转换
本文下界	\(\delta^{-1/2}\) 指数不可提升	—	—	匹配上界

消融实验¶

方法/条件	δ 指数	是否最优	说明
期望界 + Markov 不等式	\(-1\)	否	过于粗糙的转换
本文高概率分析	\(-1/2\)	是	通过精细分析改进
加强假设（如强混合）	可能更好	条件依赖	需额外假设

关键发现¶

期望界到高概率界的代价是平方根：从 \(O(T^{-1/2})\) 到 \(O(T^{-1/2}\delta^{-1/2})\)，额外付出的 \(\delta^{-1/2}\) 因子是必要且充分的
不可能性结果的根本原因：随机过程的内在变异性（inherent variability）限制了高概率集中度，不同于独立同分布设定中更强的集中现象
与有限字母表结果的对比：可数字母表的结果在形式上与有限字母表一致，但证明技术更复杂

亮点与洞察¶

极致简洁的主定理：\(O(T^{-1/2}\delta^{-1/2})\) 与期望界 \(O(T^{-1/2})\) 形式高度一致，多出的 \(\delta^{-1/2}\) 因子优雅地刻画了"概率保证的代价"
上下界匹配：不仅给出了高概率界，还通过不可能性证明了其最优性，这在理论研究中非常罕见且珍贵
重新审视经典问题：在已有大量文献的经典问题上仍能找到未回答的自然问题并给出完美解答，体现了深厚的理论功底
连接两大研究传统：将信息论中的通用预测与在线学习中的高概率分析有机结合

局限与展望¶

需知 \(T\)：学习者需要预先知道时间范围 \(T\)，对于 anytime（任意时刻成立的）设定的推广值得探索
平稳性假设：是否能推广到非平稳或对抗性环境是重要方向
实际算法效率：理论结果是否对应计算高效的预测算法需要进一步讨论
更一般的损失函数：本文聚焦于对数损失/KL 散度，能否推广到其他损失（如平方损失、绝对损失）有待研究
有限样本常数：\(O(\cdot)\) 记号隐藏的常数对实际应用的影响值得分析

评分¶

新颖性: ⭐⭐⭐⭐ — 经典问题的新回答，技术上可能非平凡但概念创新有限
实验充分度: ⭐⭐⭐ — 纯理论工作，无实验验证，但定理本身即为"实验"
写作质量: ⭐⭐⭐⭐ — 理论论文的清晰表述需要高水平技巧
价值: ⭐⭐⭐⭐ — 填补了理论空白，上下界匹配具有数学上的完美性