Optimistic Thompson Sampling for No-Regret Learning in Unknown Games
Abstract
We study the problem of learning to play a repeated multi-player game with an unknown reward function and bandit feedback. The central challenge arises from the need to balance exploration and exploitation under bandit feedback while strategically responding to other players. To address this, we propose Thompson Sampling-based algorithms that leverage available information about opponents’ actions and reward structures, resulting in a significant reduction in regret bound. Building on these insights, we introduce the Optimism-then-NoRegret framework, which encompasses various game algorithms as special cases. Simulation evaluations on three distinct types of games show that our proposed algorithms consistently and substantially outperform standard baselines.
Fields of Study & Subjects
Machine Learning and Algorithms
Domain Adaptation and Few-Shot Learning
Survey Sampling and Estimation Techniques
Publication details
- Journal / source
- IEEE Transactions on Signal Processing
- Publisher
- Institute of Electrical and Electronics Engineers (IEEE)
- Volume
- 74
- Pages
- 2434–2447
- Publication date
- 1 January 2026
- Language
- EN