Bayesian Nonparametric Thompson Sampling for Multi-Armed Bandits

Iñigo Urteaga; Chris H. Wiggins

stat.MLAug 8, 2018

Bayesian Nonparametric Thompson Sampling for Multi-Armed Bandits

Authors: Iñigo Urteaga, Chris H. Wiggins

Organizations: Department of Applied Physics and Applied Mathematics Data Science Institute Columbia University New York City, NY 10027

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.

Figures & tables

Panel of Figure 1 — Figure 1: Graphical model of the per-arm DP Gaussian mixture bandit.

Scenario	Reward model	Oracle TS
Contextual linear Gaussian	Eq. ( 4 )	Agrawal and Goyal, 2013b ()
Gaussian mixture ( A , B )	Eq. ( 8 )–( 9 )	Urteaga and Wiggins, (2018) †
Outlier-contaminated	Eq. ( 10 )	Urteaga and Wiggins, (2018) †
Exponentially distributed	Eq. ( 11 )	N/A

Table 1: Evaluated scenarios and corresponding Oracle TS.

Figure 2: Mean

R_{t}

(std. shaded) of Nonparametric TS vs. Oracle TS, Scenarios A (left) and B (right).

Figure 3: Outlier-contaminated bandit: Mean

R_{t}

(std. shaded) of Nonparametric TS vs. a correctly-specified Oracle (left), vs. a misspecified Gaussian TS (right).

Algorithm	Cumulative regret (rel.)
Nonparametric TS	189.9 $\pm$ 13.0 (0%)
NeuralBootstrapped	210.9 $\pm$ 47.4 (11%)
MultitaskGP	213.6 $\pm$ 22.0 (13%)
NeuralLinear	398.5 $\pm$ 18.2 (110%)
BNNVariationalGaussian	827.4 $\pm$ 193.1 (336%)

Table 2:

R_{T}

T=1500

, contextual linear Gaussian bandit (dense

\theta_{a}

). Parentheses: relative regret increase over Nonparametric TS . Selected baselines; full 9-baseline table in Appendix B.2 .

Figure 4: Mean

R_{t}

, Scenarios A (left) and B (right).

Algorithm	Scenario A	Scenario B
Nonparametric TS	27.5 $\pm$ 70.7 (0%)	44.1 $\pm$ 70.4 (0%)
LinearGaussian TS	51.2 (87%)	65.4 (48%)
NeuralLinear	57.0 (108%)	78.1 (77%)
BNNAlphaDiv	197.4 (619%)	325.7 (638%)

Table 3:

R_{T}

T=1000

, mixture scenarios. Parentheses: relative regret increase over Nonparametric TS . Selected baselines; full table in Appendix B.4 .

Figure 5: Mean

R_{t}

, outlier-contaminated bandit.

Algorithm	Cumulative regret (rel.)
Nonparametric TS	100.0 $\pm$ 188.9 (0%)
NeuralParamNoise	130.7 (31%)
LinearGaussian TS	142.1 (42%)
MultitaskGP	532.7 (433%)
BNNAlphaDiv	611.6 (512%)

Table 4:

R_{T}

T=1000

, outlier-contaminated bandit. Selected baselines; full table in Appendix B.5 .

Figure 6: Mean

R_{t}

, exponential-reward bandit.

Algorithm	Cumulative regret (rel.)
Nonparametric TS	67.9 $\pm$ 119.4 (0%)
NeuralLinear	94.2 (39%)
LinearGaussian TS	116.4 (71%)
BNNAlphaDiv	153.5 (126%)
MultitaskGP	197.2 (191%)

Table 5:

R_{T}

T=1000

, exponential-reward bandit. Selected baselines; full table in Appendix B.6 .

Figure 7: Mean

R_{t}

(std. shaded) of Nonparametric TS with

Gibbs_{max}\in\{1,5,10\}

, mixture Scenario B (left) and exponential rewards (right).

Appendix figures & tables21 assets

Supplementary material from the paper’s appendix.

Appendix

Hyperparameter	Value
training freq	1
training epochs	50
activation	tf.nn.relu
layer size	50
batch size	512
init scale	0.3

Appendix

Table 6: Shared neural network hyperparameters.

Algorithm	Details
NeuralLinear	Network and last-layer posterior updated every iteration; prior $a_{0}=6,b_{0}=6,\lambda_{0}=0.25$ .
NeuralRMS	RMS optimizer, default parameters.
NeuralBootstrapped	$Q=3$ networks/datasets, $p=0.95$ .
NeuralParamNoise	Noise $\mathcal{N}\left(0,\sigma=0.05\right)$ ; $\epsilon=0.1$ -greedy, 300 samples.
NeuralDropoutRMS	Dropout probability $0.2$ (keep probability $0.8$ ), RMS optimizer.
BNNVariationalGaussian	Independent Gaussian weight noise, $\sigma=0.1$ ; 100 initial training steps.

Appendix

Table 7: Per-baseline algorithm hyperparameters.

Hyperparameter	Value
training freq	1
training epochs	50
learn embeddings	True
task latent dim	5
max num points	1000
batch size	512

