research
∙
08/30/2023
Hidden-Role Games: Equilibrium Concepts and Computation
In this paper, we study the class of games known as hidden-role games in...
share
research
∙
08/16/2023
Planning in the imagination: High-level planning on learned abstract search spaces
We propose a new method, called PiZero, that gives an agent the ability ...
research
∙
07/22/2023
Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbations
Robust reinforcement learning (RL) seeks to train policies that can perf...
research
∙
06/08/2023
Steering No-Regret Learners to Optimal Equilibria
We consider the problem of steering no-regret-learning agents to play de...
research
∙
06/08/2023
Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games
We introduce a new approach for computing optimal equilibria via learnin...
research
∙
02/28/2023
Bicriteria Multidimensional Mechanism Design with Side Information
We develop a versatile new methodology for multidimensional mechanism de...
research
∙
01/26/2023
On the Convergence of No-Regret Learning Dynamics in Time-Varying Games
Most of the literature on learning in games has focused on the restricti...
research
∙
01/20/2023
Computing equilibria by minimizing exploitability with best-response ensembles
In this paper, we study the problem of computing an approximate Nash equ...
research
∙
11/29/2022
Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks
We study the problem of computing an approximate Nash equilibrium of con...
research
∙
09/28/2022
Meta-Learning in Games
In the literature on game-theoretic equilibrium finding, focus has mainl...
research
∙
08/20/2022
Near-Optimal Φ-Regret Learning in Extensive-Form Games
In this paper, we establish efficient and uncoupled learning dynamics so...
research
∙
07/13/2022
Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games
In competitive two-agent environments, deep reinforcement learning (RL) ...
research
∙
06/30/2022
Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games
For common notions of correlated equilibrium in extensive-form games, co...
research
∙
06/17/2022
Near-Optimal No-Regret Learning for General Convex Games
A recent line of work has established uncoupled learning dynamics such t...
research
∙
06/08/2022
ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret
Recent techniques for approximating Nash equilibria in very large games ...
research
∙
04/25/2022
Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games
In this paper we establish efficient and uncoupled learning dynamics so ...
research
∙
04/15/2022
Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts
The incorporation of cutting planes within the branch-and-bound algorith...
research
∙
03/22/2022
Optimistic Mirror Descent Either Converges to Nash or to Strong Coarse Correlated Equilibria in Bimatrix Games
We show that, for any sufficiently small fixed ϵ > 0, when both players ...
research
∙
03/22/2022
On Last-Iterate Convergence Beyond Zero-Sum Games
Most existing results about last-iterate convergence of learning dynamic...
research
∙
03/14/2022
Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation
We study the problem of finding optimal correlated equilibria of various...
research
∙
02/11/2022
Faster No-Regret Learning Dynamics for Extensive-Form Correlated and Coarse Correlated Equilibria
A recent emerging trend in the literature on learning in games has been ...
research
∙
02/06/2022
Differentiable Economics for Randomized Affine Maximizer Auctions
A recent approach to automated mechanism design, differentiable economic...
research
∙
02/01/2022
Team Belief DAG Form: A Concise Representation for Team-Correlated Game-Theoretic Decision Making
In this paper, we introduce a new representation for team-coordinated ga...
research
∙
01/19/2022
Anytime PSRO for Two-Player Zero-Sum Games
Policy space response oracles (PSRO) is a multi-agent reinforcement lear...
research
∙
12/07/2021
Fast Payoff Matrix Sparsification Techniques for Structured Extensive-Form Games
The practical scalability of many optimization algorithms for large exte...
research
∙
11/18/2021
Improved Learning Bounds for Branch-and-Cut
Branch-and-cut is the most widely used algorithm for solving integer pro...
research
∙
11/11/2021
Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games
Recently, Daskalakis, Fishelson, and Golowich (DFG) (NeurIPS`21) showed ...
research
∙
09/16/2021
Efficient Decentralized Learning Dynamics for Extensive-Form Coarse Correlated Equilibrium: No Expensive Computation of Stationary Distributions Required
While in two-player zero-sum games the Nash equilibrium is a well-establ...
research
∙
09/11/2021
Team Correlated Equilibria in Zero-Sum Extensive-Form Games via Tree Decompositions
Despite the many recent practical and theoretical breakthroughs in compu...
research
∙
06/10/2021
Subgame solving without common knowledge
In imperfect-information games, subgame solving is significantly more ch...
research
∙
06/08/2021
Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond
Cutting-plane methods have enabled remarkable successes in integer progr...
research
∙
05/27/2021
Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria
We study the application of iterative first-order methods to the problem...
research
∙
03/08/2021
Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games
Tree-form sequential decision making (TFSDM) extends classical one-shot ...
research
∙
03/08/2021
Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games
Regret minimization has proved to be a versatile tool for tree-form sequ...
research
∙
12/24/2020
Generalization in portfolio-based algorithm selection
Portfolio-based algorithm selection has seen tremendous practical succes...
research
∙
10/22/2020
Improving Policy-Constrained Kidney Exchange via Pre-Screening
In barter exchanges, participants swap goods with one another without ex...
research
∙
09/21/2020
Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games
We focus on the problem of finding an optimal strategy for a team of two...
research
∙
09/15/2020
Finding and Certifying (Near-)Optimal Strategies in Black-Box Extensive-Form Games
Often – for example in war games, strategy video games, and financial si...
research
∙
09/09/2020
Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond
Unlike normal-form games, where correlated equilibria have been studied ...
research
∙
07/28/2020
Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent
Blackwell approachability is a framework for reasoning about repeated ga...
research
∙
06/29/2020
Small Nash Equilibrium Certificates in Very Large Games
In many game settings, the game is not explicitly given but is only acce...
research
∙
06/21/2020
Refined bounds for algorithm configuration: The knife-edge of dual class approximability
Automating algorithm configuration is growing increasingly necessary as ...
research
∙
06/05/2020
Sparsified Linear Programming for Zero-Sum Equilibrium Finding
Computational equilibrium finding in large zero-sum extensive-form imper...
research
∙
02/24/2020
Efficient exploration of zero-sum stochastic games
We investigate the increasingly important and common game-solving settin...
research
∙
02/19/2020
Stochastic Regret Minimization in Extensive-Form Games
Monte-Carlo counterfactual regret minimization (MCCFR) is the state-of-t...
research
∙
10/28/2019
Efficient Regret Minimization Algorithm for Extensive-Form Correlated Equilibrium
Self-play methods based on regret minimization have become the state of ...
research
∙
10/24/2019
Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions
We study the performance of optimistic regret-minimization algorithms fo...
research
∙
08/26/2019
Coarse Correlation in Extensive-Form Games
Coarse correlation models strategic interactions of rational agents comp...
research
∙
08/08/2019
How much data is sufficient to learn high-performing algorithms?
Algorithms for scientific analysis typically have tunable parameters tha...
research
∙
05/29/2019