We provide the first useful, rigorous analysis of ensemble sampling for the
stochastic linear bandit setting. In particular, we show that, under standard
assumptions, for a $d$-dimensional stochastic linear bandit with an interaction
horizon $T$, ensemble sampling with an ensemble of size $m$ on the order of $d
\log T$ incurs regret bounded by order $(d \log T)^{5/2} \sqrt{T}$. Ours is the
first result in any structured setting not to require the size of the ensemble
to scale linearly with $T$ -- which defeats the purpose of ensemble sampling --
while obtaining near $\sqrt{T}$ order regret. Ours is also the first result
that allows infinite action sets.

我们提供了第一个对于随机线性老虎机设置的集成抽样方法的有用、严格的分析，特别是在标准假设下，对于一个交互时域为 T 的 d 维度随机线性老虎机，在大小约等于 d log T 的集成抽样方式下，所产生的后悔从数量级上被界定为 (d log T)^(5/2) × sqrt (T)。本文是第一个在任何结构化设置下不要求集成的大小与 T 线性扩展，同时达到接近 sqrt (T) 量级后悔的结果。本文也是第一个允许无限动作集的结果。

线性赌博机的集成抽样：小集成即可

Ensemble sampling for linear bandits: small ensembles suffice

Thompson sampling has emerged as an effective heuristic for a broad range of
online decision problems. In its basic form, the algorithm requires computing
and sampling from a posterior distribution over models, which is tractable only
for simple special cases. This paper develops ensemble sampling, which aims to
approximate Thompson sampling while maintaining tractability even in the face
of complex models such as neural networks. Ensemble sampling dramatically
expands on the range of applications for which Thompson sampling is viable. We
establish a theoretical basis that supports the approach and present
computational results that offer further insight.

本篇论文提出集成抽样（ensemble sampling）的方法来近似贝叶斯 “Thompson 抽样” 算法，从而使之适用于更复杂的模型，如神经网络，此方法保持了可计算性，扩展了该算法的应用范围，并给出实验验证和理论依据。

集成抽样

Ensemble Sampling

The development of sophisticated experimental means to control nanoscale
systems has motivated efforts to design driving protocols which minimize the
energy dissipated to the environment. Computational models are a crucial tool
in this practical challenge. We describe a general method for sampling an
ensemble of finite-time, nonequilibrium protocols biased towards a low average
dissipation. We show that this scheme can be carried out very efficiently in
several limiting cases. As an application, we sample the ensemble of
low-dissipation protocols that invert the magnetization of a 2D Ising model and
explore how the diversity of the protocols varies in response to constraints on
the average dissipation. In this example, we find that there is a large set of
protocols with average dissipation close to the optimal value, which we argue
is a general phenomenon.

通过计算模型，我们描述了一种偏向低耗散平均值的有限时间、非平衡协议的采样方法，并应用于采样二维伊辛模型磁化反转的低耗散协议集。我们发现有大量协议的平均耗散接近最优值，这是一个普遍的现象。