Appendix

Table 8: MultitaskGP hyperparameters.

Figure 8: Mean

R_{t}

, dense (left) and sparse (right) linear Gaussian bandit.

Algorithm	Linear Gaussian	Sparse Linear Gaussian
Nonparametric TS	189.9 $\pm$ 13.0 (0%)	157.4 $\pm$ 12.4 (0%)
NeuralLinear	398.5 $\pm$ 18.2 (109.9%)	334.6 $\pm$ 16.4 (112.6%)
NeuralBootstrapped	210.9 $\pm$ 47.4 (11.1%)	176.1 $\pm$ 46.6 (11.9%)
NeuralRMS	256.9 $\pm$ 69.2 (35.3%)	208.7 $\pm$ 65.0 (32.6%)
NeuralDropoutRMS	382.9 $\pm$ 87.1 (101.6%)	334.9 $\pm$ 92.3 (112.7%)
NeuralParamNoise	241.0 $\pm$ 59.3 (26.9%)	199.1 $\pm$ 62.1 (26.5%)

Appendix

Table 9:

R_{T}

(mean

\pm

std) at

T=1500

. Parentheses: relative increase over Nonparametric TS .

Panel of Figure 9 — Figure 9: Mean $R_{t}$ (std. shaded) for $N=1000$ realizations of $|\mathcal{A}|\in\{2,3,4,5\}$ -armed contextual linear Gaussian bandits with varying arm separation, $\sigma_{a}^{2}=1\;\forall a$ : Nonparametric TS vs. LinearGaussian TS (Oracle).

Algorithm	Scenario A	Scenario B
Nonparametric TS	27.5 $\pm$ 70.7 (0%)	44.1 $\pm$ 70.4 (0%)
LinearGaussian TS	51.2 $\pm$ 99.3 (86.5%)	65.4 $\pm$ 89.9 (48.3%)
NeuralLinear	57.0 $\pm$ 91.6 (107.6%)	78.1 $\pm$ 95.0 (77.0%)
NeuralBootstrapped	137.9 $\pm$ 220.2 (402.0%)	166.9 $\pm$ 267.8 (278.4%)
NeuralRMS	147.0 $\pm$ 227.5 (435.2%)	183.3 $\pm$ 282.4 (315.5%)
NeuralDropoutRMS	143.3 $\pm$ 224.6 (421.7%)	182.6 $\pm$ 282.1 (313.8%)

Appendix

Table 10:

R_{T}

(mean

\pm

std) at

T=1000

. Parentheses: relative increase over Nonparametric TS .

Figure 10: Averaged empirical frequency of playing the optimal arm, Scenario A (left) and B (right).

Algorithm	Cumulative regret
Nonparametric TS	100.0 $\pm$ 188.9 (0%)
LinearGaussian TS	142.1 $\pm$ 200.9 (42.1%)
NeuralLinear	196.8 $\pm$ 273.6 (96.9%)
NeuralBootstrapped	214.4 $\pm$ 546.0 (114.5%)
NeuralRMS	218.2 $\pm$ 556.3 (118.3%)
NeuralDropoutRMS	196.5 $\pm$ 510.8 (96.5%)

Appendix

Table 11:

R_{T}

(mean

\pm

std) at

T=1000

. Parentheses: relative increase over Nonparametric TS .

Figure 11: Averaged empirical frequency of playing the optimal arm, outlier-contaminated bandit.

Algorithm	Cumulative regret
Nonparametric TS	67.9 $\pm$ 119.4 (0%)
LinearGaussian TS	116.4 $\pm$ 129.2 (71.5%)
NeuralLinear	94.2 $\pm$ 125.7 (38.8%)
NeuralBootstrapped	138.6 $\pm$ 179.9 (104.2%)
NeuralRMS	143.7 $\pm$ 173.7 (111.8%)
NeuralDropoutRMS	110.7 $\pm$ 174.0 (63.1%)

Appendix

Table 12:

R_{T}

(mean

\pm

std) at

T=1000

. Parentheses: relative increase over Nonparametric TS .

Figure 12: Averaged empirical frequency of playing the optimal arm, exponential-reward bandit.

Figure 13: Mean

R_{t}

(std. shaded) for different

Gibbs_{max}

, linear (left) and sparse linear (right) contextual bandits.

Panel of Figure 14 — Figure 14: Mean $R_{t}$ (std. shaded) for different $Gibbs_{max}$ : Scenario A (top left), Scenario B (top right), outlier-contaminated (bottom left), exponential (bottom right).

Figure 15: Mean

R_{t}

(std. shaded) for different

\gamma

, linear (left) and sparse linear (right) contextual bandits.

Panel of Figure 16 — Figure 16: Mean $R_{t}$ (std. shaded) for different $\gamma$ : Scenario A (top left), Scenario B (top right), outlier-contaminated (bottom left), exponential (bottom right).

Figure 17: Mean run-time in seconds (error bars: one standard deviation), linear (left) and sparse linear (right) contextual bandits.

