May, 2023

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

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

    本文研究在线分配问题，涉及凹收益函数和资源限制，是收益管理和在线广告中的中心问题。通过在线镜像下降，我们提出了一种通用的算法类，可以实现次线性期望遗憾，同时也讨论了这种算法在重复拍卖中的应用。

    Feb, 2020

  • 对抗性马尔科夫决策过程中的在线凸优化

    本文研究了在线学习在没有循环的马尔可夫决策过程中的应用，提出了基于熵正则化方法实现的在线算法并给出了 $\tilde {O}(L|X|\sqrt {|A|T})$ 的遗憾界，通过处理凸性能标准并改进之前的遗憾界，扩展了对抗性 MDP 模型，并可以更好地处理单个 episode 的损失。

    May, 2019

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

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

    Dec, 2020

  • 具有长期约束的随机网络资源分配的在线优化

    本文研究了一个在线资源预订问题，通过一个由两个计算节点组成的通信网络，在有限时间内最小化整体预订成本，并且保持累计违规与运输成本在一定预算限制下的在线重复博弈，提出了一个在线鞍点算法来解决该问题。

    May, 2023

  • 具约束的有限时间 MDP 的高样本效率算法

    本文研究了约束马尔可夫决策过程，并提出了一种在线算法，该算法利用了有限时间视角下的线性规划公式来进行乐观规划，以提供概率上正确的 γ 优化策略，该算法逐渐逼近最佳结果，并且保证结果最多只是 γ 深度有损失的结果，并且在指定公差范围内具有概率保证。

    Sep, 2020

  • 非定常线性马尔可夫决策过程中的高效学习

    本研究提出了一种基于权重最小二乘值迭代的非稳态线性马尔可夫决策过程（MDP）最优模型 - free 算法 OPT-WLSVI，使用指数权重平滑地遗忘过去的数据，与先前的研究相比解决了遗忘策略上的技术差距，并分析了与最佳策略竞争的总遗憾是有上限的。

    Oct, 2020

  • 具有延迟反馈的对抗性马尔可夫决策过程学习

    本文研究了具有未知转换和拥有无限制延迟反馈的分集式马尔可夫决策过程的在线学习，表现出基于策略优化的新算法，在完全信息反馈下实现了接近最优的高概率后悔情况，同时也是第一个考虑具有延迟反馈的 MDP 的后悔最小化设置。

    Dec, 2020

  • 带有侧面信息的 MDPs 在线学习

    本文提出了一种在线学习算法，使用有限马尔可夫决策过程解决了具有临床试验和推荐系统的应用方案的问题，该算法可以在计算效率上得到提升，并且在此设置下的后悔度最多为 O (√T)。

    Jun, 2014

  • 网络资源分配的在线优化及与强化学习技术的比较

    我们在本文中解决了一种带有任务转移的在线网络资源分配问题，提出了基于指数加权方法的随机在线算法，证明了该算法具有次线性时间后悔，通过对人工数据进行性能测试并与强化学习方法进行比较表明我们的方法优于后者。

    Nov, 2023

  • 两个世界中的最佳选择：在未知到达模型下的在线资源分配与预测

    给定未知质量的预测作为输入，我们提出了一种算法，在未知预测质量和请求模型的情况下，在在线资源分配问题中实现了渐进最优表现，验证了算法的性能与任何已知到达模型和预测准确性的算法的最佳性能相匹配。

    Feb, 2024