# Learning to Control Unknown Strongly Monotone Games

arXiv: https://arxiv.org/abs/2407.00575 · HTML: https://mlsanity.com/paper/2407.00575/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 94 references that are in the map.
- First posted on arXiv 30 Jun 2024.

## Builds on (most cited first, 30 of 32)

- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [On Gradient-Based Learning in Continuous Games](https://mlsanity.com/paper/1804.05464/) (2018)
- [SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits](https://mlsanity.com/paper/1809.08151/) (2018)
- [Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance](https://mlsanity.com/paper/2011.01868/) (2020)
- [A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players](https://mlsanity.com/paper/1902.01239/) (2019)
- [Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds](https://mlsanity.com/paper/2208.04193/) (2022)
- [On Regret-Optimal Learning in Decentralized Multi-player Multi-armed Bandits](https://mlsanity.com/paper/1505.00553/) (2015)
- [My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits](https://mlsanity.com/paper/2002.09808/) (2020)
- [Convergence rate analysis of several splitting schemes](https://mlsanity.com/paper/1406.4834/) (2014)
- [Coordinating the Crowd: Inducing Desirable Equilibria in Non-Cooperative Systems](https://mlsanity.com/paper/1901.10923/) (2019)
- [Multi-Player Bandits: The Adversarial Case](https://mlsanity.com/paper/1902.08036/) (2019)
- [Learning Nash Equilibria in Monotone Games](https://mlsanity.com/paper/1904.01882/) (2019)
- [Optimally Deceiving a Learning Leader in Stackelberg Games](https://mlsanity.com/paper/2006.06566/) (2020)
- [Convergence Rates with Inexact Non-expansive Operators](https://mlsanity.com/paper/1404.4837/) (2014)
- [Multi-User MABs with User Dependent Rewards for Uncoordinated Spectrum Access](https://mlsanity.com/paper/1910.09091/) (2019)
- [A variational inequality framework for network games: Existence, uniqueness, convergence and sensitivity analysis](https://mlsanity.com/paper/1712.08277/) (2017)
- [First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/2204.03132/) (2022)
- [Distributed Nash Equilibrium Seeking by A Consensus Based Approach](https://mlsanity.com/paper/1602.00771/) (2016)
- [Geometric Convergence of Gradient Play Algorithms for Distributed Nash Equilibrium Seeking](https://mlsanity.com/paper/1809.07383/) (2018)
- [A Passivity-Based Approach to Nash Equilibrium Seeking over Networks](https://mlsanity.com/paper/1705.02424/) (2017)
- [Learning Quadratic Games on Networks](https://mlsanity.com/paper/1811.08790/) (2018)
- [Stochastic generalized Nash equilibrium seeking under partial-decision information](https://mlsanity.com/paper/2011.05357/) (2020)
- [Equilibrium Computation of Generalized Nash Games: A New Lagrangian-Based Approach](https://mlsanity.com/paper/2106.00109/) (2021)
- [Dynamic control of agents playing aggregative games with coupling constraints](https://mlsanity.com/paper/1609.08962/) (2016)
- [Targeting Interventions in Networks](https://mlsanity.com/paper/1710.06026/) (2017)
- [Distributed Mechanism Design for Multicast Transmission](https://mlsanity.com/paper/1803.08111/) (2018)
- [Optimizing Curbside Parking Resources Subject to Congestion Constraints](https://mlsanity.com/paper/1703.07802/) (2017)
- [Randomized Lagrangian Stochastic Approximation for Large-Scale Constrained Stochastic Nash Games](https://mlsanity.com/paper/2304.07688/) (2023)
- [Autonomous Demand Side Management Based on Energy Consumption Scheduling and Instantaneous Load Billing: An Aggregative Game Approach](https://mlsanity.com/paper/1306.3383/) (2013)

## Built on by (most cited first, 4 of 4)

- [Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise](https://mlsanity.com/paper/2503.18391/) (2025)
- [O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2504.19375/) (2025)
- [Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis](https://mlsanity.com/paper/2501.10806/) (2025)
- [Last-Iterate Guarantees for Learning in Co-coercive Games](https://mlsanity.com/paper/2604.19065/) (2026)

## Abstract (arXiv)

Consider a strongly monotone game where the players' utility functions include a reward function and a linear term for each dimension, with coefficients that are controlled by the manager. Gradient play converges to a unique Nash equilibrium (NE) that does not optimize the global objective. The global performance at NE can be improved by imposing linear constraints on the NE, also known as a generalized Nash equilibrium (GNE). We therefore want the manager to control the coefficients such that they impose the desired constraint on the NE. However, this requires knowing the players' rewards and action sets. Obtaining this game information is infeasible in a large-scale network and violates user privacy. To overcome this, we propose a simple algorithm that learns to shift the NE to meet the linear constraints by adjusting the controlled coefficients online. Our algorithm only requires the linear constraints violation as feedback and does not need to know the reward functions or the action sets. We prove that our algorithm converges with probability 1 to the set of GNE given by coupled linear constraints. We then prove an L2 convergence rate of near-O(t-1/4).