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

• URL: http://arxiv.org/abs/2403.07933v1
• Date: Mon, 4 Mar 2024 12:48:25 GMT
• Title: Corruption-Robust Offline Two-Player Zero-Sum Markov Games
• Abstract summary: We study data corruption robustness in offline two-player zero-sum Markov games. We consider this problem in linear Markov games under different degrees of data coverage and corruption.
• Score: 23.530166315532828
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 is to identify an approximate Nash Equilibrium policy pair from the corrupted data. We consider this problem in linear Markov games under different degrees of data coverage and corruption. We start by providing an information-theoretic lower bound on the suboptimality gap of any learner. Next, we propose robust versions of the Pessimistic Minimax Value Iteration algorithm, both under coverage on the corrupted data and under coverage only on the clean data, and show that they achieve (near)-optimal suboptimality gap bounds with respect to $\epsilon$. We note that we are the first to provide such a characterization of the problem of learning approximate Nash Equilibrium policies in offline two-player zero-sum Markov games under data corruption.

Related papers

• Corruption-robust Offline Multi-agent Reinforcement Learning From Human Feedback [26.662444975280792]
  We consider robustness against data corruption in offline multi-agent reinforcement learning from human feedback.<n>We model the problem using the framework of linear Markov games.<n>To the best of our knowledge, this is the first systematic treatment of data corruption in offline MARLHF.
  arXiv  Detail & Related papers  (2026-03-30T11:03:36Z)
• Two-Player Zero-Sum Games with Bandit Feedback [6.66618805642802]
  We study a two-player zero-sum game in which the row player aims to maximize their payoff against an adversarial column player.<n>We propose three algorithms based on the Explore-Then-Commit framework.
  arXiv  Detail & Related papers  (2025-06-17T13:46:32Z)
• Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value [15.671795887007383]
  We study the game modification problem, where a benevolent game designer or a malevolent adversary modifies the reward function of a zero-sum Markov game. We characterize the set of policy profiles that can be installed as the unique equilibrium of a game and establish sufficient and necessary conditions for successful installation.
  arXiv  Detail & Related papers  (2023-11-01T15:27:29Z)
• Corruption-Robust Offline Reinforcement Learning with General Function Approximation [60.91257031278004]
  We investigate the problem of corruption in offline reinforcement learning (RL) with general function approximation. Our goal is to find a policy that is robust to such corruption and minimizes the suboptimality gap with respect to the optimal policy for the uncorrupted Markov decision processes (MDPs)
  arXiv  Detail & Related papers  (2023-10-23T04:07:26Z)
• Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning [105.7510838453122]
  We examine online safe multi-agent reinforcement learning using constrained Markov games. We develop an upper confidence reinforcement learning algorithm to solve this Lagrangian problem. Our algorithm updates the minimax decision primal variables via online mirror descent and the dual variable via projected gradient step.
  arXiv  Detail & Related papers  (2023-05-31T22:09:24Z)
• Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback [49.1061436241109]
  We focus on developing an algorithm that is uncoupled, convergent, and rational, with non-asymptotic convergence rates. Our algorithm is related to [Chen et al., 2021, Cen et al., 2021] and also builds on the entropy regularization technique.
  arXiv  Detail & Related papers  (2023-03-05T18:08:54Z)
• Offline Learning in Markov Games with General Function Approximation [22.2472618685325]
  We study offline multi-agent reinforcement learning (RL) in Markov games. We provide the first framework for sample-efficient offline learning in Markov games.
  arXiv  Detail & Related papers  (2023-02-06T05:22:27Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  We study the linear contextual bandit problem in the presence of adversarial corruption. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$.
  arXiv  Detail & Related papers  (2021-10-25T02:53:24Z)
• Corruption-Robust Offline Reinforcement Learning [19.300465320692066]
  We study adversarial robustness in offline reinforcement learning. We show that a worst-case $Omega(depsilon) optimality gap is unavoidable. We propose robust variants of the Least-Square Value Iteration (LSVI) algorithm.
  arXiv  Detail & Related papers  (2021-06-11T22:41:53Z)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  We study reinforcement learning for two-player zero-sum Markov games with simultaneous moves. We propose an algorithm Nash-UCRL-VTR based on the principle "Optimism-in-Face-of-Uncertainty" We show that Nash-UCRL-VTR can provably achieve an $tildeO(dHsqrtT)$ regret, where $d$ is the linear function dimension.
  arXiv  Detail & Related papers  (2021-02-15T09:09:16Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret.
  arXiv  Detail & Related papers  (2020-02-17T17:04:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.