解耦学习与决策：利用一阶方法突破在线资源分配中的 O (T) 瓶颈

在线线性规划在收入管理和资源分配中发挥着重要作用，最近的研究集中在开发高效的一阶在线学习算法上。尽管一阶方法在经验上取得了成功，它们通常的遗憾不优于 O (T)，与最先进的基于线性规划（LP）的在线算法所保障的 O (T) 界限相比，这一结果是不理想的。本文确立了关于在线线性规划的几个重要事实，这揭示了基于一阶方法的在线算法在超越 O (T) 遗憾方面的挑战。为了解决这一挑战，我们引入了一种新的算法框架，将学习与决策解耦。更重要的是，我们首次展示了在这一新框架下，一阶方法可以达到 O (T^1/3) 的遗憾。最后，我们进行了数值实验以验证我们的理论结果。