针对零阶对抗性 Bandit 凸优化的改进遗憾

May, 2020

针对零阶对抗性 Bandit 凸优化的改进遗憾

Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation

Tor Lattimore

TL;DR以信息论为基础，改进探索性分布以在零阶对抗性 bandit 凸优化的 minimax regret 的信息理论上界上证明其为 O (d^{2.5} 根号 n 对数 (n))，并提高 Bubeck 等人 (2017) 的 O (d^{9.5} 根号 n 对数 (n)^{7.5} 上界。

Abstract

We prove that the information-theoretic upper bound on the minimax regret for zeroth-order adversarial bandit convex optimisation is at most $O(d^{2.5} \sqrt{n} \log(n))$, where $d$ is the dimension and $n$ is the number of interactions. This improves on $O(d^{9.5} \sqrt{n} \log(n)^{7.5}$ by Bubeck et al. (2017). The proof is based on identifying an improved

information-theoretic bound adversarial bandit optimization convex functions exploratory distribution regret minimization

发现论文，激发创造

在线牛顿方法在博弈凸优化问题中的应用

零阶强化学习的计算方法在对抗性和随机性设置中的性能界限及其与维度的关系

Jun, 2024

在线线性优化带赌博式反馈的极小极大政策

该研究提出了在线线性优化问题的带有 bandit 反馈的算法，并使用 Mirror Descent 算法在特定案例中获得具有最小二乘优化后退限制的计算高效性的策略，证明了计算上以及最小二乘上的结果优化，为输出结果减少了冗余的符号。

Feb, 2012

赌博机凸优化问题的最优算法

本文针对带有随机反馈的在线凸优化问题（称为 bandit convex optimization），通过将椭球法应用于在线学习，给出了第一个 $\tilde {O}(\sqrt {T})$-regret 算法，并引入了离散凸几何中的新工具。

Mar, 2016

线性参数赌博机的近似极小极大后悔

研究了有限动作集的线性上下文强化学习问题，介绍了一种名为 VCL SupLinUCB 的算法，并表明其与最佳下界相匹配，相较于之前的算法分析，节省了两个对数因子。

Mar, 2019

高维稀疏线性赌博机

研究高维稀疏特征的随机线性臂模型中，在数据匮乏的情况下，特征向量遵守固定的探测分布，通过探索然后提交算法，得到了 $Ω(n^{2/3})$ 的无维度极小遗憾下界和 $Θ(n^{2/3})$ 的上界。

Nov, 2020

带有强盗反馈的随机凸优化

本文提出了一种基于随机赌博反馈模型的新型优化算法，采用椭球算法的泛化形式，对凸紧致集上的凸利普希茨（Lipschitz）函数最小化问题进行求解，证明其性能在满足一定条件下与时间步数 T 为 O（d^3/2）同阶，并获得了泛化性能的高阶乘性加速，表现出良好的应用前景和性能优势。

Jul, 2011

对抗性赌博机的改进下界

该研究提供了敌对强盗算法必须遭受的遗憾的新的下界，并证明了对于最佳臂的总损失或损失的二次变化的上界是接近紧的。此外，研究还证明了两个不可能的结果，即单臂最优和遗憾不能随损失范围的提高而扩展。相比之下，在完全信息设置中这两个结果是可能的。

May, 2016

基于核的赌博式凸优化方法

提出一种新的算法解决在无导数情况下的 $adversarial convex bandit$ 问题，其包含了核方法、伯努利卷积的一般化和新的退火时间表。这个算法在要求多次迭代的场景中可以取得佳效果。

Jul, 2016

高斯过程赌博机的最优顺序简单后悔

研究了高斯过程二元组和连续性优化问题之间的联系，建立了稳健分布，使用分步方式获得最终收敛结果并得到了一系列引理。

Aug, 2021

通过极小极大对偶视角看最优遗憾的随机观点

通过 von Neumann 最小极大定理，我们研究了在线凸优化游戏的最优策略的遗憾。我们证明了，在这种对抗性环境中，最优策略的遗憾与随机进程设置中经验最小化算法的行为密切相关：它等于最小期望损失的总和与最小经验损失之间的差的最大值。我们展示了最优策略的遗憾具有自然的几何解释，因为它可以被视为一个上凸函数的 Jensen 不等式中的差距。利用此表达式，我们对各种在线学习问题的最优策略给出了上下界限制。我们的方法提供了无需构建学习算法的上界，而提供了对抗者的明确最优策略的下界。

Mar, 2009