Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value

• URL: http://arxiv.org/abs/2311.00582v5
• Date: Sat, 24 Aug 2024 20:36:58 GMT
• Title: Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value
• Abstract summary: 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.
• Score: 15.671795887007383
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 so that a target deterministic or stochastic policy profile becomes the unique Markov perfect Nash equilibrium and has a value within a target range, in a way that minimizes the modification cost. 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. We propose an efficient algorithm that solves a convex optimization problem with linear constraints and then performs random perturbation to obtain a modification plan with a near-optimal cost. The code for our algorithm is available at https://github.com/YoungWu559/game-modification .

Related papers

• 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)
• Soft-Bellman Equilibrium in Affine Markov Games: Forward Solutions and Inverse Learning [37.176741793213694]
  We formulate a class of Markov games, termed affine Markov games, where an affine reward function couples the players' actions. We introduce a novel solution concept, the soft-Bellman equilibrium, where each player is boundedly rational and chooses a soft-Bellman policy. We then solve the inverse game problem of inferring the players' reward parameters from observed state-action trajectories via a projected-gradient algorithm.
  arXiv  Detail & Related papers  (2023-03-31T22:50:47Z)
• Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
  We study how to perturb the reward in a zero-sum Markov game with two players to induce a desirable Nash equilibrium, namely arbitrating. 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.
  arXiv  Detail & Related papers  (2023-02-20T16:05:04Z)
• 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)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  We show that the state-wise average policy of this algorithm converges to an approximate Nash equilibrium (NE) of the game. We extend this algorithm to multi-player general Markov Games and show a $mathcalwidetildeO(T-1/2)$ convergence rate to Correlated Equilibria (CCE)
  arXiv  Detail & Related papers  (2022-06-06T14:23:13Z)
• Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games [16.09467599829253]
  We study the problem of finding Nash equilibrium in a two-player zero-sum game. Our main contribution is to show that under proper choices of the regularization parameter, the gradient descents to the Nash equilibrium of the original unregularized problem.
  arXiv  Detail & Related papers  (2022-05-27T03:24:12Z)
• Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
  This paper considers two-player zero-sum finite-horizon Markov games with simultaneous moves. Provably efficient algorithms for both decoupled and coordinated settings are developed.
  arXiv  Detail & Related papers  (2021-07-30T15:25:13Z)
• 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.