实例最优在线学习的 SMART 方法
内容提要
本文综述在线学习与在线优化算法，涵盖FlipFlop算法、连续时间无遗憾策略、非凸损失下的Perturbed Leader、无界域无标度算法、随时算法与动态定价、FTL曲率性质、马尔可夫决策过程两全学习、Hedge自适应学习率、动态比较基准及自适应对手强度，并统一了多种遗憾上界。
延伸解读
算法融合的平衡之道
FlipFlop算法将Follow-the-Leader与AdaHedge结合，旨在同时保留FTL在简单问题上的强势表现和AdaHedge的最坏情况保证。这种融合思路避免了单一算法的局限性，为在线学习提供了一种兼顾平均性能和鲁棒性的设计范式。
连续时间视角的统一框架
基于连续时间的在线优化策略族能够达到无遗憾学习，并导出大量离散时间算法的无遗憾性质，统一了许多经典遗憾上界。这一框架还给出了无需倍增技巧的O(n^{-1/2})遗憾上界，简化了传统分析中的复杂步骤。
非凸损失下的遗憾优化
在非凸损失设置下，经典的Perturbed Leader算法仍能达到最佳遗憾率，而乐观的FTPL算法在序列损失可预测时遗憾界更优。这表明即使损失函数非凸，通过适当的扰动或乐观策略，仍能实现高效的在线学习。
无界域与无标度算法
针对无界决策集，无标度在线线性优化算法无需损失向量的上下界，实现了适应范数的缩放不变性和最优遗憾。通过FTRL和MD元算法，该工作还研究了无界域上的非真空遗憾绑定及基于MD的无标度算法下限，为实际应用提供了理论保障。
Q&A
FlipFlop算法是如何结合Follow-the-Leader和AdaHedge的？
FlipFlop算法将Follow-the-Leader算法和AdaHedge策略相结合，同时不牺牲前者的强势表现和后者的最坏情况保证。
连续时间在线优化策略族能保证什么样的遗憾上界？
该策略族能够达到无遗憾学习，并得到一个无需倍增技巧即可保证O(n^{-1/2})遗憾上界的学习策略类。
在非凸损失下，Perturbed Leader算法的遗憾表现如何？
经典的Perturbed Leader算法在非凸损失设置下可达到最佳遗憾率，且乐观的FTPL算法在序列损失可预测时遗憾界更优。
无界域上的无标度在线线性优化算法有什么特点？
该算法不需要任何上限或下限，实现了适应损失向量范数的缩放不变性，并通过FTRL和MD元算法实现了最优遗憾，还为无界决策集开发了非真空遗憾绑定的自适应算法。
随时算法在动态定价问题中能达到什么遗憾界？
在合理的额外假设下，该随时算法在动态定价中具有O(√T)的遗憾，而该问题被证明是困难的。
FTL算法在非凸损失函数下是否仍能表现出曲率性质？
是的，在一定条件下，即使损失函数未必为凸，FTL算法仍可以表现出与曲率相似的性能，同时保证最坏情况下的良好结果。
如何通过T个episode学习马尔可夫决策过程实现两全其美？
提出了一种新的变换，将方法从已知转移推广到未知转移下，并使得转移估计错误上界为多项式级别。
Hedge算法中自适应设置学习率的方法有什么优势？
该方法在最坏情况下保证了最优表现，但在简单的情况下可以达到更小的错误率，并且有仿真研究比较其与现有方法的优劣。
在线学习中如何处理动态比较基准？
提出了一种完全自适应的方法，适用于在线学习中的动态比较基准，并且应用到了零和博弈中。
如何衡量自适应对手的强度？
使用新概念的策略遗憾去衡量玩家的表现，特别关注记忆和切换成本的自适应对手，具有均摊2/3次幂的速率且强度显著较弱。
