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

Abstract

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 $\tilde{\mathcal{O}}\left(\sqrt{\min \{d,S\}\cdot H^{2}SAK}\right)$, 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 $\epsilon$ error. Our proposed algorithm is provably efficient with a nearly optimal trajectory complexity $\tilde{\mathcal{O}}(\min \{d,S\}\cdot H^{3}SA/{\epsilon }^2)$. This result partly resolves an open problem raised by \citet{jin2020reward}.

arXiv commentNeurIPS 2021 Camera Ready Version

References in corpus (15)

• Empirical Bernstein Bounds and Sample Variance Penalization
• Multi-Objective Deep Reinforcement Learning
• Safe Reinforcement Learning in Constrained Markov Decision Processes
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Fast active learning for pure exploration in reinforcement learning
• Exploration-Exploitation in Constrained MDPs
• Reward-Free Exploration for Reinforcement Learning
• Task-agnostic Exploration in Reinforcement Learning
• Constrained episodic reinforcement learning in concave-convex and knapsack settings
• Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewards
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Adaptive Reward-Free Exploration

Cited by in corpus (4)

• A Simple Reward-free Approach to Constrained Reinforcement Learning
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• Provably Efficient Algorithms for Multi-Objective Competitive RL
• Adaptive Multi-Goal Exploration