通过弱差分隐私在线学习实现纳什激励兼容性在线机制学习
本研究提出的隐私保护算法在解决随机多臂赌博机问题时,相比之前的成果取得了较大的进展.算法可以保证最优遗憾率O(Ɛ−1+logT),通过实验证实了理论界和实践界之间的一致性。
Nov, 2015
我们展示了一种称为"Fast and Furious"的学习方法,使得在二人零和博弈中时间平均遗憾减少且步长不为零成为可能,此学习方法为最小化-最大化优化和多智能体系统中的研究提供了新的标杆,即使是在最简单的情况下,我们的研究证明该方法的遗憾界限为$\Theta(\sqrt{T})$,在学习率固定的情况下也会稳定收敛于确切的纳什均衡价值。
May, 2019
本研究旨在应用赌注机制的类型建立算法,使学习算法对于观察到的事实的最佳专家后悔,并保证每个专家都以其真实信念的方式报告其每个事件的实现,从而实现在线学习环境中的学习。
Feb, 2020
本文提出一种在线学习算法 BanditQ,基于队列理论和在线学习相结合,实现公平在线预测,并在信息完整的情况下,达到目标约束,同时实现$O(T^{3/4})$的损失率。
Apr, 2023
我们提供了一种新颖的从交换后悔最小化到外部后悔最小化的约简方法,该方法改进了Blum-Mansour和Stolz-Lugosi的经典约简,不需要动作空间的有限性。我们的结果表明,只要存在某个假设类的无外部后悔算法,同样必然存在该类别的无交换后悔算法。对于使用专家建议的学习问题,我们的结果表明,在log(N)^{O(1/ε)}轮迭代中并且每次迭代的复杂度为O(N),可以保证交换后悔受到ε的约束,而Blum-Mansour和Stolz-Lugosi的经典约简则需要O(N/ε^2)轮迭代和至少Ω(N^2)的复杂度。我们的结果还带有一个相关的下界,与[BM07]中的下界相反,该下界适用于具有遗忘性和限制的κ1的对手和学习者,以及可以使用专家分布的情况,从而说明轮数必须是Ω(N/ε^2)或以指数的方式与1/ε成反比。我们的约简意味着,如果在某个游戏中可以进行无后悔学习,那么该游戏必须具有近似的相关均衡,具有任意好的近似程度。这加强了无后悔学习所暗示的粗略相互相关均衡的存在。重要的是,它提供了一种存在相关均衡的充分条件,大大扩展了行动集有限的要求,从而回答了[DG22; Ass+23]中未解决的问题。此外,它还回答了关于均衡计算和/或游戏学习的几个未解决问题。
Oct, 2023
通过学习,设计公平分配机制,以比例公平性为基准,解决了一次性分配机制的学习问题,同时提出了可行的方法来度量机制的可利用性,并通过数据控制公平性和可利用性之间的权衡,提出了两种近似比例公平机制,分别是ExPF-Net和ExS-Net,通过大量的数值模拟验证了这些机制的有效性和鲁棒性。
Nov, 2023
我们研究了多臂赌博问题的战略变体,称为战略点击赌博问题。我们设计了一种激励感知的学习算法UCB-S,该算法实现了在不确定性下激励期望的臂行为,并且能够学习未知参数以最小化遗憾度。我们的理论结果得到了通过模拟战略臂行为进行的支持,证实了我们所提出的激励设计的有效性和鲁棒性。
Nov, 2023
在线多智能体NSW(Nash社会福利)最大化问题中,我们提出了一种完全回答NSW作为目标的无悔公平学习是否可能的算法,并且在不同设置下得到了相应的后悔界限。
May, 2024