In this paper, we investigate the streaming bandits problem, wherein the
learner aims to minimize regret by dealing with online arriving arms and
sublinear arm memory. We establish the tight worst-case regret lower bound of
$\Omega \left( (TB)^{\alpha} K^{1-\alpha}\right), \alpha = 2^{B} / (2^{B+1}-1)$
for any algorithm with a time horizon $T$, number of arms $K$, and number of
passes $B$. The result reveals a separation between the stochastic bandits
problem in the classical centralized setting and the streaming setting with
bounded arm memory. Notably, in comparison to the well-known
$\Omega(\sqrt{KT})$ lower bound, an additional double logarithmic factor is
unavoidable for any streaming bandits algorithm with sublinear memory
permitted. Furthermore, we establish the first instance-dependent lower bound
of $\Omega \left(T^{1/(B+1)} \sum_{\Delta_x>0} \frac{\mu^*}{\Delta_x}\right)$
for streaming bandits. These lower bounds are derived through a unique
reduction from the regret-minimization setting to the sample complexity
analysis for a sequence of $\epsilon$-optimal arms identification tasks, which
maybe of independent interest. To complement the lower bound, we also provide a
multi-pass algorithm that achieves a regret upper bound of $\tilde{O} \left(
(TB)^{\alpha} K^{1 - \alpha}\right)$ using constant arm memory.

这篇论文研究了流式赌博机问题，建立了时间上界、臂数、游戏轮数的算法紧确的最劣后悔下限，并证明了与分析算法复杂度上限的样本复杂性分析问题的关系。

流式赌博问题的紧凑内存遗憾下界

Tight Memory-Regret Lower Bounds for Streaming Bandits

We propose Streaming Bandits, a Restless Multi Armed Bandit (RMAB) framework
in which heterogeneous arms may arrive and leave the system after staying on
for a finite lifetime. Streaming Bandits naturally capture the health
intervention planning problem, where health workers must manage the health
outcomes of a patient cohort while new patients join and existing patients
leave the cohort each day. Our contributions are as follows: (1) We derive
conditions under which our problem satisfies indexability, a precondition that
guarantees the existence and asymptotic optimality of the Whittle Index
solution for RMABs. We establish the conditions using a polytime reduction of
the Streaming Bandit setup to regular RMABs. (2) We further prove a phenomenon
that we call index decay, whereby the Whittle index values are low for short
residual lifetimes driving the intuition underpinning our algorithm. (3) We
propose a novel and efficient algorithm to compute the index-based solution for
Streaming Bandits. Unlike previous methods, our algorithm does not rely on
solving the costly finite horizon problem on each arm of the RMAB, thereby
lowering the computational complexity compared to existing methods. (4)
Finally, we evaluate our approach via simulations run on realworld data sets
from a tuberculosis patient monitoring task and an intervention planning task
for improving maternal healthcare, in addition to other synthetic domains.
Across the board, our algorithm achieves a 2-orders-of-magnitude speed-up over
existing methods while maintaining the same solution quality.

提出了 “Streaming Bandits” 框架，该框架为不安宁的多臂赌博机问题，其中异构臂可以在有限寿命后进入和离开系统。该框架自然地解决了卫生干预计划问题，同时提供了一个新颖而高效的算法来计算 Whittle 索引解。