Scalable Exploration via Ensemble++
Authors: Yingru Li
Jiawei Xu
Baoxiang Wang
Zhi-Quan Luo
Venue: NeurIPS 2025 poster ()
Keywords: Reinforcement Learning
Ensemble Sampling
Thompson Sampling
Exploration
Posterior Approximation
Scalable Computation
Primary area: reinforcement_learning
TL;DR: We propose Ensemble++, a scalable framework that achieves the low regret of Thompson Sampling using a tiny, computationally-efficient ensemble, making it practical for large-scale models.

Abstract: Thompson Sampling is a principled method for balancing exploration and exploitation, but its real-world adoption faces computational challenges in large-scale or non-conjugate settings. While ensemble-based approaches offer partial remedies, they typically require prohibitively large ensemble sizes. We propose Ensemble++, a scalable exploration framework using a novel shared-factor ensemble architecture with random linear combinations. For linear bandits, we provide theoretical guarantees showing that Ensemble++ achieves regret comparable to exact Thompson Sampling with only $\Theta(d \log T)$ ensemble sizes--significantly outperforming prior methods. Crucially, this efficiency holds across both compact and finite action sets with either time-invariant or time-varying contexts without configuration changes. We extend this theoretical foundation to nonlinear rewards by replacing fixed features with learnable neural representations while preserving the same incremental update principle, effectively bridging theory and practice for real-world tasks. Comprehensive experiments across linear, quadratic, neural, and GPT-based contextual bandits validate our theoretical findings and demonstrate Ensemble++'s superior regret-computation tradeoff versus state-of-the-art methods.

Scalable Exploration via Ensemble++
Yingru Li
Jiawei Xu
Baoxiang Wang' Zhi-Quan Luo'
'The Chinese University of Hong Kong, Shenzhen
Shenzzhe Research Institute of Big Data
Abstract
Thompson Sampling is principled method for balancing exploration and exploita- tion, but its real-world adoption faces computational challenges in large-scale non-conjugate settings. While ensemble- basee approaches offer partial remedies, they typically require prohibitively large ensemble sizes. We propose Ensemble++, scalable exploration framework using novel shared-factor ensemble architecture with random linear combinations. For linear bandits, we provide theoretical guar- antees showing that Ensemble++ achieves regret comparable to exact Thompson Sampling with only (dd 7') ensemble sizss-iinnficcatly outperforming prior methods. Crucially, this efficiency holds across both compact and finite action sets with either inne-invariant or time-varying contexts without configuration changes. We extend this theoretical foundation nonlinear rewards by replacing fixed fea- tures with learnable neural representations while preserving the same incremental update principle, effectively bridging theory and practice for prehensive experiments across linear, quadratic, neural, and GPT-based contextual bandits validate theoretical findings and demonstrate Ensemble++*s superior regret-computation tradeoff versus state-of-the-art methods.
tasks. Com-
Introduction
Balancing exploration and exploitation core challenge sequential with applications ranging from online recommendation systems, automated content moderation to robotics, personalized healthcare and computer-using agents. A prominent Bayesian solution is Thompson Sampling (TS) [Thompson]
problems,
1933 Russo al. 2018). which maintains a posterior over unknown parameters (or reward functions). At each step. it samples a model hypothesis from this posterior and selects the action appearing optimal under that hypothesis, elegantly balancing exploration of uncertain actions and exploitation of seemingly high-reward ones. Despite its elegant theory and strong empirical performance in simpler (conjugate) bandit scenarios, TS encounters serious scalability hurdles in modern settings with high-dimensional or non-conjugate (e.g.. neural) models. Maintaining exact posterior samples can be computationally prohibitive, often requiring iterative approximation methods (Laplace, MCMC, or variational inference) that become expensive the time horizon T grows.
Ensemble-Based Approximate Sampling. A widely adopted alternative to full Bayesian updates is ensemble sampling, which keeps model replicas parallel and randomly picks one each round to act, thus approximating Thompson Sampling's 's "draw from the posterior" step [Osband and Van Roy 2013, Osband et al.] 2016 2019]. However, prior theoretical results matching TS's optimal regret in linear bandits, such Qin et al. 22022), require ensemble size M Q(T |^')), where X' is the action space. This large-Ai requirement is often infeasible in nigh-dimensional or Nong-horizon tasks. Moreover, many ensembles demand either repeated retraining or large architectural overhead, raising practical concerns in real-time or resource-constraines environments.
" "Equal contribution. Code:
Plus_ Plus
I Conresponding author: szrlee@gmail.com com.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

