arXiv:2602.06565cs.LGcs.GT2026-02

在反馈被截断的在线资源分配中,提出新算法实现高效探索与利用平衡。

Learning to Allocate Resources with Censored Feedback

  • 设计乐观算法RA-UCB和MG-UCB,结合参数估计与置信区间优化
  • 在已知预算下达到√T阶后悔上界,强假设下可降至对数多项式
  • 适用于有截断反馈的真实场景,如广告投放、医疗资源分配

我们研究在线资源分配问题:每轮需在K个臂之间分配预算B,但仅当臂被激活且预算超过随机阈值时才获得奖励。激活由未知参数的伯努利变量控制,阈值来自未知参数的参数化分布。在T轮中,学习者需联合估计未知参数并分配预算以最大化累积奖励,面临探索-利用权衡。我们证明了信息论下界Ω(T^{1/3}),表明问题固有难度。随后提出RA-UCB,一种利用非平凡参数估计和置信界的方法,在每轮开始时预算已知的情况下,实现˜O(√T)阶后悔;在更强假设下可达O(poly-log T)。对于每轮预算未知的情况,引入MG-UCB,支持轮内切换与无穷小分配,性能匹配RA-UCB。实验在真实数据集上验证了理论结果。

原文摘要 · Abstract (English)

We study the online resource allocation problem in which at each round, a budget $B$ must be allocated across $K$ arms under censored feedback. An arm yields a reward if and only if two conditions are satisfied: (i) the arm is activated according to an arm-specific Bernoulli random variable with unknown parameter, and (ii) the allocated budget exceeds a random threshold drawn from a parametric distribution with unknown parameter. Over $T$ rounds, the learner must jointly estimate the unknown parameters and allocate the budget so as to maximize cumulative reward facing the exploration--exploitation trade-off. We prove an information-theoretic regret lower bound $Ω(T^{1/3})$, demonstrating the intrinsic difficulty of the problem. We then propose RA-UCB, an optimistic algorithm that leverages non-trivial parameter estimation and confidence bounds. When the budget $B$ is known at the beginning of each round, RA-UCB achieves a regret of order $\widetilde{\mathcal{O}}(\sqrt{T})$, and even $\mathcal{O}(\mathrm{poly}\text{-}\log T)$ under stronger assumptions. As for unknown, round dependent budget, we introduce MG-UCB, which allows within-round switching and infinitesimal allocations, and matches the regret guarantees of RA-UCB. We then validate our theoretical results through experiments on real-world datasets.

在线学习资源分配强化学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。