Beyond the Lower Bound: Bridging Regret Minimization and Best Arm Identification in Lexicographic Bandits

AI summary

Overview

Research area: Multi-armed bandits, specifically multi-objective sequential decision-making under lexicographic (priority-ordered) preferences, spanning both regret minimization and best arm identification.

Technical level: Advanced. The paper is a theory-first contribution built on gap-dependent regret bounds, fixed-confidence sample complexity, minimax rates, and comparison against known lower bounds.

Scope: The paper proposes and analyzes two elimination-based algorithms for lexicographic bandits, one that eliminates arms objective-by-objective and one that eliminates arms using reward information from all objectives simultaneously, unifying regret minimization and best arm identification in a single framework.

What This Paper Is About

In a lexicographic bandit, a learner repeatedly picks one of K arms and observes a reward vector with m components, where the objectives are ranked by importance: the highest-priority objective must be optimized first, then the next, and so on. Prior work on this setting studied only regret minimization (RM), while the other major bandit task, best arm identification (BAI), was left unexplored. This paper asks whether RM and BAI can be handled together under lexicographic preferences, and shows that combining them not only is possible but also lets the multi-objective feedback accelerate arm elimination beyond what single-objective lower bounds would suggest is possible.

Key Contributions

1. LexElim-Out, a warm-up elimination algorithm that filters arms layer by layer according to objective priority, starting from the highest-priority objective and proceeding downward. It requires the cardinalities |O_*(i)| of the optimal arm sets, mirroring the standard uniqueness assumption in single-objective BAI, and matches the best-known problem-dependent BAI guarantees for the primary objective without degrading performance on additional objectives.
2. LexElim-In, an enhanced algorithm that performs inner-layer elimination using joint reward information from all objectives in each round. Its regret and sample complexity bounds are stated with a minimum over objectives, so they can fall below the known single-objective lower bounds, illustrating the benefit of cross-objective information sharing.
3. Anytime minimax guarantee for LexElim-In: a regret bound of Õ(Λ^i(λ)·√(Kt)) for each objective i ∈ [m] at any round t ≥ 1, comparable to the best-known single-objective results (Degenne and Perchet 2016) up to the factor Λ^i(λ), with Λ^1(λ) = 1 so the top-priority objective is unaffected.
4. Empirical validation on synthetic data showing both algorithms outperform baselines in cumulative regret and BAI sample complexity, with LexElim-In excelling on some instances.

Main Findings

