在线凸优化

在连续凸集行动空间中，通过离散化行动空间并套用离散算法可以得到Õ(md+k)的遗憾，但所需网格点数量随维度d指数增长，导致算法在多项式时间内不可行。

在本次研究之前，追踪切换k次专家序列的在线凸优化问题已知的最高效多项式时间算法的遗憾为Õ(dk)。

信息论最优遗憾Õ(md+k)与多项式时间可达遗憾之间存在本质分离，该鸿沟是计算复杂性所固有的，而非算法设计不足。

对于实际算法设计，当维度d较大且切换次数k不可忽略时，接受Õ(dk)级别的遗憾或寻求额外结构假设，可能是比依赖离散化或精确优化更务实的方向。