带有赌博反馈的对抗网络优化:在非平稳多跳网络中最大化效用
本文介绍了一种新颖的决策模型,以多臂老虎机框架为基础分析社交网络中的学习和决策过程。通过观察邻居的行动和得到的回报,个体可以最小化自己的后悔,我们提供了这种情况下的算法,无论是确定性还是对抗性的多臂老虎机模型,这些算法都是最优的(除去对数因子),并且可以用于社交网络中的自私智能体的近似纳什均衡。
Apr, 2017
设计考虑了存在网络结构情况下对多臂赌博问题的解决方案,提出两个基于网络结构的策略,并在真实社交网络和路由网络的数据上测试,证明相比于现有策略获得了更多的好处。
Apr, 2017
研究了拥有部分信息反馈的对抗(非随机)在线学习问题,在黑盒模型下能够获得如上小损失的概率,而其独特的设计使它在更多应用如半强盗问题和上下文强盗问题中得到有效的应用,并且能够提供一些之前无法获得的最优保证。
Nov, 2017
提出了一种新颖的算法,采用乐观性和适应性技术,结合在线镜像下降框架和特殊的对数障碍正则化器来解决对抗性多臂赌博机问题和组合半赌博问题,并在提高先前工作的同时,取得了多种新的数据依赖性遗憾界。
Jan, 2018
发展了一种新的方法,使用标准无偏估计量,并依赖于简单的递增的学习速率表和对数单调自协调障碍以及加强的弗里德曼不等式,以获取高概率遗憾边界。
Jun, 2020
本文考虑在延迟反馈下的敌对多臂老虎机问题,并分析了一些通过仅使用决策时可用的信息 (关于损失和延迟) 来调整步长的 Exp3 算法变体,从而获得适应观察到的 (而不是最坏情况下的) 延迟和 / 或损失序列的遗憾保证。最后,我们介绍了 AdaGrad 风格的版本的算法,该算法通过观察到的 (延迟的) 损失进行适应,而不仅仅是适应于累积延迟(该算法要求先验上限)。
Oct, 2020
研究用Online Mirror Descent 框架的各种新技术,包括改进的多尺度专家算法、从一般随机最短路径到特殊无环情况的降低、倾斜的占用度量空间以及添加到成本估计器的新校正项等,以解决带对手成本的随机最短路径问题并同时减小学习者方差和最优策略的偏差。
Dec, 2020
本文研究了$K$-武斗器下在非固态或时变偏好情况下动态遗憾最小化问题,设计了能够有效解决此问题的算法,证明了算法的最优性,并进行了大量模拟和与其他算法对比的实验。
Nov, 2021
研究在流言传播模型中的分布式多臂赌博设置在n个。内存受限节点的人口中:在每个回合中,每个节点本地采取m个手臂之一,观察从手臂中获得的回报(敌意选择)分布,然后与随机抽样的邻居进行通信,交换信息以确定其在下一轮中的策略。我们引入和分析了这个任务的几族动力学,这些动力学是分散的;每个节点的决策完全是本地的,并且仅取决于最近获得的奖励及其抽样邻居的奖励。我们展示了这些分散动态的全局演化与某种“零和”乘性权重更新算法之间的联系,并且我们开发了一个通用框架来分析这些自然协议的种群水平遗憾。利用这个框架,在广泛的参数范围下 (即人口规模和臂数),我们推导出静态奖励设置 (每个臂的分布均值随时间固定)和敌意奖励设置(均值随时间可变)的次线性遗憾界。此外,我们还表明,当奖励分布是由随机梯度量规产生时,这些协议可以近似地优化面对单纯形的凸函数。
Jun, 2023
对于排队系统中的学习问题,我们提出了一种新的度量标准CLQ(Cost of Learning in Queueing),该度量标准量化了由于参数不确定性引起的时间平均队列长度的最大增加;我们针对单队列多服务器系统对CLQ进行了刻画,并将这些结果推广到多队列多服务器系统和排队网络中;在建立结果的同时,我们提出了一个统一的CLQ分析框架,该框架将Lyapunov和bandit分析相融合,具有相对独立的研究价值。
Aug, 2023