Is Thompson Sampling Susceptible to Algorithmic Collusion?
Not on the map. Why?
Abstract (arXiv)
When two players are engaged in a repeated game with unknown payoff matrices, they may use single-agent multi-armed bandit algorithms to choose the actions independent of each other. We show that when the players use Thompson sampling, the game dynamics converges to the Nash equilibrium under a mild assumption on the payoff matrices. Therefore, algorithmic collusion doesn't arise in this case despite the fact that the players do not intentionally deploy competitive strategies. To prove the convergence result, we find that the framework developed in stochastic approximation doesn't apply, because of the sporadic and infrequent updates of the inferior actions and the lack of Lipschitz continuity. We develop a novel sample-path-wise approach to show the convergence. However, when the payoff matrices do not satisfy the assumption, the game may converge to collusive outcomes.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 23 of its 62 references that are in the map. First posted on arXiv 23 May 2024.
Builds on
23 of 62 references.
References · 23
- 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
- 2017A Tutorial on Thompson Samplingcited by 433
- 2018Mean Field Multi-Agent Reinforcement Learningcited by 207
- 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
- 2017Cycles in adversarial regularized learningcited by 124
- 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
- 2016Learning in games with continuous action sets and unknown payoff functionscited by 81
- 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 60
- 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
- 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
- 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 49
- 2018On Gradient-Based Learning in Continuous Gamescited by 48
11 more
- 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
- 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
- 2020Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Gamescited by 26
- 2021Independent Learning in Stochastic Gamescited by 22
- 2020Matrix games with bandit feedbackcited by 16
- 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 15
- 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
- 2023Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noisecited by 15
- 2022Artificial Intelligence and Spontaneous Collusioncited by 10
- 2023Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedbackcited by 6
- 2013Generalized Thompson Sampling for Sequential Decision-Making and Causal Inferencecited by 5
Built on by
Citing papers per year: 2026: 1.
1 paper.