强盗之中的荣誉:面向在线公平分配的无遗憾学习
该研究考虑了单人和多人多臂老虎机模型的学习问题,提出了两种可分散策略,即E³ (立方)和E³-TS,它们显示出预期遗憾增长的上限为O(log^(1+ε)T),并解决了分散的在线学习所产生的附加成本问题。
May, 2015
本研究介绍了多臂赌博问题中的公平性概念以及提出了基于“chained”置信区间的多臂赌博问题的可证公平算法,并证明了任何公平算法必须具有该算法的时间复杂度,同时也证明了公平和非公平学习之间有强烈的界限。在一般情境中,本研究证明了公平性与KWIK学习模型的紧密联系,并提出了一种多项式时间复杂度的可证公平算法来解决线性上下文赌博问题。
May, 2016
研究公平多臂老虎机问题中学习与公平之间的相互作用,通过特定向量表示公平性约束,定义一个公平感知的后悔,通过两个参数刻画一个 Fair-SMAB 算法类,并提供一个公平保证,无论学习算法的选择是什么,都可以持续地适用。
May, 2019
本文在经典赌博机问题的基础上提出了一个多智能体变种,旨在学会对赌臂进行公平分配并利用纳什社会福利来衡量它的公平性,设计了三个多智能体变种的算法并证明其实现了次线性的损失纳什社会福利, 因此可以对合理的互惠性展现出更大的感受。
Jul, 2020
为了解决个性化推荐中传统策略可能导致的不公平现象,提出了一种新的基于功绩公平的策略,并给出了两种算法,分别适用于多臂老虎机和线性老虎机,证明了算法的功绩公平和奖励公平具有亚线性,同时提供了实证分析,证明了该算法能够有效地公平分配推荐曝光。
Mar, 2021
研究了在在线学习中探索成本如何跨越多个组之间分摊,并提出了一种“分组”赌博模型,利用公理谈判和纳什谈判解来形式化地划分探索成本,并通过创造性的方法推导了平衡公平和探索成本的策略。以华法林剂量的情境赌博为例说明了此算法框架的相对优点。
Jun, 2021
通过使用双平均法,本研究解决了在不确定条件下学习在线公平分配的问题,其中中央规划者在不准确地了解代理方值或效用的情况下顺序分配物品。本研究提出了利用双平均法的包装算法,通过信息反馈逐步学习到到达物品的类型分布和代理方的值,从而实现了在线算法在具有加性效用的线性Fisher市场中渐进地达到最优的Nash社会福利。我们在Nash社会福利方面建立了遗憾界限,并通过合成和实证数据集实证验证了我们提出的算法的优越性能。
Nov, 2023
深入研究了公平性,提出了一种基于两个层次的公平性方法,保证每个组的最小曝光,并确保组内每个单元根据其优越性被拉动;通过提出的算法 BF-UCB,实现了对遗憾的上界为 O(√T) 的平衡,同时提供更好的组和个体曝光保证,并且不会显著降低奖励。
Feb, 2024
本研究针对在线公平分配中的多个代理人问题,旨在解决现有算法在用户数量庞大且每个用户仅使用少量服务时所面临的效用估计困难。通过引入情境乐队模型,本文提出了保证亚线性遗憾的在线公平分配算法,实验结果验证了所提算法在不同性能方面的优势。
Aug, 2024