Research map / Learning theory and algorithms / Submodular and game algorithms

Efficient Online Pruning and Abstraction for Imperfect Information Extensive-Form Games

ICLR 2025 · Learning theory and algorithms › Submodular and game algorithms · approach: Zero-sum game learning dynamics

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes an online pruning and abstraction method for large imperfect-information extensive-form games that integrates with counterfactual regret minimization to compute approximate equilibria efficiently.

Problem

Computing approximate equilibrium strategies in large imperfect-information extensive-form games is hard because the game tree grows exponentially, and existing pruning and abstraction methods are difficult to integrate seamlessly with CFR.

Approach

Performs pruning and abstraction online during CFR-based equilibrium computation rather than as a fixed preprocessing step, addressing the difficulty of combining pruning with regret minimization. Only the abstract was available, so details beyond this are not stated.

Experimental setup

Builds on: counterfactual regret minimization

Closest papers by meaning

• Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning (ICML 2017 · similarity 0.91)
• Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions (NeurIPS 2019 · similarity 0.90)
• Efficient Regret Minimization Algorithm for Extensive-Form Correlated Equilibrium (NeurIPS 2019 · similarity 0.90)
• Learning Imperfect Information Extensive-form Games with Last-iterate Convergence under Bandit Feedback (ICML 2025 · similarity 0.89)
• Extensive-Form Game Solving via Blackwell Approachability on Treeplexes (NeurIPS 2024 · similarity 0.89)
• Accelerating Nash Equilibrium Convergence in Monte Carlo Settings Through Counterfactual Value Based Fictitious Play (NeurIPS 2024 · similarity 0.89)