Introduction
Standard multi-armed bandit (MAB) algorithms, such as UCB1, require memory that scales linearly with the number of arms ($K$). In modern large-scale applications—like crowdsourcing with thousands of workers or online advertising with millions of products—this linear dependency becomes a significant bottleneck. This paper addresses a fundamental challenge: can we achieve sub-linear regret while only storing statistics for a small, fixed number of arms $M \ll K$?
The Memory-Constrained Challenge
In a typical stochastic MAB setting, an agent seeks to maximize cumulative rewards by choosing from $K$ arms with unknown distributions. Optimal performance usually necessitates tracking the mean reward and pull count for every arm. The authors introduce UCB-M and QUCB-M, algorithms designed to operate within a "Word RAM" model where storing an arm's statistics takes constant space. Remarkably, these algorithms achieve sub-linear regret even with as few as $M=2$ memory slots.
Proposed Algorithms
UCB-M for Finite Arm Sets
Unlike previous "explore-then-commit" strategies that rigidly separate exploration from exploitation, UCB-M employs a phased approach to interleave these processes:
- Phased Execution: Time is divided into phases of increasing length (doubling horizon).
- Sub-phase Competition: Each phase consists of sub-phases where $M$ arms are loaded into memory: $M-1$ new arms and one "recommended" arm (the winner) from the previous sub-phase.
- UCB-MPA Subroutine: Within a sub-phase, the algorithm uses a "Most Played Arm" (MPA) variant of UCB. The arm with the most pulls at the end of the sub-phase is carried over to the next competition.
QUCB-M for Infinite Arm Sets
For scenarios with an effectively infinite number of arms, the goal shifts to quantile regret—performing as well as the top $\rho$-fraction of arms. QUCB-M adapts the UCB-M logic by sampling new arms at a specific rate, ensuring that high-quality arms are eventually filtered into the limited memory slots.
Key Insights: Memory as a Filter
The core innovation lies in treating memory as a competitive filter. By always retaining the "winner" of the previous round and challenging it with new candidates, the algorithm naturally gravitates toward the optimal arm. This coupling of exploration and exploitation is far more efficient than dedicated exploration phases, which often waste resources on demonstrably poor arms.
Experimental Results
The algorithms were tested against synthetic Bernoulli bandit instances ($B_L^K, B_{0.3}^K, B_{0.6}^K$).
As shown in Figure 1, UCB-M (with $M=2$) incurs significantly less regret than the previous leading algorithm, UCBConstantSpace (which required $M=4$). This demonstrates a massive leap in efficiency, often reducing regret by an order of magnitude.
Figure 2 illustrates how regret varies with the available memory $M$. While increasing $M$ generally reduces regret, the algorithm maintains sub-linear performance even at the theoretical minimum of $M=2$. Interestingly, tuning the exploration factor ($\eta$) becomes crucial as memory constraints tighten.
Conclusion
This work proves that sub-linear regret is achievable with extremely limited memory. By moving away from rigid exploration phases and adopting a competitive filtering approach, UCB-M provides a practical solution for large-scale bandit problems. Future work remains to establish formal lower bounds for memory-constrained regret and to bridge the gap for the $M=1$ case.
Summary updated