• Primary objective is not penalized. For LexElim-Out, the regret bound for objective i = 1 is Õ(Σ_{Δ¹(a)>0} 1/Δ¹(a)), matching the known single-objective lower bound of Ω(Σ_{Δ(a)>0} 1/Δ(a)) (Lattimore 2018). Its sample complexity for i = 1 is Õ(Σ_{Δ¹(a)>0} 1/(Δ¹(a))²), matching the single-objective lower bound of Ω(Σ_{Δ(a)>0} 1/(Δ(a))²) (Jamieson et al. 2014) and the guarantees of Karnin et al. (2013).
• Explicit cross-objective cost for lower-priority objectives. For i = 2, the regret bound splits into a cross-objective cost Õ(Σ_{Δ¹(a)>0} Δ²(a)/(Δ¹(a))²) plus a single-objective term Õ(Σ_{a∈S(2)} 1/Δ²(a)). The cross-objective term vanishes when (Δ¹(a))² ≫ Δ²(a), i.e., when an arm is so clearly suboptimal on objective 1 that it is eliminated quickly. The same decomposition extends to i > 2, accumulating cross-objective costs from all higher-priority objectives j < i.
• LexElim-In goes beyond the single-objective lower bound. Its gap-dependent regret and sample complexity bounds contain a min over j ∈ [m] of terms involving (Λ^j(λ))²/(Δ^j(a))². Because Λ¹(λ) = 1 and the minimum is taken over objectives, if any auxiliary objective j ≥ 2 has a gap Δ^j(a) much larger than Δ¹(a)·Λ^j(λ), the corresponding term can be substantially smaller than 1/Δ¹(a). Since Δ̃(a) ≥ Δ¹(a) for all arms, the paper states that LexElim-In outperforms the single-objective lower bounds.
• Identification cost is governed by the most distinguishable objective. In Lemma-like Remark 4, each suboptimal arm's cost is set by the objective j that makes it easiest to distinguish, so an arm with a large gap on any objective can be eliminated early without extensive exploration of other objectives.
• Worst-case (minimax) regret. Corollary 1 gives R^i(t) ≤ Õ(Λ^i(λ)·√(Kt)) for any objective i ∈ [m], with Λ^i(λ) = 1 + λ + ⋯ + λ^{i−1}. This matches the single-objective minimax rate Õ(√(Kt)) up to the Λ^i(λ) factor, and because Λ¹(λ) = 1, the highest-priority objective's regret is unaffected by adding lower-priority objectives.
• Cross-objective acceleration depends on the conflict structure. In Figure 1, the case with no conflict among arms gives λ = 0 and LexElim-In eliminates two yellow arms quickly using large second-objective gaps. When a red suboptimal arm conflicts with the lex-optimal arm (λ = 1), only the yellow arm far from the optimum is eliminated quickly, because the second-objective confidence term is scaled by 2 + 4λ = 6.
• Experimental results. With the first baseline set (EGE from Karnin et al. 2013, UCB_α, and PF-LEX), Figure 2 reports regret comparisons for K = 10, and Figure 3 reports sample complexity comparisons against EGE and UCB_α. Both proposed algorithms outperform existing baselines in cumulative regret and BAI sample complexity, with LexElim-In superior on some instances. The truncated text does not report the numeric values, the number of objectives used in the experiments, the horizon T, or the dataset sizes.

Methodology in Plain English

The authors start from the standard elimination idea used in bandit algorithms: keep a set of still-possible arms, play the arm whose estimate is most uncertain, and discard arms that look clearly worse than the current empirical best. They adapt this to the priority structure in two different ways.

LexElim-Out processes objectives in priority order. It runs elimination rounds on the first objective until the active set shrinks to the known number of arms that are optimal on that objective, then moves to the second objective, and so on. An arm is discarded when its empirical mean on the current objective falls more than twice the confidence width below the empirical best. The confidence width is c(a_t) = sqrt((4/n(a_t))·log(6Km·n(a_t)/δ)), and empirical means are updated by an incremental average. Because it only looks at one objective at a time, lower-priority objectives get no targeted exploration early on.

LexElim-In instead nests the elimination across objectives inside each round. It starts with the full active set, then for objective 1, 2, …, m it repeatedly finds the empirical best arm within the currently remaining set and discards arms falling below it by more than (2 + 4λ + ⋯ + 4λ^{i−1})·c(a_t). The threshold grows geometrically in i, letting lower-priority objectives tolerate larger reward gaps while still contributing to elimination. The λ parameter, defined by the assumption μ^i(a) − μ^i(a_) ≤ λ · max_{j<i}{μ^j(a_) − μ^j(a)}, measures how much lower-priority objectives can conflict with higher-priority ones. Every pull returns the full reward vector, so all m empirical means are updated from the same sample.

For the theory, the authors define per-objective gaps Δ^i(a) = μ^i(a_) − μ^i(a) relative to the lex-optimal arm, define the sets S(i) and O_(i), and prove confidence-interval-based regret and sample complexity bounds. They then derive a minimax corollary and compare the resulting expressions to published single-objective lower bounds.

Why This Matters

