让每个用户都获得公平回报，设计了均衡分配的强化学习算法。
Stochastic Bandits for Egalitarian Assignment
- 基于UCB思想设计均衡分配策略EgalUCB，确保用户间收益公平。
- 理论证明累积后悔上界，实现最小收益最大化。
- 适合关注公平性资源分配的研究者与工程师。
我们研究了随机多臂老虎机中的平等分配问题EgalMAB。在EgalMAB中，一个代理需将一组用户分配给多个臂，每步必须为每位用户分配唯一一个臂，且各用户奖励来自对应臂的未知分布。目标是最大化所有用户在固定时间窗内的最小期望累计奖励。该问题适用于公平的职位与资源分配等场景。我们设计并分析了一种基于UCB的策略EgalUCB，建立了累积后悔的上界；同时给出了几乎匹配的、不依赖策略的不可能性结果。
原文摘要 · Abstract (English)
We study EgalMAB, an egalitarian assignment problem in the context of stochastic multi-armed bandits. In EgalMAB, an agent is tasked with assigning a set of users to arms. At each time step, the agent must assign exactly one arm to each user such that no two users are assigned to the same arm. Subsequently, each user obtains a reward drawn from the unknown reward distribution associated with its assigned arm. The agent's objective is to maximize the minimum expected cumulative reward among all users over a fixed horizon. This problem has applications in areas such as fairness in job and resource allocations, among others. We design and analyze a UCB-based policy EgalUCB and establish upper bounds on the cumulative regret. In complement, we establish an almost-matching policy-independent impossibility result.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。