7 papers · 1 filter
When Are We Near Nash? Certifying Solutions in General-Sum Games
Boning Li, Longbo Huang
Heuristic solvers for general-sum extensive-form games produce a stream of iterates, and practice reports the NashGap of the returned profile. We ask what a solver can know about i…
Why Alternation Speeds Up Counterfactual Regret Minimization?
Boning Li, Longbo Huang
Solving imperfect-information games at scale rests on counterfactual regret minimization with the regret matching (RM) update, and a seemingly minor implementation choi…
AV-AIVAT: 74x Cheaper Agent Evaluation with Certified Anytime-Valid Stopping in Imperfect-Information Games
Boning Li, Yu Chen, Longbo Huang
Deciding which of two agents is stronger means playing games until skill outweighs luck, and every game costs money, model inference, or expert time. Since the number of games need…
Agents That Certify Their Own Exploits: Confidence-Scheduled Restricted Responses for Safe Opponent Exploitation
Boning Li, Longbo Huang
An agent playing a Nash-equilibrium strategy in a two-player zero-sum imperfect-information game secures the game value but forfeits the additional value offered by a flawed oppone…
Correlated Chance Sampling for Monte Carlo Counterfactual Regret Minimization
Boning Li, Yu Chen, Longbo Huang
Monte Carlo Counterfactual Regret Minimization (MCCFR) repeatedly allocates chance outcomes while its strategy evolves, yet standard sampling draws those outcomes independently on…
Real-Time Parallel Counterfactual Regret Minimization
Boning Li, Longbo Huang
Counterfactual Regret Minimization (CFR) is the dominant algorithmic family for solving large imperfect-information games, underpinning breakthroughs such as Libratus and Pluribus…
RL-CFR: Improving Action Abstraction for Imperfect Information Extensive-Form Games with Reinforcement Learning
Boning Li, Zhixuan Fang, Longbo Huang
Effective action abstraction is crucial in tackling challenges associated with large action spaces in Imperfect Information Extensive-Form Games (IIEFGs). However, due to the vast…