Impact on research. This is described as the first algorithmic framework that simultaneously addresses regret minimization and best arm identification in lexicographic bandits. It also makes a conceptual point that runs against the usual intuition that lower bounds are barriers: in the multi-objective setting, feedback from auxiliary objectives can be exploited so that the achievable complexity is better than the single-objective lower bound, because the min over objectives effectively selects the easiest objective for each arm. The paper is positioned relative to single-objective combined RM/BAI work such as Degenne et al. (2019), Zhong et al. (2023), Zhang and Ying (2023), and Yang et al. (2024).

Real-world applications (drawn from the paper's stated motivations):

• Clinical trials, where ethics require giving effective treatments during the study (low regret) while the final goal is to determine the most effective treatment (accurate BAI); the paper also cites medical diagnosis, where patient safety typically outweighs cost or treatment speed.
• Recommendation systems, where fairness may be prioritized over user engagement, and where the platform wants good performance during learning plus a reliably identified best policy afterwards.
• Hyperparameter optimization, where objectives are naturally nested in priority and the practitioner wants both efficient search and a confident final configuration.
• Multi-criteria resource allocation, where higher-priority criteria must be satisfied before lower-priority ones are traded off.

Industry relevance. Any deployment that must keep performing well while running an experiment, and then commit to a single decision, is a candidate: adaptive routing, online advertising and recommendation, A/B testing with hard safety or fairness constraints, and automated configuration tuning. The lexicographic formulation avoids the common shortcut of collapsing objectives into one weighted score, preserving the dominance structure that regulators and safety teams typically require.

Future Directions

• Removing the knowledge requirements. LexElim-Out needs the cardinalities |O_*(i)| of the optimal arm sets and LexElim-In needs the trade-off parameter λ. Developing variants that estimate or avoid these inputs is a natural next step.
• Characterizing the limits of cross-objective acceleration. The paper shows LexElim-In can beat single-objective lower bounds, but the matching lower bound for the lexicographic RM-plus-BAI problem is not established here; a genuinely lexicographic lower bound would quantify how much the min-over-objectives term can help.
• Filling out the empirical picture. The available text reports that experiments are synthetic and run on a Windows 10 laptop with an Intel(R) Core(TM) i7-1170 CPU and 32GB memory, with Figure 2 using K = 10, but does not report numeric results, the number of objectives used, the horizon, or dataset sizes, so broader and more detailed empirical study is open.
• Extending beyond 1-sub-Gaussian, bounded-mean rewards. The analysis assumes rewards drawn from 1-sub-Gaussian distributions with unknown means in [0,1]; other noise models and structured feedback are untested here.

Target Audience

Researchers and graduate students working on multi-armed bandits, pure exploration, and multi-objective online learning, particularly those interested in regret-versus-identification trade-offs and in whether multi-objective structure can be exploited to beat single-objective lower bounds. It is also relevant to applied scientists in clinical trial design, recommendation, and hyperparameter optimization who need algorithms that both perform well during learning and identify a best option at the end, though the heavy theoretical notation means practitioners will need to rely on the algorithm pseudocode (Algorithms 1 and 2) rather than the proofs.

Authors’ abstract

In multi-objective decision-making with hierarchical preferences, lexicographic bandits provide a natural framework for optimizing multiple objectives in a prioritized order. In this setting, a learner repeatedly selects arms and observes reward vectors, aiming to maximize the reward for the highest-priority objective, then the next, and so on. While previous studies have primarily focused on regret minimization, this work bridges the gap between \textit{regret minimization} and \textit{best arm identification} under lexicographic preferences. We propose two elimination-based algorithms to address this joint objective. The first algorithm eliminates suboptimal arms sequentially, layer by layer, in accordance with the objective priorities, and achieves sample complexity and regret bounds comparable to those of the best single-objective algorithms. The second algorithm simultaneously leverages reward information from all objectives in each round, effectively exploiting cross-objective dependencies. Remarkably, it outperforms the known lower bound for the single-objective bandit problem, highlighting the benefit of cross-objective information sharing in the multi-objective setting. Empirical results further validate their superior performance over baselines.