Learning to Control Unknown Strongly Monotone Games

1. Problem Formulation

The paper addresses the challenge of controlling a large-scale network of agents (players) who interact via a strongly monotone game.

• The Setting: Players $n \in \mathcal{N}$ choose actions $x_n$ from convex, compact sets $\mathcal{X}_n$. Their utility functions are defined as $u_n(x) = r_n(x) - \sum \beta_{n,i} x_{n,i}$, where $r_n(x)$ is a private reward function and $\beta$ represents linear coefficients (e.g., prices) controlled by a central manager.
• The Goal: The manager aims to steer the system to a Nash Equilibrium (NE) that satisfies a set of $K$ coupled linear constraints: $Ax = \ell^*$.
  • Motivation: In uncontrolled games, the NE is often inefficient (e.g., resource over-congestion). Imposing constraints can force the NE to satisfy global optimality conditions (like minimizing a global quadratic cost) or specific load balancing targets.
• The Challenge: The manager does not know the players' reward functions $r_n(x)$ or their action sets $\mathcal{X}_n$.
  • Collecting this information is infeasible in large-scale networks and violates user privacy.
  • The manager only observes the constraint violation vector $(Ax_{t-1} - \ell^*)$ at each time step.
  • Players update their actions using stochastic gradient ascent based on noisy gradient estimates, meaning the system is never exactly at the NE during the transient phase.

2. Methodology

The authors propose an online learning algorithm based on two-time-scale stochastic approximation. The algorithm operates without the manager knowing the game structure.

The Algorithm (Algorithm 1)

The process involves two interacting loops:

1. Fast Time-Scale (Players):

   • Players update their actions $x_{n,t}$ using gradient ascent on their local utility.
   • They incorporate the controlled coefficients $\beta_{n,t}$, which are derived from the manager's control input $\alpha_t$ via $\beta_{n,t} = A_n^\top \alpha_t$.
   • The update rule: $x_{n,t} = \Pi_{\mathcal{X}_n}(x_{n,t-1} + \eta_{t-1}(g_{n,t-1} - \beta_{n,t-1}))$, where $g$ is a noisy gradient estimate and $\Pi$ is the projection onto the action set.
   • Step size: $\eta_t \sim O(t^{-\eta})$.

2. Slow Time-Scale (Manager):

   • The manager observes the constraint violation $Ax_{t-1} - \ell^*$.
   • The manager updates the control input $\alpha_t$ to minimize this violation.
   • Update rule: $\alpha_t = \alpha_{t-1} + \epsilon_{t-1}(Ax_{t-1} - \ell^*)$.
   • Step size: $\epsilon_t \sim O(t^{-\epsilon})$.
   • Key Constraint: The step sizes must satisfy $\lim_{t\to\infty} \frac{\epsilon_t^2}{\eta_t^3} = 0$ to ensure the players' dynamics converge faster than the manager's updates.

Theoretical Framework

• Game Bandit: The problem is framed as a "game bandit" where the manager receives feedback generated by game dynamics rather than a static reward distribution.
• Non-Expansive Mappings: A critical technical hurdle is that the action sets $\mathcal{X}_n$ are bounded (convex and compact). This causes the mapping from the control input $\alpha$ to the resulting NE $x^*(\alpha)$ to be non-expansive rather than contractive.
• Analysis Tools: The authors utilize:
  • Variational Inequalities (VI) to characterize the NE.
  • The Krasnosel'skiĭ–Mann (KM) algorithm theory for analyzing fixed-point iterations with non-expansive mappings.
  • Stochastic approximation theory to handle the noise in player gradients and the time-varying nature of the NE.

3. Key Contributions

1. Privacy-Preserving Control: The first distributed stochastic learning scheme that drives a game to a Generalized Nash Equilibrium (GNE) satisfying linear constraints without the manager knowing player rewards or action sets, and without requiring players to share private information.
2. Convergence Guarantees:
   • Almost Sure Convergence: Proved that the control input $\alpha_t$ converges to the set of optimal inputs $\mathcal{N}_{opt}$ (where $Ax^*(\alpha) = \ell^*$) with probability 1.
   • Convergence Rate: Established an $L_2$ convergence rate of near-$O(t^{-1/4})$ for the constraint violation.
3. Novel Analysis for Non-Expansive Maps: Unlike standard two-time-scale analyses that assume contractive mappings (yielding $O(t^{-1})$ rates), this paper handles the non-expansive nature of projections onto compact sets. The authors attribute the slower $O(t^{-1/4})$ rate to this non-expansiveness combined with two-time-scale dynamics.
4. Generalization: Extends previous work (limited to load balancing) to general linear constraints in strongly monotone games, covering applications like quadratic global optimization and weighted resource allocation.

4. Results

• Theoretical Bounds:
  • Theorem 1: $\alpha_t \to \mathcal{N}_{opt}$ and $Ax_t \to \ell^*$ almost surely.
  • Theorem 2: The mean squared error of the constraint violation is bounded by $E[\|Ax_t - \ell^*\|^2] \leq C(\eta_t + \frac{1}{t\epsilon_t})$. With optimal step sizes ($\eta \approx 0.5, \epsilon \approx 0.75$), this yields a rate of $O(t^{-0.25})$.
• Simulations:
  • Demand-Side Management: Simulated a game with 1,000 players over 24 hours. The algorithm successfully balanced loads to match target profiles, outperforming an uncontrolled system where resources were either over- or under-utilized.
  • Quadratic Global Objective: Demonstrated that the algorithm could minimize a global quadratic cost function while maintaining high sum of local player rewards, outperforming a centralized scheme that directly optimized the global cost (which ignored local incentives).
  • Robustness: The algorithm successfully tracked time-varying target loads and remained stable even when constraints were infeasible (by projecting the control input).

5. Significance

• Scalability and Privacy: The approach solves a critical bottleneck in large-scale network control (e.g., smart grids, wireless networks, data centers) where centralized optimization is impossible due to privacy concerns and communication overhead.
• New Paradigm: It introduces the concept of "Game Bandits," where the feedback noise is structural (equilibrium noise) rather than purely stochastic or adversarial.
• Theoretical Advancement: By proving convergence rates for two-time-scale stochastic approximation with non-expansive mappings, the paper provides a rigorous foundation for controlling complex, constrained multi-agent systems where players act myopically.
• Practical Applicability: The algorithm is simple to implement, requires minimal feedback (only constraint violation), and is robust to time-varying environments, making it suitable for real-world deployment in dynamic networks.