Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory

Arghya Roy Chaudhuri, Shivaram KalyanakrishnanAAAI 2020 · DOI

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$).

Figure 1: Regret comparison for $K=100$ arms across different reward distributions. UCB-M and its variants significantly outperform the previous state-of-the-art, UCBConstantSpace.

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: Impact of memory size $M$ on regret. The performance of UCB-M improves as more memory is allocated, but remains effective even at very low $M$.

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

BibTeX
@inproceedings{chaudhuri2020regret,
  author = {Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan},
  title = {{Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i06.6566},
}
Figure