Multi-Armed Bandits with Bounded Arm-Memory: Near-Optimal Guarantees for Best-Arm Identification and Regret Minimization

We study the Stochastic Multi-armed Bandit problem under bounded arm-memory. In this setting, the arms arrive in a stream, and the number of arms that can be stored in the memory at any time, is bounded. The decision-maker can only pull arms that are present in the memory. We address the problem from the perspective of two standard objectives: 1) regret minimization, and 2) best-arm identification. For regret minimization, we settle an important open question by showing an almost tight guarantee. We show Ω(T 2/3 ) cumulative regret in expectation for single-pass algorithms for arm-memory size of (n -1), where n is the number of arms. For best-arm identification, we provide an (ε, δ)-PAC algorithm with arm-memory size of O(log * n) and O( n ε 2 • log( 1 δ )) optimal sample complexity.