← Back to all news
arXiv Statistics ML

Thompson Sampling for Learning in Zero-Sum Games

Related stories

arXiv Machine Learning
Oct 15

High-Probability Regret Bounds for Feel-Good Thompson Sampling

The paper presents the first high‑probability regret bounds for both cumulative and current‑step variants of Feel‑Good Thompson Sampling (FGTS) in contextual bandits with general realizable function approximation. The bounds rely on decoupling coefficients and prior mass near the true reward function, and in the linear setting they achieve ≠d√T log(2T)+√T log(1/δ) regret with probability at least 1‑δ. This matches the dimension and horizon dependence of upper‑confidence‑bound algorithms up to logarithmic factors, while the high‑probability cost adds only linear dependence on log(1/δ).

By Xuheng Li, Qingyue Zhao, Quanquan Gu
llms
More like this →
arXiv Machine Learning
Sep 25

Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits

The paper analyzes Bayesian linear bandits with isotropic Gaussian parameters, independent Gaussian arms, and Gaussian reward noise when the time horizon scales with the dimension. It derives explicit limits for the normalized posterior uncertainty and parameter overlaps, yielding exact regret curves for several policies—including Thompson sampling, posterior‑mean greedy selection, and scaled‑covariance variants. The results show that posterior‑mean greedy selection achieves the optimal Bayes regret, while Thompson sampling incurs a strictly larger leading regret whose ratio to greedy lies between one and two, approaching two for long horizons.

By Prakhar Singhvi (Abstract Math Institute), Yi Zou (Abstract Math Institute), Abhishek Bhattacharjee (Abstract Math Institute)
reinforcement-learning
More like this →
arXiv Machine Learning
Oct 8

Expected Sample Complexity in Multi-Armed Bandits

The paper introduces the expected sample complexity metric for stochastic multi‑armed bandits and analyzes it within a new framework called approximately correct in expectation (ACE). It demonstrates that ACE guarantees lead to almost sure convergence to the optimal expected reward, contrasts this with high‑probability guarantees, and shows how to translate ACE bounds into explicit expected regret bounds. The authors prove that deterministic algorithms cannot achieve favorable ACE bounds, propose an explore‑then‑ε‑greedy algorithm when ε is known, analyze Thompson sampling when ε is unknown, and provide nearly matching lower bounds that establish tightness and a performance separation between the two regimes.

By Nadav Sukenik, Nadav Merlis
agentsreinforcement-learning
More like this →