# On reducing the order of arm-passes bandit streaming algorithms under memory bottleneck

arXiv: https://arxiv.org/abs/2112.06130 · HTML: https://mlsanity.com/paper/2112.06130/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 18 references that are in the map.
- First posted on arXiv 30 Nov 2021.

## Builds on (most cited first, 3 of 3)

- [Stochastic Multi-armed Bandits in Constant Space](https://mlsanity.com/paper/1712.09007/) (2017)
- [Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory](https://mlsanity.com/paper/1901.08387/) (2019)
- [Streaming Algorithms for Stochastic Multi-armed Bandits](https://mlsanity.com/paper/2012.05142/) (2020)

## Built on by (most cited first, 3 of 3)

- [A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits](https://mlsanity.com/paper/2205.00984/) (2022)
- [Tight Memory-Regret Lower Bounds for Streaming Bandits](https://mlsanity.com/paper/2306.07903/) (2023)
- [Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2405.19752/) (2024)

## Abstract (arXiv)

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(√Tlog(T)) regret by a logarithmic factor, and also provide 2-pass algorithms with some initial conditions to incur a similar order of regret.