Equilibrium Computation in Extensive-Form Games with Stochastic Action Sets
For game theory and multi-agent AI, this work addresses a realistic but previously unmodeled stochasticity in action availability, offering both theoretical foundations and a practical algorithm.
This paper introduces Extensive-Form Games with Stochastic Action Sets (EFGSAS), a model where actions may be stochastically unavailable, and shows that while naive representation can be exponential, under an independence assumption compact strategies exist. It presents SI-CFR, an algorithm that converges to Nash equilibria with high probability in two-player zero-sum EFGSAS.
Extensive-form games (EFGs) are a standard model for sequential decision-making in games. A fundamental and typically implicit assumption in EFGs is that players always have access to all of their actions at every decision point. However, in many realistic settings, certain actions might be unavailable during game-play due to exogenous stochasticity, hindering the expressivity of the standard EFG model. Given a `base' EFG, we formalize a model that allows for actions to be stochastically restricted, leading to a corresponding Extensive-Form Games with Stochastic Action Sets (EFGSAS). In EFGSAS, we derive an expansion procedure that results in an equivalent EFG, thus showing that standard strategy formalisms could require exponentially-large representations. However, under an appropriate independence assumption, we show that compact strategy representations polynomial in the size of the base EFG exist. Computationally, we introduce an algorithm called SI-CFR that minimizes sleeping internal regret, converging to Nash equilibria with high probability in two-player zero-sum EFGSAS. Finally, we utilize a stochastic approximation procedure to recover compact representations of Nash equilibria, utilizing only the iterates of SI-CFR.