# Optimistic Thompson Sampling for No-Regret Learning in Unknown Games

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 48 references that are in the map.
- First posted on arXiv 7 Feb 2024.

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

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity](https://mlsanity.com/paper/2206.07659/) (2022)
- [Old Dog Learns New Tricks: Randomized UCB for Bandit Problems](https://mlsanity.com/paper/1910.04928/) (2019)
- [No-Regret Learning in Unknown Games with Correlated Payoffs](https://mlsanity.com/paper/1909.08540/) (2019)
- [Matrix games with bandit feedback](https://mlsanity.com/paper/2006.05145/) (2020)
- [Regret Matching+: (In)Stability and Fast Convergence in Games](https://mlsanity.com/paper/2305.14709/) (2023)
- [Game of Thrones: Fully Distributed Learning for Multi-Player Bandits](https://mlsanity.com/paper/1810.11162/) (2018)
- [Multiplayer Bandit Learning, from Competition to Cooperation](https://mlsanity.com/paper/1908.01135/) (2019)
- [Competing for Shareable Arms in Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2305.19158/) (2023)
- [Distributed No-Regret Learning in Multi-Agent Systems](https://mlsanity.com/paper/2002.09047/) (2020)

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

- [Randomised Optimism via Competitive Co-Evolution for Matrix Games with Bandit Feedback](https://mlsanity.com/paper/2505.13562/) (2025)

## Abstract (arXiv)

This work tackles the complexities of multi-player scenarios in unknown games, where the primary challenge lies in navigating the uncertainty of the environment through bandit feedback alongside strategic decision-making. We introduce Thompson Sampling (TS)-based algorithms that exploit the information of opponents' actions and reward structures, leading to a substantial reduction in experimental budgets -- achieving over tenfold improvements compared to conventional approaches. Notably, our algorithms demonstrate that, given specific reward structures, the regret bound depends logarithmically on the total action space, significantly alleviating the curse of multi-player. Furthermore, we unveil the Optimism-then-NoRegret (OTN) framework, a pioneering methodology that seamlessly incorporates our advancements with established algorithms, showcasing its utility in practical scenarios such as traffic routing and radar sensing in the real world.