追逐长期约束的凸函数

本文介绍了一种在线凸优化算法，考虑具有对抗性时变约束的情景。通过线性优化预言机（LOO）访问约束集合，保证在长度为T的序列上，相对于损失函数产生的后悔为$O(T^{3/4})$，对约束的违反为$O(T^{7/8})$。还提出了一种更高效的算法，只需对软约束进行一阶预言机访问，并在整个序列上获得类似的边界。将后者扩展到强化学习场景，并在期望上获得类似的边界。