Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality
This work addresses the decoupled bandit problem for machine learning practitioners, offering a practical and efficient solution with best-of-both-worlds guarantees, though it is incremental in building on existing frameworks.
The paper tackles the decoupled multi-armed bandit problem by proposing a Follow-the-Perturbed-Leader policy with Pareto perturbations, achieving constant regret in stochastic regimes and minimax optimal regret in adversarial regimes, with computational improvements of about 20 times faster than prior methods.
We study the decoupled multi-armed bandit (MAB) problem, where the learner selects one arm for exploration and one arm for exploitation in each round. The loss of the explored arm is observed but not counted, while the loss of the exploited arm is incurred without being observed. We propose a policy within the Follow-the-Perturbed-Leader (FTPL) framework using Pareto perturbations. Our policy achieves (near-)optimal regret regardless of the environment, i.e., Best-of-Both-Worlds (BOBW): constant regret in the stochastic regime, improving upon the optimal bound of the standard MABs, and minimax optimal regret in the adversarial regime. Moreover, the practicality of our policy stems from avoiding both the convex optimization step required by the previous BOBW policy, Decoupled-Tsallis-INF (Rouyer & Seldin, 2020), and the resampling step that is typically necessary in FTPL. Consequently, it achieves substantial computational improvement, about $20$ times faster than Decoupled-Tsallis-INF, while also demonstrating better empirical performance in both regimes. Finally, we empirically show that our approach outperforms a pure exploration policy, and that naively combining a pure exploration with a standard exploitation policy is suboptimal.