aiqbench analysis
This arXiv paper extends Thompson sampling, a standard exploration-exploitation method for multi-armed bandits, to arbitrary reward distributions by modeling each arm's reward with a Bayesian nonparametric Gaussian mixture that adapts its complexity to the data. The authors report matching the regret of oracle policies that know the true model, and competitive results on multimodal, outlier-contaminated, and non-exponential-family rewards, though these are empirical claims on benchmark settings. For ML practitioners, the practical question is whether the computational cost and accuracy hold up in their own deployments, since the removal of manual model specification is the main selling point.
Bayesian Nonparametric Thompson Sampling for Multi-Armed Bandits
arXiv:1808.02932v5 Announce Type: replace-cross Abstract: In stochastic multi-armed bandits, rewards are generated by an unknown distribution; the world's reward uncertainty induces the exploration-exploitation trade-off. Thompson sampling (TS) addresses this trade-off elegantly, but requires knowing the reward model's parametric form to sample from its posterior and compute per-arm expected rewards ---which limits its applicability as it demands per-scenario model specification and hyperparameter tuning. We here adopt Bayesian nonparametric (BNP) mixture models to remove this requirement, extending TS to arbitrary reward distributions. We model each arm's unknown reward distribution with an independent BNP Gaussian mixture, which can approximate any continuous reward density, and adapts its complexity to sequentially observed data. Embedding the BNP mixture model into TS yields Nonparametric TS, an algorithm that sequentially learns the reward model that best approximates the true, yet unknown, per-arm reward distribution, avoiding case-by-case model specification and hyperparameter tuning. We empirically demonstrate that ($i$) Nonparametric TS matches the regret performance of Oracle TS policies that know the true reward model; ($ii$) it favorably compares (in cumulative regret and volatility) to a suite of state-of-the-art alternatives across multimodal, outlier-contaminated, and non-exponential-family reward distributions; and ($iii$) its Bayesian nonparametric inference remains computationally practical and accurate for regret minimization.
Abstract:In stochastic multi-armed bandits, rewards are generated by an unknown distribution; the world's reward uncertainty induces the exploration-exploitation trade-off. Thompson sampling (TS) addresses this trade-off elegantly, but requires knowing the reward model's parametric form to sample from its posterior and compute per-arm expected rewards ---which limits its applicability as it demands per-scenario model specification and hyperparameter tuning. We here adopt Bayesian nonparametric (BNP) mixture models to remove this requirement, extending TS to arbitrary reward distributions. We model each arm's unknown reward distribution with an independent BNP Gaussian mixture, which can approximate any continuous reward density, and adapts its complexity to sequentially observed data. Embedding the BNP mixture model into TS yields Nonparametric TS, an algorithm that sequentially learns the reward model that best approximates the true, yet unknown, per-arm reward distribution, avoiding case-by-case model specification and hyperparameter tuning. We empirically demonstrate that ($i$) Nonparametric TS matches the regret performance of Oracle TS policies that know the true reward model; ($ii$) it favorably compares (in cumulative regret and volatility) to a suite of state-of-the-art alternatives across multimodal, outlier-contaminated, and non-exponential-family reward distributions; and ($iii$) its Bayesian nonparametric inference remains computationally practical and accurate for regret minimization.
Machine Learning (stat.ML); Machine Learning (cs.LG); Computation (stat.CO)
arXiv:1808.02932 [stat.ML]
(or arXiv:1808.02932v5 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.1808.02932 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 292 words
Related coverage
Information-Directed Sampling for Causal Bandits
arXiv · Sep 22, 2026
Odds-Ratio Thompson Sampling: A Specification and Design Guide for Contrast-Based Multi-Armed Bandits
arXiv · Sep 18, 2026
LLM-Derived Priors for Thompson Sampling in Cold-Start Comment Recommendation
arXiv · Aug 5, 2026
Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithms
arXiv · Oct 6, 2026