Research map / Bandits and online learning / Multi-armed bandits
Multiobjective Lipschitz Bandits under Lexicographic Ordering
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends multiobjective bandits under lexicographic ordering to Lipschitz (infinite-arm) settings, proposing static (SDLO) and adaptive-discretization (ADLO) multi-stage algorithms with near-optimal general regret bounds.
Problem
Multiobjective bandits with lexicographically ordered objectives over possibly infinite arm sets; prior work (PF-LEX) handles only finite arms with a suboptimal bound of O((KT)^(2/3)) under priority-based regret.
Approach
A multi-stage decision strategy that first restricts to arms with large confidence width and then sequentially filters arms objective by objective, combined with adaptive discretization (zooming) and a zooming dimension defined per objective, yielding regret O~(T^((d+1)/(d+2))) per objective matching the single-objective Lipschitz lower bound in T.
Key results
- ADLO attains regret O~(T^((d_z^i+1)/(d_z^i+2))) for the i-th objective, matching the single-objective Lipschitz lower bound in T.
- SDLO and ADLO improve the regret order by O((KT)^(1/6)) over PF-LEX's O((KT)^(2/3)) for K-armed bandits.
- In simulations on [0,1] with T=6e4, SDLO significantly outperforms PF-LEX on the third objective; ADLO outperforms the zooming algorithm on the third objective and is similar on the first.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace PF-LEX with SDLO | Static methods on the three-objective experiment · First objective | cumulative regret | No clear effect |
| Replace PF-LEX with SDLO | Static methods on the three-objective experiment · Third objective | cumulative regret | Helped |
| Replace the zooming algorithm with ADLO | Adaptive methods on the three-objective experiment · First objective | cumulative regret | No clear effect |
| Replace the zooming algorithm with ADLO | Adaptive methods on the three-objective experiment · Third objective | cumulative regret | Helped |
| Use ADLO's adaptive discretization and multi-stage decision-making | MOLB · General, objective i | regret bound | Helped |
Surprising findings
- PF-LEX performs comparably to SDLO on the first objective but much worse on the third, because its guarantee is for priority-based regret and not general regret.
Limitations
- Both algorithms require prior knowledge of the lexicographic difficulty parameter lambda.
- Experiments are limited to a simple one-dimensional synthetic setting with 10 repetitions.
- Regret bound for the i-th objective grows with (1+lambda+...+lambda^(i-1)) factor, which can be large.
Experimental setup
Benchmarks: synthetic 1D arm space [0,1] with three objectives
Metrics: cumulative general regret for objectives 1 and 3
Baselines: PF-LEX zooming algorithm
Builds on: zooming algorithm PF-LEX UCB
Closest papers by meaning
- Multiple Trade-offs: An Improved Approach for Lexicographic Linear Bandits (AAAI 2025 · similarity 0.91)
- Hierarchize Pareto Dominance in Multi-Objective Stochastic Linear Bandits (AAAI 2024 · similarity 0.91)
- Thompson Sampling for Multi-Objective Linear Contextual Bandit (NeurIPS 2025 · similarity 0.88)
- On the Minimax Regret for Contextual Linear Bandits and Multi-Armed Bandits with Expert Advice (NeurIPS 2024 · similarity 0.87)
- Nearly Minimax Optimal Regret for Multinomial Logistic Bandit (NeurIPS 2024 · similarity 0.87)
- Non-Stationary Lipschitz Bandits (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.