Panel of Figure 18 — Figure 18: Mean run-time in seconds (error bars: one standard deviation): Scenario A (top left), Scenario B (top right), outlier-contaminated (bottom left), exponential (bottom right).

Figure 19: Mean

R_{t}

(left) and empirical frequency of playing the optimal arm (right), precision oncology bandit.

Algorithm	Cumulative regret
Nonparametric TS	1392.8 $\pm$ 66.0 (0%)
LinearGaussian TS	1358.6 $\pm$ 66.2 ( $-$ 2.5%)
NeuralLinear	1392.5 $\pm$ 68.1 (0.0%)
NeuralBootstrapped	1352.0 $\pm$ 139.2 ( $-$ 2.9%)
NeuralRMS	1400.8 $\pm$ 170.8 (0.6%)
NeuralDropoutRMS	1400.1 $\pm$ 167.6 (0.5%)

Appendix

Table 13:

R_{T}

(mean

\pm

std) at

T=1000

, precision oncology bandit. Parentheses: relative change vs. Nonparametric TS .

Panel of Figure 20 — Figure 20: Graphical model of the hierarchical mixture bandit.

Explore similar work

Jul 14, 2026

Thompson Sampling Is 2-Competitive for Mistakes

We consider Bayesian bandit models and prove that Thompson sampling makes at most twice the expected number of mistakes (selections of a suboptimal arm) as any other policy. Our analysis applies as long as the latent arm processes are independent and each arm evolves only when played. For stochastic bandits with best arm defined via mean reward, this confirms a conjecture of Guha and Munagala from 2014, where the factor

2

is already best possible. The result holds under any nonincreasing sequence of round weights, including fixed horizon and geometric discounting.

Mark Sellke, Gregory Valiant

Thompson Sampling Multi-Armed Bandits

Ask PDF

Sep 12, 2023

Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors

Thompson sampling (TS) is one of the most popular and earliest algorithms to solve stochastic multi-armed bandit problems. We consider a variant of TS, named

α

-TS, where we use a fractional or

α

-posterior (

α\in(0,1)

) instead of the standard posterior distribution. To compute an

α

-posterior, the likelihood in the definition of the standard posterior is tempered with a factor

α

. For

α

-TS we obtain both instance-dependent

\mathcal{O}\left(\sum_{k \neq i^*} Δ_k\left(\frac{\log(T)}{C(α)Δ_k^2} + \frac{1}{2} \right)\right)

and instance-independent

\mathcal{O}(\sqrt{KT\log K})

frequentist regret bounds under very mild conditions on the prior and reward distributions, where

Δ_k

is the gap between the true mean rewards of the

k^{th}

and the best arms, and

C(α)

is a known constant. Both the sub-Gaussian and exponential family models satisfy our general conditions on the reward distribution. Our conditions on the prior distribution can be easily satisfied by a density that is positive, continuous, and bounded. We also establish another instance-dependent regret upper bound that matches (up to constants) to that of improved UCB [Auer and Ortner, 2010]. Our regret analysis carefully adapts and combines recent theoretical developments in the non-asymptotic concentration analysis and Bernstein-von Mises type results for the

α

-posterior distribution. Moreover, our analysis does not require additional structural properties such as closed-form posteriors or conjugate priors.

Prateek Jaiswal, Debdeep Pati, Anirban Bhattacharya +1

Department of Quantitative Methods, Daniels School of Business, Purdue University, West Lafayette, IN 47906, USA. · Department of Statistics, University of Wisconsin-Madison, Madison, WI 53706, USA. · Department of Statistics, Texas A&M University, College Station, TX 77843, USA.

Thompson Sampling Multi-Armed Bandits Posterior Sampling

Ask PDF

Feb 17, 2026

Fast Online Learning with Gaussian Prior-Driven Hierarchical Unimodal Thompson Sampling

We study a type of Multi-Armed Bandit (MAB) problems in which arms with a Gaussian reward feedback are clustered. Such an arm setting finds applications in many real-world problems, for example, mmWave communications and portfolio management with risky assets, as a result of the universality of the Gaussian distribution. Based on the Thompson Sampling algorithm with Gaussian prior (TSG) algorithm for the selection of the optimal arm, we propose our Thompson Sampling with Clustered arms under Gaussian prior (TSCG) specific to the 2-level hierarchical structure. We prove that by utilizing the 2-level structure, we can achieve a lower regret bound than we do with ordinary TSG. In addition, when the reward is Unimodal, we can reach an even lower bound on the regret by our Unimodal Thompson Sampling algorithm with Clustered Arms under Gaussian prior (UTSCG). Each of our proposed algorithms are accompanied by theoretical evaluation of the upper regret bound, and our numerical experiments confirm the advantage of our proposed algorithms.

Tianchi Zhao, He Liu, Hongyin Shi +1

School of Intelligence Science and Technology, Beijing University Of Civil Engineering And Architecture, Beijing, 102616, China. · School of Economics and Management, Tsinghua University, Street, Beijing, 100084, China.

Multi-Armed Bandits Thompson Sampling

Ask PDF