Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games

2022-06-08 · Yuling Yan, Gen Li, Yuxin Chen, Jianqing Fan

This paper makes progress towards learning Nash equilibria in two-player zero-sum Markov games from offline data. Specifically, consider a $\gamma$-discounted infinite-horizon Markov game with $S$ states, where the max-player has $A$ actions and the min-player has $B$ actions. We propose a pessimistic model-based algorithm with Bernstein-style lower confidence bounds -- called VI-LCB-Game -- that provably finds an $\varepsilon$-approximate Nash equilibrium with a sample complexity no larger than $\frac{C_{\mathsf{clipped}}^{\star}S(A+B)}{(1-\gamma)^{3}\varepsilon^{2}}$ (up to some log factor). Here, $C_{\mathsf{clipped}}^{\star}$ is some unilateral clipped concentrability coefficient that reflects the coverage and distribution shift of the available data (vis-\`a-vis the target data), and the target accuracy $\varepsilon$ can be any value within $\big(0,\frac{1}{1-\gamma}\big]$. Our sample complexity bound strengthens prior art by a factor of $\min\{A,B\}$, achieving minimax optimality for the entire $\varepsilon$-range. An appealing feature of our result lies in algorithmic simplicity, which reveals the unnecessity of variance reduction and sample splitting in achieving sample optimality.

📄 PDF Abstract BibTeX arXiv:2206.04044

Code (0)

등록된 구현이 없습니다.

Tasks

Model-based Reinforcement Learningreinforcement-learning Reinforcement Learning (RL)

When is Offline Two-Player Zero-Sum Markov Game Solvable?

2022-01-10 · Qiwen Cui, Simon S. Du

We study what dataset assumption permits solving offline two-player zero-sum Markov games. In stark contrast to the offline single-agent Markov decision process, we show that the single strategy concentration assumption …

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)Vocal Bursts Valence Prediction

Data Poisoning to Fake a Nash Equilibrium in Markov Games

2023-06-13 · Young Wu, Jeremy McMahan, Xiaojin Zhu, Qiaomin Xie

We characterize offline data poisoning attacks on Multi-Agent Reinforcement Learning (MARL), where an attacker may change a data set in an attempt to install a (potentially fictitious) unique Markov-perfect Nash equilibr…

Data Poisoning Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning

Corruption-Robust Offline Two-Player Zero-Sum Markov Games

2024-03-04 · Andi Nika, Debmalya Mandal, Adish Singla, Goran Radanović

We study data corruption robustness in offline two-player zero-sum Markov games. Given a dataset of realized trajectories of two players, an adversary is allowed to modify an $\epsilon$-fraction of it. The learner's goal…

Offline Learning in Markov Games with General Function Approximation

2023-02-06 · Yuheng Zhang, Yu Bai, Nan Jiang

We study offline multi-agent reinforcement learning (RL) in Markov games, where the goal is to learn an approximate equilibrium -- such as Nash equilibrium and (Coarse) Correlated Equilibrium -- from an offline dataset p…

Multi-agent Reinforcement Learning Reinforcement Learning (RL)

Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game

2022-05-31 · Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen 외

Offline reinforcement learning (RL) aims at learning an optimal strategy using a pre-collected dataset without further interactions with the environment. While various algorithms have been proposed for offline RL in the …

Offline RL Reinforcement Learning (RL)