betaFeedback

WorksComputer Science

SHPRR: An Algorithm for Pure Exploration under Constrained Regret

Abstract

Best Arm Identification (BAI) conventionally measures the cost of experimentation by the number of samples collected. In many operational settings, however, the cost of exploration relative to a trusted baseline already in place is equally important. We study BAI under both a fixed sampling horizon and a regret budget. Unlike generic resources considered in constrained pure exploration, regret has a distinctive structure: sampling better arms is less costly relative to the baseline. We theoretically show that the regret cost of exploration decreases across the phases of Sequential Halving, a widely used pure-exploration algorithm. This observation yields improved guarantees on the probability of identifying the best arm and motivates a more effective allocation of the regret budget. We propose Sequential Halving with Proportional Regret Rationing (SHPRR), which front-loads the regret budget to allow more exploration when many arms remain. Experiments on synthetic and real-world instances show that SHPRR improves best-arm identification performance over uniform regret allocation and existing baselines.

Introduction

Pure exploration in multi-armed bandits, formalized as Best Arm Identification (BAI), has established foundational paradigms for sample-efficient decision-making under uncertainty (Kalyanakrishnan et al. 2012; Garivier and Kaufmann 2016; Audibert and Bubeck 2010; Karnin, Koren, and Somekh 2013). In classical settings—such as offline algorithm selection or clinical pre-screening—the cost of learning is measured naturally in sample complexity: every pull incurs an identical, uniform cost, and the goal is to identify the optimal arm using as few observations as possible.

However, in many live deployment settings, experimentation does not occur in a vacuum. Instead, it runs directly against a trusted, operational baseline, e.g., a production recommender or a standard-of-care treatment. Here, sampling an inferior candidate inflicts an immediate, tangible penalty on the live system. While sample-based bounds remain invaluable for offline evaluation, live deployments demand an explicit tolerance for cumulative loss. An online A/B test, for instance, cannot simply run for a fixed sample quota if cumulative degradation against the production system exceeds a strict threshold. Accordingly, regret evolves from a post-hoc evaluation metric into a scarce, active budget constraint that directly governs the exploration process in such settings.

While BAI with resource constraints has been studied (Li and Cheung 2024), budgeting realized regret introduces two structural challenges that set it apart from standard exogenous cost models (e.g., financial or computational limits): i) Signed consumption: outperforming the baseline yields a negative cost, effectively replenishing the remaining budget rather than draining it. ii) Consumption–reward coupling: consumption is not an externally sampled attribute but the recentered reward process itself. Hence, better options are less costly, a phenomenon that can be leveraged in the exploration.

Sequential Halving (SH) (Karnin, Koren, and Somekh 2013) provides a natural foundation for phase-based exploration under resource constraints. However, uniform regret allocations across phases fail to exploit a critical structural dynamic of elimination-based algorithms: as suboptimal arms are pruned, the average suboptimality gap of the surviving set contracts. Because early phases must sample from a broader, unrefined pool of arms, the expected regret cost per pull is highest at the start of the algorithm and steadily decreases across phases.

This observation directly motivates our proposed algorithm, Sequential Halving with Proportional Regret Rationing (SHPRR). Rather than distributing the regret budget uniformly, SHPRR strategically front-loads the budget toward earlier phases, where information acquisition incurs the highest regret in proportion to the number of surviving arms. Controlled by a single tuning parameter α∈[0,1]\alpha\in[0,1], SHPRR smoothly interpolates between classical uniform allocation (α=0\alpha= 0) and aggressive early-phase budget prioritization (α=1\alpha= 1), while guaranteeing budget enforcement. Across extensive synthetic and real-world benchmarks, SHPRR consistently matches or outperforms Sequential Halving with Resource Rationing (SH-RR), AT-LUCB, and Top-Two SPRT (TTSPRT). Crucially, while competing baselines demonstrate brittle performance, SHPRR remains robust across all settings.

