Optimistic Thompson Sampling for No-Regret Learning in Unknown Games
Yingru Li, Liangqi Liu, Wenqiang Pu, Hao Liang, Zhi-Quan Tom Luo · IEEE Transactions on Signal Processing · 2026
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.