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.
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:
- 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.
- 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.
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