We study adversarial attacks on linear stochastic bandits: by manipulating
the rewards, an adversary aims to control the behaviour of the bandit
algorithm. Perhaps surprisingly, we first show that some attack goals can never
be achieved. This is in sharp contrast to context-free stochastic bandits, and
is intrinsically due to the correlation among arms in linear stochastic
bandits. Motivated by this finding, this paper studies the attackability of a
$k$-armed linear bandit environment. We first provide a complete necessity and
sufficiency characterization of attackability based on the geometry of the
arms' context vectors. We then propose a two-stage attack method against LinUCB
and Robust Phase Elimination. The method first asserts whether the given
environment is attackable; and if yes, it poisons the rewards to force the
algorithm to pull a target arm linear times using only a sublinear cost.
Numerical experiments further validate the effectiveness and cost-efficiency of
the proposed attack method.

本文探讨了对线性随机赌博机的对抗攻击，提供了攻击性的充分必要条件，针对 LinUCB 和 Robust Phase Elimination 方法提出了一种有效的攻击方法并得出了数字实验结果。

线性随机臂何时易受攻击？

When Are Linear Stochastic Bandits Attackable?

A major challenge in contextual bandits is to design general-purpose
algorithms that are both practically useful and theoretically well-founded. We
present a new technique that has the empirical and computational advantages of
realizability-based approaches combined with the flexibility of agnostic
methods. Our algorithms leverage the availability of a regression oracle for
the value-function class, a more realistic and reasonable oracle than the
classification oracles over policies typically assumed by agnostic methods. Our
approach generalizes both UCB and LinUCB to far more expressive possible model
classes and achieves low regret under certain distributional assumptions. In an
extensive empirical evaluation, compared to both realizability-based and
agnostic baselines, we find that our approach typically gives comparable or
superior results.

本研究提出了一种新的技术，将可实现性方法的经验和计算优势与不可知方法的灵活性相结合，借助回归预测器的可用性来进行算法优化，实现了任何分布假设下出色的表现。

具备回归神谕的实用上下文强化学习

Practical Contextual Bandits with Regression Oracles

We consider influence maximization (IM) in social networks, which is the
problem of maximizing the number of users that become aware of a product by
selecting a set of "seed" users to expose the product to. While prior work
assumes a known model of information diffusion, we propose a novel
parametrization that not only makes our framework agnostic to the underlying
diffusion model, but also statistically efficient to learn from data. We give a
corresponding monotone, submodular surrogate function, and show that it is a
good approximation to the original IM objective. We also consider the case of a
new marketer looking to exploit an existing social network, while
simultaneously learning the factors governing information propagation. For
this, we propose a pairwise-influence semi-bandit feedback model and develop a
LinUCB-based bandit algorithm. Our model-independent analysis shows that our
regret bound has a better (as compared to previous work) dependence on the size
of the network. Experimental evaluation suggests that our framework is robust
to the underlying diffusion model and can efficiently learn a near-optimal
solution.

该论文考虑了社交网络中的影响最大化问题，提出了一种可快速从数据中学习的新颖参数化框架并开发了 LinUCB 算法来解决问题。