对抗性线性情境赌博机的一阶和二阶边界

May, 2023

对抗性线性情境赌博机的一阶和二阶边界

First- and Second-Order Bounds for Adversarial Linear Contextual Bandits

Julia Olkhovskaya, Jack Mayo, Tim van Erven, Gergely Neu, Chen-Yu Wei

TL;DR考虑对抗性线性上下文赌博机设置，文中给出了一种新的算法，通过利用与不需要上下文设置的线性赌博机的新联系，利用连续指数权重算法在概率单形上的一个截断版本来获得结果，并证明了其结果优于最坏情况下的后悔，特别的当环境相对温和时，考虑了上下文的密度是对数凹的情况，给出了一种同时优于二阶和一阶损失的方法。

Abstract

We consider the adversarial linear contextual bandit setting, which allows for the loss functions associated with each of $K$ arms to change over time without restriction. Assuming the $d$-dimensional contexts are drawn from a fixed known distribution, the worst-case expected

adversarial linear contextual bandit regret log-concave density second-order bound best policy

发现论文，激发创造

线性上下文强化学习的最佳算法

我们研究了针对 K 臂线性情境赌博机的最佳算法，无需先前对环境有所了解，在敌对和随机的情境下都能够提供接近最优的后悔边界。

Dec, 2023

广义线性情境赌博机的可证明最优算法

本文提出了针对广义线性情境臂的上界置信度算法，实现了与众不同的性能，同时我们还分析了更简单的上界置信度算法，在特定情况下证明了该算法具有最优的后悔。

Feb, 2017

基于 oracle 的对抗性情境赌博算法的改进遗憾界

提出了一种基于 oracle 的算法来应对敌对情境下的赌博问题，该算法在访问离线优化 Oracle 并且享有 $O ((KT)^{\frac {2}{3}}(\log N)^{\frac {1}{3}})$ 的遗憾度的情况下是计算有效的，其中 K 是操作的数量，T 是迭代次数，N 是基线策略的数量。

Jun, 2016

关于局部隐私线性情境赌博机的最佳后悔

通过分析均值绝对偏差误差和分层主成分回归，我们展示了一种能够在局部隐私线性情境播放机中实现 O (√T) 累积遗憾上界的解决方案。

Apr, 2024

线性上下文强化学习最佳方案

该研究探讨了在对抗性破坏下的 K 臂线性上下文赌博问题，并提出了一种在随机和对抗环境下具有理论保证的名为最佳两全（BoBW） RealFTRL 的策略。

Dec, 2023

无限臂线性情境赌博机的紧束悔恨界

本文研究线性上下文赌博机，特别是具有更改的无穷动作集的情况下的情况。我们证明了一种悔恨上界，其与以前的下界相匹配。

May, 2019

针对对抗性线性情境赌博机的高效稳健算法

针对经典 $K$-armed 线性上下文对抗性问题，我们开发了基于 Exp3 算法的计算有效算法，其中包含实时算法和鲁棒算法，它们能够实现良好的失望保证，并且对于线性奖励函数而言具有稳健性。