对抗无悔玩家
研究了两个智能体在重复对局中报酬和悔恨之间的权衡,提出了一种广义均衡概念,讨论了不同对手情况下的最优战略和可行方案,探究了利用这种广义均衡学习最优策略的方法。
May, 2023
我们研究了重复的一阶售价拍卖和一般重复贝叶斯博弈的情况,在这种情况下,一个参与者(学习者)采用了一个无悔学习算法,而另一个参与者(优化者)在了解学习者的算法的情况下,策略化地追求自己的效用最大化。 对于一类被称为基于均值的无悔学习算法,我们证明:(i)在标准(即完全信息)的一阶售价拍卖中,优化者不能获得超过 Stackelberg 效用的效用 -- 这是文献中的标准基准,但是(ii)在贝叶斯一阶售价拍卖中,存在优化者可以获得远高于 Stackelberg 效用的实例。 另一方面,Mansour 等人(2022)证明了一类更复杂的算法,称为无多面体交换后悔算法可以将优化者的效用限制在任意重复贝叶斯博弈(包括贝叶斯一阶售价拍卖)的 Stackelberg 效用上,并提出是否有必要使用无多面体交换后悔算法来限制优化者的效用。对于一般的贝叶斯博弈,在一个合理且必要的条件下,我们证明了无多面体交换后悔算法确实是将优化者的效用限制在 Stackelberg 效用上的必要条件,从而回答了他们的开放性问题。对于贝叶斯一阶售价拍卖,我们通过利用贝叶斯一阶售价拍卖的结构给出了一个简单的改进标准算法来最小化多面体交换后悔。
Feb, 2024
探讨了两个学习代理(如推荐系统或聊天机器人)相互交流并独立学习的情况下,每个代理的目标和效用如何受到影响,并提出了一种宽容于小学习误差的放松后的后悔基准,以及相应的学习算法,实现了接近最优水平的后悔率。
Feb, 2024
通过适应性算法的考虑以确保比修改行为所能达到的结果更好,我们可以基于相关学习动态产生新的博弈理论分析,这样做比基于平衡策略算法更加有效,因为前者可以处理非零和多人博弈问题。我们重新审视了博弈理论中的中介均衡和偏差类型,证明了没有可行的概念包含所有其他类型,并引出了一个追溯与规避策略算法的平衡类别的定义。
Dec, 2020
本文提出通过揭示意向方法,解决了在 follower 效用函数未知的 Stackelberg 博弈中求解 leader 最优策略的问题,并在包括利润最大化和非原子性拥塞博弈最优通行费率问题在内的广泛问题上表现良好。
Apr, 2015
本文提出了一种基于乐观的镜像下降的无悔策略算法,可以在非稳态环境下实现 O (sqrt (T)) 的后悔度,并可在变分稳定游戏中收敛到纳什均衡。
Apr, 2021
本文研究了基于分布鲁棒优化的 Stackelberg 游戏模型,特别是在不确定下属效用模型的情况下,寻找最优策略以保护某些资产。我们的研究表明,在广泛的不确定模型下,分布鲁棒 Stackelberg 均衡始终存在。当存在无限个下属效用函数且不确定性由支持有限名义分布周围的 Wasserstein 球表示时,我们提出了一种基于混合整数规划的增量算法来计算最优的分布鲁棒策略。实验结果显示,我们的方法可扩展到中等规模的 Stackelberg 游戏,从而验证了算法的可行性。
Sep, 2022
本文研究多人随机博弈中同时学习的问题,通过生成算法获得相关均衡,包括 extensive-form correlated equilibrium 和普通 coarse correlated equilbrium,并提供了一些能够多项式时间内解决的特殊情况。
Oct, 2022