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

Tianchi Zhao; He Liu; Hongyin Shi; Jinliang Li

cs.LGFeb 17, 2026

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

Authors: Tianchi Zhao, He Liu, Hongyin Shi, Jinliang Li

Organizations: 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.

Abstract

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.

Figures & tables

Figure 1: Example of mmWave communications. There are three communication frequencies: $f_{1}=24.25$ GHz, $f_{2}=43.5$ GHz, and $f_{3}=60$ GHz. For each communication frequency, there are three beams to be selected.

Figure 2: Example of Gaussian returns. The histogram in blue is synthesized according to statistics in S&P 500 index in Challa (2023) and the one in red refers to CSI 300 statistics in Li (2023) .

stock	market	return	std $\sigma$
CSI#1	China	0.00060	0.010
CSI#2	China	0.00062	0.010
CSI#3	China	0.00058	0.010
SPX#1	U.S.	0.00040	0.010
SPX#2	U.S.	0.00042	0.010
SPX#2	U.S.	0.00037	0.010

Table 1: Sample return statistics of different risky assets. Our construction of this demonstration refers to the statistics in Li (2023) .

Panel of Figure 3 — Figure 3: Three Unimodal configurations are presented. The vertical bar indicates the standard deviation. There can be either one unique maximum in the expected regret, or the mean monotonically decreases or increases with the arm labeling in the cluster.

Communication frequency (GHz)	Main/side lobe	RSS
24.25	Main	$N(0.6103,1)$
24.25	Side	$N(0.0610,1)$
43.5	Main	$N(0.1897,1)$
43.5	Side	$N(0.0190,1)$
60	Main	$N(0.0997,1)$
60	Side	$N(0.0100,1)$

Table 2: RSS under different communication frequencies.

Figure 5: Cumulative selection of the true optimal.

Figure 7: Cumulative selection of the true optimal.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

arm#	cluster	mean
1	1	0.060
2	1	0.063
3	1	0.070
4	1	0.067
5	1	0.065
6	2	0.036

Appendix

Table 3: Arm configuration of the portfolio selection experiment.

Explore similar work

Bayesian Nonparametric Thompson Sampling for Multi-Armed Bandits
Aug 8, 2018Iñigo Urteaga, Chris H. WigginsMulti-Armed Bandits Thompson Sampling
Department of Applied Physics and Applied Mathematics Data Science Institute Columbia University New York City, NY 10027
Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards
Jun 8, 2026Joel Q. L. ChangThompson Sampling Multi-Armed Bandits
Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors
Sep 12, 2023Prateek Jaiswal, Debdeep Pati, Anirban Bhattacharya +1Thompson Sampling Multi-Armed Bandits
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.

Aug 8, 2018J/K move · Enter open · S save

Bayesian Nonparametric Thompson Sampling for Multi-Armed Bandits

Iñigo Urteaga, Chris H. Wiggins

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

Multi-Armed Bandits Thompson Sampling Bayesian Mixture Models

Open paper AskPDF arXiv

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

Explore similar work

Bayesian Nonparametric Thompson Sampling for Multi-Armed Bandits

Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors