我们研究对线性随机匪徒的对抗攻击：通过操纵奖励，对手旨在控制匪徒的行为。也许令人惊讶的是，我们首先表明某些攻击目标永远无法实现。这与无上下文的随机匪徒形成了鲜明的对比，并且本质上是由于线性随机陆上的臂之间的相关性。在这一发现的激励下，本文研究了$ k $武装的线性匪徒环境的攻击性。我们首先根据武器上下文向量的几何形状提供了攻击性的完全必要性和充分性表征。然后，我们提出了针对Linucb和鲁棒相消除的两阶段攻击方法。该方法首先断言给定环境是否可攻击；而且，如果是的话，它会付出巨大的奖励，以强迫算法仅使用sublinear成本来拉动目标臂线性时间。数值实验进一步验证了拟议攻击方法的有效性和成本效益。

上下文强盗算法在各种情况下有许多申请人。为了开发值得信赖的情境强盗系统，了解各种对抗性攻击对上下文强盗算法的影响至关重要。在本文中，我们提出了一类新的攻击：动作中毒攻击，其中一个对手可以改变代理选择的动作信号。我们在白盒和黑匣子设置中设计了针对线性上下文强盗算法的动作中毒攻击方案。我们进一步分析了拟议的攻击策略的成本，非常流行和广泛使用的强盗算法：Linucb。我们展示，在白盒和黑匣子设置中，所提出的攻击方案可以强制Linucb代理通过仅度过对数成本而频繁地提取目标手臂。

我们考虑了一个随机的多武器强盗问题，其中奖励会受到对抗性腐败的影响。我们提出了一种新颖的攻击策略，该策略可以操纵UCB原理，以拉动一些非最佳目标臂$ t -o（t）$ times，累积成本将其缩放为$ \ sqrt {\ log t} $，其中$ t $是回合的数量。我们还证明了累积攻击成本的第一个下限。我们的下限将我们的上限匹配到$ \ log \ log t $因子，这表明我们的攻击非常最佳。

我们在存在对抗性腐败的情况下研究线性上下文的强盗问题，在场，每回合的奖励都被对手损坏，腐败级别（即，地平线上的腐败总数）为$ c \ geq 0 $。在这种情况下，最著名的算法受到限制，因为它们要么在计算效率低下，要么需要对腐败做出强烈的假设，或者他们的遗憾至少比没有腐败的遗憾差的$ C $倍。在本文中，为了克服这些局限性，我们提出了一种基于不确定性的乐观原则的新算法。我们算法的核心是加权山脊回归，每个选择动作的重量都取决于其置信度，直到一定的阈值。 We show that for both known $C$ and unknown $C$ cases, our algorithm with proper choice of hyperparameter achieves a regret that nearly matches the lower bounds.因此，我们的算法几乎是两种情况的对数因素的最佳选择。值得注意的是，我们的算法同时对腐败和未腐败的案件（$ c = 0 $）实现了近乎最理想的遗憾。

土匪算法已成为交互式建议的参考解决方案。但是，由于这种算法直接与用户进行改进的建议，因此对其实际使用提出了严重的隐私问题。在这项工作中，我们通过基于树的机制提出了一种差异性的线性上下文匪徒算法，以将拉普拉斯或高斯噪声添加到模型参数中。我们的关键见解是，随着模型在在线更新过程中收敛时，其参数的全局灵敏度随着时间的推移而缩小（因此命名为动态全局灵敏度）。与现有解决方案相比，我们动态的全球敏感性分析使我们能够减少噪声以获得$（\ epsilon，\ delta）$ - 差异隐私，并具有$ \ tilde o（\ log {t} \ sqrt中的噪声注入引起的额外遗憾） {t}/\ epsilon）$。我们通过动态全局灵敏度和我们提出的算法的相应上后悔界限提供了严格的理论分析。合成和现实世界数据集的实验结果证实了该算法对现有解决方案的优势。

In this paper, we address the stochastic contextual linear bandit problem, where a decision maker is provided a context (a random set of actions drawn from a distribution). The expected reward of each action is specified by the inner product of the action and an unknown parameter. The goal is to design an algorithm that learns to play as close as possible to the unknown optimal policy after a number of action plays. This problem is considered more challenging than the linear bandit problem, which can be viewed as a contextual bandit problem with a \emph{fixed} context. Surprisingly, in this paper, we show that the stochastic contextual problem can be solved as if it is a linear bandit problem. In particular, we establish a novel reduction framework that converts every stochastic contextual linear bandit instance to a linear bandit instance, when the context distribution is known. When the context distribution is unknown, we establish an algorithm that reduces the stochastic contextual instance to a sequence of linear bandit instances with small misspecifications and achieves nearly the same worst-case regret bound as the algorithm that solves the misspecified linear bandit instances. As a consequence, our results imply a $O(d\sqrt{T\log T})$ high-probability regret bound for contextual linear bandits, making progress in resolving an open problem in (Li et al., 2019), (Li et al., 2021). Our reduction framework opens up a new way to approach stochastic contextual linear bandit problems, and enables improved regret bounds in a number of instances including the batch setting, contextual bandits with misspecifications, contextual bandits with sparse unknown parameters, and contextual bandits with adversarial corruption.

