提出一种无需求解线性规划的在线资源分配算法，可实现恒定后悔值。
A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret
- 基于梯度上升更新动作选择，每周期仅一次计算。
- 期望累积后悔值为常数，不随时间长度T增长。
- 适合未知请求概率且需快速决策的实时资源分配场景。
我们研究了一个有限时域的在线资源分配问题，初始资源容量与时域长度成比例。每期观察到一个请求类型后，从有限动作集中选择一个动作，每个动作产生收益并消耗资源向量。请求类型独立同分布，但其概率未知。本文提出一种原始一阶学习策略：每期对当前请求类型对应的动作坐标执行一次梯度上升更新。该策略相对于事后最优解的期望加性后悔值为O(1)，且该界与时域长度T无关。算法无需求解任何线性规划，且后悔界不依赖于流体线性规划的非退化假设。
原文摘要 · Abstract (English)
We study a finite-horizon online resource allocation problem with initial resource capacities proportional to the horizon. In each period, a request type is observed and one action is chosen from a finite menu. Each action earns a reward and consumes a vector of resources. The arrival types are independent and identically distributed, but their probabilities are unknown. We present a primal first-order learning policy that, in each period, performs one gradient ascent update of the action coordinates associated with the current request type. The policy achieves $O(1)$ expected additive regret relative to the hindsight optimum, with a bound independent of the horizon $T$. It does not solve any linear program, and the regret bound does not require a nondegeneracy assumption on the fluid linear program.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。