自适应树形赌博机
提出了一种新颖的算法,采用乐观性和适应性技术,结合在线镜像下降框架和特殊的对数障碍正则化器来解决对抗性多臂赌博机问题和组合半赌博问题,并在提高先前工作的同时,取得了多种新的数据依赖性遗憾界。
Jan, 2018
定义了一种新的算法家族,用于对抗性多臂赌博问题,并提供基于凸平滑的简单分析技术。通过使用 Tsallis 熵进行正则化,证明了它的最小极大后悔度为 Θ(√TN);同时,对于具有有界危害率的微扰分布,广泛类的扰动方法可获得近乎最优的后悔率,低至 O (√TN log N),例如 Gumbel、Weibull、Frechet、Pareto 和 Gamma 分布都满足此特性。
Dec, 2015
本文提出了一种自适应算法以应对目标函数的未知平滑度,展示并计算适应于 H {"o} lder 正则性的多项式成本以进行后悔最小化,提供了有限时间分析和关于渐近最优性的彻底讨论。
May, 2019
在线优化中,给出了强适应遗憾的准确查询和遗憾最优的贪心算法,同时给出了多臂赌博机和赌博凸优化的最优算法,并通过实证研究表明了在不稳定环境和下游任务中的卓越表现。
Jan, 2024
本文提出了一种适用于多臂赌博机问题的解决方案,只需要以线性时间复杂度存储未知参数,可以处理一般的掌握参数相关性的问题,并用于对网络中的最大权匹配、最短路径及最小生成树计算问题的解决。
Nov, 2010
本篇论文旨在应对多臂赌博机问题中存在多个最优 / 近似最优机械臂的后悔最小化问题,通过提出自适应算法来自动适应问题的难度,并在理论和实验方面展现了该算法的优越性。
Jun, 2020
提出了用高斯过程进行连续赌博机问题的最优解优化算法,适用于在固定预算下推荐最佳赌博机并获取平均回报。在提供集合平均值等聚合反馈而精确奖励成本较高或不可能时使用,通过高斯过程约束奖励函数集合,并在节点之间自适应构建树状结构。
Dec, 2021
本文提出了一种名为 HOO 的基于乐观优化的臂选择算法,可以对一类广义随机 bandit 问题给出更好的遗憾界,在一定条件下,在欧几里得空间内的单位超立方体上,通过 HOO 算法的表现,该算法的增长速率与空间维度无关。
Jan, 2010
该研究针对随机、组合式多臂老虎机问题,提出了一种将离线算法转化为基于有限老虎机反馈的子线性 α 遗憾策略的框架,并将其应用于离散优化问题中的基数问题和背包约束问题中获得了良好的表现。
Jan, 2023
本文针对带有随机反馈的在线凸优化问题(称为 bandit convex optimization),通过将椭球法应用于在线学习,给出了第一个 $\tilde {O}(\sqrt {T})$-regret 算法,并引入了离散凸几何中的新工具。
Mar, 2016