我们考虑随机环境中在线线性回归的问题。我们派生了在线岭回归和前向算法的高概率遗憾。这使我们能够更准确地比较在线回归算法并消除有界观测和预测的假设。我们的研究由于其增强的界限和鲁棒性对正则化参数而代替脊，所以提出了前向算法的倡导者。此外，我们解释了如何将其集成在涉及线性函数近似的算法中以消除界限假设，而不会恶化理论界限。我们在线性强盗设置展示了这种修改，其中它产生了改进的遗憾范围。最后，我们提供数字实验来说明我们的结果并赞同我们的直觉。

我们研究Stackelberg游戏，其中一位校长反复与长寿，非洋流代理商进行互动，而不知道代理商的回报功能。尽管当代理商是近视，非侧心代理会带来额外的并发症时，在Stackelberg游戏中的学习是充分理解的。尤其是，非洋流代理可以从战略上选择当前劣等的行动，以误导校长的学习算法并在未来获得更好的结果。我们提供了一个通用框架，该框架可在存在近视剂的情况下降低非洋白酶的学习来优化强大的匪徒。通过设计和分析微型反应性匪徒算法，我们的还原从校长学习算法的统计效率中进行了差异，以与其在诱导接近最佳的响应中的有效性。我们将此框架应用于Stackelberg Security Games（SSG），需求曲线，战略分类和一般有限的Stackelberg游戏的价格。在每种情况下，我们都表征了近最佳响应中存在的错误的类型和影响，并为此类拼写错误开发了一种鲁棒性的学习算法。在此过程中，我们通过最先进的$ O（n^3）$从SSGS中提高了SSG中的学习复杂性，从通过发现此类游戏的基本结构属性。该结果除了对非洋流药物学习之外，还具有独立的兴趣。

带背包（BWK）的匪徒是供应/预算约束下的多武装匪徒的一般模型。虽然BWK的最坏情况遗憾的遗憾是良好的理解，但我们提出了三种结果，超出了最坏情况的观点。首先，我们提供上下界限，其数量为对数，实例相关的后悔率的完整表征。其次，我们考虑BWK中的“简单遗憾”，在给定回合追踪算法的性能，并证明它在除了几轮之外的一切。第三，我们提供从BWK到匪徒的一般“减少”，这利用了一些已知的有用结构，并将这种减少应用于组合半刺点，线性上下文匪徒和多项式登录匪徒。我们的成果从\ CiteT {AgraWaldevanur-EC14}的BWK算法构建，提供了新的分析。

我们介绍了一个多臂强盗模型，其中奖励是多个随机变量的总和，每个动作只会改变其中的分布。每次动作之后，代理都会观察所有变量的实现。该模型是由营销活动和推荐系统激励的，在该系统中，变量代表单个客户的结果，例如点击。我们提出了UCB风格的算法，以估计基线上的动作的提升。我们研究了问题的多种变体，包括何时未知基线和受影响的变量，并证明所有这些变量均具有sublrinear后悔界限。我们还提供了较低的界限，以证明我们的建模假设的必要性是合理的。关于合成和现实世界数据集的实验显示了估计不使用这种结构的策略的振奋方法的好处。

We study bandit model selection in stochastic environments. Our approach relies on a meta-algorithm that selects between candidate base algorithms. We develop a meta-algorithm-base algorithm abstraction that can work with general classes of base algorithms and different type of adversarial meta-algorithms. Our methods rely on a novel and generic smoothing transformation for bandit algorithms that permits us to obtain optimal $O(\sqrt{T})$ model selection guarantees for stochastic contextual bandit problems as long as the optimal base algorithm satisfies a high probability regret guarantee. We show through a lower bound that even when one of the base algorithms has $O(\log T)$ regret, in general it is impossible to get better than $\Omega(\sqrt{T})$ regret in model selection, even asymptotically. Using our techniques, we address model selection in a variety of problems such as misspecified linear contextual bandits, linear bandit with unknown dimension and reinforcement learning with unknown feature maps. Our algorithm requires the knowledge of the optimal base regret to adjust the meta-algorithm learning rate. We show that without such prior knowledge any meta-algorithm can suffer a regret larger than the optimal base regret.

