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

Technical Summary: Follow-the-Perturbed-Leader for Decoupled Bandits

Problem Setting
This paper addresses the decoupled multi-armed bandit (MAB) problem, a setting where the learner selects two distinct arms at each round $t$: one arm $i_t$ for exploitation (incurring the loss $\ell_{t, i_t}$ without observing it) and one arm $j_t$ for exploration (observing the loss $\ell_{t, j_t}$ without incurring it). This framework models scenarios such as ultra-wideband communication systems (sensing a channel different from the transmission channel) and sim-to-real transfer in robotics. The goal is to minimize pseudo-regret, defined as the difference between the cumulative loss incurred by the learner's exploitation choices and the cumulative loss of the best fixed arm in hindsight.

The paper targets Best-of-Both-Worlds (BOBW) guarantees, aiming to achieve:

1. Optimal regret of $O(\sqrt{KT})$ in the adversarial regime (where losses are determined by an adaptive adversary).
2. Near-optimal, time-independent regret of $O(K/\Delta_{\min})$ in the stochastically constrained adversarial (SCA) regime (which includes the standard stochastic setting), where $\Delta_{\min}$ is the minimum suboptimality gap.

Methodology
The authors propose a new policy based on the Follow-the-Perturbed-Leader (FTPL) framework, specifically designed to overcome the computational bottlenecks of existing BOBW policies in decoupled settings.

• Exploitation Strategy: The learner selects the exploitation arm $i_t$ by minimizing a perturbed cumulative loss estimate:
  $$i_t = \arg\min_{i \in [K]} \left\{ \hat{L}_{t,i} - \frac{r_{t,i}}{\eta_t} \right\}$$
  where $\hat{L}_{t,i}$ is the estimated cumulative loss, $\eta_t$ is the learning rate, and $r_{t,i}$ are i.i.d. random perturbations sampled from a Pareto distribution $P_\alpha$ with shape parameter $\alpha > 1$. This perturbation type corresponds to the $\beta$-Tsallis-INF policy (with $\alpha = 1/(1-\beta)$), known for achieving BOBW guarantees.

• Exploration Strategy (Key Innovation): In standard FTPL bandit algorithms, constructing an unbiased importance-weighted (IW) loss estimator typically requires knowing the exact probability $w_{t,i}$ of selecting arm $i$. In decoupled bandits, the exploration probability $p_{t,i}$ must be set based on $w_{t,i}$. However, FTPL does not provide a closed-form expression for $w_{t,i}$ (unlike FTRL), and estimating the full vector via geometric resampling is computationally expensive ($O(K^2)$ or higher).
  To resolve this, the authors introduce a surrogate probability $q_{t,i}$ that can be computed directly from the current loss estimates without resampling or convex optimization:
  $$q_{t,i} = \left( \frac{1}{1 + \eta_t \hat{L}_{t,i}} \wedge \frac{1}{\sigma_{t,i}^{1/\alpha}} \right)^{\frac{\alpha+1}{2}}$$
  where $\sigma_{t,i}$ is the rank of $\hat{L}_{t,i}$ among all arms. The exploration arm $j_t$ is then selected according to the normalized distribution $p_{t,i} = q_{t,i} / \sum_j q_{t,j}$. This approach avoids the need for explicit $w_{t,i}$ values while maintaining the theoretical properties required for BOBW guarantees.

Key Contributions

1. First FTPL-based BOBW Policy for Decoupled Bandits: The paper presents the first policy that achieves BOBW guarantees in decoupled bandits without solving convex optimization problems (required by FTRL-based approaches like Decoupled-Tsallis-INF) or employing resampling procedures (typically required for FTPL probability estimation).
2. Computational Efficiency: By replacing the full probability vector computation with the efficiently computable surrogate $q_{t,i}$, the proposed policy reduces the per-step computational complexity. While sorting the loss estimates takes $O(K \log K)$, the authors note that an optimized implementation can achieve $O(K)$ updates by tracking rank changes incrementally. This contrasts with FTRL policies that require iterative convex optimization (e.g., Newton's method) at every step.
3. Theoretical Guarantees:
   • Adversarial Regime: The policy achieves an $O(\sqrt{KT})$ regret bound, matching the known lower bound for decoupled bandits.
   • Stochastic/SCA Regime: The policy achieves a regret bound of $O(K/\Delta_{\min})$ (specifically $O(\sqrt{K/\Delta_{\min}} \sum_{i \neq i^*} 1/\Delta_i + K/\Delta_{\min})$ for $\alpha=3$), which is near-optimal and improves upon the time-dependent bounds of standard stochastic bandits.

Results

• Theoretical: The paper provides rigorous proofs (via regret decomposition into stability and penalty terms) showing that the surrogate probability $q_{t,i}$ is sufficiently close to the true exploitation probability to maintain the necessary regret bounds.
• Empirical: Experiments on synthetic data (both adversarial and stochastic regimes) and a real-world simulation using the MovieLens 100K dataset demonstrate that the proposed FTPL policy:
  • Achieves lower cumulative regret compared to existing BOBW policies (Decoupled-Tsallis-INF/FTRL and EXP3).
  • Demonstrates superior computational efficiency. In the adversarial regime, the proposed policy runs significantly faster than FTRL-based baselines. For $K=64$, the runtime ratio of FTRL to FTPL was observed to be approximately 1363 times slower.
  • Scales effectively with the number of arms $K$, maintaining robustness across varying gap sizes $\Delta$.

Significance and Claims
The paper claims that its primary contribution is bridging the gap between the theoretical optimality of FTRL-based BOBW policies and the computational efficiency of FTPL in the context of decoupled bandits. By eliminating the need for convex optimization and resampling, the proposed method allows FTPL to fully realize its efficiency advantages without sacrificing regret performance. The authors suggest that the technique of using efficiently computable surrogate probabilities in place of exact probability vectors may be applicable to other algorithmic frameworks (such as the Prod family) beyond FTPL, potentially enabling improved computational efficiency in broader bandit settings. The work is motivated by practical applications in communication systems and robotics where per-step computational latency is critical.