We give nearly-tight upper and lower bounds for the improving multi-armed
bandits problem. An instance of this problem has $k$ arms, each of whose reward
function is a concave and increasing function of the number of times that arm
has been pulled so far. We show that for any randomized online algorithm, there
exists an instance on which it must suffer at least an $\Omega(\sqrt{k})$
approximation factor relative to the optimal reward. We then provide a
randomized online algorithm that guarantees an $O(\sqrt{k})$ approximation
factor, if it is told the maximum reward achievable by the optimal arm in
advance. We then show how to remove this assumption at the cost of an extra
$O(\log k)$ approximation factor, achieving an overall $O(\sqrt{k} \log k)$
approximation relative to optimal.

我们对改进的多臂赌博机问题给出了近似最优的上下界。我们证明了对于任何随机在线算法，存在一个实例使其相对于最优收益至少有一个 Ω(√k) 的近似因子。然后，我们提供了一个随机在线算法，在事先告知最优臂可达到的最大收益的情况下，保证了一个 O (√k) 的近似因子。我们接下来展示了如何消除这一假设，以增加 O (log k) 的近似因子，从而实现了相对于最优的 O (√k log k) 的整体近似。

改进的多臂赌博机问题的近乎紧密逼近保证

Nearly-tight Approximation Guarantees for the Improving Multi-Armed  Bandits Problem

Fitting a function by using linear combinations of a large number $N$ of
`simple' components is one of the most fruitful ideas in statistical learning.
This idea lies at the core of a variety of methods, from two-layer neural
networks to kernel regression, to boosting. In general, the resulting risk
minimization problem is non-convex and is solved by gradient descent or its
variants. Unfortunately, little is known about global convergence properties of
these approaches.
Here we consider the problem of learning a concave function $f$ on a compact
convex domain $\Omega\subseteq {\mathbb R}^d$, using linear combinations of
`bump-like' components (neurons). The parameters to be fitted are the centers
of $N$ bumps, and the resulting empirical risk minimization problem is highly
non-convex. We prove that, in the limit in which the number of neurons
diverges, the evolution of gradient descent converges to a Wasserstein gradient
flow in the space of probability distributions over $\Omega$. Further, when the
bump width $\delta$ tends to $0$, this gradient flow has a limit which is a
viscous porous medium equation. Remarkably, the cost function optimized by this
gradient flow exhibits a special property known as displacement convexity,
which implies exponential convergence rates for $N\to\infty$, $\delta\to 0$.
Surprisingly, this asymptotic theory appears to capture well the behavior for
moderate values of $\delta, N$. Explaining this phenomenon, and understanding
the dependence on $\delta,N$ in a quantitative manner remains an outstanding
challenge.

使用线性组合的神经元对凸紧致区域上的凹函数进行拟合，将所得的经验风险最小化问题收敛到概率分布空间中的 Wasserstein 渐进流（Wasserstein gradient flow），且在 bump 宽度趋近于 0 时，具有特殊的位移凸性（displacement convexity），由于此渐进理论能够描述中等值的行为，因此在对风险最小化和对宽度数量的理解方面仍存在着挑战。