Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation

2024-12-22 · Hanrui Zhang, Yu Cheng, Vincent Conitzer

We study equilibrium computation with extensive-form correlation in two-player turn-taking stochastic games. Our main results are two-fold: (1) We give an algorithm for computing a Stackelberg extensive-form correlated equilibrium (SEFCE), which runs in time polynomial in the size of the game, as well as the number of bits required to encode each input number. (2) We give an efficient algorithm for approximately computing an optimal extensive-form correlated equilibrium (EFCE) up to machine precision, i.e., the algorithm achieves approximation error $\varepsilon$ in time polynomial in the size of the game, as well as $\log(1 / \varepsilon)$. Our algorithm for SEFCE is the first polynomial-time algorithm for equilibrium computation with commitment in such a general class of stochastic games. Existing algorithms for SEFCE typically make stronger assumptions such as no chance moves, and are designed for extensive-form games in the less succinct tree form. Our algorithm for approximately optimal EFCE is, to our knowledge, the first algorithm that achieves 3 desiderata simultaneously: approximate optimality, polylogarithmic dependency on the approximation error, and compatibility with stochastic games in the more succinct graph form. Existing algorithms achieve at most 2 of these desiderata, often also relying on additional technical assumptions.

📄 PDF Abstract BibTeX arXiv:2412.16934

Code (0)

등록된 구현이 없습니다.

Tasks

Form

On Bellman's Optimality Principle for zs-POSGs

2020-06-29 · Olivier Buffet, Jilles Dibangoye, Aurélien Delage, Abdallah Saffidine 외

Many non-trivial sequential decision-making problems are efficiently solved by relying on Bellman's optimality principle, i.e., exploiting the fact that sub-problems are nested recursively within the original problem. He…

Decision Making Heuristic Search Sequential Decision Making

The Complexity of Markov Equilibrium in Stochastic Games

2022-04-08 · Constantinos Daskalakis, Noah Golowich, Kaiqing Zhang

We show that computing approximate stationary Markov coarse correlated equilibria (CCE) in general-sum stochastic games is computationally intractable, even when there are two players, the game is turn-based, the discoun…

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

Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity

2019-08-29 · Aaron Sidford, Mengdi Wang, Lin F. Yang, Yinyu Ye

In this paper, we settle the sampling complexity of solving discounted two-player turn-based zero-sum stochastic games up to polylogarithmic factors. Given a stochastic game with discount factor $\gamma\in(0,1)$ we provi…

Q-Learning Reinforcement Learning

Experiments with Game Tree Search in Real-Time Strategy Games

2012-08-09 · Santiago Ontanon

Game tree search algorithms such as minimax have been used with enormous success in turn-based adversarial games such as Chess or Checkers. However, such algorithms cannot be directly applied to real-time strategy (RTS) …

Real-Time Strategy Games

Learning in Multi-Player Stochastic Games

2022-10-25 · William Brown

We consider the problem of simultaneous learning in stochastic games with many players in the finite-horizon setting. While the typical target solution for a stochastic game is a Nash equilibrium, this is intractable wit…