x10
Commlated Regret
EpiNet
Ensemblle
Ensemble-4
2.0x
1.0x
6.0x
Parameters
Figure 1: Preview of the regret-computation trade-off in nonlinear bandit (unknown quadratic reward). The x-axis is the number of model parameters, serving as a proxy for computational cost. Ensemble+ + outperforms state-of-the-art baselines Ensemble+ and EpiNet. See details Section
Our approach to this challenge follows a principled strategy: we propose Ensemble+ a general framework using incremental updates suitable for complex models with non-conjugate posteriors. To rigorously analyze its core sampling mechanism and establish theoretical guarantees (particularly regarding ensemble size), first analyze its instantiation in the tractable linear setting. This analysis provides foundational evidence for the mechanism's 's efficiency. method, using incremental SGD updates and neural network, achieves strong performance in the challenging non-conjugate settings it was designed for thereby bridging theoretical understanding with practical applicability.
then demonstrate that the general
1.1 Key Contributions
In this paper, we propose Ensemble+ for scalable approximate Thompson Sampling that obviates the need for large ensemble sizes or costly per-step retraining:
Novel Approximation Mechanism: We introduce Ensemble++, which maintains single shared ensemble matrix factor incrementally updated via a random linear combination scheme. This fundamental innovation enables efficient approximate posterior sampling without large ensembles or costly per-step retraining.
Theoretical Breakthrough in Linear Bandits: We prove that Linear Ensemble+ Sampling, with an ensemble size of only M = Odd T), matches the regret order of exact Thompson Sam- pling. This is foundational result for our broader approach. Specifically, it achieves regret of O /T2 T)3/2) for compact action sets and O'd- log | log 7') for finite action sets. Crucially, the same algorithm applies to both compact and finite action sets, whether in invariant varying contexts, without changing algorithmic configurations. This dramatically improves on prior analyses requiring. for example, M = Q(T (x [Qin et al. (002).
Neural Extension: We extend these ideas by incorporating neural networks. replacing fixed linear features with learnable neural feature extractor while keeping the same incremental-updae
principle. This yields a flexible approach for complex, high- dimensiooaii reward functions.
Empirical Validation: Through comprehensive experiments on synthetic and real-world bennhhmarks-includine quadratic bandits and large-scale neural tasks involving GPTs-we demon- strate that Ensemble++ achieves superior regret-ss-commptation trade-offs compared to leading baselines such as Ensemble+ [Osband et al. 2018 2019) and EpiNet [Osband al. [023a (see Fig. and Section 5); and validate the theoretical results of linear Ensemble++ sampling.
This work both closes a longstanding theoretical gap in linear ensemble sampling and provides flexible framework for deeper models. We describe linear Ensemble++ sampling and neural extension in Section 3 provide full theoretical analysis of our linear scheme Section 4 and present empirical evaluations in Section 5 building the foundational concepts in Section

---

2 Background and Related Work
2.1 Sequential Decision Making under Uncertainty
We consider a sequential decision decision-making problem over a time horizon T. At each time step t:
The agent observes decision set X; C X. which may change over time (e.g., due to evolving context or the appearance of new candidate actions).
The agent selects action X E X; based on history H, = (X,, X1, Ti....,,--11 X,, ).). It then receives a noisy reward Y, = f (X.) + Et, under unknown reward function f and noise et.
The agent's cumulative regret measures how much reward is lost by not picking the best action:
R(T)
Σ max LEE
f (x) (X.)].
key challenge is learning unknown reward function f (exploration) while simultaneously selecting good actions from X, (exploitation) in T time periods.
2.2 Thompson Sampling and the Scalability Dilemma
Principled exploration with Thompson Sampling. A popular Bayesian approach to sequential
decision-making is Thompson Sampling (TS) [Thompson] 1933 Russo 2018). Given a posterior distribution over an unknown reward function J (or unknown parameters 0*), Thompson Sampling operates as follows at each time t: (1) Sample a hypothesis 0, from the current posterior, (2) Select the action X₁ = arg ma fe, (z) under that hypothesis. (3) Observe the reward Y,, and (4) Update the posterior distribution given (X,, Yt). By sampling from its posterior, TS naturally balances exploration and exploitation.
The scalability dilemma. While elegant, TS faces scalability hurdles. When an environment model belongs to conjugate family (e.g., in high-dimensional or non-conjugate cases (c.g., neural nets), exact Bayesian updates become expansive intractable [Russo al. 2018). Approximate methods (Laplace, MCMC, variational inference) can introduce large computational overheads and/or biased uncertainty estimates [MacKay 1992 Welling and Teh] [201 Blei et al. 2017 Xu et al. 2022 approximate posterior approaches.
posterior updates tractable. However,
These challenge motivate scalable
2.3 Approximation Techniques for Thompson Sampling
Local perturbation. For Sheer-Gaassian bandits, local perturbation (Papandreou and Yuille 2010 offers an Odd2) per-step update to emulate posterior samples. It incrementally maintains A, 4 EE A A. + X.Zi), where Åo (0, Σo) and Z. NN 1). If actions {X.) were non-adaptive, μ4 + A, would be an exact posterior draw. However, adaptive action selection intro- duces sequential dependencies. biasing these draws as A, {Xa]sse no longer matches NO, E,). Resampling all perturbations {Z,} from scratch at each step resolves this but is computationally prohibitive [Oshand et al. 2019 Kveton et al. 2020aa].
Ensemble sampling. Ensemble sampling (Osband and Van Roy 2015 Osband al. 2016 Lu
and Van Roy 2017) is a widely used alternative, maintaining M models and randomly selecting one per round act. While empirically effective with moderate M, theoretical guarantees often lag. For instance, Qin al. 2022) showed that matching exact TS's VT /ty-yyp regret in linear bandits requires M = S(TT [28) ). Recent work by Lee and hwan Oh 2024 also explores ensemble methods the understanding of ensemble size requirements under different analytical approaches. A key open question has been whether TS-comparable regret can be achieved with practically small ensemble size, especially one that does not scale with T' |
for linear bandits, contributing
Approaches for Non-Linear Models. In non- linear or neural settings, methods like Ensemble+ (Os band et al. 2018 2019 and EpiNet [Osband et al., 2023a b) adapt ensemble ideas, often by training members on perturbed data or using architectural modifications to inject uncertainty. While empiri- cally successful, these methods typically rely on large ensembles or lack the rigorous ensemble size and regret guarantees established in linear settings. The challenge remains to develop methods that
3

---

are both theoretically grounded in simpler settings and practically scalable to complex, non-conjugate domains. Our work, Ensemble+++, is designed address this gap.
3 Ensemble++ for Scalable Thompson Sampling
We now introduce Ensemble++, unified and scalable approach approximate Thompson Sampling in both linear and nonlinear bandit environments. 'hhe key technical novelty is to maintain a shared ensemble factor incrementally, thereby approximating posterior covariance (in the linear case) or capturing epistemic uncertainty (in the neural case) without requiring a large ensemble size or repeated retraining from scratch. We begin with Linear Ensemble+ + Sampling (Section 3.1), describing its incremental matrix-facte updates and explaining how it approximates Thompson Sampling with only M = d log T ensemble directions. We then extend these ideas to general Ensemble+ (Section 3.3 using the same symmetrized regression principle (Section 3.2) but replacing linear features with trainable neural representation.
3.1 Linear Ensemble++ Sampling
Consider linear contextual bandit, where each action X, E Rd and reward Y. (0", Xee+ ((0,,).. Let (ju, Ex) be the usual ridge-regression posterior updates:
x-' - XXX, = -.= (x + +XY.)
(2)
The (dd)) cost for standard TS comes from matrix factorization for sampling. Linear Ensemble+
Sampling avoids this by maintaining a matrix A, E RdxM that approximates 2 incrementally:
Initialization. Construct Ao = VM Ao. A0,M] with each ensemble Åo, ~ ~O, Ep).
Per-step procedure. (1= 7):
1. Action selection:
Sample "reference" vector Se E RM from Pg (e.g., Gaussian; detailed in Appendices and Fl. Form
(G))) 14-1 + 1
via a random linear combination of the columns, then choose X = arg maxxex (x,, Oc(G)). 2. Observe reward Y, sample a "perturbation" vector Z, E R.M from Pz. and update μr via Eq. and update ensemble matrix A,- [Ai, (A,,,...,AAA.M as following:
A M A1 + X2 XzZi,m)
Vm
A. Ex A2
Approximate Posterior Sampling. With M = O(d 7),, our analysis (see Section 4 shows that Σx < A, A, < 2 E,, 0A <t T, with high probability. Hence, for Ç ~~ (0, IM the random vector /4 + A.C serves an approximate sample from ((,,, Ex), enabling near- Teaom-ooosoon Sampling performance. The key insight of Linear Ensemble++ is that a relatively small number of properly updated ensemble directions can capture the essential uncertainty structure needed for effective exploration, without requiring full independence between ensemble members. By maintaining a shared factor incrementally, avoid both large storage requirements and costly recomputation from scratch at each step. We emphasize that Pt and Pz can be chosen from distributions like Gaussian, coordinate or cube, each with different performance (Sections and
3.2 A Symmetrized Sidge-Regression View
An alternative perspective derives Ensemble++ from a ridge-regression objective. First, note that:
(1) The base parameter (4 solves the usual ridge regression objective min, Σ. [Y, (b, x,)] +
||b1|2 (2) Each column in A, can be seen perturbed ridge solution that includes random offsets Zem for each data. Combining them yields single objective for all parameters:
+ - (b. xx)) (6x-()x,)) min
M
+ Σ
(fm, x.i) )² + x1111= Σ 10mm 12) (5)
Za,m
b. (.m) am1

---

Assuming Ao 0, Eu = I and d..m 1 Au. the closed- form solution (b), (6 coincides
VM
with the incremental updates in Eq. and Eq. (4) when identify
Pr
t, or, + 00.m-
(6)
Symmetrized Loss. Finally, from a random lincar combination view (c.f. Eq. 3 and Eq. (6). define the ensemble prediction function
flinear (x, (z,
Si (0m + 0o,m)).
and let = {(x,, Y. 2. 2=)]==1 with 2, = (Z,.1..... a.) symmetrized objective includes both (+2,,,) and -m,,m) for each data point be defined:
M
L(0; (10;
Σ Σ
Y, 32.,m s(Xo, Bem))² + 2l101r
(8)
m= SE (E(+1)
Minimizing Eq. recovers the same solution Eq. (5) since the symmetrized slack variable can- cels out the cross-term. This "two-sided" perturbation perspective extends naturally to Ensemble++.
3.3 Ensemble++ for Nonlinear Bandits
Real-world tasks frequently require nonlinear function approximators (e.g., neural networks) for high-dimensional inputs or complex reward structures f*. Ensemble++ retains the same "shared ensemble factor"' principle but replaces linear features with a learnable network.
Model Architecture.
We generalize Eq. 7 by letting ha;;; w) be neural feature extractor:
fo(2, (h(a; 6 6+
Σ Sm (0. + 0),m)),
m=1
where 0 = (w, 3) are learnable parameters, and (0o.m are fixed random "prior" directions. Different from Linear Ensemble++ Sampling, there no closed-form update for and {0m). J.
Symmetrized Loss and SGD. Define the same symmetrized objective T(0; (o) as in Eq. (8) except that fe is now a neural mapping. At time step é, we store (X,, Ye, 2e) in a FIFO buffer D
(capacity C), then run fixed number G SGD steps to update: B n VoL(B D, fo).
Algorithm 1 Ensemble++
1: Initialize 0 = (w, b, {0m)), prior ensemble (ōu.m.) }, FIFO buffer D of capacity C'
2: for = 1 to T do
3: Sample Çe ~ Pc; select action X, = arg maX fa(x, G)
4: Observe reward Y;; sample 2, ~ Pa; add (X,, 2, Y,. z,) to buffer D (pop oldest if D C)
5: Perform SGD w.r.t. L (0: D, fe) (c.f. Eq. (8) up to G steps
6:
end for
Algorithm [ summarizes: by capping C' and G, the agent ensures constant-time updates even as t grows. Through comprehensive empirical studies in Section 5 and Appendix [F] Ensemble++ demonstrates strong performance on complex and high-dimensional reward functions. For clarity and reproducibility, a detailed implementation Ensemble++ is provided in Appendix
4 Theoretical Analysis
We now analyze the Linear Ensemble++ Sampling to provide foundational theoretical justification. While derived for the linear setting, these results establish the fundamental efficacy of our core mechanism the ensemble factor with incremental updates which we leverage in non-conjugate environments in Section 3.3 W.L.O.G., we impose the following mild assumption.
Assumption 4.1. The random noise & satisfies [exp(s<;) < H4, X,) < exp 2
VsER.
R,
where H, is the history up time t. In addition, all actions satisfy ||ж||| 1 for X.
5

---

4.1 Key Lemma: Covariance Tracking under Sequential Dependence
critical step in analyzing Linear Ensemble++ Sampling is to ensure that its incremental updates accurately track the true posterior covariance Σg. Specifically, recall the Ensemble++ update for the matrix A, (Eq. (4)) which aims to approximate E./² even when actions X₃ chosen adaptively based on prior [ The following lemma, a variant of a sequential Johnson-Lindense type result, establishes that provided M on the order of d log T, A,A, remains a constant- factor approximation to E, (posterior covariance defined in Eq. (2))
Lemma 4.2 (Covariance Tracking via Sequential JL Variant). Let {zr)i=1 be random vectors in RM such that they are conditionally /1/M-sube iaussiaa and are unit-norm almost surely. Define A, via the recursive update Eq. { in Linear Ensemble+ +, and let E, be the exact ridge posterior covariance from Eq. (). If the ensemble size M satisfies
M 2 320 dl log
2+ Fmim
96
v Volun +T
+ log 1 + mmn
(mm)
=
d(lo8 +lg
(9)
where s inf ||||== ||a|
and
$ mmax
|a|||a||=1 ||a||3
Then with probability at least 1 1-6 8.
20
Vt VtST: M A,
Significance. Lemma 4.2 ensures that the Ensemble++ "covariance factor" A,A, tracks the true posterior E; to within constant factors, uniformly for all t < T. Thus, the variance estimates used by Ensemble++ remain trustworthy at each decision point, despite the sequential dependencies in how actions are chosen.
Proof sketch. The central challenge that standard dimensionality reduction techniques like the Johnson-Lindenstrauu (JL) lemma assume independent projections, but our bandit setting creates sequential dependencies between actions and parameters. Our approach introduces a novel sequential JL variant that accounts for this adaptive data collection process.
The proof proceeds two main steps. First, by projecting the matrix updates onto an arbitrary direction, we can apply sequential JL theorem to establish a concentration bound, guaranteeing the approximation holds for any single, fixed direction. Second, we employ a variance-aware covering argument to extend this per-direction guarantee to uniform guarantee over the entire action space. This discretization step crucial for bounding the operator norm of the error and ensuring the covariance approximation holds universally. Formal details are deferred to Appendix C
4.2 Regret Bound for Linear Ensemble++ Sampling
show that Linear Ensemble++ Sampling attains near- hear-optimal regret comparable to linear Thompson Sampling (TS). Let Pę be the reference distribution used in sampling St for action selection (Eq. (3).
Building on Lemma 4.2
Theorem 4.3 (Distribution-dependenn Regret for Linear Ensemble++). Suppose Assumption 4.1 (i.
holds, and Lemma 4.2 applies (i.e., M satisfies Eq. (.). Then Linear Ensemble+ + Sampling, using reference vectors Se ~ Pc, achieves the following regret bound with probability at least 28:
( ((P(B) + p(PP)) + (((pc)
Regret (T) 0
(108
1 1ogg
d log
T dd
d dlo
T dA P((P)
T llg 1
where p(P:t) and p(Pc) are distribution distribution-deppedennt constants related the concentration and anti- concentration properties of Pt. See Appendix for full proof details.
This result demonstrates that our approximation mechanism achieves regret comparable to exact Thompson Sampling while maintaining computational efficiency a key insight that guides our approach in more complex settings. The specific Oig-O scaling of the regret depends on the interplay of d, T, |X| and the choice of Pç. as detailed in Table
Reference Distribution Choices. A crucial design element in Ensemble++ is the choice of sampling distribution Pc. We can sample S. ~ Ps from, e.g., Gaussian distribution N/00, Inr). Sphere distribution VM M-1), Cube distribution U({=1)*), Coordinate distribution u( u( .... +v /MMr) (scaled for unit variance projection). Each choice impacts p(Pp) and p(Pc); see Table [ for examples and Appendix E for formal definitions.

---

Table Representative values of p(Pc) and p(Pc) (or their relevant scalings) for typical distributions.
The ratio (PP)) p(P) influences the regret constant in Theorem 4.3 Here, A denotes the min(a, b).
Pc
VM (1(8-11)
U((+1)*)
ull=vMe.))
p(P)) O(VM A log ( O(VM
log (2)
OlyM A /logla)) (2))
O(VM)
p(P))
7/32
TM
Discussion of Reference Distributions. Continuous--uppon distributions (e.g., Gaussian uni- form on the sphere) often yield more favorable ratio (Ppc/p(Pt) (e.g.. O(VM) or O(v (x()) than discrete distributions like uniform on coordinate vectors (which can lead an (MM3/2 factor for this ratio). This can translate to tighter regret constants. For finite action sets, the /log |X term typically arises from p Pc) via covering arguments.
4.3 Computational Cost, Regret Guarantees, and Comparative Analysis
Computational Cost. Linear Ensemble++ Sampling has a per-step computational cost of (de for updating jl and A,. Given M (d log T') from Lemma 4.2, the complexity is O log T). While standard Linear Thompson Sampling has an (dd) cost, the log T factor for Ensemble++ is a modest price for mechanism that readily extends to non-conjugate settings using incremental SGD updates, as discussed in Section 3.3 In contrast, Langevin- -bsed methods like LMC-TS [Xu et al. 2022] can incur per-step costs Odd
Inflation for Frequentist Regret. We note that our theoretical analysis, like other related works providing frequentist bounds for TS (Abeille and Lazaric 2017]. relies
inflation parameter
(detailed in Appendix Appendix(D) to scale the sampled posterior variance. This scaling is crucial for ensuring sufficient exploration and achieving the stated regret guarantees. thus avoiding the potential for linear regret known to affect vanilla (non-inflated) TS [Hamidi and Bayati| 2020 Abeille et al., 2025]. This parameter implicitly accounted for the bounds presented in Table and we make its role explicit here to clarify the theoretical basis of our guarantees.
Regret and Ensemble Size Comparison. Table 2 summarizes the regret bounds and ensemble sizes for Ensemble++ against prior analysis of ensemble sampling in linear bandits.
Table 2: Comparison of Regret Bounds and Ensemble Sizes for Linear Bandits. X' denotes the action set, d the dimension, and T the horizon. "Inv." refers invariant contexts and "Var." to varying contexts. Ensemble++ achieves its regret bounds with an ensemble size of O l") across all
listed settings. Citations for Linear TS: Agrawal and Goyal [2013), Abeille and Lazaric (2017).
Method
Inv. & Compact
Var. & Compact
Inv. & Finite
Var. Finite
Ensemble Size
ollg")
010///Too T)
Old/Tlngg/ log)) D(a/TTog/X[oog7)
NIA
2022
N/A
Oly log T RTT)
N/A
et
(WlogT))y
0(d T)
Lee and bwan Oh
2024
NAA
N/A
N/A
a[[2 loy 73)
Rnsembles+ (Ours)
Old./Tlog log?)
e(d ?')
Discussion of Comparative Results
vs. Qin et al. [202]]: Ensemble++ offers significant improvement, particularly an exponential reduction in ensemble size (G(dlog 7') vs. 2 ((xT))). This makes Ensemble+ far more practical and scalable for large action spaces or long horizons, addressing a key limitation prior ensemble sampling analysis to achieve TS-comparable regret.
Jotting,AAsh vs. Ash et al. [2022]: For the finite arm setting, [Ash et al. 2022 provide an excellent specialized result. Our work complements theirs in two key ways: (1) We provide, to our knowledge, the first rigorous regret bounds for an incremental ensemble update in the linear bandit setting, resolving a conjecture posed by Ash et al. 2002 (who analyzed the incremental case only for MABs). This incremental nature is vital for practical, non-conjugate extensions. (2) Ensemble++ is a single, unified algorithm that applies to both finite and compact action sets, whereas their analysis is
specialized for the finite-arm case.
vs. Janz et al. |024]: For the compact action set, our O(d3/2 O/d3/2/T(logg 3/3/2) regret bound is a significant improvement over the O (dd ldg T) VT) bound from Janz et al. 2024]. while using a
7

---

comparable ensemble size (i.e.. ((dlog vs. their ((d). This theoretical improvement stems directly from our novel from our sequential Johnson- -indeensttanssss variant (Lemma 4.2).
architecture and the tighter concentration bounds derived
vs. Lee and hwan Oh [024]] This concurrent work also analyzes ensemble sampling for linear bandits. While employing different analytical techniques, Ensemble++ provides distinct advantages:
Ensemble Size Scaling: Our (gg T) scales with dimension, whereas their ( log T) scales with action set size. When d < | (common in practice, e.g., recommender systems), Ensemble++ + requires significantly smaller ensemble.
Regret for Finite Actions: For finite action sets, our regret D(dyTlon X log T) is sharper than their (Toog (T T)) (only applicable in the invariant-conter case) whenever (X| T Generality and Strengths: Ensemble++ is the first approximate TS method to achieve near-optimal regret matching exact linear TS across all four common setups (Invariant/Vann (arrying contexts Com- pact/Finite action sets, shown in Table 2 with single, unified algorithm and analysis framework. This flexibility across action space structures and contexts, without requiring algorithmic changes, is key strength. Furthermore, it achieves this with computationally feasible ensemble size of (d and a practical per-step complexity of (d log T). The core mechanism' 's design also prioritizes extensibility to non-linear models, demonstrated in Section 3.3
Overall, these theoretical results for Linear Ensemble++ Sampling confirm that it effectively balances statistical efficiency (near-optimal regret) with computational tractability (small ensemble size, manageable per-step cost) and broad applicability. This provides solid foundation for its extension to more complex, non-linear domains.
5 Experiments
In this section, we investigate the efficiency and scalability of Ensemble++ in varying linear and nonlinear contextual bandits as introduced in Section [ To empirically validate our theoretical insights, we first evaluate its performance in linear bandit settings.
5.1 Empirical Study on Linear Ensemble++ Sampling
We construct the Finite- action Linear Bandit task following prior research [Russo and Van Roy 2018 In this setup, the finite decision set X' is formed by uniformly sampling actions from 11/Vd, 1 /dja where d is the ambient dimension. The reward function is linear, perturbed by an additive Gaussian noise term. A detailed implementation is provided in Appendix F.
Fretnadior Lanour Beaki
Pesteacter Lase Benii
Faileactio Bools X200000
Pielesacion Busli 27--00000
12
12
0.88
0.00
230
26
750
10.00
3.00
750
1000
31
10
10
330
00
Diussooo
(b)
Figure 2: Performance in Finite-action Linear Bandit. All experiments are repeated over 200 random runs to ensure robust results. (a) Comparison results under d = 50 and |X|| = 10, 000. ES denotes Linear Ensemble Sampling, ES++ denotes Linear Ensemble++ Sampling. and TS refers to Thompson Sampling. (b) Minimum ensemble size M required for Linear Ensemble++ Sampling to match the regret performance of TS.
Advantage over Ensemble Sampling. We consider a special case of Linear Ensemble++ Sampling using a coordinate reference distribution, which effectively performs uniform sampling among sym- metrized ensemble members, akin to vanilla Linear Ensemble Sampling [Lu and Van Roy [017]. We compare the regret Linear Ensemble++ Sampling (with a Gaussian reference distribution) against Linear Ensemble Sampling across different ensemble sizes M in Fig. [[a). For a fair comparison, both methods utilize the same spherical perturbation distribution. The results Fig. 2]a demonstrate that Linear Ensemble++ Sampling significantly outperforms Linear Ensemble Sampling across various
8

---

ensemble sizes. Notably, Linear Ensemble++ Sampling can nearly match the performance of TS with M == 8, achieving this with half the computational cost of Linear Ensemble Sampling.
Optimal Ensemble Size Scaling, To empirically validate our theoretical prediction of M (dd T, we investigate the minimal ensemble size M required for Linear Ensemble++ Sam- pling to match the performance of TS. The minimal M is determined by the criterion: M min M
(egiet) I 0.02). We set a fixed, finite time horizon (T 1000), which renders this metric a non-asymptotic goal. We evaluate this across varying decision set sizes X and ambient dimensions d. As depicted in Fig. 2[b,, the minimal M exhibits a linear relationship with and remains largely unaffected by | strongly supporting our theoretical claims.
T
5.2 Ensemble++ for Nonlinear Bandits
To evaluate Ensemble++ (c.f. Algorithm|| D in more complex scenarios, we consider several nonlinear
contextual bandits: (1) Quadratic Bandit: Adapted from Zhou et al. 2020)). with reward f(z)
10 10-2(x TOTTO z),, where
IRd is the action feature and e E gaxd contains random variables
from (0, 1). (2) Neural Bandit: A binary classification task adapted from Osband et al. 2002
2023a using 2-layer MLPs (50 units, ReLU) with two logit outputs. Bernoulli rewards
0. are sampled via softmax probabilities. (3) UCI Shuttle: Following [Riquelme et al. [2018)
Kveton et al. 2020b we create contextual bandits for N-class classification using the UCI Shuttle
dataset Asuncion et al. (0077]. (4) Online Hate Speech Detection: Built using a language datase
The agent decides publish (reward for "free". -0.5 for "hate") or block content (reward 0.5).
Detailed descriptions of these bandits are in Appendix F.2 For all algorithms, we use 2-layer ML.ss (64 units) the backbone for the first three tasks, and GPT for the last. Implementation details for each algorithm are in Appendix A.7.1
Seate
Svard Porde
Est.
Speech Dntarkee
Petued
Croody
Figure 3: Comparison results across various nonlinear bandits.
Comparison Results We benchmark Ensemble++ against Ensemble+ (Osband et al. 2018 2019). EpiNet Osband al. 2023a b). and Greedy baseline (to exglaiggte needs). As shown in Fig. Ensemble++ consistently achieves sublinear regret and higher accuracy. In the Quadratic Bandit, Ensemble++ converges rapidly while other baselines exhibit linear regret. For the Hate Speech Detection task, Ensemble++ outperforms Ensemble+ by 5%, showcasing its scalability with complex networks like Transformers. This task's framework, extendable to applications like recommendation systems and content moderation (see Appendix G). highlights Ensemble+++ 's real-wort woaldw utility. Note that EpiNet could not be applied to the Hate Speech Detection task due to implementation details discussed in Appendix A.7.1.. Moreover, comprehensive comparisons with LMCTS (Xu et al.) [022] detailed in Appendix confirm that Ensemble++ consistently achieves sublinear, smaller regret with bounded and lower per-step computation costs across a variety of nonlinear bandits.
exploration
Regret vs. Computation Trade-off. Ensemble++ achieves sublinear regret with moderate com- putation cost, as demonstrated in the Quadratic Bandit (results in Fig. D). We measure compu- tation cost by the number of network parameters and evaluate methods in the Quadratic Bandit (d = 100, | 1000), ensuring fair comparison by using identical hidden network architectures and optimization schedules for all algorithms. Additional results in the Neural Bandit (Fig. [4] Appendix F22) corroborate this: across various ensemble sizes M, Ensemble+ surpasses baselines like EpiNet and Ensemble+ on the regret-compute frontier, affirming the cost-effectsveness of its

---

random linear combinations plus a shared base. Appendix A.7.1 further discusses the relationship between ensemble size and network parameter size for Ensemble++ and baselines.
10
Quadratic Bandit
Curmlated Regret
500
1000
1500
2000
2500
3000
Action Size
M
M
32
M
128
Figure 4: Scalability of Ensemble++ with varying decision set sizes ((x())
Ablation Studies on Scalability. Consistent with linear bandit findings, the regret performance of Ensemble++ in nonlinear bandits is also largely inaffected by decision set size, as shown in Fig. This further supports our theoretical analysis Section Larger ensemble sizes M yield additional benefits, mirroring observations in linear bandits. Furthermore, we provide more detailed empirical studies in Appendix F) Specifically, we verify that Ensemble++ maintains comparable performance even with buffer capacity significantly smaller than the total time horizon in Fig. [5] Additionally. Fig. 16 provides guidance on choosing the sampling distribution Pe and suggests that the choice of perturbation distribution has negligible impact on performance when using neural network.
Concluding Remarks
Thompson Sampling's principled treatment of exploration has inspired extensive research into Bayesian methods for sequential decision becision-making. Yet large-scale and non-conjugate contexts remained a hurdle: exact posteriors are infeasible, and naive ensemble approximations often demand huge ensemble sizes or high retraining cost. We introduced Ensemble++, showing how to:
maintain a shared ensemble matrix A, in the linear case, with ensemble size M O log T',, achieve incremental (dd M) )-time updates that approximate the posterior covariance square root
x despite adaptively collected data,
unify base and ensemble parameters within symmetrized regression objective that admits a closed-form solution (linear) or an SGD solution (ncural).
As result, Linear Ensemble+ Sampling achieves Thompson-like VT regret across diverse linear bandit settings (c.f. Section 4.3 and Table 2 without the previous M-vs-T scalability conflict typical of ensemble methods. This strong theoretical and practical foundation is seamlessly extended to the neural case, where the same symmetrized regression objective guides a trainable feature extractor, enabling broad applicability in complex, nigh-dimensional problems. Our experiments further demonstrate strong empirical performance, often superior to alternative ensemble methods, attributed to (i) computationally feasible ensemble size and (ii) efficient incremental updates.
Future directions. Ongoing work focuses on providing tighter theoretical bounds for the neural extension. particularly promising direction is applying Ensemble++ to LLM agents. The sequential decision-making involved in multi-step reasoning and tool use presents high- giggh-imensional, non- conjugate challenge where managing uncertainty is critical. Naive ensembling of foundation models is computationally prohibitive, but the parameter-efficient offers a scalable method to approximate Thompson Sampling over an agent's 's policies. We are actively exploring how this framework can manage epistemic uncertainty in an LLM's reasoning paths, effectively allowing an agent to explore which strategies or tools lead to the best outcomes. By addressing the critical interplay between Bayesian exploration and scalable computation, Ensemble++ opens the door for more principled and effective online learning and decision-makinn in the next generation of AI agents.
design of Ensemble++
10

---

Acknowledgments and Disclosure of Funding
The work of Z. Luo was supported in part by the Guangdong Major Project of Basic and Applied Basic Research (No. 202380303000001, the Guangdong Provincial Key Laboratory of Big Data Computing, and the National Key Research and Development Project (No. 2022YFA1003900) The work of B. Wang was supported in part by the National Natural Science Foundation of China (No. 72394361) and an extended support project from the Shenzhen Science and Technology Program.
References
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011a.
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Online least squares estimation with self-normalized processes: An application to bandit problems. arXiv preprint arXiv:1102.2670,
201
Marc Abeille and Alessandro Lazaric. Linear thompson sampling revisited. Electronic Journal of Statistics, 11),, 2017.
Mare Abeille, David Janz, and Ciara Burke. When and why randomised exploration works (in linear bandits). In Algorithmic Learning Theory, pages 4-22. PMLR, 2025.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127-135. PMLR, 2013.
Jordan T Ash, Cyril Zhang, Surbhi Goel, Akshay Krishnamurthy, and Sham M Kakade. Anti- concentrated confidence bonuses for scalable exploration. International Conference on Learning Representations, 2022.
Arthur Asuncion, David Newman, al. Uci machine learning repository, 2007.
David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational inference: A review for statisticians. Journal of the American statistical Association, 112(518):859-8777 2017.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 408-214.10 JMLR Workshop and Conference Proceedings, 2011.
Corp. The x rules: Safety, privacy, authenticity, and more. Inttps://help: http::///etp..titte..... twitter...t........ cww/ en/ halles-and-pollcciissss--rees 2024. Accessed: 2024-07-09.
Vikranth Dwaracherla, Xiuyuan Lu, Morteza Ibrahimi, Ian Osband, Zheng Wen, and Benjamin Van Roy. Hypermodels for exploration. In International Conference on Learning Representations, 2020. htrllatpppe///peeeeeeeeee//////p
Geir Evensen. Sequential data assimilation with a nonlinear -uasi-geottrophic model using monte carlo methods to forecast error statistics. Journal of Geophysical Research: Oceans, 99(C5): 10143-10162, 1994.
Geir Evensen. The ensemble kalman filter: Theoretical formulation and practical implementation. Ocean dynamics, 53:343-367, 2003.
Robert Gorwa, Reuben Binns, and Christian Katzenbach. Algorithmic content moderation: Technical and political challenges in the automation of platform governance. Big Data & Society, 7(1): 2053951719897945, 2020.
T. H. Gronwall. The gamma function in the integral calculus. Annals of Mathematics, 20(2):35-124, 1918. ISSN 0003486X. URL http::/www. jstor. . www.oogg//saaeee. 196718099
Nima Hamidi and Mohsen Bayati. On frequentist regret of linear thompson sampling. arXiv preprint 2rXiv:2006.06790, 2020.

---

Lawrence Hollom and Julien Portier. Tight lower bounds for onti-concentaation of rademacher sums and tomaszewski's 's counterpart problem. arXiv preprint arXiv:2306.07811 2023.
David Janz, Alexander Litvak, and Csaba Szepesvari. Ensemble sampling for linear bandits: small ensembles suffice. The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL htt.tttts///peeeeeeeeee http:///s/.pppeerrreeeeee///e//p
William Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. In Conference Modern Analysis and Probability, volume 26, pages 189-206, American Mathematical Society, 1984.
Daniel M Kane and Jelani Nelson. Sparser johnson-lindennstruus transforms. Journal of the ACM (JACM), 61(1): 2014.
Akshay Krishnamurthy, Keegan Harris, Dylan J. Foster, Cyril Zhang, and Aleksandrs Slivkins. Can large language models explore in-context?, 2024.
Branislav Kveton, Csaba Szepesvári, Mohammad Ghavamzadeh, and Craig Boutilier. Perturbed- history exploration in stochastic linear bandits. In Uncertainty in Artificial Intelligence, pages 530-540. PMLR, 2020a.
Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. International Conference on Artificial Intelligence and Statistics, pages 2066-2076. PMLR, 2020b.
John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. Advances in neural information processing systems, 20, 2007.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Harin Lee and Min hwan Oh. Improved regret of linear ensemble sampling. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024. URL https
Yingru Li. Probability tools for sequential random projection, 2024a. URL https///://r org/
abs/2402.144 14026
Yingru Li. Simple, unified analysis of Johnson-lindenstraus with applications, 2024b. URL https://arxiv.org/aat 22tp://bs/2422.... 10232
Yingru Li and Zhi-Quan Luo. Prior-dependent analysis of posterior sampling reinforcement learning with function approximation. In The 27th International Conference on Artificial Intelligence and Statistics (AISTATS), 2024.
Yingru Li, Jiawei Xu, Lei Han, and Zhi-Quan Luo. Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgent. In Forty-first International Conference on Machine Learning, Proceedings of Machine Learning Research, 2024. URL http:tt/aaxiii..ooott aba/ 2402. 10228
Xiuyuan Lu and Benjamin Van Roy. Ensemble sampling. Advances in neural information processing systems, 30, 2017.
David JC MacKay. A practical bayesian framework for backpropagation networks. Neural computa- tion, 4(3):448-4777 1992.
Todor Markov, Chong Zhang, Sandhini Agarwal, Florentine Eloundou Nekoul, Theodore Lee, Steven Adler, Angela Jiang, and Lilian Weng. A holistic approach to undesired content detection in the real world. Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 15009-15001, 2023.
Meta. Facebook community standards. httpas///rranpparecyyy.m wwwp:aaawwwnaaaaaaaaoooo.aom hatp://eee...mttaacoooooocccceee Community-standarde. 2024. Accessed: 2024-07-09.
12

---

Gergö Nemes. Error bounds and exponential improvements for the asymptotic expansions of the gammaa function and its reciprocal. Proceedings of the Royal Society of Edinburgh: Section Mathematics, 145(3)5571-56,, 2015. doi: 10100175000082001130055553
Ian Osband and Benjamin Van Roy. Bootstrapped thompson sampling and deep exploration. arXiv preprint arXiv: 150.00000..000000 2015.
lan Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances in neural information processing systems. 29, 2016.
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018.
Ian Osband, Benjamin Van Roy. Daniel J. Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1-62 2019. URL http:
339 html
lan Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Xiuyuan Lu, Morteza Ibrahimi, Dieterich Lawson, Botao Hao, Brendan O' O'Donoghue, and Benjamin Van Roy. The neural testbed: Evaluating joint predictions. Advances in Neural Information Processing Systems, 35:12554-12566 2022.
Ian Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Morteza Ibrahimi, Xiuyuan Lu, and Benjamin Van Roy. Epistemic neural networks. In Thirty-seventh Conference Neural Information Processing Systems, 2023a. URL sttt::///oeeneevvee.nneeetreeeee
dZqcC1qCmB
Ian Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Morteza Ibrahimi, Xiuyuan Lu, and Benjamin Van Roy. Approximate thompson sampling via epistemic neural networks. arXiv preprint arXiv:2302.09205, 2023b.
George Papandreou and Alan L Yuille. Gaussian sampling by local perturbations. Advances in Neural Information Processing Systems, 23, 2010.
Chao Qin, Zheng Wen, Xiuyuan Lu, and Benjamin Van Roy. An analysis of ensemble sampling. Advances in Neural Information Processing Systems, 35:11602-21114,, 2022.
Reddit.
Automoderator guide. http://www.roddt..c/////eeeeee automoderator// 2024. Accessed: 2024-07-09.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. In International Conference on Leearning Representations, 2018
Sarah T Roberts. Behind the screen. Yale University Press, 2019.
Donald B Rubin. The bayesian bootstrap. The annals of statistics, pages 130-134, 1981.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directer sampling. Operations Research, 66(1):230-252, 2018.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, al. A tutorial thompson sampling. Foundations and Trends in Machine Learning, 11(1):1-96, 2018.
Macicj Skorski. Bernstein-type bounds for beta distribution. Modern Stochastics: Theory and Applications, 10(2):211-22) 2023.
William R Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4):285-299 1933.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices, page 210-268.
Cambridge University Press, 2012.
13

---

Martin J. Wainwright. Ligh-Dimensional Statistics: A -onn-ssmpiotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi: 10.1017/9781 108627771.
Chih-Chun Wang, Sanjeev R Kulkarni, and H Vincent Poor. Bandit problems with side observations. IEEE Transactions on Automatic Control, 50(3):338 355, 2005.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings the 28th international conference machine learning (ICML-II), pages 681-688 Citeseer, 2011.
Lilian Weng, Vik Goel, and Andrea Vallone. Using gpt-4 for content moderation. August 2023. URL https://openai. com inwei/ideiueee
mot--ooooooooett--oomttttooiooo- OpenAI.
Pan Xu, Hongkai Zheng, Eric V Mazumdar, Kamyar Arizzadenesheli, and Animashree Anandkumar. Langevin monte carlo for contextual bandits. In International Conference on Machine Learning. pages -4830-24850. PMLR, 2022.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 11492-11502 PMLR, 2020.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction (Section T) clearly state the paper's main claims and contributions, which are directly supported by the theoretical analysis in Section I aand empirical results in Section and Appendix [F The claims about ensemble size scaling with (d log 7), regret bounds, and empirical performance are backed by rigorous proofs and experiments.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The paper explicitly discusses limitations in multiple sections. In Appendix F gray boxed remark openly acknowledges limitation of Theorem 2. regarding regret bounds when M increases beyond a threshold. The extension to neural networks in Section 3.3 also acknowledges the lack of closed-form updates for parameters. Additionally, Section mentions future directions including developing tighter theoretical bounds for the neural extension.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess..
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover
15

---

limitations that aren't tt acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
The paper clearly states all assumptions (see Assumption 4. for the theoretical results. Main theorems (Lemma 4.2 and Theorem 4.3) are presented with their assumptions and implications in Section 4 Complete proofs are provided in the appendix, with detailed derivations in Appendix C for the key lemma and Appendix for regret bounds. The main paper provides intuitive proof sketches to accompany these formal proofs.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
The paper provides detailed experimental settings in Section and Appendix F For linear bandits, it describes the action range, dimensions, and problem scales. For nonlinear bandits. detailed environment specifications are given for each task (Appendix(F22) The model architecture, hyperparameters (ensemble size, learning rate, buffer capacity, etc.), and implementation details are specified in Appendix B Importantly, the paper explicitly states that all experiments use P40 GPUs (except for GPT-2 experiments, which use V100s).
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
16

---

(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should descrihe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The paper provides the codebase link on the first page: https://gitae
Plus Plus| The datasets used in experiments are publicly avail- able (UCT datasets, hate speech dataset from Hugging Face) with proper citations. For baselines comparison, the paper cites the original repositories used and mentions that some were reimplemented following those repositories" guidelines.
com/
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (tttps://nips.cd
public/guides/Cont Soteedeeee/ooeeSeiisiiiieeses stw.ummmsssoooooccyyco for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ Ttips.cccpubbice gwwc///gueeee/eeeeeee http://ggudeee/eeeuuubbiieeeeeee Cww.Coooddesssioooooooooooooo sssiiiiiiiiiiiciiiiiiocco for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper provides comprehensive experimental details. Hyperparameters are specified in Appendix including network architecture (2-layer MLP with 64 units), ensemble size (M-8), learning rate (0.0001), batch size (128), weight decay (0.01), and buffer capacity (C=10,000), For each environment, the paper describes in Appendix F22 the task settings, dimensions, number of actions, and noise distributions. The choice of distributions for sampling (reference, update, perturbation) discussed in Appendix B. with ablation studies in Fig, 16
17

---

Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
The paper reports statistical significance by running multiple trials with different random seeds. As stated in Appendix F.T. the linear bandit experiments are repeated 200 times ensure robust results. For nonlinear bandits (Appendix [F2). each experiment is repeated with 10 different random seeds. The figures (e.g.. Figs. 2 3nd 18
Justification:
show error bands/bars representing the variability across these multiple runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of eтrоrs is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The paper explicitly states the computational resources used. As mentioned in Appendix [F] "All experiments are conducted P40 GPUs to maintain processing standardization." For the hate speech detection experiments with foundation models, the paper mentions that V100 GPUs were used. The paper also discusses computational complexity in Section 4.3 noting that Linear Ensemble++ has per-step complexity of (d log T'), and compares this alternatives like LMC-TS with O(PT) complexity.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
18

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics hattps://neurip:: http:///wwurisssccpppppcc//ccccc httt:/EEhhhhsieeeeeineeeeeaae
Answer: [Yes]
The research in this paper conforms with the NeurlPS Code of Ethics. The paper uses publicly available datasets with proper citations. It addresses important scientific questions around computational efficiency and effectiveness of ensemble methods. The content moderation application in Appendix G directly discusses ethical considerations around using AI for content moderation, acknowledging the need for human feedback and the risks of over-blockiin wee-bblokingg under- block-g content.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
The paper extensively discusses societal impacts, especially in Appendix G Positive impacts include more efficient and accurate content moderation systems, reduced human reviewer workload, and better handling of ambiguous paper explicitly discusses negative impacts like the risk of over-blocking benign content under-blocking harmful content. The paper proposes that the uncertainty quantification in Ensemble++ helps mitigate these risks by focusing human review resources on truly ambiguous cases.
Justification:
borderline content. The
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
19

---

11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not introduce models datasets that have high risk for misuse. The method is an algorithmic approach for more efficient and effective exploration in contextual bandits. While the paper uses pretrained language models like GPT-2, these used as feature extractors with standard published weights, rather than being novel models requiring safeguards.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The paper properly cites and credits all external assets. For datasets, it cites UCI repository [Asuncion et al. [007]] and the Hugging Face hate speech dataset (with URL). For baseline methods, it cites the original papers and repositories, specifying when code used directly (e.g.. LMCTS from https:/// // gi github. com/ cwm/ http///eehhkk/ee LMCTS) or reimplemented based on published descriptions. For pretrained models like GPT-2, the paper links to the Hugging Face model repository hhttps://huggingfacc. co openai community/ gpt2).
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
20

---

Justification: The paper introduces the Ensemble++ algorithm and provides codebase at /nttps://githul: http::///ggtaabbb.cc////l////e//
__ale_________ Laiiie______________ The algorithm is extensively detailed derivations in Ap- pendix B and hyperparameter specifications. The implementation details for reproduction are thoroughly described in Section 5 and Appendix
documented in the paper, with pseudocode in Algorithm [
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human sub- jects. The experiments are computational, using publicly available datasets and simulated environments.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does involve research with human subjects and therefore did not require IRB approval. The research focuses on algorithmic methods and computational experiments with existing datasets.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
21

---

Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [Yes]
Justification:
The paper uses foundation models (GPT-2 and Pythial4m feature extractors in the hate speech detection experiments described in Appendix G This usage clearly documented. explaining how the models are integrated into the Ensemble++ framework. The paper discusses both frozen and finetuned versions of these models and provides performance comparisons in Fig. T9
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
22

---

Contents
1
Introduction
Key Contributions
2
Background and Related Work
2.1
Sequential Decision Making under Uncertainty
2.2
Thompson Sampling and the Scalability Dilemma
2.3
Approximation Techniques for Thompson Sampling
3
Ensemble++ for Scalable Thompson Sampling
Linear Ensemble++ Sampling
3.2
A Symmetrized Ridge-Regten Regge-Regression View
3.3
Ensemble++ for Nonlinear Bandits
Theoretical Analysis
4.1
Key Lemma: Covariance Tracking under Sequential Dependence
4.2
Regret Bound for Linear Ensemble++ Sampling
4.3
Computational Cost, Regret Guarantees, and Comparative Analysis
5
Experiments
5.1
Empirical Study on Linear Ensemble++ Sampling
8
5.2
Ensemble++ for Nonlinear Bandits
6
Concluding Remarks
10
Additional Discussions on Related Works
25
Thompson Sampling (TS).
25
A.2
Challenges in Scaling Thompson Sampling
25
A.2.I Approximate Bayesian Interence
................................
25
A.3
Gaussian Sampling via Local Perturbation
26
A.3.I
Distribution Matching Proof Outline
26
A.4
Recursive Randomized Least Squares (RRLS)
................................
27
A.5
Ensemble Sampling (ES)
................................
27
A.6
Concluding Remarks and Forward Outlook
29
A.7
Ensemble Methods in Broader Context
29
A.7.1 Detailed Comparison with EpiNet and Ensemble+
30
B Ensemblet+ Algorithm Details
31
B. Design of Reference and Perturbation Distributions
33
Technical Details for Lemma 4.2 (Incremental Covariance Tracking)
34
Fundamental Probability Tool: The Sequential Johnson Johnson-Lindenstrnnn Lindenstrauss Theorem
35
23

---

Applying Sequential JL to the Incremental Update
37
C.2.1
Prior Approximation (Time / 0)
38
C.2.2
Posterior Approximation (Time / 2
38
3
From Per-Direction to Uniform Guarantee: Iellance-Awary Discretization
39
C.4
Putting Everything Together
41
Technical Details Regret Analysis for Theorem 4.3
42
D.I
General Regret Bound
42
D.2 Proof of Theorem 4.3 for linear contextual bandits
43
D.2.1 Proof of Proposition D.5
D.2.2 Proof of Proposition D.6
45
D.3
Proof of Theorem
45
Sampling, Isotropy, Concentration and Anti-concentration
47
E.1
Sphere Distribution P. U(VMSM
47
E.2
Cube Distribution P'c -1(11,-11)
49
E.3
Gaussian Distribution P' NN
50
E,4
Coordinate Distribution P. 2ul2udlMM
teM
50
Sparse Distribution P
E.6
Summary of Distribution Properties
51
In-depth Empirical and Ablation Studies
52
Fl
Additional Experiments on Linear Bandit
52
F2
Additional Experiments on Nonlinear Bandit
57
Ensemble++ Real-World Decision-Making: A Case Study on Content Moderation
58
Motivation: Content Moderation in Real-Time Time
60
Contextual Bandit Formulation
60
G.3
Challenges of Foundation Models Online Decision Makinn
4
GPT-Enneeble++ for Content Moderation
5.5
Experiments: Hate-Speech Detection
61
G.5.1 Results and Analysis
62
G.6
Conclusions Implications
62
24

---

A Additional Discussions on Related Works
This appendix provides further background and motivation for the techniques discussed in the main text, focusing Thompson Sampling and its limitations, local perturbation for Gaussian posteriors, and shemble--asse methods. We also compare Ensemble++ with advanced neural architectures
such Ensemble+ [Osband et al.
2018 2019] and EpiNet (Osband et al. 2023b].
A.1 Thompson Sampling (TS)
Thompson Sampling is Bayesian approach for balancing exploration and exploitation in bandit or sequential decision-making problems (Thompson 1933 Russo et al. 2018 Li and Luo 2024). maintains posterior distribution over unknown parameters (or functions) and selects actions by sampling from this posterior.
Methodology.
At each time step with history Hr, TS does:
1. Sample model: Draw parameter 0g P(0 H4)-
2. Select action: X, arg max fo, (I:), where fo(-) represents the expected reward under model O. ze
3. Observe reward: Receive Y,-
4. Update posterior: Incorporate (X,, Yt) into the posterior P(O (441).
Because TS samples from a posterior that encodes the agent's uncertainty, it naturally allocates exploration to regions (actions) that are less well understood, while exploiting current knowledge of high-reward actions.
Conjugate Settings. In special "conjugate" scenarios, posterior updates tractable:
Beta-Bernoulli Bandits: A Beta prior for each arm remains Beta after seeing Berouulli rewards.
Linear-Gaussin Bandits: With Gaussian priors and Gaussian noise, the posterior remains Gaussian with updated mean and covariance.
Here, each TS update is fast. However, high-dimensional or non-conjugate (e.g., neural network) reward models, exact posterior inference becomes intractable.
A.2 Challenges in Scaling Thompson Sampling
While Thompson Sampling has strong theoretical properties (e.g., near-optimal regret in finite action or linear bandit scenarios), it faces two main challenges when extended to large-scale or complex environments: (1) intractability in non-conjugate models, and (2) the computational overhead of approximate inference methods.
Non- Non-Conjugate Models. Many real-world applications (e.g.. deep neural networks, highly struc- tured rewards) do not admit closed-fome updates, which is the first challenge of intractability. Direct posterior sampling in these cases requires approximate Bayesian techniques.
A.2.1 Approximate Bayesian Inference
Motivation. This leads to the second challenge: the computational overhead of such approxima- tions. To preserve the essence TS (sampling from a distribution over plausible models), various approximate inference methods aim to produce posterior-like samples at each step. However, many of these approaches suffer from high computational overhead.
Proninent Approximate Methods.
Laplace Approximation MMcKay [992]: Approximates the posterior around its mode with Gaussian. Scales poorly if the parameter dimension large.
Uses parametric distribution and minimizes KL. divergence. Handles larger dimensions than Laplace but involves biases based on chosen family.
Variational Inference (VT) BBei al. 2017
Iteratively generate samples from the true posterior. Accurate but often expensive in high dimensions or real-time tasks.
MCMC Methods [Welling and Teh [011]:
25

---

Langevin Monte Carlo (LMC) [uu et al. 2022 A gradient- based MCMC approach adding noise gradient steps. Its iterative nature can be costly in long horizons. More precisely, the per-step computation complexity grows linearly with the size of the history interaction data set.
Key Limitations.
Biased Uncertainty: Approximate posteriors may misestimate uncertainty, harming TS's explo- ration.
Iterative Overheads: Repeated passes over the entire history per step become impractical as T grows large.
Scalability: Quadratic/cubic scaling in model dimension is prohibitive for large networks.
Thus, while approximate methods broaden TS's applicability, their computational or memory costs remain problematic large-scale, non-conjugate settings.
A.3 Gaussian Sampling via Local Perturbation
An alternative for 2010), which incrementally updates posterior samples in (df)) per step avoiding O(d") matrix factorizations.
environments is local perturbation [Papandreou and Yuille
Idea. Suppose 0" N (Mo: Eg) and observations
Yg = x 0r + ww: wI (O,
Then the posterior after observations is ((r,, Ex). Rather than factor E, at each step, local perturbation maintains
A, = Eg S Ao
Ex.7,)
8=1
with Àu ~ (0, Eo) and Zg ~ N(0, 1). Under a fixed -oonaadaptive) design {X,}. A, ~ ~(O0 Ex). hence
0. = μ4 + A, is an exact draw from N (pe, Ec).
Both b4 and A, update incrementally in Odd).
A.3.1 Distribution Matching Proof Outline
For completeness, we briefly sketch why local perturbation yields an exact posterior draw in non-adaptive case.
Let D, {(X,, Y.H.- Then:
E[A, D.] 0, Cov(A, D2) = Et,
implying μr + Ag ~ N(r, Σ.). The key steps:
Mean argument. For each s, Z. ~ N (0. 1) is independent D., so E| Di] = 0. Similarly, An ~ N(O, En) is independent D, and E[Ag D.] = Hence,
E D.]
Ex > EEÁ Dd -
X. E. D.l) = 0.
2=1
Covariance argument.
Because Z, N(O, 1) i.i.d. and Ao N(0, En),
Cov[A, Dj] = Eg E Cov[Ao Dr + Σ X.X_ E (1,1) E.
= =I - En Eo + Σ X.X Eg
= -E, Σ Σ.-
Thus A, ~ (O F.) conditionally on D,, Therefore, O, = 14 + d, has mean μt and covariance and matches exactly Nipe Ex).
26

---

A.4 Recursive Randomized Least Squares (RRLS)
Motivation. Motivated bounded per-step computation requirement, one could attempt to update the parameter vector B, in an incremental, recursive manner.
02 = Σ. 1--10-11 + X, (Y, + Zi))
(10)
where 24 ~ (0, 1) is a fresh random perturbation at each time This yields the Recursive RLS (RRLS) algorithm:
Algorithm 2 Recursive Randomized Least Squares (RRLS)
Initialize 8g ~N Eo)
2: for = 1 to I" do
3: X₃ = arg maxzex, (0)-1,
4: Observe Y
5: Sample Ze ~ (0,
6: Update 0, via equation 10
7: end for
Sequential Dependency However, RRLS introduces sequential dependency because the action X, chosen at time depends on the previous parameter estimate - which itself depends on all past perturbations Z. and past actions X, & L. Due to this sequential dependency, conditional expectation and covariance of 0g no longer match those of the posterior distribution 0" Dz. This because when conditioning on D,, the perturbations 71,... Ze are no longer independent and identically distributed (i.i.d.) Normal random variables. This results in biased estimates and ineffective exploration, giving linear regret in some scenarios. This sequential dependency is illustrated in Figure 5
Time 1
Time
Time
Time t X
Time f
X1
X2
X3
Xe+1
0o
71
Zz
Zz
Za
Figure 5: Sequential dependence due to the interplay between recursive updates and sequential decision-making. Zı.... Ze are no longer independent and identically distributed (i.i.d)) when conditioned on data X,-1-
One potential workaround to resample fresh random perturbations 1 and re-fit from scratch each step (e.g., storing all historical data) restore independence, but this computationally and memory expensive in practice (Oshand et al. 2019 Kveton et al., 2020a and defeats the purpose of a cheap incremental method.
The next subsection describes an approach-ensemble sampling-tha that mitigates sequential depen- dency via multiple parallel parameter vectors, each incrementally updated.
A.5 Ensemble Sampling (ES)
Principle.
Ensemble Sampling (Osband and Van Roy 2015 Oshand al. 2016 Lu and Van Roy
2017) keeps M independent parameter vectors (or models). At time f, it uniformly picks one model m, decide X₁ and then updates all M models incrementally and recursively. Intuitively, if these M vectors approximate M draws from the posterior, the overall policy resembles Thompson Sampling.
Algorithm Outline.
Initialization: f Nuo, Mo) for 1....,... M.
27

---

Action Selection:
mc
Uniform M,), X₁ arg max (ft-1,m,:3)) Z). tEA,
Model Updates: Each O is updated in RRLS-like manner, but with fresh noise Zu Zu
This balances memory usage (M < T) against sequential dependency.
Table 3: Comparison of methods for addressing sequential dependency.
Method
Computation per Step Memory Usage
Sequential Dependency
RLS (M 7)
((T)
High
None
ES (M < ()
((M)
Moderate
Reduced
RRLS (M 1)
((1)
Low
High
Empirical Trade-offs.
If M = T, and each model is selected exactly once at time t (i.e., m, = 6), the Ensemble Sampling method becomes equivalent original randomized least squares (RLS) with perturbations resampling and model retraining at each time step. This approach eliminates sequential dependency entirely but requires huge computation and memory overhead.
. 1, it degenerates to RRLS with minimal memory but strong sequential dependency. Hence, by choosing M < T, one often obtains good practical performance (Fig. 6). This suggest, empirically, ES with moderate M can achieve performance comparable TS while only paying factor of M overhead in memory and a moderate per-step cost.
10
Bandit
Recursive RLS (M-1)
Ensemble Sampling (M-1)
Ensemble Sampling (M-16)
Thompson Samplng (M-T)
Accumulated Rleget
800
1000
Time Period
Figure 6: Ensemble Sampling (ES) with moderate M achieves near-TS performance. Setup: | 10,000 and dimension 50.
Theoretical Limitations Qin et al. 2022 provide a rigorous regret analysis for linear ensemble sampling that could match the regret order of exact Thompson sampling but require M O( (T) to maintain /T scaling in Bayesian regret, major barrier in practical large-scale segee-cale problems. This suggests naively we might need an ensemble size that scales linearly with T or |X infeasible for large action sets and long horizons tasks, contradicting with the empirical findings moderate size of ensembles.
Remark A.1. Qin et al. 2022 consider d-dimensional linear bandit problem with an action set X.
When the true parameter follows standard normal distribution 0" NO Ta), the Bayesian regret bounded by:
|28 (1llog(MT) M
BR(T) < C dT log X
CT
(d log (+]
where C' > Ois universal constant. This bound has two significant limitations:
28

---

1. To achieve the desired /T scaling in Bayesian regret (ignoring constant and logarithmic factors), the ensemble size M must grow linearly with the time horizon T. This requirement undermines the computational efficiency that ensemble sampling aims to achieve.
2. To maintain logarithmic dependence on | in the bound, the ensemble size M must scale linearly with the number of actions |
These limitations become particularly problematic when dealing with compact action spaces. For instance, consider a bandit problem where X' = B3 (the d-dimensional unit ball). To achieve a small discretization error, we need approximately 2d-1 discrete actions. Consequently, following Qin et al.'s bound, the required ensemble size M would grow exponentially with dimension d.
Ensemble Sampling Beyond Linear Models For a general function class F, Ensemble Sampling can be extended to approximate the posterior distribution of the optimal function f E F, e.g. Bootstrapped Ensemble [Osband et al.) [016] and Ensemble+ [Osband et al.) 2018 2019 The agent maintains M models, each representing hypothesis about f based on historical data. At
each time step 1, the agent samples a model my uniformly from {1. 2, 2,..., M) and selects an action:
X, arg m fo, (2r), where fo..,, (x)) is the prediction of ensemble member my for action x. After observing the reward Y, each ensemble member m. updates its parameters 4.+1. by performing stochastic gradient descent on the loss (Eq. (II) starting from the previous iterate f,,m:
Lm (0; D)
Σ (Y, Zmm So(A.))) (()
(11)
where D = H. and Ze are independent random perturbations added to encourage diversity among ensemble members, and (((++1..)) is regularization term. This perturbed training procedure ensures that each ensemble member captures different aspects of the uncertainty in f", representing different plausible hypotheses consistent with the history. The random perturbations Zs,m are independent across time index and model index m. Once realized, Z,.m are fixed throughout the rest of the training, enabling incremental updates for real-time adaptation. This key computational feature compared to methods like Randomized Least Squares (RLS) or Perturbed History Exploration (PHE). In RLS and PHE, fresh independent perturbations for historical data are introduced at each time f, and the model requires full retraining from scratch to ensure diverse exploration of different plausible hypotheses. Yet, it is important to note that the theoretical analysis of Ensemble Sampling beyond linear models remains open research question.
A.6 Concluding Remarks and Forward Outlook
Local perturbation methods (RLS, RRLS) and ensemble-based approximations collectively aim to solve large-scale or non-conjugate posterior sampling in an online manner. Yet:
Recursive RLS (RRLS) is cheap to update but suffers from sequential dependency bias, often giving linear regret in adaptive settings.
Ensemble Sampling lessens sequential dependency empirically with moderate size of ensembles. How, current theory suggest ensemble sampling may require M x T or |XX in worst-case analyses, which is computationally or memory intensie. Moreover, maintaining M independent neural network ensembles is also computationally prohibitive for large models, even with moderate size M = 10 100.
We propose Ensemble++, which addresses these drawbacks by maintaining a single shared factor for covariance approximation, with incremental updates in O(d² M) and rigorous proof that M s dl log I suffices to achieve near-optimal regret that matches exact Thompson sampling. Before concluding, we briefly compare with broader ensemble-based research, including Ensemble+ [Osband et al. 2018 2019 and EpiNet [Osband et al. 2023a]
A.7 Ensemble Methods in Broader Context
History of Ensemble Approaches. ter [Evensen| 1994 (2003) or Bayesian bootstrap [Rubin] 1981]. In modern literature, Bootstrapped
Ensemble methods date back to the Ensemble Kalman Fil-
Ensemble [Osband and Van Roy 2015 Lu and Van Roy 2017 introduced multiple models updated
29

---

with random perturbations or "bootstrap" samples of data. Ensemble+ (Osband et al. 2018 2019 introduced the randomized prior ensembles enhance the exploration efficiency.
Hypernetworks and EpiNet. Some architectures, like Hypermodels [Dwaracherla et al. 2020 or Epistemic Neural Networks (EpiNet) [Osband et al. 2023a], treat the ensemble index or random seed as additional network imputs, effectively learning a mapping from random "epistemic index" to parameter space. Although conceptually appealing, they typically lack any rigorous understanding and proven regret bounds and may suffer from large parameter counts, discuss next.
A.7.1 Detailed Comparison with EpiNet and Ensemble+
EpiNet Overview. EpiNet is designed to estimate epistemic uncertainty in neural networks by injecting an "epistemic index" z E M into an MLP layer. Its final output is a combination of:
A base prediction (z{(x) on the raw input
An epiner MLP o,,(2e ã, 2.) that processes the concatenation of raw input the hidden repre- sentation E IR_ of a and the random index 2,
A fixed prior o² (zz 2). typically collection of M small MLPs with raw input x as the input, each producing per-class offset and combined with random as the output.
Hence, the final model is
[E)) = Mę(xr) + (1r, =]) + (xr,))
This architecture can learn uncertainty- aware predictions but often suffers from large parameter footprint (due to multiple MLPs) and lacks any proven regret guarantees in bandit settings. Addi- tionally, because both the epinet MLP and the fixed prior must take the raw input æ, it is challenging to apply EpiNet more complex networks such as Transformers. Therefore, we not compare EpiNet in the Hate Speech Detection task.
Ensemble+ Overview. Ensemble+ extends ensemble sampling to deep neural networks using a randomized prior approach [Osband al. 2018 2019]. Concretely:
A shared feature extractor processes inputs into some hidden representation ă. There are M heads [0m ). each simple linear layer that predicts the reward from उ.
Additionally, a fixed prior network is maintained there are M unique random prior heads that fixed after random initialized, each predicting the additive prior reward from a
separate feature extractor: x f. Also,
This design helps capture model uncertainty by mixing learned features with distinct randomized prior in each ensemble head. However, as with EpiNet, Ensemble+ can become large in parameter count (due to separate prior modules) and currently lacks theoretical regret bounds in deep or high-dimensionas bandits.
Parameter Counts. We compare the number parameters each method. Assuming the number of parameters of the hidden feature extractor is H. we analyze how many additional parameters each method allocates beyond a single hidden feature extractor network.
EpiNet:
Thh epinet MLP has hidden layers that receive [z, -, D input and output MCC (for C' classes or outputs). Following Osband et al. 2023b a). we use 2-layer MLPs with 15 units and bias to construct this epinet MLP. Therefore, we count the parameters of this part as:
(d + D + M + 1) x 15 + (15 + 1) x 15 + (15 + 1) x (M C) 15(dd D M + 1 x 15 + 16 x (M C)
-15d + 15D + 31M + + 16C
15d 15/ 31 + 255 16C.
-he fixed prior P is composed of M small MLPs, each adding parameters. Following Osband et (2023b a). we use 2-layer MLPs with units and bias to construct this prior network. takes the raw input E IRd and each MLP outputs RC, Therefore, count the parameters of this part as:
M x ((d + x 5 (5
C)
= M X 15dd+1)+30+4 30 60) = M x (5d 30 6C) M x (5d +5 3--++66)
30

---

Together, EpiNet can have large overhead as M small prior MLPs or the epinet's hidden size grow. We can calculate the total parameters as:
H 15d 15D + 31M + 255 + 16C + M x (5d + +5 6C).
Ensemble+:
M linear heads, each taking the hidden representation RDD input, produce the main ensemble predictions IRC and each head has the same random prior network. Therefore, we count the parameters of this part
2 M x ((D + 1) C) 2MDC + 2MC.
A separate feature extractor for the M linear prior network heads form the prior offset. Therefore, we count the parameters of this part as H.
This leads to approximately 2M last-layer transforms (main + prior), plus the potential duplica- tion of feature extractors. We can calculate the total parameters as:
2H + M x ((D + 1) x C) = 2H 2M DC 2MC.
Ensemble++:
There are M linear heads without bias for the main ensemble for uncertainty estimation, each mapping RD. - IRC and equipped with the same prior networks. Therefore, calculate the parameters of this part as:
2 x M DxC.
One more base linear head with bias estimate the mean. The parameters of this part are (D + 1) C.
In total, this results in (2M 1) linear layers of dimension D RC. but each is relatively lightweight. We can calculate the total parameters as:
2 M X D C (D+1)xC=+Xxx H (2M + +)DC+CC +C
Computational Efficiency.
Concatenates [xr i. 2] of dimension (d + D + M). driving up the input size for the epinet MLP. The fixed prior a also has multiple small MLPs. Training/inference cost grows significantly with M.
EpiNet:
Ensemble+: Combines main network and a separate prior network, each with M linear heads. While each head is relatively cheap, maintaining two feature extractors can be more expensive than Ensemble+++s single shared representation.
Ensemble++: Each ensemble head is just a R + RC linear map, combined additively with base head. Training/inferenee overhead remains modest, as backprop only flows through linear heads plus one shared feature extractor. The stop-gradient trick can further reduce overhead.
Practical Implications. Empirical studies [Li al. 2024 show that EpiNet's parameter overhead often slows training and can degrade exploration. Likewise, Ensemble+ can be parameter-heavy if the prior network is large or if M grows. By contrast, Ensemble++ uses a single shared representation with relatively simple linear heads (for both ensemble and prior), yielding a smaller parameter footprint and faster training. Crucially, Ensemble+ also provides theoretical foundation guaranteeing near-optimal linear-bandit regret with M Ö(d log T'), whereas EpiNet and Ensemble+ currently lack proven regret bounds.
summary, EpiNet and Ensemble+ push ensemble-based methods toward richer neural function approximation but face large parameter counts and priori theoretical guarantees. Ensemble++ uses lightweight linear heads on top a shared feature extractor-much more efficient in large-scale real-time settings-and does come with rigorous regret analyses for the linear bandit case. Extending those theoretical insights to deep bandits is an ongoing research direction, but empirical results ($5) show strong performance of Ensemble+ relative to EpiNet and Ensemble+.
Conclusion.
B Ensemble++ Algorithm Details
Here we provide detailed derivations and design choices for Ensemble++ algorithm. Let a X denote the input, and h(2;; w) be the shared feature extractor parameterized by w. The extracted features are denoted by
ã 1(2;; w).
31

---

The base network (²; b). parameterized by b, estimates the mean prediction based on the shared features. The ensemble components (3)(s(()); ), Im= )
parameterized by 8m. capture the uncer-
tainty in the prediction. The stop-gradient operator sg(.) prevents gradients from flowing through when computing gradients with respect to Pm. effectively decoupling the ensemble components from the shared layers. The prior ensemble components (1b(2;; f0,m)) m== are fixed throughout the learning process, incentivizing diverse exploration with prior variations in the initial stage where the data region is under-explored. Put all together, 0 {w, b, ...... 0M, 00.1..... 0o.M) are the model parameters. By default, we choose y as a linear function:
( 0) = (i, 0)
the Ensemble++ model predicts via random linear combinations of the base network and ensemble components, with the prior ensemble components fixed throughout the learning process. The model defined as:
5t (x, (x) (z;; + (sg(()); Σ
mmmmm + sg( Oo.mo.mm)
(12)
where C (Gr, S1,M)) is random vector sampled from an sampling distribution Pc- Loss Function Derivation. Starting from the loss function L(0; D) with symmetric auxiliary variables:
M
N Σ
Σ
Σ B1(1,-11
(Y, + 82..m (((;;;b) (x(ss((..) (ss((b((,; 00mm) +b0)).
2M
m=
(13)
Expanding the square and summing over 3:
Σ
(Y,+ + 82s.m b) (x((s((5.); (a.((((;:
1E(L.-1)
Σ
((Y, - -bb(s;;s)) b)) + B(z.,m - sg(b(E, 00,m)) 0m
-E(L-11)
= ((Y, ()): + (Za,m - sg(W(Ts; Oo.m) 1 (sg((t)); 0m)))
since the cross terms cancel out due summing over 8 (1.-1) This leads to the simplified loss function L(O; D):
M
N Σ
Y, bz): + (Z..m - sg(tb((s;; - + ( (14)
(ss((2))::
M
2
m-
Gradient Computations. The gradients with respect to the shared parameters (w, b) are derived solely from the base network loss:
V L(I:D)
Σ (b));;b) Y.) Va, bB
(15)
V)L(O: = Σ (b) Ys) (o,;b.
(16)
The gradients with respect to the ensemble parameters On are independent of the base network:
Ven. L(0: D)
Σ ()(sg(E)): Za.m. Ven. (sg((..): 0m.)
(17)
Note that due to the stop-gradient operator sg(.), the ensemble components do not contribute the gradients of shared parameters.
32

---

Classification Loss Function. For classification tasks, we use the cross-entropy loss function instead of the squared loss function in Eq. [3)
M
N
T(0; D) 2M
CF (X,, (Y,, Y.]) + (0)
(18)
m= s=l (E(1,-1)
where CE(X,Y)=-XX (X, log E. exp X₂) is the cross-entropy loss function, and [Y, 1 Y,] is the one-hot encoding of the label Y,
log
Hyperparameters. For the practical implementation of Ensemble++, we utilize a 2-layer MLP with 64 units and ReLU activation construct the feature extractor h(2;; w.) The ensemble size is set to M = 8, and we use a symmetrized slack variable 3 = 0.01 and weight decay À = 0.01 across all nonlinear bandit tasks. During training, unified batch size of 128 and a learning rate of 0.0001 are employed for all tasks. Based on the ablation studies presented in Fig. T6, we adopt the Coordinate update distributions, Sphere reference distribution, and Sphere perturbation distribution to achieve optimal performance. Two key hyperparameters for training are the buffer capacity C and the number of gradient steps G. As demonstrated in Fig. [5 we found that setting the buffer capacity to C' = 10, 000 achieves strong performance, even for tasks with T 100, 000 steps. For gradient steps G, task-specific optimal values are determined via parameter sweeps. In the case of synthetic bandits, such as the Quadratic Bandit and Neural Bandit, we use a smaller gradient step size of G 1. For tasks involving UCI datasets, we increase the gradient steps to = 50 in Mushroom task and G 100 in Shuttle task.
Summary. We have provided an overview of Ensemble++ in Algorithm | Through comprehensive empirical studies detailed in Section aand Appendix Ensemble++ demonstrates strong performance in practice, even for complex and high-dimensional reward functions. Moreover, we observe that Ensemble++ exhibits consistent performance in the linear setting, where the agent's regret remains largely unaffected by the size of the decision set. This finding, illustrated in Fig. 4 strongly supports the effectiveness of our neural extension. For clarity and reproducibility, we provide the codebase of Ensemble++ at /antps:///nnnymouus :opp:e.uuuuuu.nn....oooooo /ciencce///Ensemblelluu//
B.1 Design of Reference and Perturbation Distributions
In the Ensemble++ algorithm, we distinguish between two key distributions: the perturbation distribution P2 and the reference distribution Pc- While both play critical roles, they serve different purposes and operate under different theoretical constraints.
The perturbation distribution Ps generates vectors z, used in the incremental update of the ensemble matrix factor A, through Equation equation 4 These vectors must satisfy strict theoretical require- ments-they need to be almost surely unit-norm, and conditionally VM -Suu--aussian--- ensure
the covariance tracking guarantees established in Lemma
In contrast, the reference distribution Pg is used during action selection to sample exploration vectors S. for generating parameter samples according to 0, = 0, + ArG. The theoretical properties of Pc directly impact the exploration behavior and regret bounds of the algorithm. Specifically, as shown in
Theorem 4.3 the regret bound depends on the ratio p(P2) where: p(P()*
pf P&) captures the concentration properties of Pc, relating to how tightly the distribution concentrates around its mean
p( P3) quantifies the inti-concentration properties, which are crucial for ensuring adequate exploration in the action space
For effective implementation, the reference distribution Pe should satisfy zero-mean and unit-variance properties (E(Ga) 0 and B[GGTT] = TM) to maintain proper statistical interpretation when used with A, The scaling factors in certain distributions (c.g., VM for sphere distribution) ensure this variance normalization.
We consider five candidate distributions for Pc, each with different theoretical guarantees for explo- ration and computational properties:
1. Gaussian Distribution (Ge NO (M)))
33

---

2. Sphere Distribution (C. VM U($
3. Cube Distribution (G. -1
4. Coordinate Distribution (G. (1 (+er,........................... tear)e
5. Sparse Distribution (s-sparse random vectors):
As shown in Table ! continuous distributions (Gaussian, Sphere, and Cube) generally offer more favorable p(Pc) ratios compared to discrete distributions like the Coordinate distribution. This
p(P.)
translates tighter regret constants in Theorem 4.3 The anti-concentration property p(Pç) is particularly important as it directly influences how effectively the algorithm explores the parameter space, with larger values leading more efficient exploration.
For sampling algorithms and the detailed theoretical analysis of the properties of these distributions (isotropy, concentration, and anticoncentrationn), see Appendix
C Technical Details for Lemma 4.2 (Incremental Covariance Tracking)
This appendix provides detailed proof for Lemma 4.2 which establishes that the Ensemble++ with sufficiently large ensemble size M, can maintain an accurate approximation of the posterior covariance matrix incrementally. The core the argument relies on adapting sequential Johnson- Lindenstrauss (JL) results to the context of adaptive data collection in bandits.
Proof Sketch The recursive update rule for the ensemble matrix factor A₁ in Ensemble++, given by Eq. (4) in the main paper, can be expressed in terms of the inverse covariance Σ, as:
E
A = Σ A Xiz!
(19)
Our proof strategy involves two main steps:
1. Reduction to Sequential Sum:
We first simplify the problem by analyzing the projection of Eq. (19) onto an arbitrary direction. This transforms the matrix update into sum of vector products, resembling the structure required by sequential JL theorems.
2. Application of Sequential JL and Discretization: We then apply sequential Johnson- Lindenstrauss theorem to bound the error in this sum. To extend this result from a single direction all directions (i.e., bound the operator norm of the matrix), we employ discretization argument over the unit sphere.
To build intuition, we first consider simplified multi-armed bandit (MAB) setting where the feature vectors X, are standard basis vectors. In this scenario, the covariance matrix E, becomes diagonal. The update rule in Eq. (19), when projected appropriately, reduces to the incremental update for the variance estimate of single
detailed in example 1 The core challenge, even in this simpler MAB case, is the sequential dependence: the choice of arm X, (and thus the data w. in Eq. (2I) depends past random perturbations (z, }sst- Standard JL. arguments do not directly apply under such adaptivity, necessitating the use of a sequential JL. theorem (Theorem C.6).
Example 1 (Approximate Posterior in a Multi-Armed Bandit). Consider a multi-armed bandit with K independent arms. Let the unknown mean reward of arm be 07, We place Gaussian prior on each arm's mean: 8 ~N(H/: 2). At each time step t, the algorithm selects an arm X, fei..... ex}. where e; is the i-th standard basis vector. The posterior variance (af)² for arm i updated via Sherman Woodbury formula, which simplifies to:
(o:)2 (o²_))² (xx==)))
and (of)² remains unchanged for l # i if arm & was not chosen (assuming unit observation noise variance for simplicity).
Ensemble++ aims to approximate the posterior samples. It stores factor mf E RRM for each arm i such that its squared norm |[ approximates the posterior variance (at)2. An approximate
posterior sample for arm is then formed as μ + (m,, C). where N(0, I M) is a random vector.
34

---

To maintain mf efficiently, an incremental update rule is derived from the general form in Eq. 19).
For specific arm this update becomes:
(of)² mi
(oi_1)² mi + (x,=0,)) Z
(20)
where zę RM fresh random perturbation vectors at each step t. For initialization, set my = σ z for some random vector zó satisfying conditions Theorem C.6 so that ideally ||mi]l (at)²
The crucial observation is that the choice arm X, (and thus the indicator 1 (X,=e,)) depends on all past data and consequently on the past random vectors 2o...., -. Let La,i == [x,=e;) be the indicator that arm i was chosen at step s. Rewriting Eq. (20) for fixed arm i by unrolling the recursion:
(ot) mi =
Σ
Tzss Zz. ==U
while the true precision
(ot)²
Tz
==U
==0
(since si is or 1, r2., .. The goal is ensure that the squared norm of the sum of random vectors approximates the sum of squares of the adaptive coefficients:
Σ J a
J (uniformly over E (O....,T} and all arms
(21)
==0
Standard JL. arguments typically require Tx to be independent of 2,, which is violated here due to the adaptive nature of X,. This motivates the need for sequential such as Theorem C.6
theorem,
which is designed to handle such sequential dependencies.
For the general linear bandit case, where X, are arbitrary bounded feature vectors (not just standard basis vectors), the approach is analogous but more involved. We cannot simply look at individual diagonal elements of E, Instead, we analyze the behavior of the matrix update Eq. by projecting it onto arbitrary directions E gd-1,
EE T X.)2.
This expression has similar sequential sum structure. The term a X; is adaptive scalar coefficient, and z, is the random vector. The core idea is to show that ||a Σ, 1 A.ll concentrates around its expectation, which is related to a Σ,'a. 'a. The proof then requires discretization argument (covering the unit sphere gd-1 with a finite set of representative directions) and union bound to extend the concentration results from these discrete directions to the entire continuous space. This allows to
bound the operator norm Σ A.A, E 1/2 I]I. which equivalent to the desired statement in Lemma 4.2
In the subsequent subsections, we rigorously formalize each of these components, starting with the sequential Johnson-Linddestrrass tools.
C.1 Fundamental Probability Tool: The Sequential Johnson-Lindenstrann Theorem
As outlined in the proof sketch, our analysis the incremental updates in Ensemble++ under adaptive data collection hinges sequential version of the introduces the necessary definitions and the specific sequential JL theorem we utilize. While the original tool from [Li 2024a] was developed for scalar processes, work extends these concepts to handle the high-dimensional vector processes inherent in linear bandits with ensemble methods, requiring the non-trivial discretization argument detailed in Appendix C.3
(JL) lemma. This section
We begin by defining some key concepts within filtered probability space. Let (2,F,F (Fi)LeN, P) be complete filtered probability space, where F is the filtration.
Definition C.1 (Adapted Stochastic Process). A stochastic process (Xt)teı> where / is vector set (e.g., N or (1 E N: 1. 2 4o)), is said be adapted to the filtration (Fi)ter if, for every the random variable X, is Fr-mcauurale.
35

---

Definition C.2 (Conditionally o o-Sub-Gaud Gaussian Random Variable / Process), A random variable
X
(for 0) if its moment generating function satisfies:
Aoo22
E e(xx - exp
AA
A stochastic process (Xe)121 taking values in R is conditionally o gy-sub-Gaussid with respect to filtration (Fi)c20 if X, is Fe-eesurabbl,, and for a non-negative process (0t-1)(21 where dt-1 is Ft mee--beasrrbll, have:
\o 2
E(exp(AXX) Fi-1) exp
almost surely (a.s.), AA E IR
If oy a constant) for all t, the process is called conditionally
For random vector X E RR (or vector process (X1)x21 C R M), it said to be r-sub-Gaussien (or conditionally ry-sub-Gaussiag if for every fixed vector E gM-1, 11 the scalar random variable (u,X) X) (or the scalar process ((v, X())(21) is o-sub-Gaussian (or conditionally respectively).
Definition C.3 (Almost Surely Unit-Norm). A random vector E RMM M is said to be almost surely (a.s.) unit-norm if ||x||2 = 1 almost surely.
Remark C.4 (Properties of Perturbation Distribution Pz). The perturbation vectors 2, E RM used in Ensemble++ are drawn from distribution Pz. For theoretical analysis, particularly for applying Theorem[C.6 these distributions are chosen and scaled such that specific properties are met. When normalizing all specific distributions discussed in Appendix B both the spherical distribution U(S M-1 and the uniform over scaled cube U( V (1, -1) MM satisfy:
1. Each z, is almost surely unit-norm (Definition
3
For the discrete cube, this holds because
[L (MM.....
#1 ( M
2. The process (2)) is conditionally r-sub-Gaussian with tion C
/M according Defini-
While our ultimate goal is to establish concentration results for adaptive processes in bandits, we first review the classical Maanson-Lindenstraann lemma which forms the foundation of our analysis. This will help contextualize the sequential variant we subsequently employ.
The essence of geometry preservation within the context of dimensionality reduction can be mathemat- ically formulated as the challenge of designing a probability distribution over matrices that effectively retains the norm of any vector within specified error margin after transformation. Specifically, for given vector I E R", the objective is to ensure that with probability at least 1 - 5, the norm of x after transformation by matrix II [z [2,,.... z,,] E mxx drawn from the distribution De,s remains an e-approximation of its original norm, as shown below:
PI~PE. (||[I E [(1 - <) |= (1 ++)1)(11 21
(22)
A foundational result in this domain, the following Johnson- Liwoon-Lindeer Lindenstrauss (JL) lemma, establishes theoretical upper bound on the reduced dimension m, achievable while adhering to the above- prescribed fidelity criterion.
Lemma C.5 (JL lemma [Johnson and Lindenstrauss 1984). For any < E, 1/2, there exists a distribution De.s Rmxx m O log(1 (1/)) that satisfies eq. equation 22
The standard Moinson-Lindenstratne lemma (Lemma C.5 provides dimension reduction guarantees for fixed vectors (or a fixed set of vectors). However, this classical result is insufficient for our bandit setting, where vectors are chosen adaptively based on past observations. As illustrated in Example [ the choice of arm X, depends on all past perturbation vectors Zo..... Zt-1, creating sequential dependency that violates the independence assumptions of the standard JL lemma. To address this challenge, we require sequential version of the JI. lemma that can handle these adaptive processes. The following theorem provides exactly such a tool:
Theorem C.6 (Sequential
Theorem, adapted from Li] 2024a]). Fix E (0. 1), and let (Fi)1zo be a filtration. Consider random vectors {z, J:20 C adaapted to {Fihizo. satisfying:
36

---

Initial vector Zo: Zo is Fo-measurable, E zo = L, and Izol
S e/2 almost surely.
Subsequent vectors (Zz) (=1) For t 2 1, the process {ze)e21 is conditionally /o//M
Gaussian (see Definition C.2 where Co
an absolute constant. Furthermore, each
|zell2 = almost surely (Definition
C.3
Let (11)121 C R be adapted (Ft-1)e21 and satisfy x? S Ox a.s., where Oz > is an absolute constant. For fixed xo E R \ {0), if
M 2
c6 (1+
(log())
+ log(1 1+ ))
2²
then with probability least 1 - 6,
14 0, T
2y Zi
(1+ 8)
Σ
2 Z/..
2
C.2 Applying Sequential JL to the Incremental Update
This subsection details how the Sequential Johnson-LLindenstrauss Theorem (Theorem C.6 is applied to analyze the incremental update rule of Ensemble++. The goal is to show that for any fixed direction E gd-1, the squared norm of the projected ensemble factor, ||a true projected precision, 2, a, uniformly over time.
AA,12, E,'A, remains close the
We aim to establish bounds on the approximation error for the posterior variance. For chosen direction 3d-1 and desired precision e E (0, 1), define the "good event" (a E) time I E T == {0, ,,...,T) T} as the event where the approximate posterior variance a A,A, is e-close (multiplicatively) to the true posterior variance a Σạo:
G((a,e) == {1a A.T.AAT a Ejal s <E(a" [ma)]=
(23)
The overall good event at time & for all directions is then
(c(c) = (((a
(24)
acS4-1
Lemma 4.2 in the main paper essentially claims that (1/2) holds with high probability for all t T
Reduction to Scalar Sequences for Theorem C.6 To utilize the Sequential Johnson- Johnson-Lindenstrune Lindenstrauss
Theorem, need to transform matrix update equation into form that involves sums of scalar
coefficients multiplying random vectors. For a fixed a gd-1 we s(a) a" Σ 1/2 1/22
Zo and
s(a)2 = ET aa. We define short notation Zg == s(a) T T/s(ssss (a( and 2o = sa). For 2 1, we define It = TX,
With these definitions, we can relate the incremental update to scalar sequences:
a T Σ A, = a Σ
1/2 Zo
(X.) 2T,
s(a)=2 20
a Σ a a T 0
(Xx) Ta
These equations transform the matrix update into sequences (2r) and (2r)22 that be analyzed using Theorem C.6
Filtration and Measurability To apply Theorem C.6 we need to define the filtration and verify the measurability conditions. Let H, be the o-algebra generated from history (X,, X1, Vi...., X,-1, Y, Denote 2, = =Zo)) and Z, = a (Zn, 21,..., 2+-1) for
t > 2. We observe the following statistical relationships:
37

---

2, IL (H, 2x), while X, depends on H4. 2
A--1 E OHH,, 2x)
Pt-1, -1-1 E H4
For / N, let us define the sigma-algebra J, = a(He+1, Eх41, X We can verify F& C
for all k S L. Thus F = (Fe)Len is filtration. With this construction, we can verify that (2+) is
adapted (Fi) and (21)221 is adapted to (Fi-1)e2 1221, satisfying the conditions in Theorem C.6
Time t =1
Time =
Time =
Time t X
Time +
X1
X2
X3
X
Zo
Z
Z2
Z3
Zt
Figure 7: Sequential Dependence Structure: The choice of action X, depends on past random perturbations, illustrating why standard results are insufficient for this setting.
C.2.1 Prior Approximation (Time
First, we need ensure that the initial condition for (a) in Theorem C.6 holds. Standard covering argument for the unit sphere and the distributional Johnson-Lindensttrnn lemma (Lemma C.5 2024b]) establish that when
M (1 256 (d log(2/5)),
(25)
the initial good event for prior approximation Go(e/2) holds with probability least 8. Under the event Gu(=/2), we have:
(1 - 1--e))aa Σna I |1a"
1///2 Zoll S (1 + e//2ja" Eqa, Va s
+ [ZoZ - /|| < 8/2
+ - (e-22)aa Σn a S Ila En
-1/22 S (1+e/2)aa Ey'a, Va E E8-1
(26)
Recall s(a)
a E, Zu and s(a) = Σn E-' la. Using the short notation Zu = s(a) /s(a).
equation Eq. 26 implies that ||zz||| 1| I (e/2), satisfying the initial condition required by
Theorem C.6
C.2.2 Posterior Approximation (Time
We now verify the remaining conditions needed to apply Theorem C.6 / 1.
Notice that = = a 2n 2 inf aa? 27 aa = s By the assumption of bounded features in Assumption 4.1 we have x² (a xx)² < for 1. That is, the sequence (a" X,)x21 is 1-square-bounded for any a E gd-1
We can also verify that (Zz)22 is 1/VM/ MWV.M--ubuaaaa nuu-Gauusiian and has unit-norm when the perturbation distribution P. either the Cube ((( -1] M) or the Sphere M11))
Under the prior approximation event Go(e/2), we can apply Theorem C.6 to show that for any fixed a E gd-1
W T, T, {la M. Σ.'A,A, D. Σ- S ea" ET
(27)
holds with probability at least 5 when
16(1 16(1+E) +E)
1
>
log
log
(28)
2²
$2 mii
38

---

C.3 From Per-Direction to Uniform Guarantee: Variance-Aware Discretization
In Appendix C.2 we established that for any fixed direction a s the approximate preci-
sion la E A : close the true precision a' Σ with high probability (event (r in Eq. 27 However, Lemma
4.2 requires stronger guarantee: that the approximation holds uniformly Sd-1 This section details the discretization argument used to bridge this gap.
for all directions
We first need some standard tools for covering the unit sphere:
Lemma C.7 (Covering Number of a Sphere |Vershynin 2012). There exists a set C, gd-1 with |c.I & (1 + 2/1)² such that for all x E Sd-1 there exists y C. with || - yll2 S
Lemma C.8 (Computing Spectral Norm on Covering Set [Vershynin] 2012). Let be a symmetric d x d matrix, and let C, be an 1-covering of Sul1 for some E (0, 2). Then,
||
sup -EB1-1
1 Aa
S
sup x Az|. =EC.
1
Insufficiency of Standard Discretization Utilizing standard discretization for computing the spectral norm as Lemma C.8
we could set 2 = 1/4 and show that
n aEC1/4
E, S Go(s).
This follows because:
T
E A,A, Σ,
Σ- )at)
E 1/2 A,A, E, 1/2
1/2
Tllop = sup
=E3é-1
x Σ
2
sup la (E A Ee' -E
Amin E
aEC1/4
sup SupaECi/4 a T 22, a
S 25
< 2 Rs E S 2T
Amin
Then by union bound over C1/4 and plugging in e/2f Eq. 28 Q(dT T) ensure Nuec, E(,,E holds with probability least 1-8. 8.
we would require M >
This result is not acceptable as the per-step computational complexity grows polynomially with the interaction steps T. We now introduce a variance-awar discretization approach to resolve this issue.
Variance-Aware Discretization The key contribution here that we choose a variance-weighted norm to measure discretization error. This variance-awarenesss, together with specific choice of ((1/VT)) O discretizatio error and constant approximation error allows us to achieve M = (d 7) bound.
Let S, = E.'AA A, and r, = E--11 A,. From Eq.
27 we know that the event
Vt E E,(a,')) a T
S.S.T a a
Σx al
<
Σ
holds with probability at least
8' when
M 16(1 + +')
T
llog
log
1
(c))2
2 min
Let C, gd-1 be the s-covering set from Lemma C.7 and assume the event Naec, Es(a, E²) holds.
Let gd-1 and y C, such that ||x yll
Define
1/2 Σ, and
E, 1/2
3. We want to
39

---

bound the difference between the error for and the error for
x S.S. x. E,
20
y TTS,S U.S. y y Σ, yl
r 2x
D; "y U cl
I T,T, u u. TTul
T,r, V
T 1 ||/|
[
u u
v
|u|12
|
|
T |
T
<
|0
u 2
||
|
(2)
(IT)
We now bound terms (T) and (77) separately. Without loss of generality, assume ||u]| ||e|| Recall ||a||
S 2 _ 2o-l a minn for all a E gd-1, Since
x Σ, x x (Ep" + E.=1 XxX, )a
have 2 S |||||| S max
For term (1):
T 2u
(T + [Tel]]
Tx(u w)ll
Trull
|Trol
(1)
<
+
||/|2
|ul
Smin
T u wll
2 T
oaua +
(2([T.|)= v
Smin
8min
Smin
For term (I7):
[ 2 |u
||011
||
|00|2 ||T1| (1|ull |]]l[ + ([lll)
(IT) <
|
|10|
|/112
1/
2 T,
||
wll
2
2
E 1/2 110
2 2
2 +
max
8min
Smin
8min
Combining terms (I) and (II), we get:
E A,A, -T-- Ex )
E 1/2 A. Σ, 1/2
sup Tlpop
-
T. E1-10
1 2 +t
(E,, A,AT E, 1 E, yl
sup VEC.
Smin
y Σ y
4| T e|| P
o +t +
(29)
Smin
Let us set
Q8min
4 S +
where a will be determined shortly.
An equivalent formulation of the norm is | Amax (I.IT). Therefore:
Σ 1/2 A,A, E, 1/2 Il max Amxx (I.T.) 1, Amiu (T.
From Eq. 29
we get:
1 gl
a(1 a(1+e') +
Amaxe (TT.T) < a'
Amin (T.I. - admax 2 6
1-a a
Claim 1. If L+g' I-a
= 1 + and e' +
afl+e')
1-a e, then
- 5 Amin (T.T.) < Amax (T,I,) < +
40

---

For our target precision E = 1/2, the parameter values (f',a) (1/4, satisfy Claim these values, the discretization error becomes:
| With
Smin
24v max +
The covering number |c,1 S (1 + 2/1)2 S (1 (48/8mis Smin) V Max T)). By union bound and defining d' = 6/(1 + (48/8min) ) V maax + -T), we have
n (,(122 LET
2 21- | (60(1/4)
PP
when
M 2 M2(6) = 16(5/4)
(48/smin)
Smin ) $ max +T
(
(1+
T
d
+ log
1+
(1/4)²
s min
This gives constant of 320 multiplying the logarithmic terms.
C.4 Putting Everything Together
We now consolidate the requirements on the ensemble size M to ensure that Lemma 4.2 holds. We want to show that with probability at least 1 8, for all / {0, 1, ,
Σ 1/2 A,A, E. 1/
Illop S E,
(30)
where we target = 1/2.
When
M 2 M3 = max MAX
we have
P (nGcc/2)) =P (p (. (60(14)) (o0()))))))( (CG(11/4) 2 (1- 8/2)2 2 1 1
LET
GET
With some calculations, we derive:
M1(14,5/22 1024(dlog (ogg4///)))))(
and
2 + (96/smin)
smin /v
22 max +T
T 82
M2(6/2) 320
d log
+ log
1+
6
min
Since the total time periods T is the dominant growing term, there exists constant To such that M3 (2 when 7 > To. This leads to the key insight that M scales as 2dd T), rather than polynomially with
Remark C.9 (Constants and Parameters). The constants involved in the bounds depend on known properties of the algorithm's components (like the perturbation distribution). The parameters Smin: Smax related to the initial covariance properties, while T is the horizon and d is the feature dimension. The analysis crucially demonstrates that the ensemble size does not need to depend polynomially on T. which is essential for the practical efficiency of Ensemble+++
This completes the proof of Lemma 4.2
showing that with suitable ensemble size M = Oo T), Ensemble++ can maintain accurate posterior uncertainty estimates throughout the learning process, despite the sequential dependencies introduced by the adaptive data collection.
41

---

D Technical Details in Regret Analysis for Theorem 4.3
D.1 General Regret Bound
We start by providing general analytical framework for agents, potentially randomized, operating in generic bandit environments. Let us introduce a few necessary definitions to facilitate the understand- ing and analysis. The confidence bound is used for uncertainty estimation over the true function f" given the history H4-
Definition D.1 (Confidence bounds). Confidence bounds are sequence of real-valued Ht- measurable functions L₂(+) and Uz(-) for t E [T] such that, with probability at least 6, the joint event & = & holds, where & = (a) [L)(a), Uz(a)], Va X.).
The agent may not perform well unless is well-behaved, defined by reasonableness and optimism. Intuitively, an agent that explores too much or too little will incur high regret. Reasonableness and optimism are the mechanisms for controlling these potential flaws respectively.
Definition D.2 (Reasonableness)) Given confidence bounds (+(.) and U.(-) for E [7], (ran- domized) agent is called reasonable if it produces sequence of functions (fr(), [7]) such that with probability at least 5, the joint event & = O holds, where & {f((a) (L)(a), Uz(a)], Va E ).).
In short, reasonableness ensures that the chosen action according to f. is close to the best action, which ensures the agent does not explore actions unnecessarily. The following optimism guarantees that the agent explores sufficiently.
Definition D.3 (p-optimism). Let p be sequence of positive real numbers (pr, t [[]). We say (randomized) agent is p-optimistic when produces a sequence of functions (ff()), E (T)) such that for all t E [1]. fe(-) is pr-optimistic, i.c., P(maxxxx, fa(a) 2 max.ex, (a) He) 2 Pc-
The generic agent satisfying the conditions on reasonableness and optimism has desired behavior. Building upon these definitions, we establish general regret bound applicable any agent satisfying these conditions.
Theorem D.4 (General Regret Bound). Given confidence bounds defined in Definition D.I and assuming the agent is reasonable and p-optimistic, the cumulative regret over T time steps satisfies
T R(T)
T
[X,))x,) - L, Hdl +
(U,(X,) - Lx())).
(31)
Pt
t=1
with probability al least -
Interpretation
The regret bound in equation 31 decomposes into two main components:
1.
Trade-off: The first term scales with 1 and the expected width of the confidence bounds. A higher ps (i.c., greater optimism) reduces this component, promoting exploration.
2. Confidence Bound Widths: The second term aggregates the widths of the confidence intervals across all time steps, reflecting the uncertainty inherent in the agent's 's estimates.
For the regret to be sublinear in T, it is essential that the confidence bounds Uz(a) - T=(a) shrink appropriately as increases, ensuring that both terms grow slower than linearly with T'.
Proof. Let X, = arg max,gx, [a(a) be the action chosen by the agent and A arg max (a) be the optimal action at time 1. Let B, = max T,, (a), which is memmaauuable..
Conditioned on the event & E, both f*(A)) 2 B, and (x,,) 2 B, hold.
By p-optimism and the fact that (f² B,) is 7 and non-negative:
Pt < ((f. - B, 2 (At) - B, H4)
x Bl,((x,) - B, (441((f((A)) B.).
42

---

where (+) is due to Markov's inequality.
Rearranging and using the fact B. (x,( yields:
(AA) (x,) - (At) - Be
(62)
1 Blf((X)) Bi H4l
(33)
Pt
1 E[U,(X,) - Lx Hz).
(34)
By reasonableness, f((,,) & Ux(X)). Then, from the definition of confidence bounds:
- ("(,) s U,(X,) - Lx(,))
(35)
Putting equation 32 and equation 35 together, and then summing over the time index t yields the
general regret upper bound.
D.2 Proof of Theorem 4.3 for linear contextual bandits
To make the proof easy access, we restate the core results and few notations that are needed for the proof of the propositions.
Table 4:
The coefficients p(Pp) and p(Pc) related to reasonableness and optimism conditions. Restated from Table I with evidence from Appendix E
Ps Gaussian (000, lx)) Sphere v /MU(SM-1)
Cuhe ((11,-1) Coord
Sparse
p(P)) Pi A Pa
P2 A ps
p(P()
//113
7/32
N/A
4yes
237
Adapting the results from (Abbasi-Yadkori al. 201 Abeille and Lazaric 2017). let B,
VĀ + log((1/)) log det det(E, Under Assumption 4.1
we define the confidence bounds
as:
T.(() = - U.(-) A ((44-1 + (.l])o())llx
For the purpose of analysis with various reference distributions, we define slightly inflated confidence bounds:
- Pc(:P)) -Bo
U,(:P() ((
Here, p(Pp) is defined via:
P1 O(v M log())))),
P2 = O(VM),
P3 0 0(V/lg((1*1/0)
and Table
An immediate observation is that (.), c [L (L(::P)) Thus, L,(: Pş) and U.(: are also valid confidence bounds.
We consider the following functional form for Ensemble++ under linear setup: for time
i.(a): (a, (ő(a), A, 14-1); Va X,
(36)
where the parameters include 0, (At,
43

---

The condition on the propositions and theorem for regret analysis is when equation 9 is satisfied, that is when M (gg T,, the Lemma 4.2 implies that with high probability, the good events g = Ne Ge hold jointly, where
3 E, Ve Rd 9t E A,A, x S
In the following section, we discuss the proof conditioned on the joint event G and also the confidence event that I (a) E (a), Uz(a)] for all E [T] and E X.
D.2.1 Proof of Proposition D.5
Proposition D.5. Under linear setups in equation 30 and equation Ensemble++ is reasonable, i.e., VI E [T), fe(+) = Sa, (x) ( Pc), Uz(; Pc) with probability at least 5.
+ if eqquation 9 is satisfied, linear
Proof. From equation 36 we derive:
(f)(a) (M-11, Ø(a))) (oo(o),
Bl/o - A
o(a) A.
(T((a) A, A.-
<
:(a) A
(3/2)8, v p(a) E 1
(o(a) A
where the last inequality is due to the good event G. For compact action sets, by the Cauchy- Schharr inequality:
6(a) T(a)TA A [o(a) A.- (e)
Using the concentration properties of Ps from Section B can bound ||G/]]:
For Gaussian distribution: ||c/ll s O(VM log(M/6)) with probability at least 1
For Sphere, Cube, Coordinate, and Sparse distributions: |[<r]] || = VM by construction
For finite action sets X, leverage the concentration properties to bound:
IP (K A A (6)
/ log 2| Hes 2e
2
since &. is independent of the history Hr and Z, Combining these bounds, we have:
(f((a) (1-11 o(a)) S B.o(Pt))
where p(P²) is defined in Table and incorporates both the factor from the good event and the appropriate concentration bound for each distribution.
Therefore, with probability at least 1 - 5:
(u)-1,0(a)) - B.p(P:))l & Fela) & (m--1, + +B:p(P))l
After applying the truncation to [-,,1], we conclude that fa(a) E (L, Pc), U.(a; Pc) with probability least 1 - ö, which establishes the reasonableness of linear Ensemblett. D
44

---

D.2.2 Proof of Proposition D.6
Proposition D.6. Under linear setups in equation 30 and equation + if equation is satisfied, linear Ensemble++ using reference distribution Pg is p( optimistic.
Proof. Let X, = arg maX fe(a) and A = arg maX f (a). Conditioned on and the confidence event:
fx(),) (A,) 2 f((A)) (*())
f((A)) Up(AT)
3.AA)),,Ai-ISe + He-1) - ((0,),,,(AA)) + +
- Bello(A7)1l
((47)T A (6) - -elll(A4)1lE.-
3. B. ((A7) A ( AL- (((A))
[I((A)TTA
3.10(A7))
( (V2 [0{(A))
((Az) A.-1
A .58) -1)
where we used the good event G to relate A A to Er-1- Therefore, the agent is optimistic if:
T(AR)T Ar-1 [10(A7) A.-1ll .6 2/2
V
We consider the conditional probability:
((
o(A7) Ac-1
P(f(X,)) 2 ("A) H., 2,) 2
(o(At) Ar-il Go
(222222 He, Zz
(37)
Since o(47)* A.-1 is fixed unit vector in RM (given H, and Z,), need the probability [6(1)) A.-il
P((v, Gt) 2 /2).
By the unti-concentration properties derived in Section E and scaling arguments, we know that
P((e, G) 2 1) 2 p((c) for the distributions Table Since P((v, G.) v2) S P((v, G) 2 1),
we have:
((f((X)) 2 (A)) H.
This establishes that linear Ensemble++ with reference distribution Pę is p(P::)
D.3 Proof of Theorem 4.3
Proof. The theorem follows directly from Propositions D.5 D.6 and Theorem D.4
First, by Proposition D.5 linear Ensemble++ is reasonable with respect to the inflated confidence
bounds [-: Pę).
Pc::)))
Second, by Proposition D.6 linear Ensemble++ is pPP::(-optinise
Applying Theorem
D.4 with these properties:
R(T)
ElU, L,, Pc) H.) Σ - L,(X,;
p
T
p B(23,p (P))
H..] Σ 28.p(
(38)
Additionally, by Azuma's inequality for the sum of bounded martingale differences (since U.(-) Lx(-) < is bounded):
Σ E(UU,(X,;P) P() T,((X;; H4] - (U,(X,; Pc) T,2 Pc)) & 0( 1og(1/5)).
E
45

---

with probability at least - 8.
Thus, it suffices to bound:
T
Σ
23 28, S 2p(pc) t=1
16 > 1 T
[=1
Es T 2:33 log det Eg
22p {
(39)
where the first inequality is by Cauchy- Schhaar and the second applies the elliptical potential lemma (Lemma 19.4 in [Lattimore and Szepesvári 2020 and [Abbasi- Yanaori et al. 201
Since
T
BT S Vx+ V 2log(1/6) dlog [1 di
and
det 24 det En
T
r)
log
dlog 1
di
we have:
T
T
Σ
0o 50
((P2) T.
(og((16)) + d dA
dlog Yd
=0 (p(PE) dPTlog?(T)
= (p(p.)dvv
(40)
General case
Combining all terms, the regret bound becomes:
((P)) dv dodddloooooo log(T) + p(P))dVTlog(() + p(Pc) v Tlog(1/8)
R(T) 00
((Pc)
=0 ((((1) (((Ps)
+ p(pp)) dv dvTlog(T) p(Pp)
(41)
Compact action sets Based Table 4 for all distributions except Coordinate, p(Pc) O( 7) (since M = O(d 7)) and P(P O(1). For the Coordinate distribution,
p(P)) = ((M) = (ld T)
Therefore, for Gaussian, Sphere, and Cube distributions:
R(T) 0(88/2 3/2 T)
And for the Coordinate distribution:
R(T) 0(25/2/TT 5/2
Finite action sets For finite action sets | achieve improved regret bound. Recall from Table 4 that for Gaussian, Sphere, and Cube distributions, p(Pc) = Pi A P3 or P2 A Pa. where
P3 0( log([ (()5)))
When | is not too large, specifically when log | dl lol T. we have A3 < P1 and P3 P2- In
this case:
((Pc) = 00
(42)
Substituting this into our regret bound:
Vlog(IX1/8) p(Pc)
vl0g(1x1100) d d (ogg)
R(T) =
(43)
Vlog [X p(Pc)
=
d d (oTTlog(T))
(44)
46

---

For Gaussian, Sphere, and Cube distributions, where p(P() = O(1), this gives:
R(T) Widd/Tloo X (Tg(
This represents significant improvement over the bound for compact action sets when | is small, as the dependence on dimension changes from O(18/2) to ((d).
This completes the proof.
E Sampling, Isotropy, Concentration and Anti-concentrrttion
This appendix analyzes various probability distributions used in the Ensemble++ algorithm, focusing their isotropy, concentration, and anti-connentratton properties. We begin by clarifying the relationship between two key distributions in our framework.
In Ensemble++,, utilize two related yet distinct distributions:
Reference Distribution (Pc): This is the base distribution from which we sample M- dimensional vectors Ç E R We analyze several options for this distribution, including Gaussian, Sphere, Cube, Coordinate, and Sparse.
2. Perturbation Distribution (Pz): This distribution derived from Pc (which exhibits Jub-Gaussianity) through normalization process. For vector independently sampled from Pg. the corresponding perturbation vector is obtained as z = C/1[C]|2-
This normalization ensures that all perturbation vectors z have unit norm (i.e., |z]|a 1). This property is a crucial requirement for our theoretical analysis, specifically for Lemma 4.2 The characteristics of the reference distribution Pc directly influence the ensemble size M required to achieve our theoretical guarantees.
The choice of reference distribution affects both statistical efficiency and computational properties of our algorithm. Different reference distributions lead different constants our theoretical bounds while offering various practical advantages.
Definition E.1 (Isotropic). A distribution P over IR M is called isotropic [Xx,XX dij. i.e. Ex~P[XA = Equivalently, is isotropic if Ex=P((X; x} = || for all RR
The isotropy property (Definition E. is used for the update distribution and proving equation in concentration property is used for perturbation distributions
The sub-Gaussianit, (Definition and proving Lemma 4.2 The concentration and anti-concentration propertics are used for reference distributions and in the discussion on the reasonableness condition (Proposition D.5) and optimism condition (Proposition D.6).
We now analyze each distribution case by case.
E.1 Sphere Distribution P. = MM(MM
Algorithm 3 Sampling from U1 (MM1))
Require: Number of ensemble members M
1: Sample vector 2; (O, for i I,...,A M
2: Construct vector: { / Mo/llull
3: Return E
Isotropy. By the rotational invariance of the sphere distribution, for any fixed orthogonal matrix Q:
(5.x) (QÇ,x)) = Q z) Vx E Rd.
Then, for any fixed æ, we can select M orthogonal matrices QI...., Qm to rotate x such that Q x ||ælee where e; is the i-th coordinate vector. With this construction, for any fixed
M
M
ME x)
(C. x.
||
2
M|
47

---

and hence B[[s; x> = | which is the definition of isotropy.
Concentration. By definition, |||||
V. For a random variable Ç U(S and any fixed E g the inner product follows the transformed Beta distribution:
M
M -
(C, u) Beta
2
2
As shown in Skorski 2023]_ Li 2024a], Pg u( U(VMSM-1) is 1-sub--saaate Gaussian. For finite action
set A, using the concentration of Beta random variables with union bound:
(Ya
2
P
Va A [1
log 5
2 1 5.
Anti-concentration. Let's rewrite the problem in terms of the incomplete Beta function:
Given:
M - M-1
X ~ Beta
2
We want:
P (((S, 2 1) =P 2X -1>
X
VM
2v M
Theorem E.2. For all d 2 2, the random variable X ~ Beta concentration behavior:
d=1 (
1-1)
has the following anti-
1
1
1/12
P x
2vd
2T
Remark E.3. We did not find existing literature that provides such anti-concentration results for Beta distributions.
Proof. Using the incomplete Beta function (a, b), this probability can be expressed as:
p(x
1 2
( d (d-1d-1 d
P
x
2/d
2 2
For the regularized incomplete Beta function (a(
(a b) B(r; a)
B(a,b)
where a(I;a, is the incomplete Beta function and B(a, b) B(1; b) is the complete Beta function. d-1 2 2
For b=
the complete Beta function is:
d - d -
D
B
2
[(d 1)
For the incomplete Beta function with x +
and a =b= d-1
2vd
d-
d
2v4
2 +
2 (1 -
dl
2/d 2
Ju
Since f(t)
t
(1 1)
symmetric at
1/2 in the interval [0, 1]:
B
1 d
1
d
--1
1
)
1
d - d d-13
v
t t (1 dt.
2/d' 2
2
2
48

---

As f(t) achieves its maximum at t = 1/2. we can upper bound the incomplete Beta function:
d=3 (1- de
d-3
(45)
2vd
2vd
For the complete Beta function, we use Stirling's 's approximation for the Gamma function, which provides a strict lower bound [Nemes]
2015):
[(=) 2 22T== -
and upper bound [Gronwall 1918:
T(z) S 2 1 -
for all 2 0.
This gives us the lower bound:
d d
22 - (2)(()))
(1)
d-2
B
= 2
(d - 1/2 1_d_1,
2 2 (d - 1d- 2e d+I+ d+1+12(011)
2
1/12 whenever d 12 2: Since 12id-1 2
1 d d-1 2
11
d-2
1
B
> 2Te 1/12
(46)
2
vd
Combining equation 45 and equation 46
222
d-1 1
1
2vd
I
+
(2ttval 2vd
2
2
2
V2T
Va
1
e/112
+
2
22
Therefore:
1
1
1/12
X
+
2
0.0668.
2vd
2m
E.2
Cube Distribution 12=,((1,-1)-)
Algorithm 4 Sampling from 2/([-1,1)
Require: Number of ensemble members M 1: Sample vector E: & ~ 1{{-1,13) for = I,...,M M
2: Return &
Isotropy.
Easy to verify by definition.
Concentration. By definition, ||E|| = VM. We sample the random vector by independently
sampling each entry from 4 u((1, 11)) for i [M]. Then, for any E S. -1 by independence:
Efexp(X(u,CH))
II E(exp(Ae:Ci)] i=1
II exp((2 exp(1 2 Σ :=1
The inequality due to the moment generating function the Rademacher distribution [Wainwright] 2019]. This confirms that Ps = ((11, -1) is Sub-Gaussian. For finite action set A, from the sub-Gaussian property:
2 log 8
P Va A. < [(((a)]
2 21 8.
Anti-concentration. Using the anti-concentration result from Hollom and Portier 2023 for any fixed unit vector v in M
P((G,t v) 2 2 7/32 R 0.21875.
49

---

E.3
Gaussian Distribution P. = NNO
Algorithm 5 Sampling from (M,
Require: Number of ensemble members M Sample vector &: & (0 1) for ,,.... M
2: Return f
Isotropy.
Easy to verify by definition.
Concentration. The concentration property comes from the Chernoff bound for standard Gaussian random variables with the union bound. For any a > 0:
P(IICI Mv 2 P(V1 S M, 2 21 MP((5) 2 a).
Standard concentration inequality for Gaussian random variables gives, Va >
P(GG a) S 2e 02/2
With 2
2M II S 2M log 8
with probability at least 6.
For finite action set A:
2
P (V, s [ log
2 5.
5
Anti-concentration. For any fixed unit vector in 1R (C, 0) ~ N 1):
1
P( u) 2 1) = erfe
0.0856
V2
4 Cπ
E.4 Coordinate Distribution = =U=U tel,...,, LeM))
Algorithm Sampling from U(V M (ten..... =eM})
Require: Number of ensemble members M
1: Sample index: i 7~ ((((....,,M)
2: Sample sign: ~
3: Construct vector: { = 8V Me, where e is the i-th standard basis vector
4: Return &
Isotropy: By definition:
1 M
Eiçc
2Mece I.
2M
Concentration. By definition, ||<|| = VM.
Anti-concentration.
P(C, v) 1)
Σ
Dj
1
+ o2
1 VM
})
2M
M
jE[M]
1
Σ
>
2M
M
2M
SE(M]
where the last inequality uses the fact that for any u E RM with ||ll|| one entry j E [M] with |u,l 2 VM
1, there always exists least
50

---

E,5 Sparse Distribution Pg
Algorithm 7 Sampling from 8-sparse random vector
Require: Number of ensemble members M, sparsity s
1: Sample sign vector: wi (((-1,1)) for i == 1......, M
2: Construct a set S by randomly picking & elements from (1,...,Au without replacement
3: Let 7/s for i E S and fu 0 for /' [1.....M] S
4: Construct vector Ç: & W: 7)
5: Return E
Definition E.4 (s-sparse distribution). The sparse vector is in the form < - / E @ w where
Pw := U( (()))))) and is independently and uniformly sampled from all possible s-hot vectors, where s-hot vector has exactly non-zero entries with value This construction introduced by Kane and Nelson 2014).
Isotropy. By definition:
EKG - Bm
For * k. E[wsaak] = 0 since the signs are independent. For j = k. B[w = 1.
For 7/, we have E[n/]] 17 since each coordinate has probability x of being selected in the s-hot vector. For j * k, B[m M(M-1y since this is the probability that both coordinates are selected. Therefore:
M
E(
E mh B[wywa]]
M
E B[n mi 15k
M M
if = k if j
0
55k
Thus, the sparse distribution in Definition
E.4 is indeed isotropic.
Concentration. By construction, |||||
VM.
Anti-concentration. The anti-concentration behavior of sparse distributions depends the sparsity parameter s and requires further investigation for precise bounds.
E.6 Summary of Distribution Properties
Table summarizes the key properties of each reference distribution Pe discussed in this appendix:
Table 5: Summary of Reference Distribution Properties
Distribution
Isotropy
Sub-Gaussian
Anti-concentrattio
Computational Benefits
Sphere
Yes
Co
> 0.0668
Standard implementation
Cube
Yes
Co
2 0.21875
Simple sampling
Gaussian
Yes
Co
2 0.0856
Standard implementation
Coordinate
Yes
Not characterized
2 1/(2M)
Sparse matrix operations 0(s) non-zero entries
s-sparse
Yes
Not characterized
Not characterized
These properties directly influence the behavior of the derived perturbation distribution P: and ultimately affect the exploration-exploitttio trade-off in the Ensemble++ algorithm. The choice of distribution can tailored to the specific requirements of the application, balancing theoretical guarantees with computational efficiency.
51

---

F In-depth Empirical and Ablation Studies
In this section, we dive into the intricacies of each evaluation testbed. Through a comprehensive set of empirical results, we'll ll'll further illuminate the benefits afforded by Ensemble++. All experiments are conducted on P40 GPUs to maintain processing standardization.
F.1 Additional Experiments on Linear Bandit
We begin by examining Linear Ensemble++ Sampling in linear bandits. In this section, we focus on studying the impact of perturbation and reference distributions, and we provide detailed results under varying numbers of ensembles M.
Environment Settings. We use the action feature set X' to denote the set of features o(a) : a E A induced by action set A and feature mapping 6(-). We build two linear bandit environments with different action distribution as follow:
We construct the finite set X' by uniformly sampling set of action features from the range [-1/ V5, 1 /5]d where d is the ambient dimension of the linear reward function. This environment builds upon prior research Russo and Van Roy (2018). We vary the action size | over set of {100, 1000, 10000]. and the ambient dimension across { (10, 50}.
Finite-action Linear Bandit:
Compact-action Linear Bandit: Let the action feature set X' = Sd be the unit sphere. In this environment, we vary the ambient dimension d over a of {10, 50, 100).
In both bandits, the reward for feature X, E Rd computed as rı = X 0 e, where 0 NOO,, 101) is drawn from the multivariate Gaussian prior distribution, and e ~ NO is an independent additive Gaussian noise term. At each step only the reward from the chosen feature X, is discernible. To ensure robust results, each experiment is executed 1000 time steps and repeated 200 times.
Impact of Reference and Perturbation Distributions. We investigated all 25 combinations of perturbation and reference distribution under different scales of the linear bandit environments and numerous #ensembles M. As depicted Figs. 10 the outcomes across diverse problem scales corroborate each other. The use of Gaussian reference distribution significantly enhances performance when the is relatively small, such as when M is or 4. As the #ensembles M grows, all combinations show analogous performance under varying problem scales. However, it worth noting that for extremely large M, such as 512 or 1024, combinations involving the Coordinate perturbation and Coordinate reference distribution significantly underperform compared to other combinations. Given that Coordinate distributions are used the Ensemble+, the results prompt compelling argument. Linear Ensemble++ Sampling equipped with continuous reference distribution presents superior performance, suggesting its potential for surpassing traditional Linear Ensemble Sampling. These findings strongly support the superior advantage of our sampling method, validating our theoretical analysis.
Analysis of Computational Efficiency. We delve deeper into the effects of varying #en- sembles M within Linear Ensemble++ Sampling. We assess its performance across differ- ent combinations of perturbation and reference distributions using an assortment of M E 8, 16, 32, 64, 128, 256, 512, 1024). The outcomes, visualized in Figs. 11 and 12, are consis- tent with the findings illustrated Figs. [ to TO We observe that for large M, the Coordinate perturbation and Coordinate reference distributions degrade performance, indicating that the sam- pling method employed by Ensemble+ lacks efficiency. However, when Linear Ensemble++ Sampling utilizes Gaussian Sphere reference distributions, it achieves satisfactory performance, comparable to Thompson Sampling with small M.
Remark F. (Limitation of Theorem 4.3).. Notice that Theorem 4.3 suggest that when M > log the regret bound of Linear Ensemble sampling would increase with factor M332 which contradicts with our empirical evidence in Figs. 8 to 12
Remark F.2 (Good prediction of Theorem 4.3)).
Our empirical evidence Figs. 8 12
confirms the Theorem 4.3 in finite decision set setting for cattinuous-suppond reference distributions: when M larger then threshold Od T",, the regret is independence on M.
52

---

H-1
M--PX
2--52
9-1H
(a) d = 10 |
100
(b) d= 10 |2|
1000
064
(c) d 10 | 10000
Figure 8: Results on the combinations of perturbation and reference distribution in Finite-action Linear Bandit under action dimension d = 10. A deeper color signifies lower accumulated regret and hence superior performance. Gaussian reference distribution significantly enhances performance.
53

---

H-
M--PX
V-
2--52
(a) d = 50
|
100
(b) d= 50
|
1000
064
(c) d 50
| 10000
Figure 9: Results on the combinations of perturbation and reference distribution in Finite-action Linear Bandit under action dimension d = 50. A deeper color signifies lower accumulated regret and hence superior performance. Gaussian reference distribution significantly enhances performance.
54

---

(a) d 10
1
12
11 13
11
1 LEC
3.0 All
(b) d = 50
Mi
21
(c) d 100
Figure 10: Results the combinations of perturbation and reference distribution in Compact-action Linear Bandit. deeper color signifies lower accumulated regret and hence superior performance. Gaussian reference distribution significantly enhances performance.
55

---

a = 10 | 100
(b) d = 10
X 1000
(c) d= 10
| 10000
(d) = 50
X2 100
c d= 50
|2 1000
(1) 50
X 10000
Figure 11: Results regret under various #ensembles M in Finite-action Linear Bandit. The label B indicates that Ensemble++ uses A as the reference distribution and as the perturbation distribution. Ensemble++ with Gaussian Sphere reference distribution could achieve comparable performance with that of Thompson sampling under same M for different action spaces |
56

---

Ceecle Cal
Ascumuusas
(a) d = 10
Accumulatec Accurmulates Regret
Cale
(b) d = 50
(c) d= 100
Figure 12: Results regret under various #ensembles M in Compact-action Linear Bandit. The label A - B indicates that Ensemble++ uses A as the reference distribution and B as the perturbation distribution. Ensemble++ with Gaussian Sphere reference distribution could achieve comparable performance with that of Thompson sampling under small M.
F.2
Additional Experiments on Nonlinear Bandit
We conduct more comprehensive comparison of Ensemble++ with several baselines that utilize approximate posterior sampling across wide range of nonlinear bandits.
Environments Settings. We formulate several nonlinear contextual bandit environments, with rewards generated by nonlinear functions in each.
Quadratic Bandit: Its reward generation mechanism is built on quadratic function. expressed as fi(z) = 10 2(x "0 z). Here, IRd stands for the action, while θ e RRdxd is matrix filled with random variables originating from (0, 1). This task is used as the testbed in Zhou et al. 2220
Vector Quadratic Bandit:
Its reward generation mechanism built on different quadratic function, expressed as f2(2)) = 10(x 0)2. Here, E IR stands for the action, while 0 e Rd is a vector filled with random variables generated from a uniform distribution over the unit ball. This task is utilized as the testbed in Zhou et al. 22200] Xu et al. 2022).
Neural Bandit: This bandit employs nonlinear neural network built 2-layer MIPs with 50 units and ReLU activations, producing two output logits. We apply the softmax function with a temperature parameter p 0.1 the two output logits to obtain probabilities. Subsequently, we use binomial sampling based on the second probability to generate the reward. The temperature parameter p is used control the signal-to-noise ratio. This task used as the testbed in Osband et al. 2022 2023a
UCI Dataset:
Following prior works [Riquelme et al. 2018 Kveton al. 2020b
conduct contextual bandits with N-class classification using the UCI datasets [Asuncion et al. 2007) Mushroom and Shuttle. Specifically, given data feature E R in the dataset, construct context vectors for N arms, such (1) (x, 0.... .),, ......(.) (N)
57

---

(0, 0, ... .I) E IR
Only the arm 200 where j matches the correct class of this data has a reward of while all other arms have reward of O.
Online Hate Speech Detection: The motivation, problem formulation and environment setups of the automated content moderation task are detailed in Appendix G
In all tasks except the Neural Bandit, the original reward is disrupted by additive Gaussian noise e drawn from (0,, 0.1). .)....... In the Neural Bandit, we use the temperature parameter p to introduce noise into the reward. For the first three tasks, we set the action dimension to 100 and generate a total of 1000 candidated actions, randomly sampling 50 actions in each round. Each experiment is repeated with 10 distinct random seeds to ensure robust results.
Comparison Results with Baselines. We set the Sphere reference distribution, Coordinate update distribution, and Sphere perturbation distribution for Ensemble++ to compare with baselines. When comparing with Ensemble+ [Osband et al.) 20188) and EpiNet (Osband et al. [023a]] we the same hyperparameters, such as prior scale, learning rate, and batch size. Additionally, we employ the same network backbone for feature extraction ensure fairness. As shown in Fig. [3]a] and (b), Ensemble++ achieves sublinear regret and consistently outperforms these baselines across all tasks, demonstrating superior data efficiency.
For comparison with LMCTS [uu et al. 2022]. we use its official implementatior to ensure credible results. As illustrated in Fig. O Ensemble++ consistently outperforms LMCTS. Notably, LMCTS uses the entire buffer data to update the network per step, which incurs significant computational costs. In contrast, Ensemble+ achieves better performance with bounded computational steps, requiring only a minibatch to update the network. As LMCTS was already demonstrated in its original work to outperform classical baselines (c.g.. LinearUCB [Chu et al., 2011], NeuralUCB Zhou et al. 2020)), we omit redundant validation of this result to avoid duplicating prior findings. These findings highlight the effective exploration and computational efficiency of Ensemble+++
Additional Comparison on Trade-off between Regret and Computation. We have demonstrated that Ensemble++ can achieve sublinear regret with moderate computational cost in the Quadratic Bandit, as shown in Fig. Here, we further investigate the frontier relationship between regret and computation in the Neural Bandit, As shown in Fig. 14, we observe similar findings: Ensemble++ achieves minimal cumulative regret with the lowest computational cost. These results substantiate the scalability and efficiency of Ensemble++ when combined with neural networks.
Ablation Studies on Storage Requirement. As discussed in Section 3.3 Ensemble+ does not require storing the entire history. We tested different buffer capacity over 100,000 time steps (Fig. [5). Using smaller buffer leads only slight performance decrease, and Ensemble++ maintains comparable performance even with buffer capacity significantly smaller than the total time horizon.
Ablation Study on Update, Reference and Perturbation Distribution. To further evaluate the impact of different design of distributions, we perform an ablation study on the Quadratic Bandit. When fixing the Sphere reference distribution, we find that discrete update distributions such as Coordinate, Cube, and Sparse achieve similar better performance, shown in Fig. a). Conversely, when fixing the Coordinate update distribution, continuous reference distributions like Sphere and Gaussian also yield comparable better performance, as depicted in Fig. [6].). Regarding the perturbation distribution, our findings indicate that does not significantly influence performance
when the neural network is involved in Ensemble++. This is evidenced in Fig. 16 c), where all different perturbation distributions achieve similar performance.
G Ensemble++ in Real- Decision-Making: A Case Study on Content Moderation
This section demonstrates how Ensemble++ can be integrated with large foundation models (e.g. GPTs) to address real-time decision-making under uncertainty. We focus the high-stakes domain of content moderation on social media platforms, where rare or borderline hateful content arises frequently. By fusing GPT-style feature extraction with Ensemble++, uncertainty-drive sampling selectively allocates human review to ambiguous posts. This yields a scalable, adaptive pipeline that reduces moderator workload while improving overall safety and accuracy.
https///ggitub..cc///vaabt////
58

---

Konal
-117
0.3
Conviaton Boyns
0.3
Petiod
Tire
(a) Comparison results with Ensemble+ Oshand al.
2018
Veuubute Howr
Seand theds
Oroaleen hoge
Tex: Persd
237
Tixel Peraed
X107
Trx Periet
XB2
Tiz Firaed
(b) Comparison results with EpiNet Osband 2023a
Qtorlaatee Doggre
2.2
12
(c) Comparison results with LMCTS Xu et al. 2022
Figure 13: Results on different bandits with various baselines. performance compared other methods.
Ensemble++ could achieve better
x 10
x10
Quadratic Bandis
EdiNet
Rosmidl-
Counlated Hogres
Cancalacive Regret
1.2x104
166x10
2.0
2.
5000
10000
50000
100000
Parumetens
Butker Size
Figure 14: The regret-computation trade-off in Neural Bandit. Ensemble++ beats the SOTA baselines, e.g. Ensemble+ and EpiNet.
Figure 15: Performance of Ensemble++ under varying replay buffer capacity C.
Quabile
Qpabate
Sperse
Sphie
Sparre
Spans
Sybce
Sporso
(a) Results on update distribution.
(b) Results on reference distribu-
(c) Results on perturhation distri-
tion.
bution.
Figure 16: Ablation studies about different distributions on the Quadratic Bandit.
59

---

G.1 Motivation: Content Moderation in Real-Time
Modern social-media platforms handle volume of user-generated content every second, creating critical need for automated moderation [Gorwa et al. 2020 Roberts 2019) Historically, human reviewers manually inspected each post to detect policy violations. However, as platforms like Facebook Meta 2024], Twitter [Corp. [2024], and Reddit [Reddit [024] expanded to hundreds of millions of users. fully manual moderation became infeasible. Consequently. Al-driven moderation systems emerged, often leveraging foundation models Weng et al. 2023 (large pretrained language or vision models) for real-time filtering.
Despite robust performance on the distributions seen during training, these large models often face high uncertainty in novel formed harassment styles [Markov et al. 2023 A purely deterministic policy (e.g., the model's single best guess) can етr severely by
content: emergent slang, subtle borderline hate speech, newly
over-blocking benign content (harmful to user experience), or
under-blocking hateful material (a safety hazard).
Hence, human feedback remains indispensable for correcting the system, especially on ambiguous boundary cases. The key dilemma when to rely on human reviewers (which yields better learning but increases workload) versus auto-removing content (which saves labor but risks higher error).
Human-AI Collaboration. Figure depicts human-in-the-lon moderation pipeline:
1. A new post Ie arrives.
The Al system either auto-removes or requests a human review.
3. If reviewed, moderator provides corrective label y/+ (e.g.. "hate" or "benign"), and the AI system updates its internal policy.
Over time, decisions become more accurate, reducing human intervention.
Balancing exploitation (avoiding unnecessary reviews) and exploration (gathering feedback on uncertain content) is central improving moderation quality while minimizing reviewer workload. This tension aligns well with a contextual bandit formulation.
Moderation System
Auto
Remove
Context(r)
Human Review
Label(I)
Data
Figure 17: Real-time decision-making pipeline for content moderation. At each time 4, the AI moderation system receives a post It, decides auto-remove or request human review, then obtains feedback (if reviewed) update its policy. This setup inherently involves uncertainty about borderline or novel content.
G.2 Contextual Bandit Formulation
We model moderation as contextual bandit (Wang et al. 2005 Langford and Zhang 2007
Context xı: the textual (or multimedia) representation of the post time (.
Action set A. fauto-remove, human-review].
Reward r; E IR: quantifying correctness vs. cost. For example:
+1 for correctly publishing benign content,
-00. for inadvertently publishing hateful content,
+00.5 for blocking any post (safer fallback, but potentially suboptimal if content was
benign).
60

---

At each step, the agent chooses an action based on the context (21,....,((.............. = and partial knowledge gained so far. Crucially, the agent must explore suspicious or uncertain contexts (requesting reviews) to learn from human labels, while exploiting confident predictions (auto-removing) to conserve human effort.
This exploration exploration-explootttion trade-off, typical of contextual bandits, poses significant challenge for large-scale moderation pipelines. As we show next, foundation models alone are not sufficient to address this adaptivity, motivating the need for an ensemble-based approach like +nsemble++.
G.3 Challenges of Foundation Models in Online Decision-Making
Large foundation models (e.g. GPT series) have shown remarkable generalist capability but lack intrinsic uncertainty modeling and adaptive exploration (Krishnamurthy et al., [024]. Indeed, even top-tier LLMs can fail in multi-armed bandit or contextual-bandit scenarios if not provided with explicit "memory" or "sampling" mechanisms [Krishnamurthy et al. [202]]. Hence, foundation models alone often struggle in large-scale, real-time moderation because:
Uncertainty Estimation. Large models do not, by default, provide robust estimates how uncertain they are on out-of-distribution content. As result, they can incur high misclassification rates for novel forms of hate speech, rapidly changing memes, or new harassment tactics.
Incremental Adaptation at Scale. The moderation stream is both continuous and high higumvolume. We need an approach that updates quickly (in near-constant or modest cost per step) to keep pace with new data, while preserving strong overall performance.
In short, to address rare or emerging forms of hateful content, a model must actively explore uncertain contexts and incorporate human corrections with minimal overhead. This is exactly where Ensemble++ comes in.
G.4 GPT-Ensemble++ for Content Moderation
We now introduce GPT-Ensemble++ adapting the Ensemble++ agent (cf.. Section 3.3 to text-based moderation scenarios with foundation model backhone.
1. LLM Feature Extractor. We define o(x; w), mapping a post æ into Rd using a GPT-2 (or Pythial4m) backbone, with w either frozen or partially finetuned. This captures context and semantic cues.
Ensemble++ Decision Head. For each action a, we define base parameter ba E R and an ensemble factor A e Rd eaca time step, sample random reference vector Ç~ P. C RM (e.g. Gaussian). Then the action-value is:
følæ, [a] = (ő(z; w), b²) + (sgló(æ; w)], A <)-
Hence, the agent picks arg max, {a). Drawing each round fosters randomized (Thompson- like) exploration around uncertain or borderline posts.
Incremental Updates. If the system chooses human- for a post 2,, we obtain a corrective label Ve (hate free) which implies reward rı. As describe in Algorithm 1 we then update 0 = {b A"), w) using the symmetrized objective with bounded gradient steps. This step yields a fast, incremental refinement of the policy, allowing GPT-Ensemble- adapt quickly whenever new borderline cases arise in production.
G.5 Experiments: Hate-Speech Detection
Dataset and Setup. We employ a hate- eate-speech datase of about 135k posts, each assigned continuous "hate" score. Thresholding at 0.5 yields "hate vs. "free." At round t, the agent sees zt (text), chooses publish (A, 1) or block (A, = 2), and receives:
+1
if publishes free post,
0.5
if publishes hate post,
+0.5
if blocks any post.
61

---

Hate Speoch Detoction
0.8
Detection Accuracy
0.7
0.6
0.5
Ensemble
0.4
Ensemble
Gradyy
0.00
0.02
0.04
0,06
0.08
0.10
Submitted Posts
x10"
Figure 18: Detection accuracy over time in hateful vs. free moderation, averaged across random seeds, the number of submitted posts increases. Ensemblet+ (bluc) outperforms Greedy (purple) and Ensemble+ (orange) with lower variance.
We embed text with GPT-2 Pythia 14 in either frozen or partially finetuned mode, then feed into Ensemble++ or baselines.
Comparative Baselines.
We consider:
1. Greedy: A single LLM-based classifier with no ensemble factor, i.e. A = O,
2. Ensemble+ Osband et al. 2018): multiple ensemble heads jointly upated,
Ensemble++ (ours): separated ensemble updates plus partial or full LLM finetuning.
We also vary frozen vs. finetuned embeddings for GPT-based models.
G.5.1 Results and Analysis
Uncertainty-Aware Gains. Fig. shows that Ensemble++ significantly outperforms Greedy in cumulative reward, clarifying borderline expressions faster and reducing eтror variance.
Frozen vs. Finetuned. In Fig. 19 together with Ensemble++, full finetuning of GPT-based features yields further gains compared to frozen embeddings. This suggests that active adaptation of the LLM backbone crucial for handling evolving content.
Reduced Human Overhead. Although not depicted, Ensemble++ quickly pinpoints which posts are certain vs. borderline, leading to 80% fewer "human-review" actions after 10' steps compared naive or deterministic triggers (e.g.. Greedy).
G.6 Conclusions & Implications
In this chapter, we showed how Ensemble++ can be integrated with foundation models like GPT-2 for large-scale content moderation-4 domain rife with domain shifts, ambiguous inputs, and costly feedback. Our key findings:
Uncertainty quantification: Ensemble++ better identifies borderline novel forms of hate speech, enabling more selective human intervention.
Incremental adaptation:
The ensemble updates per step remain bounded, even with partial LLM
finetuning.
Reduced moderator workload: By focusing reviews on genuinely uncertain posts, Ensemble++ drastically cuts human oversight needs.
Overall, these results highlight Ensemble++ as powerful approach for real-time, uncertain tasks in industrial settings where foundation models alone lack the uncertainty-awar needed for adaptive exploration.
62

---

17.5 X100
15.0
Ozzunlatos Togget
Cummlazios Rogret
12.0
10.0
-00
0.0
0.2
0.4
0.6
0.00
0.22
6.01
0.00
0.08
0.10
Time period
X100
Time period
KIM
Pythinl4M Pine-tned tuned
Pythis14M Freaez
GPT-2 Fine-tuned tuned
GPT-2 Pronen
(a) Pythial4m
(b) GPT-2
Figure 19: Ablation in hateful-content moderation. (a.b) Fully finetuning yields stronger improve- ments in uncertain areas than freezing GPT (Pythia 44)) backbone.
Potential future directions include:
Multi-modal moderation:
Extending Ensemble++ to handle multimedia content (e.g.. images, videos) for more comprehensive moderation.
Adversarial robustness: Investigating how Ensemble++ can adapt to adversarial attacks or adver- sarial examples in moderation tasks.
Scalable crowdsourcing: Integrating Ensemble++ with scalable human-in-the-logg systems to further reduce human moderation costs.
63


Reviews:
[{"review_id": "9B5o2m7PEN", "reviewer": "Reviewer_jj6e", "summary": "This paper proposes a new computationally efficient randomized algorithm, Ensemble++, for solving linear bandit problems. The idea of Ensemble++ is to approximate the exact posterior distribution by ensembling simple models. To approximate the exact posterior distribution, they take the approach of ensemble sampling invented by Lu and Van Roy, 2017. They consider the settings of a finite arm set and a compact arm set. They provide both ensemble model complexity and regret bounds for their proposed algorithm. \n\n\nLu and Van Roy, 2017: https://arxiv.org/pdf/1705.07347", "questions": "When going beyond linear reward function, for the nonlinear reward functions, I have some questions. Is there any assumption on the non-linear reward function? Does it need to be live in an RKHS with a low norm or the norm can be in the order of $e^d$ or the norm can be unbounded? \n\nA small question for Figure 1: why the cumulative regret is decreasing with time for Ensemble++?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: their results for the compact arm set case improve the existing ones.\n\nWeakness: this work over-claims contributions by missing some important literature works. \n\nFor the case of a finite arm set, they miss an important literature, Ash et al., 2022, that weakens their claimed contribution. Proposition 2  in Ash et al., 2022 seems to be a better result for the finite arm set case. They achieve the same regret as Ensemble++, but with a smaller ensembling size. \n\nFor the case of compact arm set, they also miss an important literature, Janz et al., 2024. But the $\\tilde{O}(d^{2.5}\\sqrt{T})$ regret and $d \\log T$ ensembling size results in Janz et al., 2024 is worse than the result claimed in this paper. Note that in this paper, with the same ensemble size, the regret is in the order of $d^{1.5} \\sqrt{T}$.\n\nI hope to see some discussions about why the proposed algorithm for the infinite arm case can improve the results shown in Janz et al., 2024. I hope to see some discussions about why the proposed algorithm for the finite arm case is worse than Ash et al., 2022.\n\n\nAsh et al., 2022:   https://arxiv.org/pdf/2110.11202\nJanz et al., 2024: https://proceedings.neurips.cc/paper_files/paper/2024/file/2a568a9a84577769d838793433c817d9-Paper-Conference.pdf", "was_revised": true, "final_justification": "The result via using sequential Johnson-Lindenstrauss variant is significant as compared to the results shown in Janz et al., (2024). However, I hope the authors will add detailed discussions about the missing literature and give them enough credits in terms of their ideas.", "rebuttal": "We sincerely thank the reviewer for their excellent and careful reading of our work. We appreciate their positive assessment of our results for the compact action set case and for raising important questions about related literature. These comments are invaluable for situating our work accurately.\n\n### Response to Weaknesses (Missing Literature)\n\nWe agree that a discussion of the cited papers is important for clarity. We will add a detailed discussion of both Ash et al. [2022] and Janz et al. [2024] to the Related Work section of our revised manuscript. Below, we address the specific comparisons the reviewer requested.\n\n1.  **Discussion regarding Ash et al. [2022] (Finite Arm Set):**\n\n    **The key advantage of our work lies in *two aspects*: a. its incremental nature; b. its generality and unification**. \n\n   - a. For the incremental algorithm in Ash et al. [2022], they only provide analysis in multi-armed bandit setting in proposition 3. Ash et al. [2022] did not provide any analysis for linear bandit setting for its incremental version as they explicitly mentioned, \n>  Ash et al. [2022]: \"We conjecture that the incrementally-updated version guarantees can be extended to linear bandits beyond MAB for reasonable ensemble sizes.\"\n\n     Thus, our work can be regarded as the one resolving Ash et al. [2022]'s conjecture.\n\n   - b. **Ensemble++ is a single, unified algorithm** that, with a single analysis framework, achieves near-optimal regret across **all four standard settings**: finite actions, compact actions, invariant contexts, and varying contexts. While the result from Ash et al. is excellent, it is specialized for the finite action setting. Our framework provides a general-purpose solution that maintains strong performance and theoretical guarantees across a much broader range of problem structures without modification, a key contribution we will emphasize in the revision.\n    **These two aspects are important to build the connection to practical algorithms that can operate in complex environment when requiring function approximation such as neural nets. Moreover, it is much more challenging technically to provide rigorous justification for algorithms considering these two aspects.** \n\n2.  **Discussion regarding Janz et al. [2024] (Compact Arm Set):**\n\n    As the reviewer correctly notes, our regret bound of $\\mathcal{O}(d^{1.5}\\sqrt{T}(\\log T)^{1.5})$ is a significant improvement over the $\\tilde{\\mathcal{O}}(d^{2.5}\\sqrt{T})$ bound in Janz et al. [2024] for the same ensemble size complexity of $M = \\Theta(d \\log T)$.\n\n    This improvement stems directly from our novel **shared-factor architecture** as well as the  random linear combination schemes and its corresponding theoretical analysis. The core technical reason is that our incremental update mechanism (Eq. 4) and its analysis via a tight, **sequential Johnson-Lindenstrauss variant** (Lemma 4.2) allow us to prove a stronger concentration result for the ensemble's covariance approximation. Together with the random linear combination schemes, this tighter handle on the approximation error propagates through the regret analysis, directly leading to the improved $d^{1.5}$ dependency in the final bound. We will add a sentence to Section 4.3 clarifying that this architectural and analytical novelty is the source of the improvement.\n\n---\n\n### Responses to Questions\n\n1.  **On assumptions for nonlinear reward functions:**\n    > Is there any assumption on the non-linear reward function? Does it need to be live in an RKHS with a low norm or the norm can be in the order of $e^d$ or the norm can be unbounded?\n\n    **Rebuttal:**\n    This is a very insightful question. Our extension to the nonlinear case is **empirical and algorithmic**, rather than theoretical. As such, for the experiments in Section 5.2, **we do not impose any formal assumptions** on the reward function (e.g., belonging to an RKHS with a bounded norm).\n\n    The goal of the nonlinear section is to demonstrate that the same architectural principle—a shared base model plus ensemble directions trained with a symmetrized loss and **incremental update**—is practically effective. We validate this across a range of challenging reward functions, including quadratic, neural network-defined, and those implicit in large datasets (as detailed in Appendix F.2). A formal theoretical analysis of the nonlinear case under specific structural assumptions is an important and interesting direction for future work, as we mention in our conclusion.\n\n2.  **On the decreasing regret in Figure 1:**\n    > A small question for Figure 1: why the cumulative regret is decreasing with time for Ensemble++?\n\n    **Rebuttal:**\n    Thank you for this sharp observation, which highlights a point we can clarify. The x-axis in Figure 1 is **not time, but the number of model parameters**, serving as a proxy for computational cost. The plot illustrates the **regret-vs-computation trade-off**.\n\n    The data points for Ensemble++ (the blue stars) are clustered on the left, showing it achieves a low final regret (y-axis) with a significantly smaller model size (fewer parameters on the x-axis) compared to the baselines. We will revise the figure caption to explicitly state \"x-axis represents the number of parameters\" to prevent any future confusion."}, {"review_id": "OZKWrp6TEW", "reviewer": "Reviewer_1Pj5", "summary": "This paper introduces Ensemble++, a scalable framework for approximate Thompson Sampling in sequential decision-making tasks. It tackles the scalability bottleneck of TS in high-dimensional and non-conjugate settings by using a shared-factor ensemble architecture with random linear combinations.", "questions": "How should P be determined in Algorithm 1 in practice? To what extent does the assumed prior distribution affect performance? Moreover, since the regret bound in Theorem 4.3 also depends on P, what is the scale of \\rho(P)?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. Provides regret guarantees comparable to exact TS for linear bandits with reduced ensemble sizes. A novel approximation mechanism that reduces ensemble size from T |X| to  d \\log T while preserving theoretical regret guarantees.\n\n2. Extends seamlessly to nonlinear settings by adding a layer of neural representation, allowing practical applicability in complex tasks.\n\n3. Experiments demonstrate robustness across various domains and scalability to real-world high-dimensional problems.\n\nWeakness: \n\n(1) The performance of Ensemble++ in practice relies on choices like ensemble size M, buffer size C, and SGD steps G. Guidance for these is empirical and may not generalize.\n\n(2) Although the main contribution of this paper lies in its theoretical development, the empirical comparisons could be strengthened. For instance, the comparison with LinearUCB is missing. In the neural bandit setting, it would be valuable to include comparisons with alternative approaches such as NeuralUCB (https://arxiv.org/abs/1911.04462) and EE-Net (https://arxiv.org/abs/2110.03177).\n\n(3) The authors are encouraged to add a dedicated section on related work in the Appendix to provide broader coverage of existing methods in both linear bandits and neural bandits. Additionally, it would be helpful to mention TS or bandits in the title.", "was_revised": true, "final_justification": "Thanks for author's detailed responses, which addressed most of my concerns. I keep my positive score.", "rebuttal": "We sincerely thank the reviewer for their positive assessment, **\"Excellent\" quality rating**, and insightful feedback. We are grateful for their recognition of our work's strengths, particularly the novel approximation mechanism and the extension to nonlinear settings. We address the reviewer's valuable suggestions below.\n\n### Response to Weaknesses\n\n1.  **On Hyperparameter Guidance:**\n    > The performance of Ensemble++ in practice relies on choices like ensemble size M, buffer size C, and SGD steps G. Guidance for these is empirical and may not generalize.\n\n    **Rebuttal:**\n    This is an important practical point. While optimal hyperparameters can be task-dependent, we have provided extensive ablation studies to offer empirical guidance:\n    * For **ensemble size M**, we demonstrate its impact on the regret-computation trade-off in Figures 1 and 14. These results show that while a small M (e.g., M=4 or M=8) is often sufficient, performance consistently improves as M increases, aligning with our theory.\n    * For **buffer size C**, our study in Figure 15 shows that Ensemble++ is robust, maintaining strong performance even with a buffer capacity significantly smaller than the total time horizon.\n    * For **SGD steps G**, we agree that this is best tuned per task. We determine optimal values via parameter sweeps, as detailed in our implementation section (Appendix B, lines 845–848), which is a standard practice for training neural network-based agents.\n\n2.  **On Missing Experimental Baselines:**\n    > ...the comparison with LinearUCB is missing. In the neural bandit setting, it would be valuable to include comparisons with alternative approaches such as NeuralUCB and EE-Net.\n\n    **Rebuttal:**\n    This is a valuable suggestion. We chose our baselines to represent the most challenging and relevant state-of-the-art competitors. Specifically, we provide extensive comparisons against **LMCTS**, a powerful algorithm that was shown in its original paper to outperform classic baselines like NeuralUCB. Our results in Figure 13\\(c\\) (Appendix F.2) show that **Ensemble++ consistently and significantly outperforms LMCTS** across a variety of tasks. By demonstrating superiority over a stronger baseline, we implicitly show that Ensemble++ is also more effective than the suggested alternatives.\n\n3.  **On a Dedicated Related Work Section and Title:**\n    > The authors are encouraged to add a dedicated section on related work in the Appendix... Additionally, it would be helpful to mention TS or bandits in the title.\n\n    **Rebuttal:**\n    Thank you for these helpful presentation suggestions. We agree completely. In the final version of the paper, we will add a dedicated related work section to the Appendix to provide a more comprehensive overview of the field. We will also revise the title to better highlight the paper's contributions to Thompson Sampling and the broader bandit literature.\n\n---\n### Response to Questions\n\n> How should $P_\\zeta$ be determined in Algorithm 1 in practice? To what extent does the assumed prior distribution affect performance? Moreover, since the regret bound in Theorem 4.3 also depends on $P_\\zeta$, what is the scale of $\\rho(P_\\zeta)$?\n\n**Rebuttal:**\nThis is an excellent question that touches on both the practical and theoretical aspects of our algorithm.\n\nFor the practical choice of the reference distribution $P_\\zeta$, our ablation studies in **Figure 16** (Appendix F.2) provide clear guidance. The results show that continuous reference distributions (like Gaussian or Sphere) consistently yield superior results in practice. This empirical finding aligns perfectly with our theoretical analysis, which shows these distributions provide better regret constants.\n\nThe theoretical scale of the key distribution-dependent constant, $\\rho(P_\\zeta)$, is provided explicitly in **Table 1** and derived in detail in Appendices D and E. For the best-performing continuous distributions, $\\rho(P_\\zeta)$ scales favorably as $\\tilde{\\mathcal{O}}(\\sqrt{M})$ for compact sets or $\\tilde{\\mathcal{O}}(\\sqrt{\\log|\\mathcal{X}|})$ for finite sets, which in turn leads to the tighter final regret bounds presented in our work."}, {"review_id": "K5YOq72fQC", "reviewer": "Reviewer_zUNr", "summary": "The paper provides a nice contribution to ensemble sampling-type algorithms to minimise the cumulative regret of an unknown function with bandit feedback. It provides a state-of-the-art theoretical bound on the regret and on the number of particles for the linear bandit problem. The paper constructs an ensemble of particles that are sequentially updated, which can simulate samples from the true posterior and simulate Thompson Sampling (up to a constant). It also extends the method to nonlinear functions and verifies its validity with experiments.", "questions": "I will raise my score substantially if the following questions are adequately addressed and explained.  \n\n1) I think that Thompson Sampling (for linear bandit) is not properly described in the paper. In general,  sampling from $\\mathcal{N}(\\mu_{t}, \\Sigma_t)$ does not give a guarantied upper bound of $\\tilde{O}(d^{\\frac{3}{2}} \\sqrt{T})$ for Frequentist regret see Nima Hamidi and Mohsen Bayati. \"On frequentist regret of linear Thompson sampling\" and Marc Abeille, David Janz, Ciara Pike-Burke, \" When and why randomised exploration works (in linear bandits)\". (Which I think would also be a nice addition to the bibliography) Thompson Sampling without an inflation term can have linear regret behaviour according to Hamidi. Because your method simulates a sample from Thompson sampling without inflation, I believe there could be a mistake in the analysis. Could you explain why your method does not behave like Vanilla TS (without inflation) and make some simulations of Hamidi's counterexample?\n\n2) For the experiment on the Linear Ensemble ++, the number of sample runs should be given. There is no error bar on the minimal $M$. And more importantly, the characterisation of the minimal $M$ is poorly chosen as any algorithm $\\pi$ that is sub-linear in $T$ will verify $\\frac{\\text{Regret}(\\pi, T) - \\text{Regret}(TS, T)}{T} < \\epsilon$ asymptotically. I believe that another test should be designed to estimate the minimal $M$. Furthermore, a comparison of the regret as a function of the dimension should also be added.", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strenghts\n\nThe claims made by the paper are powerful, and if true, are very interesting for the bandit community. The bounds on the regret and the number of particles are state of the art and cover the most extensive applications for the particle sample kind algorithm applied in the linear bandit field. \n\n==================\n\nWeaknesses\n\nHowever, I have a few reasons to doubt the veracity of the result. See the question and the following reason. \n\nMajor reasons :\n\n-The paper did not cite a similar work published last year at NeurIPS. from David Janz, Alexander Litvak, and Csaba Szepesvári. \"Ensemble sampling for linear bandits: small ensembles suffice\". The paper deals with linear ensemble sampling and has a similar ensemble construction and size. However, it shows an upper bound of $O(d^{5/2} \\sqrt{T})$ regret.\n- One key lemma shown in the paper is based on another unpublished, non-peer-reviewed, and non-cited paper. \n- Some claims made about other algorithms are factually wrong, I believe. (see question for the most important one 1)\n- Some of the experiments on the linear bandit problem were very unsatisfactory. (see question 2)\n\nMinor reasons :\n\n-The paper does not make apparent the contribution of the past paper from which some part of their proof is taken. Especially, I don't think it is a proper way to cite cornerstone work (from which your analysis is based) like Line 247, \"Citations for Linear TS: Agrawal and Goyal [2013], Abeille and Lazaric [2017].\" Their work is never explained in the main paper or the introduction, while it is one of the first works on frequentist regret for Linear Thomson Sampling.\n- There are, I believe, minor typos/inaccurate facts such as Line 139 \"Sampling from $\\mathcal{N}(\\mu_{t},\\Sigma_t)$ requires $O(d^{3})$ matrix factorisation. Linear Ensemble++ sampling avoids this\". Sampling from $\\mathcal{N}(\\mu_{t},\\Sigma_t)$ requires one matrix factorisation and not $d^3$ which cost $O(d^3)$ operations. Linear ensemble sampling does not avoid this, as it costs $O(d^2M)$ to maintain $A_t$ and $O(d^3)$ to invert the matrix $\\Sigma_t$ if not done sequentially.\n- Some sentences are not finished, such as Line 583: \"It faces two main challenges when extended to large-scale or complex environments:\" But only one is given.\n\n==================\n\nMinimal remarks :\n\n- $p_z$ is never mathematically defined in the main text.", "was_revised": true, "final_justification": "The rebuttal addressed most of my concerns, and I have raised my grade. Provided that the correct description of the algorithm is made Line 143 with the added inflation term.  However, I cannot give more than 3 because of the weak evaluation in the Linear case. (Small time horizon $T$ compared to the dimension, improper evaluation of the minimal M, easy cases that come from Bayesian analysis of TS, while it is the frequentist regret that is studied here). I also suspect that the evaluation was not made with the inflated variance, as the table added with the rebuttal suggests.  The regret there seems linear in $d$.\nThe paper boasts very strong extensions to non-linear cases with added experiments. As I am not a neural network experimentalist nor an expert on particle filter/online method, I cannot vouch for those.", "rebuttal": "We sincerely thank the reviewer for their detailed feedback and for recognizing that our work provides a \"state-of-the-art theoretical bound\" with \"powerful claims\" that are \"very interesting for the bandit community.\" The concerns raised are excellent points of clarification that we are happy to address. We believe they can be fully resolved by highlighting details already in the appendix and by adding the suggested context to the revised paper.\n\n---\nResponses to Major Reasons\n\n1.  **On the uncited work by Janz et al.:**\n    * **We will gladly cite Janz et al. and our revised paper will clarify that our work is distinct in its broader scope, unified analysis, and superior regret bound.** Thank you for bringing this relevant work to our attention. We will add a detailed discussion of Janz et al. in our Related Work section. While their work is an important contribution, our **Ensemble++** offers key advantages:\n        * **Unified Framework:** Our work provides a single algorithm and analysis for all four common linear bandit settings (Invariant/Varying contexts & Compact/Finite action sets).\n        * **Tighter Regret:** As the reviewer notes, the analysis by Janz et al. [2024] results in an $\\tilde{O}(d^{2.5}\\sqrt{T})$ regret bound. Our analysis achieves a significantly better $\\tilde{O}(d^{1.5}\\sqrt{T})$ bound for the same setting.\n        * **Extensibility:** Our framework is explicitly designed to extend to complex non-linear and neural settings, a scope not covered by Janz et al.\n\n2.  **On the key lemma's citation:**\n    * **This concern is resolved, as the cited work has now been accepted and published at a top-tier peer-reviewed conference (ICML 2024).** We appreciate the reviewer's diligence. The foundational result for our key lemma (Lemma 4.2) has now been peer-reviewed as part of the paper \"Q-Star Meets Scalable Posterior Sampling...\", accepted at ICML 2024. We will update the citation to its published version, confirming the soundness of our proof.\n\n---\n### Responses to Minor Reasons\n\n1.  **On contextualizing cornerstone work:**\n    * **We agree and will expand our discussion of prior work.** Thank you for this suggestion. In the revised version, we will enhance Section 2 to better explain the cornerstone contributions of Agrawal and Goyal [2013] and Abeille and Lazaric [2017].\n\n2.  **On the accuracy of Line 139 regarding computational cost:**\n    * **We will revise the imprecise wording on Line 139 and clarify the computational trade-offs.** We agree the phrasing can be more precise. The $\\mathcal{O}(d^3)$ cost for standard TS comes from matrix factorization for sampling. Our method avoids this, and while its theoretical complexity is also $\\tilde{\\mathcal{O}}(d^3)$, it is empirically closer to $\\mathcal{O}(d^2)$ with a practical choice of M. More importantly, as we will clarify, the key advantage of our incremental framework is its seamless extension to non-conjugate neural models.\n\n3.  **On the unfinished sentence on Line 583:**\n    * **We will fix this writing oversight.** Thank you for catching this. We will revise the sentence in Appendix A.2 to explicitly state the two intended challenges: (1) intractability in non-conjugate models and (2) the computational overhead of approximate inference methods.\n\n---\n### Response to Minimal Remarks\n\n1.  **On the definition of $P_z$:**\n    * We appreciate the reviewer pointing this out. The distribution $P_z$ is indeed mentioned in the main text (e.g., Line 145, Algorithm 1) but defined and discussed in detail in Appendices B.1 and E. **To further improve readability**, we will add a forward reference in the main text (Section 3.1) to guide the reader to the detailed discussion in the appendix.\n\n---\n### Responses to Questions\n\n1.  **On the lack of an inflation term in the analysis:**\n    * **Our analysis does use an inflation term ($\\beta_t$), which is crucial for the regret bound.** This is an excellent technical question. Our analysis is based on an inflated version of posterior sampling, as is required. This inflation is explicitly achieved via the confidence scaling parameter $\\beta_t$ in our sampled model definition: $\\tilde{f_t}(a) := \\langle\\phi(a),\\beta_{t}A_{t-1}\\zeta_{t}+\\mu_{t-1}\\rangle$ (Equation 36). Our core proof shows our ensemble mechanism correctly approximates the uncertainty, which is then correctly scaled by $\\beta_t$. We will clarify this in the main text.\n\n2.  **On the experiments for minimal M:**\n    * **We will add the requested details on experimental setup and the new regret vs. dimension analysis to the main paper.** Thank you for these important suggestions to strengthen our empirical validation.\n        * **Number of Runs:** This detail (200 runs) is in Appendix F.1 (Line 1370) and we will move it to the main text for better visibility.\n        * **Error Bars for Minimal M:** This is a thoughtful point. The minimal M is an estimate derived from our 200-run averaged regret curves. Instead of adding error bars directly to M in Figure 2(b), which could clutter the figure, we will add a plot to the appendix showing the metric value versus M. This will clearly illustrate the stability of the curve as it crosses the threshold, giving confidence in our estimate.\n        * **Metric for Minimal M:** The reviewer's asymptotic argument is correct, but our experiment uses a **fixed, finite horizon ($T=1000$)**, where the metric is a standard way to quantify practical performance matching. We will add a sentence to clarify this non-asymptotic goal.\n        * **Regret vs. Dimension:** This is a great suggestion. We will add the following table and analysis to the paper. The results confirm that **ES++ with a small M (e.g., M=8 or M=16) tracks the performance of exact TS very closely across all dimensions**, strengthening our claims of practical efficiency.\n\n| Method | d=10 | d=20 | d=30 | d=40 | d=50 | d=60 | d=70 |\n| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |\n| TS | 133.51 | 224.37 | 343.11 | 478.27 | 634.64 | 803.01 | 992.55 |\n| ES++ (M=4) | 160.03 | 328.79 | 566.29 | 947.18 | 1274.01| 1583.49| 1985.69|\n| ES++ (M=8) | 136.72 | 250.42 | 397.26 | 592.30 | 801.08 | 995.61 | 1237.55|\n| ES++(M=16)| 134.16 | 227.47 | 359.63 | 504.00 | 659.69 | 851.36 | 1033.53 |"}, {"review_id": "QPXhZGYpgH", "reviewer": "Reviewer_Kuk5", "summary": "This paper presents Ensemble++ - a novel algorithm to approximate Thompson sampling - handling non-conjugate cases. They analyse the linear case, showing that (in terms of regret bound) they perform nearly as well as exact Thompson sampling whilst requiring an ensemble size that is independent of the cardinality of the total action set. They perform experiments for both linear bandits and non-linear bandits - including neural bandits - comparing to other algorithms in the literature.", "questions": "Ensemble+ and EpiNet don’t appear in the linear bandit regret/time comparison - do these have regret bounds? Likewise, the two algorithms in the regret/time comparison don’t appear in the empirical comparison - why is this?", "limitations": "I cannot see any limitations hidden.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper is clearly written and conveys the result well. The experimental results are good and it appears to me that the paper should have impact. \n\nSince, for linear bandits, exact Thompson sampling outperforms (only just) Ensembe++ both in the regret and time complexity, the theoretical results by themselves don’t add anything new in terms of theory. However, these theoretical results strongly suggest that the algorithm will be powerful in non-conjugate cases and are hence important. \n\nThe ensemble size required for (what are essentially) the Thompson sampling results are, unlike previous works, independent of the cardinality of the total action set (replacing it by the dimensionality instead) which is a dramatic improvement. The algorithm achieves this regret for varying contexts and infinite compact action sets - which is a first for approximate Thompson sampling algorithms. However, I am not an expert in the area so I cannot validate these claims about previous works. \n\nI guess a weakness is that there are no theoretical results beyond the linear problem.", "was_revised": true, "final_justification": "Good result - my concerns were satisfied and I am happy for the paper to be accepted. My score is a borderline accept currently but I am open to changing it based on what the other reviewers say (I feel I don't have as much expertise when it comes to Thompson sampling).", "rebuttal": "We sincerely thank the reviewer for their positive and encouraging feedback. We are glad they found the paper clearly written and impactful. We agree with their assessment that while the theoretical results are for the linear case, they provide a strong foundation for the algorithm's power in the non-conjugate settings where it truly shines.\n\nWe would like to address the excellent question raised by the reviewer regarding the separation of algorithms between our theoretical and empirical comparisons.\n\n> **Reviewer Question:** Ensemble+ and EpiNet don’t appear in the linear bandit regret/time comparison - do these have regret bounds? Likewise, the two algorithms in the regret/time comparison don’t appear in the empirical comparison - why is this?\n\n**Rebuttal:**\n\nThis is a great question that gets to the heart of how we structured our evaluation. The separation is intentional and reflects the different domains where these algorithms are relevant.\n\n1.  **Why Ensemble+ and EpiNet are not in the Theoretical Comparison (Table 2):**\n    The reviewer is correct that **Ensemble+** and **EpiNet** are absent from our theoretical comparison table. This is because these methods are primarily designed as practical, heuristic approaches for **deep neural bandits**. To our knowledge, they do not have established theoretical regret bounds for the standard linear bandit setting. Therefore, including them in Table 2, which specifically compares formal regret guarantees, would not be appropriate. We compare against them extensively in the empirical sections (Section 5.2, Figure 3) where they are considered the state-of-the-art.\n\n2.  **Why the algorithms from the Theoretical Comparison are not in the Empirical Comparisons:**\n    The works of **Qin et al. [2022]** and **Lee and hwan Oh [2024]** provide valuable *theoretical analyses* of ensemble sampling, but their requirements make them unsuitable as practical empirical baselines.\n    * Specifically, the analysis by Qin et al. requires an ensemble size of $M=\\Omega(|\\mathcal{X}|T)$ to achieve the stated regret bound. In our experiments where the action set $|\\mathcal{X}|$ is up to 10,000 and the horizon $T$ is 1000, this would require an ensemble of millions, which is **computationally infeasible** to implement.\n    * Our empirical comparisons therefore focus on benchmarking against algorithms that represent the practical state-of-the-art and can be run under *realistic* computational constraints.\n    * **We have compared empirically Ensemble++ Sampling with Ensemble Sampling in linear bandit setting** where Ensemble Sampling is the algorithm Qin and Lee analyzed.\n\nIn summary, we deliberately separated our comparisons: **Table 2 compares theoretical guarantees** among formally analyzed linear bandit algorithms, while **our empirical studies (e.g., Figure 3) compare practical performance** against the most relevant state-of-the-art methods for each specific environment (linear or nonlinear). We will add a sentence to the main text to make this distinction clearer for the reader.\n\n**To highlight, the primary advantage of our incremental framework of the Ensemble++ is its seamless extension from linear setting to non-conjugate neural models where updates are performed with SGD, which is a key focus of our work.**"}]

Author rebuttal:

Meta-review: This paper proposes Ensemble++ for linear/nonlinear bandits. The analysis reveals improvements over existing ensemble sampling algorithms.

This paper have made a significant improvement in the regret bounds, and the use of sequential Johnson-Lindenstrauss is novel. On the other hand, there was a minor issue regarding the evaluation of TS (it was not clear if they used the inflated version or not), and the experiments could enjoy more baselines as mentioned by reviewers.

Overall, I believe the strengths outweighs the weaknesses, so I am recommending an accept.
Decision: Accept (poster)