带有赌徒反馈的最小化最大化子模优化
本文提出了一种基于随机赌博反馈模型的新型优化算法,采用椭球算法的泛化形式,对凸紧致集上的凸利普希茨(Lipschitz)函数最小化问题进行求解,证明其性能在满足一定条件下与时间步数T为O(d^3/2)同阶,并获得了泛化性能的高阶乘性加速,表现出良好的应用前景和性能优势。
Jul, 2011
本文提出了kl-UCB ++算法,用于在具有指数分布族的随机赌博机模型中实现遗憾最小化,并证明了其同时渐近最优(按Lai和Robbins的下限界定)和极小化最优。这是第一种证明同时具有这两个性质的算法,因此将两种不同的研究方向合并在一起,并提供了简单明了的证明。
Feb, 2017
研究了有限动作集的线性上下文强化学习问题,介绍了一种名为VCL SupLinUCB的算法,并表明其与最佳下界相匹配,相较于之前的算法分析,节省了两个对数因子。
Mar, 2019
本文提出了三种在线算法,分别用于子模最大化问题中的函数渐变计算优化、带赌博的子模最大化问题和响应式带乘积集约束的带乘积子模问题。三个算法在达到 $(1-1/e)$ -regret bound 的前提下,分别取得了复杂度为$O(T^{4/5})$、$O(T^{8/9})$ 以及$O(T^{8/9})$ 的折损。
Oct, 2019
本文研究具有完全机器人反馈和随机奖励的无限制组合多臂武器匪徒问题,提出随机贪心学习算法(RGL),证明其对于时间区间T和武器数n,达到1/2遗憾上限Õ(T^(2/3)),并在实验中展示了其对于非次模和次模设置都优于其他全机器人变体。
Feb, 2023
研究在线赌徒学习中的单调多线性DR-子模函数设计算法BanditMLSM,可以获得(1-1/e)遗憾的O(T ^ {2/3} log T);将子模随机带入分割拟阵约束和赌徒顺序单调最大化,可以在两个问题中获得O(T ^ {2/3} log T)的(1-1 / e)遗憾,这比现有结果更好。给出第一个关于具有分割拟阵约束的子模赌徒的次线性遗憾算法。
May, 2023