Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Hierarchize Pareto Dominance in Multi-Objective Stochastic 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.
Proposes UCB-based multi-objective stochastic linear bandit algorithms (MOSLB-PC, MOSLB-PL) for mixed Pareto-lexicographic orders, using Grossone gross-scalars to encode priority and regret.
Problem
Multi-objective stochastic linear bandits where objectives mix Pareto dominance with lexicographic priority (priority chains or priority levels), which existing methods handle only as pure Pareto or pure lexicographic orders.
Approach
Represents mixed Pareto-lexicographic preferences with Grossone gross-scalars, defines gross-scalar suboptimality gaps and regrets, and combines UCB confidence bounds with a prior-free lexicographical filter (for chains) or level-wise empirical Pareto filtering (for levels) in an explore-then-exploit framework.
Key results
- MOSLB-PC and MOSLB-PL converge after exploration in simulated experiments, while P-UCB1 (pure Pareto) attains nearly linear regret in the chain setting.
- Theory: MOSLB-PC regret is eÕ((dKT)^{2/3}) and MOSLB-PL regret is eÕ((dT)^{2/3}) with tuned epsilon, matching existing lexicographic bounds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MOSLB-PC to account for lexicographic relationships within priority chains | MOSLB-PC · MPL-PC, two priority chains | Pareto chain regret | Helped |
| Discard the lexicographic relationships and treat all objectives equivalently in Pareto order | MPL-PC bandit methods · MPL-PC, two priority chains | Pareto chain regret | Hurt |
| Optimize only the first objective in each priority chain | MPL-PC bandit methods · MPL-PC, two priority chains | first-priority regret | Helped |
| Use MOSLB-PL to account for ordered priority levels | MOSLB-PL · MPL-PL, two priority levels | Pareto level regret | Helped |
| Treat all objectives jointly in Pareto order | MPL-PL bandit methods · MPL-PL, three priority levels | Pareto level regret | Hurt |
| Consider only objectives in the first priority level | MPL-PL bandit methods · MPL-PL, three priority levels | Pareto level regret | Mixed |
Surprising findings
- Treating all objectives in pure Pareto order (P-UCB1) yields almost linear regret, showing ignoring priority is harmful.
Limitations
- Regret bounds are sub-optimal (T^{2/3}) and depend on an explicit exploration threshold epsilon.
- Evaluation is limited to simulated synthetic linear environments with m=5 objectives.
- Regret correlates with the number of objectives in the longest priority chain.
Experimental setup
Benchmarks: simulated MOSLB environments with m=5 objectives (MPL-PC and MPL-PL settings)
Metrics: Pareto chain regret Pareto level regret
Baselines: P-UCB1 P-UCB2
Builds on: Pareto regret (Drugan and Nowe 2013) P-UCB (Lu et al. 2019a) priority-based lexicographic bandit regret (Hüyük and Tekin 2021) Grossone methodology (Sergeyev 2017) OFUL-style confidence sets (Abbasi-Yadkori et al. 2011)
Closest papers by meaning
- Multiple Trade-offs: An Improved Approach for Lexicographic Linear Bandits (AAAI 2025 · similarity 0.91)
- Multiobjective Lipschitz Bandits under Lexicographic Ordering (AAAI 2024 · similarity 0.91)
- Thompson Sampling for Multi-Objective Linear Contextual Bandit (NeurIPS 2025 · similarity 0.89)
- Constrained Pareto Set Identification with Bandit Feedback (ICML 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.87)
- Forced Exploration in Bandit Problems (AAAI 2024 · 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.