解耦学习与决策：用一阶方法突破在线资源分配中的 $O (√T)$ 障碍
内容提要
本文综述在线线性规划与资源分配研究，提出基于学习的在线算法，在近似预言机下改进复杂度并获得常数遗憾界；利用鲁棒估计为强化学习提供遗憾上界；针对未知分布与敌对分布设计统一算法；研究线性动态系统的在线控制与二次控制，实现O(√T)遗憾；并给出长期约束优化的次线性遗憾算法。
延伸解读
从近似预言机到常数遗憾：算法效率的权衡
文章指出，在可行操作集通过近似线性优化预言机具有α乘性逼近保证时，新算法能显著改进预言机复杂度，甚至达到多项式对数级别，并获得常数α遗憾界。这意味着在资源分配等场景中，即使预言机不精确，也能实现高效学习与决策，但需注意α值对遗憾界的直接影响。
鲁棒估计如何为强化学习提供遗憾上界
针对大状态空间强化学习中遗憾上界难以获得的问题，研究基于鲁棒Catoni平均值估计器提出新的自归一化浓度界，并在线性MDP设定下证明了遗憾上界与最优策略性能的某种度量成比例。这为强化学习在复杂环境下的理论分析提供了新工具，但实际性能仍取决于估计器的鲁棒性参数设置。
在线控制中的O(√T)遗憾：从线性系统到二次控制
文章综述了线性动态系统在线控制的研究，包括对抗性二次损失下首个保证O(√T)遗憾的算法，以及基于在线梯度下降和自然梯度的方法。这些工作将控制问题转化为在线学习，但均假设系统动态已知或可学习，实际应用中需考虑模型误差与对抗扰动的平衡。
长期约束优化的次线性遗憾：非凸场景的突破
针对目标和约束非凸的长期约束优化，文章提出Follow-the-Perturbed-Leader型算法，通过引入随机线性扰动和强凸扰动，首次实现O(T^{8/9})次线性遗憾。该算法在河流污染源辨识问题中验证了有效性，但收敛速率较慢，适用于对精度要求不苛刻的长期决策场景。
Q&A
在线资源分配问题中，如何突破O(√T)遗憾障碍？
本文提出基于学习的在线算法，在近似预言机下改进复杂度，获得常数遗憾界，从而突破O(√T)障碍。
在线线性规划中，近似预言机的复杂度能改进到什么程度？
在可行操作集通过近似线性优化预言机具有α乘性逼近保证的情况下，新算法实现了显著改进甚至多项式对数的预言机复杂度，并得到常数c>0的alpha遗憾界。
如何为强化学习提供遗憾上界？
基于鲁棒Catoni平均值估计器，提出新的鲁棒自归一化浓度界，解决了大状态空间强化学习中无法获得遗憾上界的问题，并证明了在线性MDP设定下可获得与最优策略性能某种度量成比例的遗憾上界。
针对未知分布和敌对分布的在线资源分配，有统一算法吗？
有。本文提出一种算法体系，将在线请求建模为从未知概率分布独立抽取，给出在任意接受数据下获得一定比例最优解的单一算法，并探究了如何应对敌对分布。
线性动态系统的在线控制如何实现O(√T)遗憾？
针对已知嘈杂动力学和对抗选择二次损失的线性时不变系统，提出第一种保证O(√T)遗憾的有效在线学习算法，依赖于对系统稳态分布的新型SDP松弛，其可行解对应强稳定策略。
长期约束优化问题有哪些次线性遗憾算法？
提出一种新型Follow-the-Perturbed-Leader类型算法，用于在线解决一般长期受约束优化问题，目标和约束不一定是凸的，通过引入随机线性扰动和强凸扰动，推导出第一个次线性O(T^{8/9})遗憾复杂度。
