# No-Regret Learning in Unknown Games with Correlated Payoffs

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2019.

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

- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [Differentially Private Federated Bayesian Optimization with Distributed Exploration](https://mlsanity.com/paper/2110.14153/) (2021)
- [Distributionally Robust Bayesian Optimization with varphi-divergences](https://mlsanity.com/paper/2203.02128/) (2022)
- [Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computation](https://mlsanity.com/paper/2203.07322/) (2022)
- [Contextual Games: Multi-Agent Learning with Side Information](https://mlsanity.com/paper/2107.06327/) (2021)
- [On Provably Robust Meta-Bayesian Optimization](https://mlsanity.com/paper/2206.06872/) (2022)
- [Movement Penalized Bayesian Optimization with Application to Wind Energy Systems](https://mlsanity.com/paper/2210.08087/) (2022)
- [Risk-Averse No-Regret Learning in Online Convex Games](https://mlsanity.com/paper/2203.08957/) (2022)
- [Adversarial Causal Bayesian Optimization](https://mlsanity.com/paper/2307.16625/) (2023)
- [Optimistic Games for Combinatorial Bayesian Optimization with Application to Protein Design](https://mlsanity.com/paper/2409.18582/) (2024)
- [Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions](https://mlsanity.com/paper/2605.09363/) (2026)
- [A Zeroth-Order Momentum Method for Risk-Averse Online Convex Games](https://mlsanity.com/paper/2209.02838/) (2022)
- [REDUCR: Robust Data Downsampling Using Class Priority Reweighting](https://mlsanity.com/paper/2312.00486/) (2023)
- [No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes](https://mlsanity.com/paper/2405.08318/) (2024)
- [Risk-averse Learning with Non-Stationary Distributions](https://mlsanity.com/paper/2404.02988/) (2024)
- [Optimistic Thompson Sampling for No-Regret Learning in Unknown Games](https://mlsanity.com/paper/2402.09456/) (2024)
- [Nearly-Optimal Algorithm for Adversarial Kernelized Bandits](https://mlsanity.com/paper/2605.10299/) (2026)
- [Randomised Optimism via Competitive Co-Evolution for Matrix Games with Bandit Feedback](https://mlsanity.com/paper/2505.13562/) (2025)

## Abstract (arXiv)

We consider the problem of learning to play a repeated multi-agent game with an unknown reward function. Single player online learning algorithms attain strong regret bounds when provided with full information feedback, which unfortunately is unavailable in many real-world scenarios. Bandit feedback alone, i.e., observing outcomes only for the selected action, yields substantially worse performance. In this paper, we consider a natural model where, besides a noisy measurement of the obtained reward, the player can also observe the opponents' actions. This feedback model, together with a regularity assumption on the reward function, allows us to exploit the correlations among different game outcomes by means of Gaussian processes (GPs). We propose a novel confidence-bound based bandit algorithm GP-MW, which utilizes the GP model for the reward function and runs a multiplicative weight (MW) method. We obtain novel kernel-dependent regret bounds that are comparable to the known bounds in the full information setting, while substantially improving upon the existing bandit results. We experimentally demonstrate the effectiveness of GP-MW in random matrix games, as well as real-world problems of traffic routing and movie recommendation. In our experiments, GP-MW consistently outperforms several baselines, while its performance is often comparable to methods that have access to full information feedback.