mlsanityData to 7 Oct 2026

Provably Efficient Algorithms for Multi-Objective Competitive RL

arXiv 2102.03192 ↗First posted 5 Feb 2021cs.LGcited by 20

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). Builds on 25 of its 38 references that are in the map. First posted on arXiv 5 Feb 2021.

Builds on

25 of 38 references.

References · 25

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  4. 2013Bandits with Knapsackscited by 163
  5. 2020Exploration-Exploitation in Constrained MDPscited by 146
  6. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  7. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  8. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  9. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  10. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  11. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  12. 2014Bandits with concave rewards and convex knapsackscited by 83
13 more
  1. 2015Adaptive Algorithms for Online Convex Optimization with Long-term Constraintscited by 65
  2. 2019Reinforcement Learning with Convex Constraintscited by 57
  3. 2018Online convex optimization for cumulative constraintscited by 47
  4. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  5. 2014Near-optimal Reinforcement Learning in Factored MDPscited by 41
  6. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 33
  7. 2020Learning in Markov Decision Processes under Constraintscited by 20
  8. 2020Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RLcited by 16
  9. 2020Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processescited by 13
  10. 2020Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learningcited by 11
  11. 2014Approachability in unknown games: Online learning meets multi-objective optimizationcited by 10
  12. 2015An Online Convex Optimization Approach to Blackwell's Approachabilitycited by 10
  13. 2020Online Learning in Unknown Markov Gamescited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 6; 2023: 4; 2024: 3; 2025: 2; 2026: 2.

20 papers.

Sort:

By area:

  1. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  2. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 36
  3. 2022Challenging Common Assumptions in Convex Reinforcement Learningcited by 29
  4. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 28
  5. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  6. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  7. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  8. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  9. 2024Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learningcited by 13
  10. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
  11. 2023Provably Safe Reinforcement Learning with Step-wise Violation Constraintscited by 10
  12. 2022A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDPcited by 5
8 more
  1. 2023Pseudonorm Approachability and Applications to Regret Minimizationcited by 5
  2. 2024Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPscited by 4
  3. 2025Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPscited by 3
  4. 2024Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learningcited by 2
  5. 2025Risk-Averse Constrained Reinforcement Learning with Optimized Certainty Equivalentscited by 1
  6. 2026Near-Optimal Sample Complexity for Online Constrained MDPscited by 1
  7. 2023Time-Dependent Blackwell Approachability and Application to Absorbing Gamescited by 0
  8. 2026The Theorems of Dr. David Blackwell and Their Contributions to Artificial Intelligencecited by 0