Beyond the Lower Bound: Bridging Regret Minimization and Best Arm Identification in Lexicographic Bandits
2025
Read Beyond the Lower Bound: Bridging Regret Minimization and Best Arm Identification in Lexicographic Bandits (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-05802.txt.
Description
Bo Xue and co-authors unite two goals for decision systems that rank their objectives in a strict order. In lexicographic bandits, each choice pays off on several objectives, and the learner must serve the top objective first, then the next. Past work chased either low regret over time or quick identification of the best arm.
Two elimination algorithms are proposed. One prunes arms layer by layer in priority order, matching the best single-objective rates. The other reads all objectives each round and shares information across them. Strikingly, it beats the known lower bound for single-objective bandits, showing the bonus that cross-objective sharing brings. Tests confirmed both beat baselines, and the theory ties the two classic goals together.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-05802