Safe Subgame Resolving for Extensive Form Correlated Equilibrium

• URL: http://arxiv.org/abs/2212.14317v1
• Date: Thu, 29 Dec 2022 14:20:48 GMT
• Title: Safe Subgame Resolving for Extensive Form Correlated Equilibrium
• Authors: Chun Kai Ling, Fei Fang
• Abstract summary: Correlated Equilibrium is a solution concept that is more general than Nash Equilibrium (NE) and can lead to better social welfare. We apply textitsubgame resolving, a technique extremely successful in finding NE in zero-sum games to solving general-sum EFCEs. Subgame resolving refines a correlation plan in an textitonline manner: instead of solving for the full game upfront, it only solves for strategies in subgames that are reached in actual play.
• Score: 47.155175336085364
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Correlated Equilibrium is a solution concept that is more general than Nash Equilibrium (NE) and can lead to outcomes with better social welfare. However, its natural extension to the sequential setting, the \textit{Extensive Form Correlated Equilibrium} (EFCE), requires a quadratic amount of space to solve, even in restricted settings without randomness in nature. To alleviate these concerns, we apply \textit{subgame resolving}, a technique extremely successful in finding NE in zero-sum games to solving general-sum EFCEs. Subgame resolving refines a correlation plan in an \textit{online} manner: instead of solving for the full game upfront, it only solves for strategies in subgames that are reached in actual play, resulting in significant computational gains. In this paper, we (i) lay out the foundations to quantify the quality of a refined strategy, in terms of the \textit{social welfare} and \textit{exploitability} of correlation plans, (ii) show that EFCEs possess a sufficient amount of independence between subgames to perform resolving efficiently, and (iii) provide two algorithms for resolving, one using linear programming and the other based on regret minimization. Both methods guarantee \textit{safety}, i.e., they will never be counterproductive. Our methods are the first time an online method has been applied to the correlated, general-sum setting.

Related papers

• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  We prove lower bounds for computing a near-optimal $T$-sparse CCE. In particular, we show that the inapproximability of maximum clique precludes attaining any non-trivial sparsity in time.
  arXiv  Detail & Related papers  (2024-11-04T00:34:56Z)
• 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)
• Function Approximation for Solving Stackelberg Equilibrium in Large Perfect Information Games [115.77438739169155]
  We propose learning the textitEnforceable Payoff Frontier (EPF) -- a generalization of the state value function for general-sum games. This is the first method that applies FA to the Stackelberg setting, allowing us to scale to much larger games.
  arXiv  Detail & Related papers  (2022-12-29T19:05:50Z)
• HSVI can solve zero-sum Partially Observable Stochastic Games [7.293053431456775]
  State-of-the-art methods for solving 2-player zero-sum imperfect games rely on linear programming or dynamic regret minimization. We propose a novel family of promising approaches complementing those relying on linear programming or iterative methods.
  arXiv  Detail & Related papers  (2022-10-26T11:41:57Z)
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
  We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games. We introduce a new algorithm for computing optimal equilibria in all three notions.
  arXiv  Detail & Related papers  (2022-03-14T15:21:18Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  In large two-player zero-sum imperfect-information games, modern extensions of counterfactual regret minimization (CFR) are currently the practical state of the art for computing a Nash equilibrium. We formalize an online learning setting in which the strategy space is not known to the agent. We give an efficient algorithm that achieves $O(T3/4)$ regret with high probability for that setting, even when the agent faces an adversarial environment.
  arXiv  Detail & Related papers  (2021-03-08T04:03:24Z)
• 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.