💻 computer science

On the Convergence of Thompson Sampling to Nash Equilibria in Multi-Agent Models

This paper demonstrates and proves that Thompson Sampling, when combined with a simple imitation mechanism in a symmetric multi-agent Bertrand pricing game, reliably converges to the Nash equilibrium in a decentralized, model-free manner, offering a practical reinforcement learning approach for complex multi-agent environments.

Original authors: Marco Gross, Elisa Letizia

Published 2026-08-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Marco Gross, Elisa Letizia

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a bustling marketplace where dozens of shops are trying to figure out the perfect price for their wares. They can't talk to each other, they don't have a crystal ball, and they don't even know the exact formula for how much money they'll make. This is the world of multi-agent learning, a branch of computer science and economics where independent "agents" (like robots, software programs, or even simulated people) try to learn the best strategy just by trial and error. The ultimate goal in these games is often to reach a Nash equilibrium. Think of this as a "stable standoff": a point where no single shop can change its price to make more money without the others changing theirs first. It's the sweet spot where everyone is doing the best they can, given what everyone else is doing. For decades, figuring out how to get there without a central boss or a perfect map has been a tricky puzzle.

Enter Thompson Sampling, a clever learning trick originally designed for one person trying to find the best slot machine in a casino. It works by being a bit of a gambler: it tries different options, but it gets smarter over time by betting more on the ones that seem to be paying off, while still occasionally taking a risk on the unknowns just in case. The big question researchers have been asking is: Can this solo gambler's trick work when a whole crowd of agents is playing a game together, all trying to find that stable price point at the same time?

In this paper, Marco Gross and Elisa Letizia from the International Monetary Fund set up a digital experiment to see if Thompson Sampling could solve this group puzzle. They created a simulated world of shops (called a "Bertrand pricing game") where every shop sells the exact same product and faces the same customers. They gave these shops a simple rule: if one shop tries a new price and makes more profit, everyone else copies it immediately. This "imitation" is the secret sauce.

The authors found that when they combined Thompson Sampling with this copying behavior, the shops didn't just stumble around; they reliably marched straight toward the perfect, stable price—the Nash equilibrium. They proved mathematically that this works and showed it happening on a computer. In their simulations, with anywhere from one shop to many, the algorithm found the right price in about 200 to 300 rounds of trading. It's like watching a chaotic crowd of people suddenly realize, "Oh, this price works for everyone!" and all moving in lockstep to that number.

However, the paper is careful to note the limits of this success. This magic only works because the shops are identical and the rules are fair (a "symmetric" setup). If the shops were different sizes or had different costs, the simple copying trick might break down. Also, while the math proves it works in theory and the computer simulations show it working in practice, this is a specific type of game. The authors suggest this is a promising first step, a way to teach computers to find stable solutions in complex markets without needing a human to write out the answer first, but they admit that making it work for messy, real-world situations with different players is a job for future research.

To make sure their digital shops were learning efficiently, the researchers also had to figure out how to set up the "price grid"—the list of possible prices the shops could choose from. If the list is too short, they might miss the perfect price. If it's too long, the shops get confused by the noise. They discovered a sweet spot using a clever measurement called "Normalized Shannon Entropy," which basically acts like a "confusion meter." They found that a grid with about 7 to 30 price options worked best, allowing the shops to converge quickly without getting lost in the details.

In the end, this paper shows that you don't need a supercomputer or a central planner to find a fair price in a competitive market. You just need a group of agents that are willing to try new things, learn from their mistakes, and copy their neighbors when they see a win. It's a small but significant step toward building smarter, self-regulating economic models that can handle the complexity of the real world.

Technical Summary: On the Convergence of Thompson Sampling to Nash Equilibria in Multi-Agent Models

Problem Statement
The paper addresses the challenge of achieving convergence to a Nash equilibrium in multi-agent strategic settings using model-free reinforcement learning. Specifically, the authors examine a symmetric multi-agent Bertrand pricing game with logit demand. The core problem is to demonstrate that a decentralized learning algorithm, which operates without knowledge of the payoff structure or gradient information, can reliably guide agents to a mutual best response (Nash equilibrium). While existing literature explores Thompson Sampling (TS) in single-agent bandit problems and various Multi-Agent Reinforcement Learning (MARL) frameworks, formal convergence proofs for TS in strategic, multi-agent games with a known analytical benchmark remain limited.

Methodology
The authors propose a Thompson Sampling (TS) learning algorithm coupled with a simple imitation mechanism. The methodology is structured as follows:

