历史平均相关成本的在线决策

在许多在线顺序决策场景中，学习者的选择不仅影响当前的成本，还影响未来的成本。本文研究了一种特殊情况，其中成本依赖于过去决策的时间平均值，我们提出了一种新颖的算法 Follow-The-Adaptively-Regularized-Leader (FTARL)，该算法通过历史决策来动态调整正则化项，从而在满足阶段性约束的同时确保最小遗憾值。我们还讨论了历史视野长度对于无遗憾算法设计的影响，并在完全学习视野下给出了一些不可能性的结果。