Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Thompson Sampling for Multi-Objective Linear Contextual Bandit
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 MOL-TS, a Thompson Sampling algorithm for multi-objective linear contextual bandits that samples M parameters per objective (optimistic sampling) and picks uniformly from an empirical effective Pareto front, with a worst-case Pareto/effective Pareto regret of Õ(d^{3/2}√T).
Problem
Multi-objective linear contextual bandits, where the agent must optimize several conflicting objectives simultaneously; existing Pareto-regret analyses cover UCB-type methods only, and TS has no worst-case Pareto regret guarantee.
Approach
Each objective gets M Gaussian posterior samples and each arm is scored by its best sample (optimistic sampling), so that the probability all objectives are jointly optimistic stays constant in L with M = O(log L); the arm is then drawn uniformly from an empirical effective Pareto front that accounts for convex combinations of arm reward vectors.
Key results
- MOL-TS is claimed to achieve worst-case Pareto regret and effective Pareto regret of Õ(d^{3/2}√T), matching single-objective randomized linear bandit order, with only O(log L) dependence on objectives.
- In experiments with K=50, d=5, L=4, T=10000 over 10 instances, MOL-TS outperforms MOL-UCB and MOL-epsilon-Greedy on Pareto regret, effective Pareto regret and per-objective cumulative reward.
- MOL-TS with optimistic sampling (M=O(log L)) yields lower regret than M=1 standard Thompson sampling.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MOL-TS instead of MOL-UCB or MOL-ε-Greedy | Multi-objective linear contextual bandits · K=50, d=5, L=4; 10000 rounds | Pareto regret | Helped |
| Use MOL-TS instead of MOL-UCB or MOL-ε-Greedy | Multi-objective linear contextual bandits · K=50, d=5, L=4; 10000 rounds | effective Pareto regret | Helped |
| Use MOL-TS instead of MOL-UCB or MOL-ε-Greedy | Multi-objective linear contextual bandits · K=50, d=5, L=4; 10000 rounds | cumulative reward | Helped |
| Add optimistic sampling (use M=O(log L) rather than M=1) (ablation) | MOL-TS · Multi-objective linear contextual bandits | Pareto regret | Helped |
| Add optimistic sampling (use M=O(log L) rather than M=1) (ablation) | MOL-TS · Multi-objective linear contextual bandits | effective Pareto regret | Helped |
| Select arms from the effective Pareto front rather than the plain Pareto front | Multi-objective bandit policies · Cumulative rewards across objectives | cumulative reward | Helped |
| Use MOL-ε-Greedy instead of MOL-UCB | Multi-objective linear contextual bandits · K=50, d=5, L=4; 10000 rounds | Pareto regret | Hurt |
| Use MOL-ε-Greedy instead of MOL-UCB | Multi-objective linear contextual bandits · K=50, d=5, L=4; 10000 rounds | effective Pareto regret | Hurt |
| Use MOL-ε-Greedy instead of MOL-UCB | Multi-objective linear contextual bandits · K=50, d=5, L=4; 10000 rounds | total reward | Hurt |
Surprising findings
- MOL-epsilon-Greedy shows higher Pareto and effective Pareto regret yet higher total rewards than MOL-UCB, which the authors attribute to averaging over randomly chosen Pareto-optimal arms.
Limitations
- Regret bound depends on M = O(log L) samples per objective, and the optimism probability analysis relies on Gaussian anti-concentration with constant p=0.15.
- Empirical evaluation is limited to a single synthetic setting in the main text; other K, d, L settings are deferred to the appendix.
- Analysis assumes bounded contexts and parameters and sub-Gaussian noise; violation would scale the bound.
Experimental setup
Datasets: synthetic linear bandit instances (K=50 arms, d=5, L=4, T=10000, Gaussian noise sigma=1)
Benchmarks: synthetic multi-objective linear bandit (K=50, d=5, L=4)
Metrics: Pareto regret effective Pareto regret cumulative reward per objective
Baselines: MOL-UCB (MOGLM-UCB) MOL-epsilon-Greedy MOL-TS without optimistic sampling (M=1) PFIwR
Builds on: linear Thompson sampling (Agrawal and Goyal) ParetoUCB MOGLM-UCB optimistic sampling in combinatorial/assortment bandits
Closest papers by meaning
- Constrained Linear Thompson Sampling (NeurIPS 2025 · similarity 0.89)
- Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits (NeurIPS 2025 · similarity 0.89)
- Hierarchize Pareto Dominance in Multi-Objective Stochastic Linear Bandits (AAAI 2024 · similarity 0.89)
- Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits (ICLR 2025 · similarity 0.89)
- Constrained Pareto Set Identification with Bandit Feedback (ICML 2025 · similarity 0.89)
- Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.89)
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.