State-Action Selection in General Stochastic Games under Regularized Policy Gradient Methods

We study a general class of regularized policy gradient methods for episodic learning in general-sum stochastic games, with the aim of describing the long-run behavior of the induced policy iterates. In this challenging setting, learning even the simplest pointwise solution concepts is known to be intractable. This leads us to switch our focus to less restrictive *setwise* solution concepts: rather than only asking whether the iterates converge to a specific policy, we ask which *sets of policies* are selected by the learning dynamics in the long-run. In one-shot games, this setwise perspective admits a crisp characterization: a product set of pure strategies is asymptotically stable if and only if it is *closed under better replies* (club). We show that the direct statewise analogue of this principle *fails* outright in stochastic games because actions affect not only current rewards but also the future evolution of the game. To restore this principle in a transition-aware form, we introduce $Q$-*club* sets, namely state-action sets in which every *allowed* action has a strict $Q$-value advantage over every *excluded* action, thereby providing a setwise generalization of *strict Nash policies*. We then prove that $Q$-club sets are stochastically stable and attracting under the learning dynamics, even in the presence of noise and uncertainty. Finally, we establish local convergence rates to $Q$-club sets governed by the regularizer; in particular, entropic regularization yields exponential convergence, while Euclidean regularization yields finite-time convergence.