Research map / Bandits and online learning / Multi-armed bandits
Multiple Trade-offs: An Improved Approach for Lexicographic Linear Bandits
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 lexicographic multiobjective bandits to stochastic linear bandits and proposes MTLO, using a new lexicographic arm filter and multiple trade-off stages to reach near-optimal regret of about d√T per objective.
Problem
Lexicographic online learning in multiobjective stochastic linear bandits, where prior work (PF-LEX) gives suboptimal regret (KT)^{2/3} under a priority-based regret metric and cannot handle infinite arms.
Approach
A lexicographic ordered arm filter (LOAF) that scales confidence intervals of later objectives by a trade-off parameter lambda so the lexicographic optimal arm is never removed, combined with a multi-stage schedule of decreasing confidence widths that balances exploration and exploitation across objectives.
Key results
- MTLO achieves regret bound of order d√T (times 1+λ^{i-1}) per objective, versus the (KT)^{2/3} bound of PF-LEX for MOMAB.
- In simulations (K=d=10, m=3, T=5e4), MTLO's regret curves for the first and second objectives flatten, indicating identification of the lexicographic optimal arm, while OFUL shows linear regret on the third objective.
- STLO, a direct extension of PF-LEX, can suffer linear regret on the first objective when epsilon is large, illustrating the need for MTLO's multi-stage design.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MTLO instead of PF-LEX | Lexicographic bandit algorithms · First objective, λ=0.2 | general regret | Helped |
| Use MTLO instead of OFUL | Lexicographic MOSLB · Third objective, λ=0.2 | general regret | Helped |
| Use OFUL instead of MTLO | Lexicographic MOSLB · First objective, λ=0.2 | general regret | Helped |
| Use MTLO instead of STLO | Lexicographic MOSLB · First objective, λ=0.2 | general regret | Helped |
| Increase the trade-off parameter from λ=0.2 to λ=2 (ablation) | MTLO · Third objective | general regret | Helped |
Surprising findings
- The priority-based regret metric of prior work is zero for infinite-armed problems on lower-priority objectives, making it an unreasonable measure.
Limitations
- Regret bound grows exponentially in the objective index i through the factor (1+lambda^{i-1}).
- Experiments are limited to a single synthetic setting with standard basis arms and three objectives.
- Requires knowledge of an upper bound lambda satisfying the trade-off condition.
Experimental setup
Benchmarks: synthetic lexicographic linear bandit simulation
Metrics: general regret cumulative regret per objective
Baselines: PF-LEX OFUL STLO
Builds on: PF-LEX OFUL Chu et al. 2011 SupLinRel-style finite-arm reduction Dani et al. 2008 confidence region technique
Closest papers by meaning
- Multiobjective Lipschitz Bandits under Lexicographic Ordering (AAAI 2024 · similarity 0.91)
- Hierarchize Pareto Dominance in Multi-Objective Stochastic Linear Bandits (AAAI 2024 · similarity 0.91)
- Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update (NeurIPS 2025 · similarity 0.87)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.86)
- On the Minimax Regret for Contextual Linear Bandits and Multi-Armed Bandits with Expert Advice (NeurIPS 2024 · similarity 0.86)
- Multi-objective Linear Reinforcement Learning with Lexicographic Rewards (ICML 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.