Our contributions are summarized as follows: we formalize BAI under a realized regret budget, capturing real-world deployment settings where cumulative underperformance against a baseline—rather than sample count—is the critical resource. We characterize two fundamental structural properties that distinguish regret budgeting from standard resource constraints: signed consumption and *consumption– reward coupling. Furthermore, we reveal that elimination-based algorithms exhibit a contracting average suboptimality gap across phases, establishing that early-phase exploration is inherently the most expensive in terms of regret. Guided by this phase-contraction insight, we propose SHPRR, which strategically front-loads the regret budget toward early phases in proportion to the active arm count, controlled by a single parameter α∈[0,1]\alpha\in[0, 1]. We provide theoretical guarantees showing that SHPRR controls failure probability under bounded regret. Empirically, SHPRR consistently matches or outperforms SH-RR, AT-LUCB, and TTSPRT across synthetic and real-world environments. Crucially, while existing baselines display brittle behavior, performing well in specific settings but collapsing in others, SHPRR maintains strong, robust performance across all domains.

Literature on BAI follows one of two formulations: fixed-confidence (PAC) BAI, where the algorithm must identify the best arm with probability at least 1−δ1-\delta while minimizing pulls (Kalyanakrishnan et al. 2012; Garivier and Kaufmann 2016; Kaufmann, Cappé, and Garivier 2016), and fixed-budget BAI, where a limited budget TT is used to maximize the probability of correct identification (Audibert and Bubeck 2010; Karnin, Koren, and Somekh 2013; Gabillon, Ghavamzadeh, and Lazaric 2012; Carpentier and Locatelli 2016). Identification quality is measured via Success Probability (SP), or via simple regret – the expected gap between the best arm’s mean and that of the recommended arm (Bubeck, Munos, and Stoltz 2009, 2011; Zhao et al. 2023).

Elimination and Confidence-Bound Methods: SH (Karnin, Koren, and Somekh 2013) and Successive Rejects (Audibert and Bubeck 2010) allocate an increasing number of pulls per arm across rounds while discarding the weakest arms. Carpentier and Locatelli (2016) established a matching lower bound for the latter, closing the gap with existing upper bounds, while Barrier, Garivier, and Stoltz (2023) study fixed-budget BAI in non-parametric models, sharpening these bounds via KL-based large deviation arguments. Confidence-bound methods instead use interval estimates to guide sampling and stopping: LUCB (Kalyanakrishnan et al. 2012) pulls the empirical best arm together with its most optimistic competitor, KL-LUCB (Kaufmann and Kalyanakrishnan 2013) and lil’UCB (Jamieson et al. 2014) sharpen the underlying confidence intervals, and Track-and-Stop (Garivier and Kaufmann 2016) instead tracks the sampling proportions prescribed by the instance-dependent lower bound, attaining asymptotically optimal sample complexity. Jun and Nowak (2016) extended LUCB to the anytime setting (AT-LUCB), while UGapE (Gabillon, Ghavamzadeh, and Lazaric 2012) unifies the confidence-bound principle across the fixed-budget and fixed-confidence settings.

Top-Two Methods: Russo (2016) introduced Top-Two Thompson Sampling (TTTS), which maintains a posterior over each arm’s mean and performs randomized sampling between the current best arm and a challenger; Shang et al. (2020) and Jourdan et al. (2022) later established δ\delta-PAC guarantees and sample complexity bounds for TTTS variants.

Mukherjee and Tajer (2023) adopt a related top-two structure but replace posterior sampling with Sequential Probability Ratio Test (SPRT) likelihood-ratio statistics to select arms and decide when to stop, yielding a δ\delta-PAC algorithm that is asymptotically optimal for exponential-family rewards without the computational cost of posterior sampling. None of these classical formulations account for the cost of arm pulls, feasibility constraints, or the regret incurred while exploring, motivating the lines of work surveyed next.

