In a recent work, Laforgue et al. introduce the model of last switch
dependent (LSD) bandits, in an attempt to capture nonstationary phenomena
induced by the interaction between the player and the environment. Examples
include satiation, where consecutive plays of the same action lead to decreased
performance, or deprivation, where the payoff of an action increases after an
interval of inactivity. In this work, we take a step towards understanding the
approximability of planning LSD bandits, namely, the (NP-hard) problem of
computing an optimal arm-pulling strategy under complete knowledge of the
model. In particular, we design the first efficient constant approximation
algorithm for the problem and show that, under a natural monotonicity
assumption on the payoffs, its approximation guarantee (almost) matches the
state-of-the-art for the special and well-studied class of recharging bandits
(also known as delay-dependent). In this attempt, we develop new tools and
insights for this class of problems, including a novel higher-dimensional
relaxation and the technique of mirroring the evolution of virtual states. We
believe that these novel elements could potentially be used for approaching
richer classes of action-induced nonstationary bandits (e.g., special instances
of restless bandits). In the case where the model parameters are initially
unknown, we develop an online learning adaptation of our algorithm for which we
provide sublinear regret guarantees against its full-information counterpart.

该论文介绍了一个名为 LSD Bandits 的模型，主要针对交互式非稳态问题，提出了一种近似求解它的算法，并在模型参数未知的情况下提供在线学习的适应算法。

具有单调收益函数的最后转换相关赌博机

Last Switch Dependent Bandits with Monotone Payoff Functions

Deep neural nets have caused a revolution in many classification tasks. A
related ongoing revolution -- also theoretically not understood -- concerns
their ability to serve as generative models for complicated types of data such
as images and texts. These models are trained using ideas like variational
autoencoders and Generative Adversarial Networks.
We take a first cut at explaining the expressivity of multilayer nets by
giving a sufficient criterion for a function to be approximable by a neural
network with $n$ hidden layers. A key ingredient is Barron's Theorem
\cite{Barron1993}, which gives a Fourier criterion for approximability of a
function by a neural network with 1 hidden layer. We show that a composition of
$n$ functions which satisfy certain Fourier conditions ("Barron functions") can
be approximated by a $n+1$-layer neural network.
For probability distributions, this translates into a criterion for a
probability distribution to be approximable in Wasserstein distance -- a
natural metric on probability distributions -- by a neural network applied to a
fixed base distribution (e.g., multivariate gaussian).
Building up recent lower bound work, we also give an example function that
shows that composition of Barron functions is more expressive than Barron
functions alone.

通过 Barron 定理，我们证明了一组满足某些 Fourier 条件的函数的组合可以通过一个多达 $n+1$ 层的神经网络来逼近，为深度神经网络的表达能力提供了解释。英文原文主要探讨了神经网络的一些基本性质以及其在生成模型领域的应用，建议阅读原文以获取更多细节。

神经网络表达分布能力探究

On the ability of neural nets to express distributions

We introduce several generalizations of classical computer science problems
obtained by replacing simpler objective functions with general submodular
functions. The new problems include submodular load balancing, which
generalizes load balancing or minimum-makespan scheduling, submodular sparsest
cut and submodular balanced cut, which generalize their respective graph cut
problems, as well as submodular function minimization with a cardinality lower
bound. We establish upper and lower bounds for the approximability of these
problems with a polynomial number of queries to a function-value oracle. The
approximation guarantees for most of our algorithms are of the order of
sqrt(n/ln n). We show that this is the inherent difficulty of the problems by
proving matching lower bounds. We also give an improved lower bound for the
problem of approximately learning a monotone submodular function. In addition,
we present an algorithm for approximately learning submodular functions with
special structure, whose guarantee is close to the lower bound. Although quite
restrictive, the class of functions with this structure includes the ones that
are used for lower bounds both by us and in previous work. This demonstrates
that if there are significantly stronger lower bounds for this problem, they
rely on more general submodular functions.

本文介绍了通过使用广义子模函数代替较简单的目标函数获得的几个传统计算机科学问题的推广，包括子模型负载平衡，子模型最稀疏切割和子模型平衡切割等，并建立了这些问题的近似界限。