Provably Efficient Algorithms for Multi-Objective Competitive RL
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Objective Reinforcement LearningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
This paper examines multiplayer symmetric constant-sum games with more than two players in a competitive setting, including examples like Mahjong, Poker, and various board and video games. In contrast to two-player zero-…
Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization
Constrained submodular optimization problems play a key role in the area of combinatorial optimization as they capture many NP-hard optimization problems. So far, Pareto optimization approaches using multi-objective form…
Combinatorial OptimizationEvolutionary AlgorithmsTS-RSR: A provably efficient approach for batch Bayesian Optimization
This paper presents a new approach for batch Bayesian Optimization (BO) called Thompson Sampling-Regret to Sigma Ratio directed sampling (TS-RSR), where we sample a new batch of actions by minimizing a Thompson Sampling …
Bayesian OptimizationThompson SamplingProvably Improved Context-Based Offline Meta-RL with Attention and Contrastive Learning
Meta-learning for offline reinforcement learning (OMRL) is an understudied problem with tremendous potential impact by enabling RL algorithms in many real-world applications. A popular solution to the problem is to infer…
Contrastive LearningMeta-Learningreinforcement-learningReinforcement Learning (RL)+1Convergence to Second-Order Stationarity for Non-negative Matrix Factorization: Provably and Concurrently
Non-negative matrix factorization (NMF) is a fundamental non-convex optimization problem with numerous applications in Machine Learning (music analysis, document clustering, speech-source separation etc). Despite having …
Clustering