mlsanityData to 7 Oct 2026

Stochastic Multi-armed Bandits in Constant Space

arXiv 1712.09007 ↗First posted 25 Dec 2017cs.DS cs.LG stat.MLcited by 21

Not on the map. Why?

Abstract (arXiv)

We consider the stochastic bandit problem in the sublinear space setting, where one cannot record the win-loss record for all K arms. We give an algorithm using O(1) words of space with regret [ sumi=1Kfrac1Deltailog fracDeltaiDeltalog T ] where Deltai is the gap between the best arm and arm i and Delta is the gap between the best and the second-best arms. If the rewards are bounded away from 0 and 1, this is within an O(log 1/Delta) factor of the optimum regret possible without space constraints.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 Dec 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 4; 2023: 7; 2024: 3; 2025: 1; 2026: 4.

21 papers.

Sort:

  1. 2022Memory Bounds for the Experts Problemcited by 20
  2. 2022Online Prediction in Sub-linear Spacecited by 16
  3. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  4. 2022A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Banditscited by 12
  5. 2023Tight Regret Bounds for Single-pass Streaming Multi-armed Banditscited by 9
  6. 2023Towards a Pretrained Model for Restless Bandits via Multi-arm Generalizationcited by 9
  7. 2021Linear Bandit Algorithms with Sublinear Time Complexitycited by 8
  8. 2023Improved Space Bounds for Learning with Expertscited by 5
  9. 2023Streaming Kernel PCA Algorithm With Small Spacecited by 5
  10. 2023The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Banditscited by 5
  11. 2024Optimal Streaming Algorithms for Multi-Armed Banditscited by 5
  12. 2023Tight Memory-Regret Lower Bounds for Streaming Banditscited by 4
9 more
  1. 2024Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Banditscited by 4
  2. 2021On reducing the order of arm-passes bandit streaming algorithms under memory bottleneckcited by 3
  3. 2022Hypothesis Transfer in Bandits by Weighted Modelscited by 2
  4. 2025Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Banditscited by 2
  5. 2026Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Banditscited by 1
  6. 2024HELLINGER-UCB: A novel algorithm for stochastic multi-armed bandit problem and cold start problem in recommender systemcited by 0
  7. 2026Better Bounds for the Distributed Experts Problemcited by 0
  8. 2026Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Banditscited by 0
  9. 2026Memory--Batch Tradeoffs in Lipschitz Banditscited by 0