Technical Summary: Finite-Time Regret Analysis of Retry-Aware Bandits

1. Problem Formulation

The paper addresses the stochastic multi-armed bandit (MAB) problem, traditionally framed as maximizing cumulative reward by balancing exploration and exploitation. However, the authors motivate a shift toward retry-aware objectives, where performance is evaluated based on the best outcome among multiple attempts (e.g., pass@k or max@k in large language model evaluation) rather than the payoff of a single draw.

The specific algorithm studied is ReMax (Retry-aware Maximum), introduced by Nishimori et al. [2026]. In the bandit setting, ReMax operates by selecting a sampling distribution $\pi_t$ over arms that maximizes the posterior expected maximum reward over $M$ virtual draws. While prior work suggested ReMax explores effectively, its finite-time regret properties remained theoretically unclear. The paper focuses on the Gaussian reward setting with $M=2$ (the first nontrivial case) to characterize the algorithm's behavior and derive a regret bound.

2. Methodology and Theoretical Framework

2.1 The ReMax Objective

Given a posterior distribution $\Pi_{t-1}$ over arm values, ReMax chooses $\pi_t$ to maximize:
$$J^{(M)}_{\text{ReMax}}(\pi; \Pi_{t-1}) := \mathbb{E}_{\theta \sim \Pi_{t-1}} \left[ \mathbb{E}_{A_{1:M} \sim \pi} \left[ \max_{m \in [M]} \theta_{A_m} \mid \theta \right] \right]$$
where $A_{1:M}$ are $M$ i.i.d. draws from $\pi$. If an arm is drawn multiple times, the same posterior sample is reused.

2.2 Expected-Improvement Balance Condition

A central structural insight of the paper is the Expected-Improvement (EI) Balance Condition (Proposition 1). For the optimal sampling distribution $\pi_t$, the posterior-averaged marginal contribution of any arm in the support to the "best-of-two" objective is equalized. Specifically, for any two arms $i, j$ in the support:
$$\bar{s}_{t,i} = \bar{s}_{t,j}$$
where $\bar{s}_{t,i}$ is the expected improvement of arm $i$ over the maximum of $M-1$ other draws. This condition distinguishes ReMax from Thompson Sampling (TS); while TS randomizes based on the probability an arm is optimal, ReMax accounts for the magnitude of potential improvement in the maximum reward.

2.3 Regret Analysis Strategy

The authors derive a finite-time regret bound for Gaussian rewards with $M=2$. The analysis decomposes the regret into two distinct regimes:

1. Saturation Term: Rounds where the optimal arm is not underestimated. The analysis shows that once suboptimal arms are sufficiently sampled, ReMax correctly favors the optimal arm, leading to logarithmic regret growth similar to standard bandit algorithms.
2. Underestimation Term: Rounds where the optimal arm's empirical mean is significantly lower than its true mean ($\hat{\mu}_1(t) < \mu_1 - \epsilon$). This is identified as the primary technical bottleneck.

Key Technical Challenge: The paper demonstrates that ReMax can be more exploitative than Thompson Sampling. If the optimal arm is underestimated, the EI balance condition may cause the algorithm to delay returning to the optimal arm because suboptimal arms (which might have high variance or favorable pairwise comparisons) offer a larger expected improvement to the "best-of-two" objective. This leads to a prolonged recovery period.

3. Key Contributions

1. Characterization of the Optimizer: The paper provides the first characterization of the ReMax optimizer via a Bayesian expected-improvement balance condition, clarifying how the algorithm utilizes posterior uncertainty.
2. First Sublinear Regret Bound: For Gaussian rewards with $M=2$, the authors prove a sublinear regret bound:
   $$\mathbb{E}[\text{Reg}(T)] \leq \sum_{i=2}^K O\left(\frac{\log T}{\Delta_i}\right) + \Delta_{\max} \tilde{O}\left(\frac{K^{1/3} T^{2/3}}{\Delta_{\min}^3}\right)$$
   The first term corresponds to the standard saturation behavior, while the second term ($\tilde{O}(T^{2/3})$) arises from the underestimation effect.
3. Identification of Underestimation as a Bottleneck: The analysis explicitly identifies that ReMax's aggressive exploitation can lead to slow recovery from underestimation of the optimal arm, explaining why its regret bound is looser than asymptotically optimal algorithms like UCB or TS.
4. Mitigation Strategy: The authors propose and empirically validate posterior-variance scaling (inflating the posterior variance by a factor $c \geq 1$) as a heuristic to mitigate the underestimation effect, suggesting it can reduce the recovery time.

4. Experimental Results

The authors evaluate ReMax ($M=2$) against Thompson Sampling (TS) and KL-UCB on:

• Synthetic Instances: Gaussian bandits with 2, 3, and 10 arms, featuring small gaps between the best and second-best arms to stress the underestimation regime.
• Real-World Datasets: Instances derived from the Open Bandit Dataset (OBD, 80 arms) and MovieLens 1M (31 arms).

Findings:

• Performance: ReMax generally outperforms TS and KL-UCB in cumulative regret, particularly in synthetic instances with mild underestimation.
• Underestimation Dynamics: In scenarios with many arms (e.g., 10-arm synthetic, OBD), ReMax exhibits more frequent or prolonged underestimation of the optimal arm compared to baselines. This correlates with a reduction in its regret advantage in the most challenging settings.
• Variance Scaling: Experiments in the "designed failure mode" (where underestimation is likely) show that inflating the posterior variance significantly reduces the cumulative underestimation and improves regret, supporting the theoretical intuition.
• Effect of $M$: Experiments with $M > 2$ (using a gradient-based approximation, ReMaxGrad) show that larger $M$ reduces underestimation rounds but does not necessarily improve cumulative regret, suggesting $M$ acts as an exploration knob rather than a universal performance booster.

5. Significance and Claims

The paper claims to provide the first theoretical regret analysis for the ReMax algorithm in the bandit setting. Its significance lies in:

• Bridging Objectives: Connecting retry-aware objectives (common in LLM evaluation) to formal bandit theory.
• Explaining Behavior: Offering a structural explanation for why ReMax behaves differently from TS, specifically highlighting the trade-off between exploiting the magnitude of potential improvements and the risk of underestimation.
• Practical Insight: Demonstrating that while ReMax is often empirically superior, its theoretical guarantees are currently looser due to the underestimation bottleneck. The paper modestly concludes that refining the regret bound (potentially via variance inflation analysis) is a necessary direction for future work to close the gap with asymptotically optimal algorithms.

The authors emphasize that their regret bound is likely not tight (specifically the $T^{2/3}$ term) and that the empirical evidence suggests the underestimation regret grows very slowly, implying the theoretical bound may be conservative.