在线公平分配中，用带置信上界的方法实现近似最优的收益与公平性平衡。
Improved Regret Bounds for Online Fair Division with Bandit Learning
- 采用双轮线性优化的置信上界算法，应对未知价值分布的物品分配。
- 在高概率下满足期望公平性，且达到约 √T 的遗憾率（优于之前的 T^{2/3}）。
- 适合关注在线资源分配公平性与效率的研究者或系统设计者。
研究有限类型物品、玩家价值来自未知均值分布的在线公平分配问题。物品按随机过程依次到达，每件物品必须分配给单一玩家，目标是最大化期望社会福利，同时保证分配在期望上满足比例公平性。当玩家价值被归一化时，我们证明可高概率地满足比例约束，并实现 Õ(√T) 的遗憾率。为此提出一种使用两轮线性优化的上置信界（UCB）算法，揭示了比例约束在存在大量（可能紧致）约束时仍可适用UCB的关键机制。该结果改进了此前最优遗憾率 Õ(T^{2/3})。
原文摘要 · Abstract (English)
We study online fair division when there are a finite number of item types and the player values for the items are drawn randomly from distributions with unknown means. In this setting, a sequence of indivisible items arrives according to a random online process, and each item must be allocated to a single player. The goal is to maximize expected social welfare while maintaining that the allocation satisfies proportionality in expectation. When player values are normalized, we show that it is possible to with high probability guarantee proportionality constraint satisfaction and achieve $\tilde{O}(\sqrt{T})$ regret. To achieve this result, we present an upper confidence bound (UCB) algorithm that uses two rounds of linear optimization. This algorithm highlights fundamental aspects of proportionality constraints that allow for a UCB algorithm despite the presence of many (potentially tight) constraints. This result improves upon the previous best regret rate of $\tilde{O}(T^{2/3})$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。