BAI with Costs, Constraints and Cumulative Regret: BAI with safety constraints imposes per-pull feasibility requirements (Wang, Wagemaker, and Jamieson 2022; Sui et al. 2015), while variance-constrained BAI (Hou, Tan, and Zhong 2022) instead constrains the variance of the identified arm. Poiani, Metelli, and Restelli (2022) and Wang et al. (2023) study multi-fidelity BAI, where biased approximations of each arm’s reward are available at varying known costs, and the goal is to minimize total identification cost while guaranteeing correct identification with high probability. Kanarios, Zhang, and Ying (2024) study Cost-Aware BAI (CABAI), identifying the highest-reward arm at minimum expected cost, whereas Qin et al. (2025) target the highest reward-to-cost ratio using the fewest samples. Lardy, Katsimerou, and Koolen (2026) study BAI constrained to the subset of arms with costs under a specific threshold when reward and cost are dependent. Harding and Kandasamy (2026) minimize a risk functional jointly penalizing a performance criterion and cumulative sampling cost, avoiding the need to pre-specify a budget or confidence level and Yang, Tan, and Jin (2026) couple identification quality with the cumulative regret incurred during exploration. The closest setting to ours is Li and Cheung (2024), who impose cumulative resource-consumption constraints across arm pulls, and develop SH-RR, an extension of SH that eliminates arms in phases while uniformly rationing each phase’s budget given arm costs. Our setting differs from Li and Cheung (2024) in two respects. First, consumption is signed: because it is an arm’s regret relative to a baseline, outperforming the baseline yields a negative cost that replenishes the budget rather than draining it, unlike the strictly non-negative costs assumed there. Second, consumption is coupled to the reward process: it is not an externally sampled attribute but the recentered reward itself, rendering better arms cheaper to explore.

Problem Setting

We consider a stochastic multi-armed bandit problem augmented with an exogenous baseline and a realized regret budget, in addition to the usual sampling horizon.

Bandit Model

Let S={1,…,K}S = \{1,\ldots,K\} be a finite set of KK arms available to the agent. Pulling arm i∈Si \in S at round tt yields a stochastic reward rt∼νir_t \sim\nu_i, bounded almost surely in [0,1][0, 1], with mean μi=E[rt]\mu_i = \mathbb{E}[r_t]. We assume a unique arm with highest mean reward, and wlog μ1>μ2≥…≥μK\mu_1 > \mu_2 \geq\ldots\geq\mu_K. We denote by μ∗=μ1\mu^* = \mu_1 the mean of the optimal arm, and write Δi=μ∗−μi≥0\Delta_i = \mu^* - \mu_i \geq0 for the suboptimality gap of arm ii. The distributions νi\nu_i, and in particular the means μi\mu_i, are unknown to the agent for every i∈Si \in S at the beginning of the run.

In addition to SS, there is a baseline arm k0∉Sk_0 \notin S, representing an incumbent policy or status-quo action against which arms in SS are evaluated. Unlike the arms in SS, the baseline arm is not available to the agent: it is never pulled, and its reward distribution ν0\nu_0 is never observed. Only its mean μ0=Eν0[r]\mu_0 = \mathbb{E}_{\nu_0}[r] is known, provided as a fixed reference point. We assume μ0≤μ∗\mu_0 \le\mu^\ast, i.e., the baseline is weakly dominated by the best available arm, reflecting its role as an incumbent reference rather than an unattainable ideal.

A policy π\pi sequentially selects arms, with ktk_t being the arm selected at time tt, and, at stopping time τ\tau, outputs a recommendation ϕ∈S\phi\in S. Formally, let Ft=σ(k1,r1,…,kt,rt)\mathcal{F}_t = \sigma(k_1, r_1, \ldots, k_t, r_t) be the filtration generated by the history of pulls and observed rewards, and let τ\tau be a stopping time with respect to (Ft)t≥0(\mathcal{F}_t)_{t\ge0}. At each round t≤τt \le\tau, π\pi selects ktk_t as a function of Ft−1\mathcal{F}_{t-1}; at τ\tau, π\pi outputs ϕ\phi as a function of Fτ\mathcal{F}_\tau.

Realized baseline regret. When the agent pulls arm ktk_t at round tt and observes reward rtr_t, it incurs a realized baseline regret δt=μ0−rt\delta_t = \mu_0 - r_t, measuring the shortfall of the pulled arm’s reward relative to the baseline mean. Because δt\delta_t is defined against the realized reward rtr_t rather than the arm mean μkt\mu_{k_t}, it is a noisy, round-level quantity that can be negative whenever rtr_t exceeds μ0\mu_0, at which point the pull replenishes rather than depletes the budget. The cumulative realized regret after nn pulls is

