May, 2024

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

PDF
TL;DR在线多智能体 NSW（Nash 社会福利）最大化问题中，我们提出了一种完全回答 NSW 作为目标的无悔公平学习是否可能的算法，并且在不同设置下得到了相应的后悔界限。
online multi-agent nsw maximizationfair learningstochastic banditsadversarial rewardsfull-information feedback
发现论文，激发创造
  • 线性赌臂机器人的纳什后悔保证

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

    Oct, 2023

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

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

    Jul, 2024

  • 无悔的 M${}^{atural}$ 凹函数最大化：随机赌博算法和对抗完全信息设置的 NP 困难性

    基于反馈的交互式最大化在线 M${}^{atural}$- 凹函数研究中，我们提出了 $O (T^{-1/2})$-simple regret 和 $O (T^{2/3})$-regret 算法，证明了贪心算法对于 M${}^{atural}$- 凹函数最大化中的局部误差的鲁棒性，并对于多项式时间每回合运行算法无法实现 $O (T^{1-c})$ regret 的可能性给出了证明。

    May, 2024

  • BanditQ -- 在对抗环境中具有保证的每个用户收益的无懊悔学习

    本文提出一种在线学习算法 BanditQ，基于队列理论和在线学习相结合，实现公平在线预测，并在信息完整的情况下，达到目标约束，同时实现 $O (T^{3/4})$ 的损失率。

    Apr, 2023

  • 拍卖中的学习：遗憾很难，嫉妒很容易

    本研究提出一种称为 “无嫉妒学习” 的拍卖学习概念，它是建立在 Walras 均衡基础上的，可有效实现且结果达到近似最优福利，即使投标人有分数次可减（XOS）估值或覆盖估值（无需具备要求），同时扩展到其他在文献中研究过的拍卖格式。

    Nov, 2015

  • 连续博弈中的自适应学习：最优遗憾边界和纳什均衡收敛

    本文提出了一种基于乐观的镜像下降的无悔策略算法，可以在非稳态环境下实现 O (sqrt (T)) 的后悔度，并可在变分稳定游戏中收敛到纳什均衡。

    Apr, 2021

  • 多人零和游戏中相关均衡的几乎最优无悔学习

    提出了新的技术，将 DFG 的技术用于解决内部遗憾和交换遗憾，从而使得多人游戏中的学习动态能够收敛到近似相关均衡，同时分析了 Blum 和 Mansour 算法中的近似最优遗憾保证。

    Nov, 2021

  • 无悔在线强化学习中的对抗损失和转换

    本篇论文提出了一种在线学习算法，能够同时应对恶意对手的损失函数和状态转移，并且随着对手的恶意程度而平稳地增加遗憾，同时采用黑盒约简方法达到无需先验知识的效果。此外，本文还对算法进行了改进，在生成损失的环境易于控制的情况下可以实现较小的遗憾。

    May, 2023

  • 合作非随机多臂老虎机中的个体遗憾

    研究通过交换信息在底层网络上通信的代理，以优化共同的非随机多臂赌博问题中各自的遗憾。我们推导出遗憾最小化算法，其中保证每个代理 v 的期望遗憾都是（1+K/|N (v)|)^T 的平方根量级。

    Jul, 2019

  • 社会福利的自适应最大化

    旨在最大化社会福利，我们研究重复选择政策的问题，由私人效用和公共收入构成的加权和。通过实验证明，我们获得了与误差下界相匹配的上界，表明福利最大化比多臂赌博问题更困难，且我们的算法实现了最佳速率。

    Oct, 2023