Model Environment: The study utilizes a static Bertrand game with $B$ players choosing prices from a discrete grid $G \subset [0, r]$ . Participants derive utility from a Random Utility Model (RUM) with logit demand. All players share a common base utility ( $\alpha$ ), ensuring a symmetric payoff structure and a single symmetric Nash equilibrium.
Algorithm Design:
- Grid and Distributions: A discrete grid of prices is defined. For each grid point, two Beta distributions (for "up" and "down" price moves) are maintained, initialized with uniform priors.
- Exploration: In each iteration, one "explorer" player is randomly selected. This player samples a move direction (up or down) based on the current Beta distributions and updates its price.
- Reward and Update: The explorer observes a binary reward ( $r_t \in \{0, 1\}$ ) indicating whether the price move increased its profit compared to the previous non-exploration period. The Beta distribution parameters are updated via Bayesian rules (incrementing shape parameters based on success or failure).
- Imitation: If the explorer's move results in a profit increase ("success"), all other players imitate this new price in the subsequent period. If the move fails, the system remains in an exploration phase, using the last successful price as the reference.
Convergence Proof: The authors provide a formal proof of convergence based on five assumptions: grid regularity, sufficient exploration, strict concavity of the profit function, common posterior updates, and bounded reward noise. The proof relies on:
1. Posterior Consistency: Beta posteriors converge to Dirac measures centered at the true probability of profit improvement.
2. Hill Climbing: Due to profit concavity, TS asymptotically favors moves toward the global optimum.
3. Synchronization: The imitation mechanism ensures that all players synchronize to the profitable price level, reducing the $B$ -dimensional problem to the convergence of a single scalar price.

Key Contributions

Formal Convergence Proof: The paper establishes a formal convergence proof for a decentralized, model-free TS algorithm in a multi-agent strategic setting, complementing existing simulation-based evidence.
Decentralized Equilibrium Search: Unlike centralized optimization or Q-learning approaches that may require explicit equilibrium computation or Q-value iteration, this method guides agents to equilibrium through local exploration and imitation without requiring knowledge of the payoff function.
Grid Design Metric: The authors propose using Normalized Shannon Entropy (NSE) of the posterior sampling frequencies as a model-free metric to select optimal grid resolution. This addresses the bias-variance trade-off in discretized strategy sets without requiring knowledge of the true equilibrium.
Integration with Agent-Based Models (ABMs): The paper suggests embedding TS mechanisms into ABMs as a methodological tool for simulating market dynamics in competitive environments with symmetric players.

Results

Numerical Validation: Simulations with $B=6$ players and $R=50$ runs demonstrate that the algorithm converges to the analytically derived Nash equilibrium price, total profit, and market shares within approximately 200–300 periods.
Convergence Metrics: Using a Gelman-Rubin inspired statistic, the study confirms that the distribution of simulated paths stabilizes over time, with the convergence statistic approaching 1.
Grid Resolution Analysis: The study finds that intermediate grid resolutions (specifically $G=7$ in the tested parameterization) minimize the Normalized Shannon Entropy, indicating robust convergence. Both very coarse and very fine grids result in higher entropy or instability due to discretization bias or stochastic noise, respectively. The entropy metric correlates well with Mean Absolute Errors (MAE) against the analytical benchmark but offers the advantage of not requiring the benchmark for selection.

Significance and Claims
The authors position this work as a "first step" toward utilizing TS-based learning in richer multi-agent environments where analytical Nash solutions are difficult or infeasible to derive. The significance lies in:

Bridging Literature: It connects Thompson Sampling, reinforcement learning, and game-theoretic equilibrium search, providing formal guarantees in a domain previously dominated by heuristics.
Practical Applicability: The algorithm is presented as a practical tool for agent-based modeling in economics and finance, particularly for markets with symmetric competitors (e.g., banking deposits/loans or firm pricing) where analytical solutions are tractable but decentralized learning is preferred for realism.
Modest Scope: The authors explicitly limit their claims to games with a common payoff structure and symmetric players. They acknowledge that extending the approach to heterogeneous base utilities (asymmetric equilibria) and non-stationary environments remains an open direction for future work. The paper does not claim to solve the general PPAD-complete problem of finding Nash equilibria in arbitrary non-cooperative games but rather demonstrates reliable convergence for a specific, tractable class of games using a decentralized, model-free approach.

Technical Summary: On the Convergence of Thompson Sampling to Nash Equilibria in Multi-Agent Models

More like this