Nov, 2023

从强盗反馈中学习公平分配

HTML
PDF
TL;DR通过使用双平均法，本研究解决了在不确定条件下学习在线公平分配的问题，其中中央规划者在不准确地了解代理方值或效用的情况下顺序分配物品。本研究提出了利用双平均法的包装算法，通过信息反馈逐步学习到到达物品的类型分布和代理方的值，从而实现了在线算法在具有加性效用的线性Fisher市场中渐进地达到最优的Nash社会福利。我们在Nash社会福利方面建立了遗憾界限，并通过合成和实证数据集实证验证了我们提出的算法的优越性能。
发现论文，激发创造
  • 实现随机多臂赌博问题的公正性

    研究公平多臂老虎机问题中学习与公平之间的相互作用，通过特定向量表示公平性约束，定义一个公平感知的后悔，通过两个参数刻画一个 Fair-SMAB 算法类，并提供一个公平保证，无论学习算法的选择是什么，都可以持续地适用。

    May, 2019

  • 多智体多臂赌博机公平算法

    本文在经典赌博机问题的基础上提出了一个多智能体变种，旨在学会对赌臂进行公平分配并利用纳什社会福利来衡量它的公平性，设计了三个多智能体变种的算法并证明其实现了次线性的损失纳什社会福利， 因此可以对合理的互惠性展现出更大的感受。

    Jul, 2020

  • 去中心化匹配市场中的强盗学习

    该研究针对两侧市场匹配问题，通过引入一种新算法，提高了在分散式多人选手竞争、无优先认知偏好和与偏好相关猜测等场景下博弈的结果鲁棒性。

    Dec, 2020

  • 具有不完全信息的广义博弈的近最优学习

    本文提出两种新算法：平衡在线镜像下降和平衡对策后悔最小化，通过整合平衡探索策略到它们的经典对应物算法，解决学习不完美信息的广义零和游戏的近似Nash均衡问题。同时，将结果推广到学习多人游戏的粗略相关均衡。

    Feb, 2022

  • 公平最优多智能体赌博机

    研究多智能体多臂赌博学习问题，以无通信和有限奖励为前提，提出了一种分布式拍卖算法并进行样本最优匹配学习和新的拍卖决策策略，通过新颖的基于次序统计量的后悔分析带来了全新的性能，实验模拟表明性能依赖于对数时间。

    Jun, 2023

  • 线性赌臂机器人的纳什后悔保证

    在随机线性赌博机的框架中，我们获得了强化的后悔概念的紧密上界。这个强化的后悔概念被称为Nash后悔，它被定义为线性赌博机算法累积的预期奖励的几何平均值与（事先未知的）最优解之间的差异。我们开发了一种算法，在有限的臂集和无限的臂集两种情况下，实现了Nash后悔的上界。

    Oct, 2023

  • 公平多智体社会福利优化的无懊悔学习

    在线多智能体NSW（Nash社会福利）最大化问题中，我们提出了一种完全回答NSW作为目标的无悔公平学习是否可能的算法，并且在不同设置下得到了相应的后悔界限。

    May, 2024

  • 公平稳定的在线分配的主动学习

    我们探索了一种用于动态公平资源分配问题的主动学习方法，该方法假设在在线资源分配过程的每个时期，仅从选择的代理人子集中获取反馈。尽管存在这种限制，我们提出的算法在包括资源分配问题中常用的公平度量和匹配机制中的稳定性考虑等各种度量中，提供了与时间周期数次线性相关的后悔界限。我们算法的关键洞察在于通过利用对决性的上限和下限置信区间来自适应地识别最具信息量的反馈。通过这种策略，我们证明高效的决策不需要大量的反馈，并为各种问题类别产生高效的结果。

    Jun, 2024

  • 强盗之中的荣誉：面向在线公平分配的无遗憾学习

    通过探索-执行算法设计实现在线公平分配研究, 解决基于多臂赌博携带公平约束的未知价值非可分配商品的社会福利最大化问题.

    Jul, 2024

  • 基于情境乐队的在线公平分配

    本研究针对在线公平分配中的多个代理人问题，旨在解决现有算法在用户数量庞大且每个用户仅使用少量服务时所面临的效用估计困难。通过引入情境乐队模型，本文提出了保证亚线性遗憾的在线公平分配算法，实验结果验证了所提算法在不同性能方面的优势。

    Aug, 2024