Jun, 2022

基于结构匹配市场的去中心化、无需通信和协调的学习

PDF
TL;DR在双边撮合市场中，我们研究了竞争环境下在线学习的问题，如一方的代理人必须通过重复互动了解对另一方的企业的偏好，并与其他代理人竞争成功匹配。我们提出了一类分散、不需要协调的算法，代理人可以使用该算法在结构化匹配市场中达到稳定匹配，其决策仅基于代理人自己的游戏历史，不需要预先了解企业的偏好。研究表明，在代理人和企业的底层偏好具有现实结构假设的情况下，所提出的算法在时间范围内具有最多对数增加的后悔成本。在匹配市场的情况下，我们的结果表明，竞争不会极大地影响分散、不需要通信和协调的在线学习算法的性能。
competitive settingsonline learningtwo-sided matching marketsdecentralized algorithmsregret
发现论文，激发创造
  • 去中心化匹配市场中的强盗学习

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

    Dec, 2020

  • 匹配市场中的竞争赌徒

    本研究提出了一种统计学习模型，用于解决双边市场中的稳定匹配问题，其中一方需从随机奖励中学习另一方的偏好，该模型扩展了标准的多臂赌博机框架，并研究了集中式和分散式方法，发现与单人多臂赌博机设置相比，具有令人惊讶的探索 - 利用权衡。

    Jun, 2019

  • 无遗憾学习匹配：基于 Markov 匹配市场的强化学习

    研究马尔可夫匹配市场，提出强化学习框架，结合最大权匹配算法解决序列探索、匹配稳定性和函数逼近等问题，并证明算法可达到次线性的遗憾率。

    Mar, 2022

  • 分散学习对斯塔克尔贝格博弈中玩家效用的影响

    探讨了两个学习代理（如推荐系统或聊天机器人）相互交流并独立学习的情况下，每个代理的目标和效用如何受到影响，并提出了一种宽容于小学习误差的放松后的后悔基准，以及相应的学习算法，实现了接近最优水平的后悔率。

    Feb, 2024

  • 学习如何在小型市场中最大化贸易利益

    设计一个双边市场（双向拍卖）以在给定约束条件下（优势策略）实现最大化交易利益（社会福利），并在未知分布中使用多项式数量的样本进行研究。我们的首要结果是，在即使只有一个卖方和两个买方之间的相关价值分布的情况下，与一个卖方和一个买方（双边交易）的情况不同，这是不可能的。我们的第二个结果是，在独立分布的情况下，对于一个卖方和两个买方，我们提出了一种基于一种新算法的高效学习算法，用于计算有限支持和明确给定的独立分布的最优机制。这两个结果都严重依赖于（优势策略）激励兼容机制的特征，这些机制在经济上是强平衡的。

    Jan, 2024

  • 匹配市场中玩家最优稳定遗憾的赌博学习

    我们提供了一种名为 explore-then-Gale-Shapley（ETGS）的新算法，并展示了每个参与者的最佳稳定后悔可以由 O（KlogT/Δ^2）上界来限制，其中 K 是参与者的数量，T 是时间，Δ 是参与者在前 N+1 个排名的选择中的最小差距。

    Jul, 2023

  • 广义和谐史塔克伯格博弈中的去中心化在线学习

    我们研究了分布式和策略性在线学习问题，通过对不完全信息和附加信息两种不同情境进行研究，发现追随者在有限信息情境中按照局部最优策略响应领导者的行动，然而在附加信息情境中，追随者可以通过策略性行动操控领导者的奖励信号，以使得领导者的策略收敛到对自己更有利的均衡状态。基于这些洞察，我们针对这两种情境研究了分布式在线学习，主要贡献是提出了最后迭代收敛和样本复杂度方面的结果。尤其值得注意的是，我们设计了一种新的操控策略，用于处理附加信息情境，并证明它相对于最优应对策略具有内在优势。我们的理论结果也得到了实证结果的支持。

    May, 2024

  • 经纪人的在线学习理论

    在线学习视角下研究交易者间的经纪服务，在不同情况下，通过算法实现不同的后悔率和界定密度。

    Oct, 2023

  • 匹配市场中去中心化赌机的超过 log^2 (T) 的遗憾

    该研究设计了一种分散的算法模型，用于在双方匹配市场中实现遗憾最小化和一面策略反馈。

    Mar, 2021

  • 多任务在线学习：聆听邻域嗡嗡声

    我们在一个能够通过网络与邻居交换信息的设定中研究多任务在线学习。我们介绍了一种分散算法 $ exttt {MT-CO}_2 exttt {OL}$，其遗憾度取决于任务相似性和网络结构之间的相互作用。我们的分析表明，$ exttt {MT-CO}_2 exttt {OL}$ 的遗憾度（在常数范围内）永远不会比没有信息共享的情况更糟。另一方面，在邻近代理在相似任务上操作时，我们的边界显著改进。此外，我们证明了当损失是线性的时候，我们的算法可以以微不足道的遗憾影响实现差分隐私。最后，我们提供对我们理论的实验支持。

    Oct, 2023