这篇论文解决了有预算限制下在线拍卖竞价的理论问题，用DAG算法实现了亚线性遗憾，适合对拍卖理论和在线学习感兴趣的人。
本文研究多单元歧视性拍卖中重复竞价问题，单一投标人每轮效用为价值减去α倍支付（α∈[0,1]为资金成本参数），目标是在总预算B下最大化T轮累计效用。通过单位效用分解，论文提出基于有向无环图（DAG）的多项式时间学习算法，在全信息和赌博机反馈下均实现亚线性遗憾。在赌博机设置下，由于完全交叉学习，遗憾与上下文数量无关：观察到所选动作在实现上下文下的效用即可揭示同一动作在所有反事实上下文下的效用。当预算约束下平均归一化每轮预算ρ=B/(MT)<1时，设计耦合原对偶算法，DAG过程使用对偶调整边权重进行原始更新，在线梯度下降更新对偶变量，得到ρ近似亚线性遗憾。最后给出逐轮时间和空间与上下文数量无关的实现，可扩展至大规模甚至无限上下文空间。
Learning to Bid in Discriminatory Auctions with Budget Constraints
We study repeated bidding in multi-unit discriminatory (pay-as-bid) auctions for a single bidder with per-round utility equal to value minus $α$ times payment, where $α\in[0,1]$ is a cost-of-capital parameter. The bidder aims to maximize cumulative utility over $T$ rounds subject to a total budget $B$. The problem is challenging even without budgets: the action space is exponential in $M$, the maximum demand of the bidder and the valuation vector (context) varies over time. Exploiting a decomposition of utility across units, we develop polynomial-time learning algorithms based on shortest paths in a directed acyclic graph, obtaining sublinear regret under both full-information and bandit feedback. In the bandit setting, the regret is independent of the number of contexts due to complete cross-learning: observing the utility of the chosen action under the realized context reveals the utility for the same action under all counterfactual contexts. With budget constraints, when the average normalized per-round budget $ρ=\frac{B}{MT}<1$, we design a coupled primal-dual algorithm in which the DAG-based procedure uses dual-adjusted edge weights for primal updates, while online gradient descent updates the dual variable, yielding $ρ$-approximate sublinear regret. Finally, we give implementations whose per-round time and space are independent of the number of contexts, enabling scalability to large or even infinite context spaces.