# Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2020.

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

- [A Simple Reward-free Approach to Constrained Reinforcement Learning](https://mlsanity.com/paper/2107.05216/) (2021)
- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2206.05357/) (2022)
- [Provably Feedback-Efficient Reinforcement Learning via Active Reward Learning](https://mlsanity.com/paper/2304.08944/) (2023)
- [Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2407.17466/) (2024)
- [Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs](https://mlsanity.com/paper/2303.10859/) (2023)
- [Gap-Dependent Unsupervised Exploration for Reinforcement Learning](https://mlsanity.com/paper/2108.05439/) (2021)
- [Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approach](https://mlsanity.com/paper/2202.12797/) (2022)
- [Adaptive Multi-Goal Exploration](https://mlsanity.com/paper/2111.12045/) (2021)
- [Provably Efficient Lifelong Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2206.00270/) (2022)
- [Scaling Distributed Multi-task Reinforcement Learning with Experience Sharing](https://mlsanity.com/paper/2307.05834/) (2023)

## Abstract (arXiv)

In this paper we consider multi-objective reinforcement learning where the objectives are balanced using preferences. In practice, the preferences are often given in an adversarial manner, e.g., customers can be picky in many applications. We formalize this problem as an episodic learning problem on a Markov decision process, where transitions are unknown and a reward function is the inner product of a preference vector with pre-specified multi-objective reward functions. We consider two settings. In the online setting, the agent receives a (adversarial) preference every episode and proposes policies to interact with the environment. We provide a model-based algorithm that achieves a nearly minimax optimal regret bound widetildeObigl(√mind,S· H2 SAKbigr), where d is the number of objectives, S is the number of states, A is the number of actions, H is the length of the horizon, and K is the number of episodes. Furthermore, we consider preference-free exploration, i.e., the agent first interacts with the environment without specifying any preference and then is able to accommodate arbitrary preference vector up to ε error. Our proposed algorithm is provably efficient with a nearly optimal trajectory complexity widetildeObigl(mind,S· H3 SA/ε2bigr). This result partly resolves an open problem raised by citetjin2020reward.