Provably Efficient Algorithms for Multi-Objective Competitive RL
arXiv:2102.03192
Abstract
We study multi-objective reinforcement learning (RL) where an agent's reward is represented as a vector. In settings where an agent competes against opponents, its performance is measured by the distance of its average return vector to a target set. We develop statistically and computationally efficient algorithms to approach the associated target set. Our results extend Blackwell's approachability theorem (Blackwell, 1956) to tabular RL, where strategic exploration becomes essential. The algorithms presented are adaptive; their guarantees hold even without Blackwell's approachability condition. If the opponents use fixed policies, we give an improved rate of approaching the target set while also tackling the more ambitious goal of simultaneously minimizing a scalar cost function. We discuss our analysis for this special case by relating our results to previous works on constrained RL. To our knowledge, this work provides the first provably efficient algorithms for vector-valued Markov games and our theoretical guarantees are near-optimal.
References in corpus (14)
- Empirical Bernstein Bounds and Sample Variance Penalization
- Bandits with Knapsacks
- Online convex optimization for cumulative constraints
- Provable Self-Play Algorithms for Competitive Reinforcement Learning
- Near-optimal Reinforcement Learning in Factored MDPs
- Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
- Exploration-Exploitation in Constrained MDPs
- Reward-Free Exploration for Reinforcement Learning
- Near-Optimal Reinforcement Learning with Self-Play
- Constrained episodic reinforcement learning in concave-convex and knapsack settings
- Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss
- Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
- Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited
- Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL