2026/02/18 by Thomas Schwarz, Ryann Sim, Chun Kai Ling · 1 citation
#cs.GT
The study of learning in games typically assumes that each player always has access to all of their actions. However, in many practical scenarios, players' available actions might be restricted due to exogenous stochasticity. To model this setting, for a game Gorig with action set Ai for each player i, we introduce the corresponding Game with Stochastic Action Sets (GSAS) which is parametrized by a probability distribution over the players' set of possible action subsets Si ⊆ 2\vert Ai\vert\backslash\\varnothing\. In a GSAS, players' strategies and Nash equilibria (NE) admit prohibitively large representations, and existing algorithms for NE computation scale poorly. Under the assumption that action availabilities are independent between players, we show that NE in two-player zero-sum (2p0s) GSAS can be compactly represented by a vector of size \vert Ai\vert, overcoming the naïve exponential-sized representation. Computationally, we introduce an efficient algorithm called SI-MWU that minimizes sleeping internal regret, converging to NE with high probability in 2p0s-GSAS with rate O(√(log\vert Ai\vert/T)). Finally, using the SI-MWU iterates, we develop a procedure based on stochastic approximation to recover compactly represented NE.