Differentiable Arbitrating in Zero-sum Markov Games

2023-02-20 · Jing Wang, Meichen Song, Feng Gao, Boyi Liu, Zhaoran Wang, Yi Wu

We initiate the study of how to perturb the reward in a zero-sum Markov game with two players to induce a desirable Nash equilibrium, namely arbitrating. Such a problem admits a bi-level optimization formulation. The lower level requires solving the Nash equilibrium under a given reward function, which makes the overall problem challenging to optimize in an end-to-end way. We propose a backpropagation scheme that differentiates through the Nash equilibrium, which provides the gradient feedback for the upper level. In particular, our method only requires a black-box solver for the (regularized) Nash equilibrium (NE). We develop the convergence analysis for the proposed framework with proper black-box NE solvers and demonstrate the empirical successes in two multi-agent reinforcement learning (MARL) environments.

📄 PDF Abstract BibTeX arXiv:2302.10058

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)

Multi-Player Zero-Sum Markov Games with Networked Separable Interactions

2023-07-13 · NeurIPS 2023 11 · Chanwoo Park, Kaiqing Zhang, Asuman Ozdaglar

We study a new class of Markov games, \emph(multi-player) zero-sum Markov Games} with \emph{Networked separable interactions} (zero-sum NMGs), to model the local interaction structure in non-cooperative multi-agent seque…

Decision Making Sequential Decision Making

Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games

2021-02-17 · Yulai Zhao, Yuandong Tian, Jason D. Lee, Simon S. Du

Policy-based methods with function approximation are widely used for solving two-player zero-sum games with large state and/or action spaces. However, it remains elusive how to obtain optimization and statistical guarant…

Policy Gradient Methods Vocal Bursts Valence Prediction

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…

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