在内存有限的流式老虎机问题中，首次给出精确的误差与内存权衡结果。
Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
- 设计两种算法，根据内存大小自动切换策略以平衡误差与存储。
- 证明了当内存不足时，误差随内存平方根递减，且达到理论最优。
- 适用于在线推荐、广告投放等实时决策场景，尤其适合资源受限环境。
研究单次遍历流式随机多臂老虎机问题中的间隙依赖后悔值最小化。在此问题中，共存在 n 个臂，但最多只能存储 m < n 个臂及其统计信息。本文建立了关于所有相关参数（包括臂数 n、内存大小 m、轮次数 T 以及各臂与最优臂的期望奖励差距 Δ_i）的紧致非渐近后悔上界。对于任意常数 α ≥ 1，提出两个算法：当 m ≥ 2/3n 时，后悔值上界为 O_α((n−m)T^{1/(α+1)} / n^{1+1/(α+1)} ∑_{Δ_i>0} Δ_i^{1−2α})；当 m < 2/3n 时，上界为 O_α(T^{1/(α+1)} / m^{1/(α+1)} ∑_{Δ_i>0} Δ_i^{1−2α})。同时，通过构造硬实例证明了下界匹配：对任意 α ≥ 1 与任意 m ≤ k < n，存在实例使得任意算法的后悔值至少为 Ω_α((k−m+1)T^{1/(α+1)} / k^{1+1/(α+1)} ∑_{Δ_i>0} Δ_i^{1−2α})。这是首个针对流式 MAB 的紧致间隙依赖后悔界。此前仅知 α=1、m=O(1) 时有 O(∑_{Δ_i>0} √T log T / Δ_i) 上界，而本工作揭示其正确阶为 Θ(1/√m ∑_{Δ_i>0} √T / Δ_i)。
原文摘要 · Abstract (English)
We study the problem of minimizing gap-dependent regret for single-pass streaming stochastic multi-armed bandits (MAB). In this problem, the $n$ arms are present in a stream, and at most $m<n$ arms and their statistics can be stored in the memory. We establish tight non-asymptotic regret bounds regarding all relevant parameters, including the number of arms $n$, the memory size $m$, the number of rounds $T$ and $(Δ_i)_{i\in [n]}$ where $Δ_i$ is the reward mean gap between the best arm and the $i$-th arm. These gaps are not known in advance by the player. Specifically, for any constant $α\ge 1$, we present two algorithms: one applicable for $m\ge \frac{2}{3}n$ with regret at most $O_α\Big(\frac{(n-m)T^{\frac{1}{α+ 1}}}{n^{1 + {\frac{1}{α+ 1}}}}\displaystyle\sum_{i:Δ_i > 0}Δ_i^{1 - 2α}\Big)$ and another applicable for $m<\frac{2}{3}n$ with regret at most $O_α\Big(\frac{T^{\frac{1}{α+1}}}{m^{\frac{1}{α+1}}}\displaystyle\sum_{i:Δ_i > 0}Δ_i^{1 - 2α}\Big)$. We also prove matching lower bounds for both cases by showing that for any constant $α\ge 1$ and any $m\leq k < n$, there exists a set of hard instances on which the regret of any algorithm is $Ω_α\Big(\frac{(k-m+1) T^{\frac{1}{α+1}}}{k^{1 + \frac{1}{α+1}}} \sum_{i:Δ_i > 0}Δ_i^{1-2α}\Big)$. This is the first tight gap-dependent regret bound for streaming MAB. Prior to our work, an $O\Big(\sum_{i\colonΔ>0} \frac{\sqrt{T}\log T}{Δ_i}\Big)$ upper bound for the special case of $α=1$ and $m=O(1)$ was established by Agarwal, Khanna and Patil (COLT'22). In contrast, our results provide the correct order of regret as $Θ\Big(\frac{1}{\sqrt{m}}\sum_{i\colonΔ>0}\frac{\sqrt{T}}{Δ_i}\Big)$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。