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

CREATORZichun Ye, Chihao Zhang, Jiahao Zhao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-02428

Browse the full library · About the Tower of Babel