Rn=∑t=1n(μ0−rt),R0=0.(1)\mathcal{R}_n = \sum_{t=1}^{n}(\mu_0-r_t), \qquad\mathcal{R}_0 = 0. \tag*{(1)}

Constraints. The agent operates under two simultaneous constraints. First, a regret budget B≥0B \ge0 bounds the cumulative realized regret at every pull along the trajectory:

Rt≤B,∀ t≤τ.(2)\mathcal{R}_t \le B, \qquad\forall\, t \le\tau. \tag*{(2)}

Second, a pull budget T∈NT \in\mathbb{N} caps the total number of arm pulls, so that τ≤T\tau\le T. The pull budget is necessary for the problem to be well posed: since δt\delta_t can be negative, an agent that repeatedly pulls a high-reward arm can drive Rn\mathcal{R}_n to be non-increasing, so the regret constraint alone would permit indefinite sampling. The two constraints together guarantee a genuine trade-off between information gained and risk incurred, even when the regret budget does not bind.

Objective. The goal of π\pi is to maximize the probability of exactly identifying the best arm, subject to both constraints:

max⁡π P(ϕ=1)s.t.Rt≤B, ∀ t≤τ,τ≤T.(3)\max_{\pi}\ \mathbb{P}(\phi= 1)\quad\text{s.t.}\quad\mathcal{R}_t \le B,\ \forall\, t \le\tau,\quad\tau\le T. \tag*{(3)}

Structural Properties of SH

SH is a widely used elimination algorithm for fixed-budget BAI. For simplicity, suppose throughout this section that KK is a power of 2 and that there is a margin of safety in the budget to complete the last round-robin cycle. This standard simplification avoids the clutter associated with floors, ceilings, and incomplete round-robin cycles, without affecting the leading-order terms in the resulting bounds. Starting from the full set of arms, SH proceeds over log⁡2(K)\log_2(K) phases. In each phase, the active arms are sampled in round-robin fashion, and the half with the largest empirical means is retained. Throughout, denote by nqn_q the number of arms in each phase qq, and, when nq=2n_q = 2, use the convention nq/4+1=2n_q/4 + 1 = 2 and Δ2K=1\Delta_{2K} = 1.

This phase structure admits a natural extension to BAI under resource constraints when the consumption associated with each pull is nonnegative. A pull quota and a resource quota are assigned to each phase. The active arms are then sampled until one of these quotas binds, after which the usual SH elimination step is performed. This is the principle underlying SH-RR introduced by Li and Cheung (2024).

A conservative reduction to nonnegative consumption. Our regret-budgeted problem can be embedded into this generic framework. For each arm i∈[K]i \in[K], we define the positive-part regret consumption Di+D_i^+ as the random variable with distribution (μ0−ri)+(\mu_0-r_i)_+, with ri∼νir_i \sim\nu_i. As the positive-part regret consumption dominates the regret consumption, any algorithm that respects a budget BB for cumulative positive-part regret also respects the original signed-regret constraint. Applying SH-RR with Di+D_i^+ as the resource consumption therefore provides an immediate feasible benchmark for our problem.

To state the resulting guarantee, let di+:=E[Di+]d_i^+ := \mathbb{E}[D_i^+], and let d(1)+≥⋯≥d(K)+d_{(1)}^+ \ge\cdots\ge d_{(K)}^+ denote these expected consumptions in nonincreasing order. Define