我们为线性上下文匪徒提出了一种新颖的算法（\ sqrt {dt \ log t}）$遗憾，其中$ d $是上下文的尺寸，$ t $是时间范围。我们提出的算法配备了一种新型估计量，其中探索通过显式随机化嵌入。根据随机化的不同，我们提出的估计器从所有武器的上下文或选定的上下文中都取得了贡献。我们为我们的估计器建立了一个自称的绑定，这使累积遗憾的新颖分解为依赖添加剂的术语而不是乘法术语。在我们的问题设置下，我们还证明了$ \ omega（\ sqrt {dt}）$的新颖下限。因此，我们提出的算法的遗憾与对数因素的下限相匹配。数值实验支持理论保证，并表明我们所提出的方法的表现优于现有的线性匪徒算法。

我们研究了一个顺序决策问题，其中学习者面临$ k $武装的随机匪徒任务的顺序。对手可能会设计任务，但是对手受到限制，以在$ m $ and的较小（但未知）子集中选择每个任务的最佳组。任务边界可能是已知的（强盗元学习设置）或未知（非平稳的强盗设置）。我们设计了一种基于Burnit subsodular最大化的减少的算法，并表明，在大量任务和少数最佳武器的制度中，它在两种情况下的遗憾都比$ \ tilde {o}的简单基线要小。 \ sqrt {knt}）$可以通过使用为非平稳匪徒问题设计的标准算法获得。对于固定任务长度$ \ tau $的强盗元学习问题，我们证明该算法的遗憾被限制为$ \ tilde {o}（nm \ sqrt {m \ tau}+n^{2/3} m \ tau）$。在每个任务中最佳武器的可识别性的其他假设下，我们显示了一个带有改进的$ \ tilde {o}（n \ sqrt {m \ tau}+n^{1/2} {1/2} \ sqrt的强盗元学习算法{m k \ tau}）$遗憾。

通过图形反馈的在线学习问题已经在文献中进行了广泛的研究，因为它的一般性和对各种学习任务进行建模的潜力。现有作品主要研究对抗和随机反馈。如果对反馈机制的先验知识是不可用的或错误的，那么这种专门设计的算法可能会遭受巨大的损失。为了避免此问题，\ citet {ererez2021towards}尝试针对两个环境进行优化。但是，他们认为反馈图是无方向性的，每个顶点都有一个自循环，这会损害框架的通用性，并且在应用程序中可能无法满足。有了一般的反馈图，在拉动该手臂时可能无法观察到手臂，这使得探索更加昂贵，并且在两种环境中最佳性能的算法更具挑战性。在这项工作中，我们通过新的权衡机制克服了这一困难，并精心设计的探索和剥削比例。我们证明了所提出的算法同时实现$ \ mathrm {poly} \ log t $在随机设置中的遗憾，而在$ versarial设置中，$ \ tilde {o} $ \ tilde {o}的最小值遗憾t $是地平线，$ \ tilde {o} $隐藏参数独立于$ t $以及对数项。据我们所知，这是通用反馈图的第一个最佳世界结果。

我们考虑带有背包的土匪（从此以后，BWK），这是一种在供应/预算限制下的多臂土匪的通用模型。特别是，强盗算法需要解决一个众所周知的背包问题：找到最佳的物品包装到有限尺寸的背包中。 BWK问题是众多激励示例的普遍概括，范围从动态定价到重复拍卖，再到动态AD分配，再到网络路由和调度。尽管BWK的先前工作集中在随机版本上，但我们开创了可以在对手身上选择结果的另一个极端。与随机版本和“经典”对抗土匪相比，这是一个更加困难的问题，因为遗憾的最小化不再可行。相反，目的是最大程度地减少竞争比率：基准奖励与算法奖励的比率。我们设计了一种具有竞争比O（log t）的算法，相对于动作的最佳固定分布，其中T是时间范围；我们还证明了一个匹配的下限。关键的概念贡献是对问题的随机版本的新观点。我们为随机版本提出了一种新的算法，该算法是基于重复游戏中遗憾最小化的框架，并且与先前的工作相比，它具有更简单的分析。然后，我们为对抗版本分析此算法，并将其用作求解后者的子例程。

