Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality

We study the decoupled multi-armed bandit problem, where the learner separately selects one arm for exploration and one, possibly different, arm for exploitation at each round. In this setting, the loss of the explored arm is observed but not incurred, whereas the loss of the exploited arm is incurred without being observed. We propose an efficient Follow-the-Perturbed-Leader (FTPL) policy that achieves Best-of-Both-Worlds (BOBW) guarantee with constant regret in the stochastic regime and optimal $\mathcal{O}(\sqrt{KT})$ regret in the adversarial regime. A key feature of our method is that it completely avoids both the convex optimization required by prior BOBW policies and the resampling procedures typically used in FTPL bandit policies. This allows FTPL to fully realize its computational efficiency advantages, leading to substantial reductions in computational cost. We empirically confirm that our policy not only improves the runtime but also demonstrates superior regret performance in both regimes.

Imagine you are playing a game with multiple slot machines. Your goal is to find the balance between choosing the most promising machine to earn rewards and testing other machines to gather information. In our study, we look at a unique setup where you can separate these tasks by choosing two different machines at once. In the real world, it is often difficult to predict how rewards are generated in advance. For example, a machine's jackpots might follow a fixed pattern, or the reward process may change over time due to external manipulation or unexpected environmental shifts. To address this, we developed a robust method that guarantees optimal performance under any kind of uncertainty. Furthermore, our approach is not only much faster to compute than existing methods but also delivers better actual performance. By successfully combining robustness and efficiency, this method offers a practical solution for real-world decision-making.