非凸赌臂优化的最优梯度算法
近年来,与人类不断互动的现实世界安全关键系统中的强盗优化引起了极大关注。本文提出了一个综合性研究,重点研究了安全线性强盗算法的计算方面,通过引入凸规划工具创建了计算效率高的策略。具体而言,我们首先对安全线性强盗问题的最优策略进行了特征化,并提出了一个仅涉及求解凸问题的端到端安全线性强盗算法流程。我们还对我们提出的方法的性能进行了数值评估。
Nov, 2023
本文主要研究基于模型的赌博机和强化学习,针对非线性函数逼近,构建了一个可证明收敛至本地最大值的模型 ——ViOlin 算法,提高了样本效率,并在多个具体场景中给出了全局或本地损失的保证。
Feb, 2021
在这篇论文中,我们提出了一种广义的勘探 - 开发权衡模型,该模型允许在时间序列上对任意凹奖励和凸度约束进行决策,并对时间范围进行规定。我们证明了一种用于 MAB 的 UCB 系列算法自然而简单的扩展,提供了一个具有近乎最优的后悔保证的多项式时间算法,满足 Badanidiyuru 等人给出的 BwK 特殊情况下的边界,这一点非常惊人。此外,我们还通过建立此问题与其他研究领域中好的算法之间的有趣联系,提供了更高效的算法。
Feb, 2014
本文研究了在线凸优化的问题,在该问题中,决策者是风险规避的。我们提供了两个算法来解决这个问题。第一个是降落算法,易于实现。第二个算法结合了椭圆体方法和中心点装置,对于回合数实现了(几乎)最优的后悔界限。据我们所知,这是在在线凸博弈问题中首次尝试解决风险规避问题。
Oct, 2018
提出了一种基于在线到置信区间映射和基于低秩矩阵覆盖的指数加权平均预测器相结合的算法,解决了低秩线性赌博机问题,具体算法延伸自探索子空间再精炼算法,可以使得拥有低秩矩阵 Theta 的线性赌博机达到更好的期望累积损失表现并得到了实验的验证。
Jun, 2020
通过将问题转化为 tree-armed bandits 并提供新结果,我们描述了一种适用于无穷多个多项式极大值的任何连续奖励函数的噪声全局优化和连续臂赌博算法,并在不需要先前信息的情况下实现了臂赌博的平方根遗憾和优化的反平方根误差,并证明了能够自适应地组合多个树以最小化遗憾,并且在缩放维度方面提供了接近匹配的较低界。
Feb, 2013
本文提出了一种适用于多臂赌博机问题的解决方案,只需要以线性时间复杂度存储未知参数,可以处理一般的掌握参数相关性的问题,并用于对网络中的最大权匹配、最短路径及最小生成树计算问题的解决。
Nov, 2010
本文针对带有随机反馈的在线凸优化问题(称为 bandit convex optimization),通过将椭球法应用于在线学习,给出了第一个 $\tilde {O}(\sqrt {T})$-regret 算法,并引入了离散凸几何中的新工具。
Mar, 2016
带限界凸优化是研究零阶凸优化的基本框架。这篇论文涵盖了解决此问题的许多工具,包括切平面法、内点法、连续指数权重、梯度下降和在线牛顿步。解释了许多假设和设置之间的细微差别。虽然没有太多真正新颖的东西,但一些现有工具以新颖的方式应用,得到了新的算法。一些边界有些改进。
Feb, 2024