# No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 69 references that are in the map.
- First posted on arXiv 14 May 2024.

## Builds on (most cited first, 27 of 27)

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Deep Kernel Learning](https://mlsanity.com/paper/1511.02222/) (2015)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2001.11659/) (2020)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Increasing the Scope as You Learn: Adaptive Bayesian Optimization in Nested Subspaces](https://mlsanity.com/paper/2304.11468/) (2023)
- [No-Regret Bayesian Optimization with Unknown Hyperparameters](https://mlsanity.com/paper/1901.03357/) (2019)
- [Monte Carlo Tree Search based Variable Selection for High Dimensional Bayesian Optimization](https://mlsanity.com/paper/2210.01628/) (2022)
- [Bayesian Optimization of Function Networks](https://mlsanity.com/paper/2112.15311/) (2021)
- [Inducing Point Allocation for Sparse Gaussian Processes in High-Throughput Bayesian Optimisation](https://mlsanity.com/paper/2301.10123/) (2023)
- [Model-based Causal Bayesian Optimization](https://mlsanity.com/paper/2211.10257/) (2022)
- [Self-Correcting Bayesian Optimization through Bayesian Active Learning](https://mlsanity.com/paper/2304.11005/) (2023)
- [No-Regret Learning in Unknown Games with Correlated Payoffs](https://mlsanity.com/paper/1909.08540/) (2019)
- [Watch and Learn: Optimizing from Revealed Preferences Feedback](https://mlsanity.com/paper/1504.01033/) (2015)
- [Bayesian Optimization of Function Networks with Partial Evaluations](https://mlsanity.com/paper/2311.02146/) (2023)
- [A Bayesian optimization approach to find Nash equilibria](https://mlsanity.com/paper/1611.02440/) (2016)
- [Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization](https://mlsanity.com/paper/2310.06689/) (2023)
- [Learning Equilibria of Games via Payoff Queries](https://mlsanity.com/paper/1302.3116/) (2013)
- [Learning Probably Approximately Correct Maximin Strategies in Simulation-Based Games with Infinite Strategy Spaces](https://mlsanity.com/paper/1911.07755/) (2019)
- [Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation](https://mlsanity.com/paper/2307.13371/) (2023)
- [Learning in Online Principal-Agent Interactions: The Power of Menus](https://mlsanity.com/paper/2312.09869/) (2023)
- [Approximating Nash Equilibria for Black-Box Games: A Bayesian Optimization Approach](https://mlsanity.com/paper/1804.10586/) (2018)
- [The Limits of Optimal Pricing in the Dark](https://mlsanity.com/paper/2110.01707/) (2021)
- [Learning Representation for Bayesian Optimization with Collision-free Regularization](https://mlsanity.com/paper/2203.08656/) (2022)
- [A Bayesian optimization approach to compute the Nash equilibria of potential games using bandit feedback](https://mlsanity.com/paper/1811.06503/) (2018)

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

- [Optimistic Games for Combinatorial Bayesian Optimization with Application to Protein Design](https://mlsanity.com/paper/2409.18582/) (2024)
- [A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Box Games](https://mlsanity.com/paper/2503.18224/) (2025)
- [Efficient Nash Equilibrium Computation for Cybersecurity Games](https://mlsanity.com/paper/2609.19399/) (2026)

## Abstract (arXiv)

This paper investigates the challenge of learning in black-box games, where the underlying utility function is unknown to any of the agents. While there is an extensive body of literature on the theoretical analysis of algorithms for computing the Nash equilibrium with complete information about the game, studies on Nash equilibrium in black-box games are less common. In this paper, we focus on learning the Nash equilibrium when the only available information about an agent's payoff comes in the form of empirical queries. We provide a no-regret learning algorithm that utilizes Gaussian processes to identify the equilibrium in such games. Our approach not only ensures a theoretical convergence rate but also demonstrates effectiveness across a variety collection of games through experimental validation.