AIConfPaper
← Search

Brian Hu Zhang

17 accepted papers

2026

Convergence of Regret Matching in Potential Games and Constrained Optimization

Ioannis Anagnostides, Emanuel Tewolde, Brian Hu Zhang, Ioannis Panageas, Vincent Conitzer, Tuomas Sandholm
ICLR 2026poster

Regret matching (RM)---and its modern variants---is a foundational online algorithm that has been at the heart of many AI breakthrough results in solving benchmark zero-sum games, such as poker. Yet, surprisingly little is known so far in theory about its convergence beyond two-player zero-sum games…

Cited by 0Source ↗Scholar ↗
2026

General search techniques without common knowledge for imperfect-information games, and application to superhuman Fog of War chess

Brian Hu Zhang, Tuomas Sandholm
ICLR 2026poster

Since the advent of AI, games have served as progress benchmarks. Meanwhile, imperfect-information variants of chess have existed for over a century, present extreme challenges, and have been the focus of decades of AI research. Beyond calculation needed in regular chess, they require reasoning abou…

Cited by 0Source ↗Scholar ↗
2025

Computing Game Symmetries and Equilibria That Respect Them

Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Tuomas Sandholm, Vincent Conitzer
AAAI 2025technical

Strategic interactions can be represented more concisely, and analyzed and solved more efficiently, if we are aware of the symmetries within the multiagent system. Symmetries also have conceptual implications, for example for equilibrium selection. We study the computational complexity of identifyin…

Cited by 1Source ↗PDF ↗Scholar ↗
2025

Expected Variational Inequalities

Brian Hu Zhang, Ioannis Anagnostides, Emanuel Tewolde, Ratip Emin Berker, Gabriele Farina, Vincent Conitzer +1
ICML 2025oral

*Variational inequalities (VIs)* encompass many fundamental problems in diverse areas ranging from engineering to economics and machine learning. However, their considerable expressivity comes at the cost of computational intractability. In this paper, we introduce and analyze a natural relaxation—w…

Cited by 1Source ↗PDF ↗Scholar ↗
2024

Efficient $\Phi$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games

Brian Hu Zhang, Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm
NeurIPS 2024poster

Recent breakthrough results by Dagan, Daskalakis, Fishelson and Golowich [2023] and Peng and Rubinstein [2023] established an efficient algorithm attaining at most $\epsilon$ swap regret over extensive-form strategy spaces of dimension $N$ in $N^{\tilde O(1/\epsilon)}$ rounds. On the other extreme,…

Cited by 11Source ↗PDF ↗Scholar ↗
2024

Imperfect-Recall Games: Equilibrium Concepts and Their Complexity

Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Manolis Zampetakis, Tuomas Sandholm, Paul Goldberg +1
IJCAI 2024poster

We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. An example is the absentminded driver game, as well as team games in which the members have limited communication capabilities. In the framework of extensive-form games with…

Cited by 6Source ↗PDF ↗Scholar ↗
2024

Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games

Brian Hu Zhang, Gabriele Farina, Tuomas Sandholm
ICLR 2024poster

A recent paper by Farina and Pipis (2023) established the existence of uncoupled no-linear-swap regret dynamics with polynomial-time iterations in extensive-form games. The equilibrium points reached by these dynamics, known as linear correlated equilibria, are currently the tightest known relaxatio…

Cited by 3Source ↗PDF ↗Scholar ↗
2024

On the Outcome Equivalence of Extensive-Form and Behavioral Correlated Equilibria

Brian Hu Zhang, Tuomas Sandholm
AAAI 2024technical

We investigate two notions of correlated equilibrium for extensive-form games: the extensive-form correlated equilibrium (EFCE) and the behavioral correlated equilibrium (BCE). We show that the two are outcome-equivalent, in the sense that every outcome distribution achievable under one notion is ac…

Cited by 2Source ↗PDF ↗Scholar ↗
2023

Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games

Brian Hu Zhang, Gabriele Farina, Ioannis Anagnostides, Federico Cacciamani, Stephen Marcus McAleer, Andreas Alexander Haupt +4
NeurIPS 2023poster

We introduce a new approach for computing optimal equilibria via learning in games. It applies to extensive-form settings with any number of players, including mechanism design, information design, and solution concepts such as correlated, communication, and certification equilibria. We observe that…

Cited by 24Source ↗PDF ↗Scholar ↗
2023

Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimization

Brian Hu Zhang, Gabriele Farina, Tuomas Sandholm
ICML 2023poster

A classic result in the theory of extensive-form games asserts that the set of strategies available to any perfect-recall player is strategically equivalent to a low-dimensional convex polytope, called the *sequence-form polytope*. Online convex optimization tools operating on this polytope are the…

Cited by 20Source ↗PDF ↗Scholar ↗
2022

Subgame Solving in Adversarial Team Games

Brian Hu Zhang, Luca Carminati, Federico Cacciamani, Gabriele Farina, Pierriccardo Olivieri, Nicola Gatti +1
NeurIPS 2022accept

In adversarial team games, a team of players sequentially faces a team of adversaries. These games are the simplest setting with multiple players where cooperation and competition coexist, and it is known that the information asymmetry among the team members makes equilibrium approximation computati…

Cited by 13Source ↗PDF ↗Scholar ↗
2022

Team Correlated Equilibria in Zero-Sum Extensive-Form Games via Tree Decompositions

Brian Hu Zhang, Tuomas Sandholm
AAAI 2022technical

Despite the many recent practical and theoretical breakthroughs in computational game theory, equilibrium finding in extensive-form team games remains a significant challenge. While NP-hard in the worst case, there are provably efficient algorithms for certain families of team game. In particular, i…

Cited by 31Source ↗PDF ↗Scholar ↗
2021

Finding and Certifying (Near-)Optimal Strategies in Black-Box Extensive-Form Games

Brian Hu Zhang, Tuomas Sandholm
AAAI 2021technical

Often---for example in war games, strategy video games, and financial simulations---the game is given to us only as a black-box simulator in which we can play it. In these settings, since the game may have unknown nature action distributions (from which we can only obtain samples) and/or be too larg…

Cited by 19Source ↗PDF ↗Scholar ↗