Problem-dependent Regret for Lexicographic Multi-Armed Bandits with Adversarial Corruptions

Bo Xue, Xi Lin, Yuanyu Wan, Qingfu ZhangIJCAI 2025 · DOI

Introduction

In many real-world decision-making scenarios, objectives are not equal but follow a strict hierarchy. For instance, in clinical trials, patient safety is a non-negotiable priority over secondary efficacy metrics. This hierarchical structure is formally known as lexicographic ordering. While the Multi-Armed Bandit (MAB) framework is a standard for sequential decision-making, traditional algorithms struggle when multiple objectives are involved, especially when rewards are subject to adversarial corruptions.

The Lexicographic Challenge

The core difficulty in lexicographic MAB lies in identifying arms that are optimal across a sequence of priorities. Existing methods often suffer from three major issues: fragility to reward manipulation (corruptions), suboptimal regret bounds ($O(T^{2/3})$), and an inability to adapt to the specific "difficulty" or reward gaps of a problem instance.

Lexicographic ordering scenarios: (a) multiple arms optimal for the first objective, and (b) a single optimal arm for the first objective.

As illustrated above, an algorithm must navigate the trade-offs between objectives. A "Single-Objective Trap" occurs when an agent focuses solely on the primary goal ($\mu^1$), potentially failing to optimize lower-priority objectives ($\mu^2, \mu^3, \dots$) where significant gains could still be made among the top-tier candidates.

Robust Algorithms: CMOB-KB and CMOB-UB

To address these challenges, this paper introduces the Arm Elimination under Lexicographic Ordering (AELO) framework. This approach sequentially filters out sub-optimal arms objective-by-objective. Based on this, two robust algorithms are proposed:

  1. CMOB-KB (Known Budget): Designed for scenarios where the total corruption budget is known, it utilizes enlarged confidence intervals to remain robust against reward manipulation.
  2. CMOB-UB (Unknown Budget): Since corruption levels are rarely known in practice, this version employs a multi-instance technique to adaptively handle unknown levels of corruption by dynamically switching between different tolerance levels.

The primary theoretical contribution is achieving problem-dependent regret. By scaling with the "reward gap" ($\Delta^i$) of each objective, these algorithms improve the regret bound from $O(T^{2/3})$ to $O(\log T)$ in stochastic settings, matching the theoretical lower bounds for single-objective bandits.

Experimental Validation

The researchers evaluated the proposed methods against state-of-the-art baselines like PF-LEX using both synthetic and real-world datasets, including the COV-BOOST vaccine trials.

Regret comparison across multi-objective, known budget, and unknown budget methods.

The results demonstrate that the CMOB family of algorithms consistently achieves lower regret and higher stability. While previous methods like PF-LEX fail to converge under even minor adversarial pressure, CMOB-KB and CMOB-UB maintain near-optimal performance. In the COV-BOOST trials, these algorithms successfully identified vaccine strategies that satisfied all three hierarchical health objectives, whereas single-objective baselines failed on lower-priority metrics.

Conclusion

This work provides the first robust, problem-dependent algorithms for lexicographic multi-objective bandits. By bridging the gap between robustness and efficiency, the CMOB algorithms offer a practical solution for complex, high-stakes decision environments. Future research aims to remove the dependence on the local trade-off parameter ($\lambda$), moving toward fully parameter-free robust optimization.

Summary updated

BibTeX
@inproceedings{xue2025problem,
  author = {Bo Xue and Xi Lin and Yuanyu Wan and Qingfu Zhang},
  title = {{Problem-dependent Regret for Lexicographic Multi-Armed Bandits with Adversarial Corruptions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/754},
}
Figure