Learning Stationary Correlated Equilibria in Constrained General-Sum Stochastic Games

Area of Science:

• Game Theory
• Machine Learning
• Control Theory

Background:

• General-sum stochastic games with unknown dynamics present significant challenges.
• Existing methods for unconstrained games lack convergence guarantees and use complex structures.
• Decentralized resource control in wireless networks requires robust game-theoretic solutions.

Purpose of the Study:

• To develop a novel algorithm for constrained general-sum stochastic games with unknown dynamics.
• To guarantee convergence to stationary correlated equilibria in these complex game settings.
• To demonstrate the algorithm's efficacy in decentralized resource control for wireless networks.

Main Methods:

• A distributed constrained no-regret Q-learning (CNR Q) scheme is proposed.
• The algorithm is formulated as a single-loop, three-timescale asynchronous stochastic approximation.
• Convergence is rigorously analyzed using differential inclusion arguments and advanced stochastic approximation theory.

Main Results:

• The CNR Q scheme guarantees convergence to the set of stationary correlated equilibria.
• The proposed method overcomes limitations of prior art, including lack of convergence and complex control structures.
• Numerical simulations validate the application of CNR Q to decentralized resource control in heterogeneous wireless networks.

Conclusions:

• The CNR Q algorithm offers a robust and convergent solution for constrained stochastic games.
• This work provides a significant theoretical advancement in game theory and stochastic approximation.
• The findings have practical implications for decentralized control systems, particularly in wireless communications.