Scholarlink

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&lt;n_ arms="" and="" their="" statistics="" can="" be="" stored="" in="" the="" memory.="" We="" establish="" tight="" non-asymptotic="" regret="" bounds="" regarding="" all="" relevant="" parameters_="" including="" number="" of="" n_="" memory="" size="" m_="" rounds="" T="" _varDelta="" _i___i_in="" _n_="" where="" _varDelta="" _i_="" is="" reward="" mean="" gap="" between="" best="" arm="" i-th="" arm.="" These="" gaps="" are="" not="" known="" advance="" by="" player.="" Specifically_="" for="" any="" constant="" _alpha="" _ge="" _="" we="" present="" two="" algorithms:="" one="" applicable="" _m_ge="" _frac_2_3_n_="" with="" at="" most="" _mathcal="" _O___alpha="" _Big="" _frac_n-m_T_frac_1_alpha="" _="" _frac_1_alpha="" _sum="" __i:_varDelta="" _i=""&gt; 0}\varDelta _i^{1 - 2\alpha }\Big )\) \( ^{1}\) and another applicable for \(m&lt;\frac{2}{3}n\) with regret at most \(\mathcal {O}_\alpha \Big (\frac{T^{\frac{1}{\alpha +1}}}{m^{\frac{1}{\alpha +1}}}\displaystyle \sum _{i:\varDelta _i &gt; 0}\varDelta _i^{1 - 2\alpha }\Big )\) . We also prove matching lower bounds for both cases by showing that for any constant \(\alpha \ge 1\) and any \(m\le k &lt; n\) , there exists a set of hard instances on which the regret of any algorithm is \(\varOmega _\alpha \Big (\frac{(k-m+1) T^{\frac{1}{\alpha +1}}}{k^{1 + \frac{1}{\alpha +1}}} \sum _{i:\varDelta _i &gt; 0}\varDelta _i^{1-2\alpha }\Big )\) . This is the first tight gap-dependent regret bound for streaming MAB. Prior to our work, an \(\mathcal {O}\Big (\sum _{i:\varDelta _i&gt;0} \frac{\sqrt{T}\log T}{\varDelta _i}\Big )\) upper bound for the special case of \(\alpha =1\) and \(m=\mathcal {O}(1)\) was established by Agarwal, Khanna and Patil (COLT’22). In contrast, our results provide the correct order of regret as \(\varTheta \Big (\frac{1}{\sqrt{m}}\sum _{i:\varDelta _i&gt;0}\frac{\sqrt{T}}{\varDelta _i}\Big )\) (1 In this paper, the notations \(\mathcal {O}_\alpha , \varOmega _\alpha , \varTheta _\alpha \) subsume a multiplicative factor depending only on \(\alpha \) . This is fine since we usually take \(\alpha \) to be a constant.).</n_>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Zichun Ye,
  • Chihao Zhang,
  • Jiahao Zhao

摘要

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="" number="" of="" n_="" memory="" size="" m_="" rounds="" T="" _varDelta="" _i___i_in="" _n_="" where="" _varDelta="" _i_="" is="" reward="" mean="" gap="" between="" best="" arm="" i-th="" arm.="" These="" gaps="" are="" not="" known="" advance="" by="" player.="" Specifically_="" for="" any="" constant="" _alpha="" _ge="" _="" we="" present="" two="" algorithms:="" one="" applicable="" _m_ge="" _frac_2_3_n_="" with="" at="" most="" _mathcal="" _O___alpha="" _Big="" _frac_n-m_T_frac_1_alpha="" _="" _frac_1_alpha="" _sum="" __i:_varDelta="" _i=""> 0}\varDelta _i^{1 - 2\alpha }\Big )\) \( ^{1}\) and another applicable for \(m<\frac{2}{3}n\) with regret at most \(\mathcal {O}_\alpha \Big (\frac{T^{\frac{1}{\alpha +1}}}{m^{\frac{1}{\alpha +1}}}\displaystyle \sum _{i:\varDelta _i > 0}\varDelta _i^{1 - 2\alpha }\Big )\) . We also prove matching lower bounds for both cases by showing that for any constant \(\alpha \ge 1\) and any \(m\le k < n\) , there exists a set of hard instances on which the regret of any algorithm is \(\varOmega _\alpha \Big (\frac{(k-m+1) T^{\frac{1}{\alpha +1}}}{k^{1 + \frac{1}{\alpha +1}}} \sum _{i:\varDelta _i > 0}\varDelta _i^{1-2\alpha }\Big )\) . This is the first tight gap-dependent regret bound for streaming MAB. Prior to our work, an \(\mathcal {O}\Big (\sum _{i:\varDelta _i>0} \frac{\sqrt{T}\log T}{\varDelta _i}\Big )\) upper bound for the special case of \(\alpha =1\) and \(m=\mathcal {O}(1)\) was established by Agarwal, Khanna and Patil (COLT’22). In contrast, our results provide the correct order of regret as \(\varTheta \Big (\frac{1}{\sqrt{m}}\sum _{i:\varDelta _i>0}\frac{\sqrt{T}}{\varDelta _i}\Big )\) (1 In this paper, the notations \(\mathcal {O}_\alpha , \varOmega _\alpha , \varTheta _\alpha \) subsume a multiplicative factor depending only on \(\alpha \) . This is fine since we usually take \(\alpha \) to be a constant.).