广泛观察到，在实际推荐系统中，诸如“点击框架”等“点击框架”的战略行为。通过这种行为的激励，我们在奖励的战略操纵下研究组合多武装匪徒（CMAB）的问题，其中每个臂可以为自己的兴趣修改发出的奖励信号。这种对抗性行为的表征是对先前研究的环境放松，例如对抗性攻击和对抗性腐败。我们提出了一种战略变体的组合UCB算法，其遗憾是最多的$ O（m \ log t + m b_ {max}）$的战略操作，其中$ t $是时间范围，$ m $武器数量和$ b_ {max} $是手臂的最大预算。我们为武器预算提供了下限，以引起强盗算法的某些遗憾。在线工人选择对众包系统的大量实验，在线影响合成和实际数据集的最大化和在线建议，以鲁棒性和遗憾的界限提供了我们的理论发现，在各种操纵预算制度中。

We consider the stochastic linear contextual bandit problem with high-dimensional features. We analyze the Thompson sampling (TS) algorithm, using special classes of sparsity-inducing priors (e.g. spike-and-slab) to model the unknown parameter, and provide a nearly optimal upper bound on the expected cumulative regret. To the best of our knowledge, this is the first work that provides theoretical guarantees of Thompson sampling in high dimensional and sparse contextual bandits. For faster computation, we use spike-and-slab prior to model the unknown parameter and variational inference instead of MCMC to approximate the posterior distribution. Extensive simulations demonstrate improved performance of our proposed algorithm over existing ones.

我们通过审查反馈重复进行一定的第一价格拍卖来研究在线学习，在每次拍卖结束时，出价者只观察获胜的出价，学会了适应性地出价，以最大程度地提高她的累积回报。为了实现这一目标，投标人面临着一个具有挑战性的困境：如果她赢得了竞标 - 获得正收益的唯一方法 - 然后她无法观察其他竞标者的最高竞标，我们认为我们认为这是从中汲取的。一个未知的分布。尽管这一困境让人联想到上下文强盗中的探索探索折衷权，但现有的UCB或汤普森采样算法无法直接解决。在本文中，通过利用第一价格拍卖的结构属性，我们开发了第一个实现$ o（\ sqrt {t} \ log^{2.5} t）$ hearry bund的第一个学习算法（\ sqrt {t} \ log^{2.5} t），这是最小值的最低$ $ \ log $因素，当投标人的私人价值随机生成时。我们这样做是通过在一系列问题上提供算法，称为部分有序的上下文匪徒，该算法将图形反馈跨动作，跨环境跨上下文进行结合，以及在上下文中的部分顺序。我们通过表现出一个奇怪的分离来确定该框架的优势和劣势，即在随机环境下几乎可以独立于动作/背景规模的遗憾，但是在对抗性环境下是不可能的。尽管这一通用框架有限制，但我们进一步利用了第一价格拍卖的结构，并开发了一种学习算法，该算法在存在对手生成的私有价值的情况下，在存在的情况下可以有效地运行样本（并有效地计算）。我们建立了一个$ o（\ sqrt {t} \ log^3 t）$遗憾，以此为此算法，因此提供了对第一价格拍卖的最佳学习保证的完整表征。

我们考虑一个多武装的强盗设置，在每一轮的开始时，学习者接收嘈杂的独立，并且可能偏见，\ emph {评估}每个臂的真正奖励，它选择$ k $武器的目标累积尽可能多的奖励超过$ $ rounds。在假设每轮在每个臂的真正奖励从固定分发中汲取的，我们得出了不同的算法方法和理论保证，具体取决于评估的生成方式。首先，在观察功能是真正奖励的遗传化线性函数时，我们在一般情况下展示$ \ widetilde {o}（t ^ {2/3}）$后悔。另一方面，当观察功能是真正奖励的嘈杂线性函数时，我们就可以派生改进的$ \ widetilde {o}（\ sqrt {t}）$后悔。最后，我们报告了一个实证验证，确认我们的理论发现，与替代方法进行了彻底的比较，并进一步支持在实践中实现这一环境的兴趣。

We study Pareto optimality in multi-objective multi-armed bandit by providing a formulation of adversarial multi-objective multi-armed bandit and properly defining its Pareto regrets that can be generalized to stochastic settings as well. The regrets do not rely on any scalarization functions and reflect Pareto optimality compared to scalarized regrets. We also present new algorithms assuming both with and without prior information of the multi-objective multi-armed bandit setting. The algorithms are shown optimal in adversarial settings and nearly optimal in stochastic settings simultaneously by our established upper bounds and lower bounds on Pareto regrets. Moreover, the lower bound analyses show that the new regrets are consistent with the existing Pareto regret for stochastic settings and extend an adversarial attack mechanism from bandit to the multi-objective one.