Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits
<|reference_start|>Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits: We study the stochastic multi-armed bandit problem in the $P$-pass streaming model. 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 give a complete characterization of the optimal regret in terms of $m, n$ and $P$. Specifically, we design an algorithm with $\tilde O\left((n-m)^{1+\frac{2^{P}-2}{2^{P+1}-1}} n^{\frac{2-2^{P+1}}{2^{P+1}-1}} T^{\frac{2^P}{2^{P+1}-1}}\right)$ regret and complement it with an $\tilde \Omega\left((n-m)^{1+\frac{2^{P}-2}{2^{P+1}-1}} n^{\frac{2-2^{P+1}}{2^{P+1}-1}} T^{\frac{2^P}{2^{P+1}-1}}\right)$ lower bound when the number of rounds $T$ is sufficiently large. Our results are tight up to a logarithmic factor in $n$ and $P$.<|reference_end|>
@article{he2024understanding,
    title={Understanding Memory-Regret Trade-Off for Streaming Stochastic
  Multi-Armed Bandits},
    author={Yuchen He, Zichun Ye, Chihao Zhang},
    journal={arXiv preprint arXiv:2405.19752},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.19752},
    primaryClass={cs.LG cs.DS stat.ML}
}