Feb, 2024

解耦学习与决策：用一阶方法突破在线资源分配中的 $O (√T)$ 障碍

PDF
TL;DR在线线性规划在收入管理和资源分配中起着重要作用，本文提出了一种新的算法框架，将学习与决策分离，首次展示了基于一阶方法的在线算法可以达到 O (T^{1/3}) 的遗憾，同时进行了数值实验以验证理论发现。
online linear programmingfirst-order online learning algorithmsregretalgorithmic frameworknumerical experiments
发现论文，激发创造
  • 在线线性规划的动态近最优算法

    本文提出了一种基于学习的在线线性规划算法，可应用于许多在线资源分配和收入管理问题，具有良好的竞争优势。

    Nov, 2009

  • 高效使用近似算法的在线线性优化

    本文讨论在线线性优化问题，考虑可行操作集通过近似线性优化预言机具有 α 乘性逼近保证的情况，给出了新算法并提出了显著改进甚至多项式对数的预言机复杂度，同时得到了常数 c>0 的 alpha 遗憾界。

    Sep, 2017

  • 利用线性函数近似的强化学习的一阶遗憾：一种鲁棒估计方法

    本研究基于鲁棒 Catoni 平均值估计器，提出一种新的鲁棒自归一化浓度界，解决了已有技术在大状态空间强化学习中无法获得遗憾上界的问题，并证明了在线性 MDP 设定下，可以获得与最优策略性能某种度量成比例的遗憾上界。

    Dec, 2021

  • 资源分配问题的近最优在线算法和快速近似算法

    本文提出一种针对多个资源分配问题的算法体系，将在线请求建模为每次从未知的概率分布中独立抽取，给出了一个在任意接受数据的情况下获得一定比例最优解的单一算法，并且探究了如何在任意情况下应对敌对分布。同时，文中提出了解决大型 LPs 混合装填覆盖问题的快速算法，并分析了该算法在在线拍卖、网络路由和广告策略方案等特殊情况下的应用。

    Mar, 2019

  • 一种统一的离线 - 在线资源分配的双阶段模型

    本文针对在线资源分配问题提出了一个基于非均匀和已知到达分布的参数化线性规划算法，并进行了实验结果测试。

    Dec, 2020

  • 在线线性二次控制

    我们研究了控制具有已知嘈杂动力学和对抗选择二次损失的线性时不变系统的问题，并提出了第一种在这种情况下保证 O（sqrt（T））遗憾的有效在线学习算法。我们的算法依赖于对系统稳态分布的新型 SDP 松弛。与以前提出的松弛相反，我们的 SDP 的可行解都对应于 “强稳定” 策略，这些策略混合到稳定状态的速度呈指数增长。

    Jun, 2018

  • 在线控制的对数后悔

    本研究中，我们研究了在线控制下的线性动态系统在拥有转移动态知识的拥有敌意的变化强凸成本函数下的最优遗憾界限，并提出了在线梯度下降和在线自然梯度两种不同且高效的迭代方法来实现遗憾边界小而有效。

    Sep, 2019

  • 对抗性在线控制的对数遗憾

    本文针对已知系统且受到敌对扰动的情况下，介绍了新的在线线性二次控制算法，通过将在线控制问题转化为具有近似优越函数的（延迟的）在线学习，无需控制迭代的运动成本，从而提高了算法的效果。

    Feb, 2020

  • 学习覆盖：在线学习和优化与不可逆决策

    通过限制在线学习和优化策略的探索次数，将不确定性减少为最低程度，从而最小化成本并实现覆盖目标。

    Jun, 2024

  • 时序马尔可夫决策过程中的在线资源分配

    本文研究了一个多期的长期资源分配问题，其中每个周期需要一个多阶段的决策过程。我们将此问题定义为具有未知非平稳转换和随机非平稳奖励和资源消耗函数的离散时段有限马尔可夫决策过程的在线资源分配问题。我们提出了一种基于占用度量的等效在线线性规划重构方法，并开发了一种在线镜像下降算法。我们证明，在随机奖励和资源消耗函数下，在线镜像下降算法的期望遗憾值受到了限制。

    May, 2023