Parameter-Free Heavy-Tailed Bandits

Technical Summary: Parameter-Free Heavy-Tailed Bandits

Problem Statement

The paper addresses the stochastic multi-armed bandit (MAB) problem under heavy-tailed reward distributions. In this setting, rewards $X$ satisfy a finite moment condition $\mathbb{E}[|X|^{1+\epsilon}] \leq u$ for a tail exponent $\epsilon \in (0, 1]$ and a moment bound $u < +\infty$. While robust estimators can achieve optimal regret rates when both $\epsilon$ and $u$ are known, real-world applications (e.g., finance, advertising) often lack reliable estimates for these parameters.

The core problem, posed as an open question by Genalti and Metelli (COLT 2025), is to determine the best possible regret guarantees for algorithms that are assumption-free regarding $u$ and $\epsilon$. Specifically, the paper investigates:

1. The fundamental trade-offs between distribution-free (worst-case) and distribution-dependent (instance-specific) regret when $u$ is unknown.
2. The additional cost incurred when $\epsilon$ is also unknown.
3. Whether a single algorithm can achieve sublinear regret uniformly across all $\epsilon \in (0, 1]$.

Methodology

The authors employ a two-step analytical approach:

1. $u$-Adaptivity (Fixed $\epsilon$): They first analyze the scenario where $\epsilon$ is known but $u$ is unknown. They define two regret rates:

   • $\Phi_{free}(K, T)$: A moment-free distribution-free regret bound.
   • $\Phi_{dep}(K, T)$: A gap-sum-normalized distribution-dependent regret bound.
     Using a change-of-measure argument combined with specific instance constructions, they derive a lower bound on the product of these rates, establishing a "frontier" of achievable performance.

2. Algorithm Design (AdaR-ETC): To match the derived lower bounds, the authors propose Adaptive Robust ETC (AdaR-ETC). This is an Explore-Then-Commit strategy utilizing:

   • Median-of-Means (MoM) Estimator: To robustly estimate arm means without requiring knowledge of $u$ or $\epsilon$.
   • Scheduled Exploration: The exploration budget $L_T$ is tuned via parameters $\alpha$ (controlling horizon dependence) and $q$ (controlling arm dependence). In the $u$-adaptive setting (where $\epsilon$ is known), these parameters are explicitly set based on $\epsilon$. However, the algorithm can be made fully parameter-free (unaware of both $u$ and $\epsilon$) by calibrating the exploration schedule to the finite-variance endpoint $\epsilon = 1$.

3. $(\epsilon, u)$-Adaptivity (Unknown $\epsilon$): The authors extend the analysis to the case where both parameters are unknown. They calibrate the AdaR-ETC algorithm to the finite-variance endpoint $\epsilon = 1$ (setting $q=1/3$ and $\alpha=2/3$) to create a single, parameter-free strategy. They then prove a pairwise lower bound to show that this calibration yields an optimal profile among strategies that retain the optimal guarantee at $\epsilon=1$.

Key Contributions and Results

1. The Trade-off Frontier for Unknown $u$
The paper proves that for any strategy unaware of $u$, there is a sharp trade-off between distribution-free and distribution-dependent guarantees. Specifically, for fixed $\epsilon$:
$$\Phi_{dep}(K, T) \cdot \Phi_{free}(K, T)^{\frac{1+\epsilon}{\epsilon}} = \Omega\left(T^{\frac{1+\epsilon}{\epsilon}}\right)$$
This implies that improving the worst-case (distribution-free) rate necessarily deteriorates the instance-dependent rate. The authors characterize the "K-frontier" and "T-frontier," showing that no single algorithm can simultaneously optimize both.

2. The AdaR-ETC Algorithm
The proposed AdaR-ETC algorithm achieves regret bounds that match the theoretical frontier up to logarithmic factors. By tuning parameters $\alpha$ and $q$, the algorithm can select any operating point on the trade-off frontier.

• Distribution-free bound: $\tilde{O}\left(u^{\frac{1}{1+\epsilon}} K^{\frac{\epsilon}{1+\epsilon}(1-q)} T^{\alpha}\right)$
• Distribution-dependent bound: $\tilde{O}\left(K^{q-1} T^{\beta_\alpha}\right)$
  where $\beta_\alpha = (1-\alpha)(1+\epsilon)/\epsilon$.
  The "balanced" point (equal dependence on $K$ and $T$) yields a rate of $\tilde{O}\left(u^{\frac{1}{1+\epsilon}} K^{\frac{\epsilon}{1+2\epsilon}} T^{\frac{1+\epsilon}{1+2\epsilon}}\right)$. For the finite-variance case ($\epsilon=1$), this results in a $\tilde{O}(T^{2/3})$ rate, which is strictly worse than the $\tilde{O}(\sqrt{T})$ rate attainable when $u$ is known, quantifying the "price of adaptivity."

3. Limits of Simultaneous $(\epsilon, u)$ Adaptation
When $\epsilon$ is also unknown, the authors propose calibrating AdaR-ETC to $\epsilon=1$.

• Pointwise Sublinearity: For any fixed $\epsilon > 0$, the calibrated algorithm achieves sublinear regret.
• Impossibility of Uniformity: The paper proves that no single strategy can guarantee sublinear regret uniformly over all $\epsilon \in (0, 1]$. As $\epsilon \to 0$, the exponent of $T$ approaches 1, meaning the regret becomes linear.
• Optimality of Calibration: Among strategies that maintain the optimal $\tilde{O}(K^{1/3}T^{2/3})$ guarantee at $\epsilon=1$, the $\epsilon=1$-calibrated AdaR-ETC is shown to be frontier-optimal for all other $\epsilon$.

Significance and Claims

The paper claims to resolve the COLT 2025 open problem regarding assumption-free heavy-tailed bandits. Its primary significance lies in:

• Characterizing the Statistical Cost: It provides a sharp characterization of the statistical cost of adapting to unknown heavy tails, demonstrating that adaptation to unknown scale ($u$) and order ($\epsilon$) introduces fundamental trade-offs rather than just constant factors.
• Frontier vs. Oracle: It establishes that there is no "oracle curve" that is optimal for all moment orders; instead, adaptation is described by a frontier.
• Algorithmic Solution: It provides a simple, parameter-free algorithm (AdaR-ETC) that achieves these optimal trade-offs without requiring prior knowledge of the distribution's tail properties.

The authors explicitly state that their results do not recover oracle rates without additional structural assumptions, confirming that the "price of adaptivity" is inherent to the heavy-tailed setting. They identify the limits of uniform sublinear regret and suggest that future work should focus on designing anytime versions of the algorithm and identifying the weakest additional assumptions required to recover oracle rates.