Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
Zichun Ye, Chihao Zhang, Jiahao Zhao · 2025
Read Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits by Zichun Ye, Chihao Zhang, Jiahao Zhao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-02428.txt.
Description
Zichun Ye, Chihao Zhang, and Jiahao Zhao pin down the memory cost of learning on the fly in a 2025 paper. In the streaming bandit problem, options arrive one by one and only a few can be kept in memory. Each choice earns a reward, and regret measures the loss against always picking the best.
The twist is that the gaps between options are unknown beforehand. The authors give two algorithms split by how much memory is available relative to the stream length. Their regret bounds involve every key quantity: stream size, memory, rounds, and the unknown gaps. Matching lower bounds prove no method can do better in general. The tight result closes a theory gap for learning under strict memory limits.
Catalog record
| CREATOR | Zichun Ye, Chihao Zhang, Jiahao Zhao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-02428