On reducing the order of arm-passes bandit streaming algorithms under memory bottleneck
This work addresses memory bottlenecks in streaming bandit algorithms, offering incremental improvements for resource-constrained applications.
The paper tackles the problem of reducing the number of streaming passes in multi-arm bandit algorithms under memory constraints, achieving a logarithmic factor improvement to achieve O(√(T log T)) regret and introducing 2-pass algorithms under certain conditions.
In this work we explore multi-arm bandit streaming model, especially in cases where the model faces resource bottleneck. We build over existing algorithms conditioned by limited arm memory at any instance of time. Specifically, we improve the amount of streaming passes it takes for a bandit algorithm to incur a $O(\sqrt{T\log(T)})$ regret by a logarithmic factor, and also provide 2-pass algorithms with some initial conditions to incur a similar order of regret.