f(d):={2log⁡(1/d),0<d<e−2,e2d,e−2≤d≤1 or d=0,f(d) := \begin{cases} \dfrac{2}{\log(1/d)}, & 0 < d < e^{-2},\\ e^2d, & e^{-2} \le d \le1\ \text{or}\ d=0, \end{cases}

together with the complexity terms

H2,T:=max⁡k>1kΔk2,H2,+sto:=max⁡k>1∑j=1kf(d(j)+)Δk2.H_{2,T} := \max_{k>1}\frac{k}{\Delta_k^2},\qquad H_{2,+}^{\mathrm{sto}} := \max_{k>1}\frac{\sum_{j=1}^{k} f(d_{(j)}^+)}{\Delta_k^2}.

Finally, let γ+:=min⁡{TH2,T,BH2,+sto}\gamma_+ := \min\left\{\frac{T}{H_{2,T}},\frac{B}{H_{2,+}^{\mathrm{sto}}}\right\}. Ignoring integer-rounding effects, SH-RR satisfies

P(ϕ≠1)≤14Klog⁡2(K)exp⁡(−γ+8log⁡2(K)).(4)\mathbb{P}(\phi\ne1) \le14K\log_2(K)\exp\left(-\frac{\gamma_+}{8\log_2(K)}\right). \tag*{(4)}

Remark 4.1 In the Supplementary Material, we also analyze a phase-wise-estimate variant of SH-RR, in which each elimination decision uses only the samples collected during the current phase. This modification leaves the resource-rationing mechanism unchanged and removes the extraneous factor KK from the prefactor in (4).

What the positive-part reduction misses. Bound (4) is a useful benchmark, but the reduction on which it relies deliberately discards the distinctive structure of regret. First, a pull whose reward exceeds the baseline has zero positive-part consumption, whereas its signed consumption is negative. Such a pull replenishes the original regret budget and can finance additional exploration. This effect is entirely absent from the positive-part formulation. For example, suppose that rewards for arm ii are Bernoulli and that 0<μ0<μi<10 < \mu_0 < \mu_i < 1. Then EXi∼νi[μ0−Xi]=μ0−μi<0\mathbb{E}_{X_i\sim\nu_i}[\mu_0-X_i] = \mu_0-\mu_i < 0, whereas EXi∼νi[(μ0−Xi)+]=μ0(1−μi)>0\mathbb{E}_{X_i\sim\nu_i}[(\mu_0-X_i)_+] = \mu_0(1-\mu_i) > 0. Thus, an arm that replenishes the signed-regret budget in expectation is nevertheless assigned a strictly positive expected cost by the positive-part reduction.

Second, generic resource-constrained analyses treat each arm’s consumption distribution as a fixed, exogenous attribute. Although the arm-level distributions are also fixed in our setting, the consumption profile of the active set changes endogenously as elimination removes poorly performing arms. In particular, the generic bound controls a phase containing nqn_q arms using the nqn_q largest effective consumptions f(di+)f(d_i^+), independently of which arms have actually survived. It therefore charges each phase according to a worst-case consumption profile of the corresponding cardinality. Signed regret is more structured. Under round-robin sampling, the expected regret consumption per pull in phase qq is 1nq∑i∈SqΔi−Δ0\frac{1}{n_q}\sum_{i\in S_q}\Delta_i-\Delta_0 where Δ0=μ⋆−μ0\Delta_0=\mu^\star-\mu_0. Consequently, controlling the average suboptimality of the surviving arms simultaneously controls the expected resource consumption of the phase.

A regret-specific structural bound. We now analyze the signed-regret process directly. Consider a phase-rationed version of SH in which phase qq is assigned a regret budget B(q)B^{(q)}. The allocation B(q)B^{(q)} need not be uniform. The result below applies to any phase-budget allocation; the proportional allocation defining SHPRR is introduced in the next section.

For the theoretical analysis, elimination decisions are based on empirical means computed only from the observations collected during the current phase. Algorithm 1, which is used in our experiments, instead computes empirical means from all observations accumulated up to that phase. We analyze the phase-wise-estimate variant because it follows the standard theoretical formulation of SH and permits sharper guarantees, even though discarding past observations may degrade empirical performance. The two variants otherwise share the same sampling, stopping, and budget-rationing mechanisms.

Define, for each phase qq:

References

  1. [1]Diemert, E., Meynet, J., Galland, P., and Lefortier, D. (2017). Attribution modeling increases efficiency of bidding in display advertising. In Proceedings of the AdKDD and TargetAd Workshop, KDD, Halifax, NS, Canada. ACM.arxiv.org/abs/1707.06409
  2. [2]Howard, S. R., Ramdas, A., McAuliffe, J., and Sekhon, J. (2020). Time-uniform chernoff bounds via nonnegative supermartingales. Probability Surveys, 17(none):257–317.DOI
  3. [3]Jain, L., Jamieson, K., Mankoff, R., Nowak, R., and Sievert, S. (2020). The new yorker cartoon caption contest dataset. https://nextml.github.io/caption-contest-data/.

Paper details

vlnc:W_kfh53vb5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents