# Multi-objective Contextual Bandit Problem with Similarity Information

arXiv: https://arxiv.org/abs/1803.04015 · HTML: https://mlsanity.com/paper/1803.04015/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Mar 2018.

## Built on by (most cited first, 21 of 21)

- [A Practical Guide to Multi-Objective Reinforcement Learning and Planning](https://mlsanity.com/paper/2103.09568/) (2021)
- [Almost Optimal Variance-Constrained Best Arm Identification](https://mlsanity.com/paper/2201.10142/) (2022)
- [Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2407.17466/) (2024)
- [Learning Personalized Decision Support Policies](https://mlsanity.com/paper/2304.06701/) (2023)
- [Vector Optimization with Stochastic Bandit Feedback](https://mlsanity.com/paper/2110.12311/) (2021)
- [On Generalization Across Environments In Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2503.00799/) (2025)
- [Integrating Reward Maximization and Population Estimation: Sequential Decision-Making for Internal Revenue Service Audit Selection](https://mlsanity.com/paper/2204.11910/) (2022)
- [Preference-based Pure Exploration](https://mlsanity.com/paper/2412.02988/) (2024)
- [Provably Efficient Multi-Objective Bandit Algorithms under Preference-Centric Customization](https://mlsanity.com/paper/2502.13457/) (2025)
- [Thompson Sampling for Multi-Objective Linear Contextual Bandit](https://mlsanity.com/paper/2512.00930/) (2025)
- [Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits](https://mlsanity.com/paper/2608.04324/) (2026)
- [The Digital Transformation in Health: How AI Can Improve the Performance of Health Systems](https://mlsanity.com/paper/2409.16098/) (2024)
- [Stochastic Multi-Objective Multi-Armed Bandits: Regret Definition and Algorithm](https://mlsanity.com/paper/2506.13125/) (2025)
- [Robust Pareto Set Identification with Contaminated Bandit Feedback](https://mlsanity.com/paper/2206.02666/) (2022)
- [Online Pareto-Optimal Decision-Making for Complex Tasks using Active Inference](https://mlsanity.com/paper/2406.11984/) (2024)
- [Unlocking the Potential of Global Human Expertise](https://mlsanity.com/paper/2411.00156/) (2024)
- [Vector preference-based contextual bandits under distributional shifts](https://mlsanity.com/paper/2508.15966/) (2025)
- [Are Stochastic Multi-objective Bandits Harder than Single-objective Bandits?](https://mlsanity.com/paper/2604.07096/) (2026)
- [Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries](https://mlsanity.com/paper/2606.08410/) (2026)
- [Few-for-Many Best-Arm Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2610.16840/) (2026)
- [When More Objectives Make Identification Easier: The Role of Preferences and Feedback](https://mlsanity.com/paper/2610.18577/) (2026)

## Abstract (arXiv)

In this paper we propose the multi-objective contextual bandit problem with similarity information. This problem extends the classical contextual bandit problem with similarity information by introducing multiple and possibly conflicting objectives. Since the best arm in each objective can be different given the context, learning the best arm based on a single objective can jeopardize the rewards obtained from the other objectives. In order to evaluate the performance of the learner in this setup, we use a performance metric called the contextual Pareto regret. Essentially, the contextual Pareto regret is the sum of the distances of the arms chosen by the learner to the context dependent Pareto front. For this problem, we develop a new online learning algorithm called Pareto Contextual Zooming (PCZ), which exploits the idea of contextual zooming to learn the arms that are close to the Pareto front for each observed context by adaptively partitioning the joint context-arm set according to the observed rewards and locations of the context-arm pairs selected in the past. Then, we prove that PCZ achieves tilde O (T(1+dp)/(2+dp)) Pareto regret where dp is the Pareto zooming dimension that depends on the size of the set of near-optimal context-arm pairs. Moreover, we show that this regret bound is nearly optimal by providing an almost matching Omega (T(1+dp)/(2+dp)) lower bound.