# Learning in Matching Games with Bandit Feedback

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 38 references that are in the map.
- First posted on arXiv 4 Jun 2025.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [Player-optimal Stable Regret for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2307.10890/) (2023)
- [Matrix games with bandit feedback](https://mlsanity.com/paper/2006.05145/) (2020)
- [Explore-then-Commit Algorithms for Decentralized Two-Sided Matching Markets](https://mlsanity.com/paper/2408.08690/) (2024)
- [Probably Correct Optimal Stable Matching for Two-Sided Markets Under Uncertainty](https://mlsanity.com/paper/2501.03018/) (2025)

## Abstract (arXiv)

We introduce a learning problem in a generalized two-sided matching market, where agents select actions to interact with their match. Specifically, we consider a setting in which matched agents engage in zero-sum games with initially unknown payoff matrices, and we investigate whether a centralized procedure can learn an equilibrium from bandit feedback. We adopt the solution concept of a matching equilibrium, where a matching ( mathfrakm ) and a set of agent strategies ( X ) form an equilibrium if no agent has an incentive to deviate from ( (mathfrakm, X) ). To quantify deviations of a candidate solution ( (mathfrakm, X) ) from the equilibrium ( (mathfrakm^star, X^star) ), we introduce the notion of matching instability, which serves as a regret measure for the learning problem. We propose a UCB-based algorithm in which agents form preferences and select actions according to optimistic estimates of the payoffs. Our analysis establishes a sublinear, instance-independent regret upper bound, further supported by empirical evidence.