线性上下文贪婪算法问题的平滑分析

Jan, 2018

线性上下文贪婪算法问题的平滑分析

A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem

Sampath Kannan, Jamie Morgenstern, Aaron Roth, Bo Waggoner, Zhiwei Steven Wu

TL;DR本文研究线性情境赌徒算法问题，重新审视贪心算法的性能，通过平滑分析证明，即使情境可以由对手选择，对对手选择进行小干扰就足以实现 “无悔算法”，这表明在线性设置中，“普遍地”（即在稍微扰动的环境中）探索和开发不必在冲突。

Abstract

bandit learning is characterized by the tension between long-term exploration and short-term exploitation. However, as has recently been n

bandit learning contextual bandit exploration exploitation regret

发现论文，激发创造

线性上下文臂优化中的自适应探索

我们设计了一种渐近上限最优算法，并充分利用线性结构和精确探索，从而减少了在多种合理情境下的失算，数值结果表明，与其他基准算法相比，我们的方法大大减少了失算。

Oct, 2019

上下文臂机问题的大部分无需探索算法

证明了当观察到的上下文具有足够的随机性时，贪心算法可以达到速率最优，并介绍了一种新的算法 Greedy-First，该算法仅使用观察到的上下文和奖励来确定是否按照贪心策略或探索策略，同时证明该算法在没有对上下文分布或手臂数量做任何其他假设的情况下具有速率最优的性质，并大量模拟结果表明，Greedy-First 成功地减少了探索并优于现有的基于 Exploration 的上下文 bandit 算法，如 Thompson sampling 或 upper confidence bound（UCB）。

Apr, 2017

结构化线性情境赌博机：一种锐利且几何平滑的分析

该研究提出了针对带有 Gaussian 噪声下的结构化线性上下文 Bandit 学习算法的简单贪心算法，并对其进行了统一的遗憾分析，其中包括带有任何假定结构的 $ heta^*$，表现出了隐含的探索行为。

Feb, 2020

上下文赌博机的超参数调整

本文探讨了在线学习环境下，通过使用赌博机算法来自动确定探索参数，优化上下文赌博算法探索与利用的平衡问题。

May, 2020

平衡线性情境臂

本篇论文针对强异质性或复杂结果模型容易引起难以估计问题的上下文匹配算法，通过整合因果推断文献中的平衡方法来降低其偏差估计的问题，并对具有平衡的线性上下文匹配算法进行损失分析，从而展示了其在多个监督学习数据集上的实用优势以及在初级训练数据中模拟模型错误和偏见的工作中所展现出的优越性。

Dec, 2018

线性情境赌博机的对抗性攻击

本文研究了恶意代理如何在 linear contextual bandit algorithm 上执行攻击，并提出了一种有效的算法来执行此攻击。