Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits

## Abstract

Abstract We provide a unified algorithmic framework for ensemble sampling in nonlinear contextual bandits and develop corresponding regret bounds for two most common nonlinear contextual bandit settings: Generalized Linear Ensemble Sampling ( GLM-ES ) for generalized linear bandits and Neural Ensemble Sampling ( Neural-ES ) for neural contextual bandits. Both methods maintain multiple estimators for the reward model parameters via maximum likelihood estimation on randomly perturbed data. We prove high-probability frequentist regret bounds of 𝒪 ​ ( d 3 / 2 ​ T + d 9 / 2 ) \mathcal{O}(d^{3/2}\sqrt{T}+d^{9/2}) for GLM-ES and 𝒪 ​ ( d ~ ​ T ) \mathcal{O}(\widetilde{d}\sqrt{T}) for Neural-ES , where d d is the dimension of feature vectors, d ~ \widetilde{d} is the effective dimension of a neural tangent kernel matrix, and T T is the number of rounds. These regret bounds match the state-of-the-art results of randomized exploration algorithms in nonlinear contextual bandit settings. In the theoretical analysis, we introduce techniques that address challenges specific to nonlinear models. Practically, we remove fixed-time horizon assumptions by developing anytime versions of our algorithms, suitable when T T is unknown. Finally, we empirically evaluate GLM-ES , Neural-ES , and their anytime variants, demonstrating strong performance. Overall, our results establish ensemble sampling as a provable and practical randomized exploration approach for nonlinear contextual bandits.

## 1 Introduction

The contextual bandit is an online learning problem where an agent interacts with an environment by pulling arms, each associated with a feature vector. After each pull, the agent receives a stochastic reward whose expected value depends on the chosen arm’s feature vector. The agent’s goal is to maximize the accumulated reward. Contextual bandits provide a natural abstraction for real-world sequential decision-making problems such as content recommendation (Zhu and Van Roy, 2023) and clinical trials (Varatharajah and Berry, 2022). To maximize rewards, the agent must learn the mapping from an arm’s feature vector to its expected reward. Most prior work has focused on the linear contextual bandit setting (Abbasi-Yadkori et al., 2011; Abeille and Lazaric, 2017; Kveton et al., 2020b), where the expected reward is assumed to be a linear function of the feature vector. While this assumption facilitates theoretical analysis and efficient implementations, it fails to capture complex relationships between features and rewards. This has motivated the study of nonlinear contextual bandits, where the expected reward is modeled as a nonlinear function of the arm’s features, e.g., through generalized linear models (GLMs) or neural networks. In the GLM setting (Filippi et al., 2010; Kveton et al., 2020b), the reward is generated by applying a nonlinear function $\mu(\cdot)$ to the inner product of the feature vector and an unknown parameter vector, a setting referred to as generalized linear bandits. In more general cases where the reward cannot be expressed within the GLM structure, neural contextual bandits approximate the reward function with deep neural networks, without assuming any particular functional form (Jacot et al., 2018; Zhou et al., 2020; Zhang et al., 2021; Xu et al., 2022a; Jia et al., 2022). These nonlinear approaches have substantially improved the empirical performance of linear bandit algorithms, especially in complex environments (Xu et al., 2022b; Jia et al., 2022).

While nonlinear models enhance expressivity, they also complicate the design of effective exploration strategies. Existing exploration methods such as Upper Confidence Bound (UCB) (Abbasi-Yadkori et al., 2011) and Thompson Sampling (TS) (Agrawal and Goyal, 2013) heavily depend on reward structure and distributional assumptions. Extending them to nonlinear settings requires significant approximations (Zhou et al., 2020; Zhang et al., 2021; Xu et al., 2022a, b), often making the methods impractical in real-world applications. This motivates the search for exploration strategies that combine strong empirical performance with theoretical guarantees in nonlinear bandits. Ensemble sampling (Lu and Van Roy, 2017) has emerged as a promising class of algorithms for online decision-making problems, including bandits (Lee and Oh, 2024), deep reinforcement learning (Osband et al., 2016), and recommendation systems (Zhu and Van Roy, 2023). Ensemble sampling maintains an ensemble of $m$ models, each trained on randomly perturbed historical data consisting of arm features and rewards. At each round, one model is sampled to estimate expected rewards, and the arm with the highest estimate is selected. After receiving the reward, the new data point—with random perturbation—is added to the dataset, and all models are updated.

In recent years, ensemble sampling has gained popularity due to its strong empirical performance and moderate computational cost. However, theoretical understanding has lagged behind. Existing analyses provide regret guarantees only in the linear contextual bandit setting. For example, Lee and Oh (2024) proved a high-probability $T$-round regret bound of $\widetilde{\mathcal{O}}(d^{3/2}\sqrt{T})$ with ensemble size $m=\Omega(K\log T)$, where $d$ is the feature dimension and $K$ is the number of arms. More recently, Janz et al. (2024a) established a regret bound of $\widetilde{\mathcal{O}}(d^{5/2}\sqrt{T})$ for infinitely many arms with ensemble size $\Theta(d\log T)$. While these theoretical works provide valuable insights, they are far from fully elucidating the empirical success of ensemble sampling in complex decision-making applications, where reward models are typically nonlinear in the arm features.

In this work, we extend ensemble sampling to nonlinear bandit settings with finitely many arms. Specifically, we study the two most widely used models: generalized linear bandits and neural contextual bandits. We show that ensemble sampling in these settings achieves high-probability regret bounds matching the state-of-the-art for randomized exploration algorithms, with ensemble size logarithmic in $T$. In addition, we develop anytime versions of ensemble sampling using the doubling trick, addressing the limitation that ensemble size and other hyperparameters traditionally depend on the horizon $T$. These anytime variants significantly broaden the applicability of ensemble sampling. Finally, we complement our theoretical results with experiments on Lin-ES, GLM-ES, and Neural-ES against baselines. Our experiments highlight the practicality of ensemble sampling in nonlinear bandits, balancing strong performance with computational efficiency.

Our contributions are summarized as follows.

- •
We propose a general framework for ensemble sampling in bandit problems and introduce GLM-ES and Neural-ES as its realizations in nonlinear settings.
- •
We provide theoretical analyses of GLM-ES and Neural-ES, proving regret bounds of $\widetilde{\mathcal{O}}(d^{3/2}\sqrt{T}+d^{9/2})$ and $\widetilde{\mathcal{O}}(\widetilde{d}\sqrt{T})$, respectively, both matching the state-of-the-art for randomized exploration algorithms. To the best of our knowledge, these are the first high-probability regret bounds for ensemble sampling in nonlinear bandit settings.
- •
For generalized linear bandits, we optimize the warm-up procedure in existing literature, reducing regret from $d^{9}$ to $d^{9/2}$. This improvement also applies to perturbed-history type of exploration strategies. We further remove the need for adaptive reward perturbations, simplifying the design and improving the efficiency of our algorithm.
- •
We develop anytime versions of ensemble sampling using the doubling trick and show that their asymptotic cumulative regret guarantees are preserved.
- •
We conduct empirical evaluations comparing cumulative regret and computational cost with baselines, demonstrating the practicality of ensemble sampling.

## 2 Related Work

#### Randomized Exploration

Randomized exploration strategies add controlled randomness to promote exploration of actions with high uncertainty. In sequential decision-making problems, randomized exploration strategies often outperform deterministic strategies such as Upper Confidence Bound (UCB) (Chu et al., 2011; Lattimore and Szepesvári, 2020) by preventing early convergence to suboptimal actions. Among such methods, Thompson Sampling (TS) (Thompson, 1933) is a key approach for multi-armed bandits (Agrawal and Goyal, 2017; Jin et al., 2021, 2023), contextual bandits (Agrawal and Goyal, 2013; Abeille and Lazaric, 2017), and RL (Osband et al., 2013; Fan and Ming, 2021; Sasso et al., 2023). TS maintains a posterior over model parameters, updated each round from a prior (e.g., Gaussian) and observed rewards (Agrawal and Goyal, 2013), and samples a parameter from this posterior for arm selection. Despite its simplicity, many TS variants rely on exact posteriors or accurate Laplace approximations, which can be costly. To address this, approximate sampling methods such as Langevin Monte Carlo (LMC) (Xu et al., 2022b; Hsu et al., 2024), Stochastic gradient Langevin dynamics (SGLD) variants (Mazumdar et al., 2020; Zheng et al., 2024; Wang et al., 2025b), and variational inference (Clavier et al., 2024) have been developed and applied to various problem settings, including multi-armed bandits with non-conjugate or highly nonlinear rewards, nonlinear contextual bandits, and RL (Ishfaq et al., 2024a, b; Hsu et al., 2024). Another important method is perturb-history exploration (PHE) method, which involves introducing random perturbations in the historical data to approximate posterior sampling, making it applicable to complex reward distributions (Kveton et al., 2020b; Ishfaq et al., 2021). Ensemble sampling maintains a small set of independently perturbed model replicas and selects arms using a randomly chosen replica (Lu and Van Roy, 2017). Follow-up work provided theory for the linear contextual bandit setting. Qin et al. (2022) gave the first regret bound. Janz et al. (2024a) tightened guarantees with an ensemble of size $\Theta(d\log T)$ for linear bandits with infinitely many arms. LinES (Lee and Oh, 2024) further improved the regret to $\widetilde{\mathcal{O}}(d^{3/2}\sqrt{T})$ and clarified its connection to LinPHE.

#### Generalized Linear Bandits

Generalized linear contextual bandits model rewards via a link function of a linear predictor, extending linear bandits to a more general setting. Early work introduced GLM-UCB and proved regret guarantees under standard regularity conditions (Filippi et al., 2010). Subsequent advances focused on optimality and efficiency. Li et al. (2017) gave provably optimal algorithms with refined confidence sets. Ding et al. (2021) combined online stochastic gradient updates with Thompson Sampling for scalable inference. Kveton et al. (2020b) developed randomized exploration for GLMs with sharper analyses. Perturbation-based methods provide practical alternatives: linearly perturbed loss minimization yields simple, sampling-free exploration with strong guarantees (Janz et al., 2024b), and PHE adapts perturb-history exploration to sub-Gaussian GLMs (Liu, 2023). Sawarni et al. (2024) analyze GLMs under limited adaptivity (batched policies) with communication and deployment constraints. Anytime-valid confidence sequences for GLMs enable principled UCB/TS decisions and valid sequential inference (Lee et al., 2024). At large horizons, One-pass update methods achieve near-optimal regret with single-pass, low-memory updates (Zhang et al., 2025).

#### Neural Bandits

Neural bandits combine deep neural networks (DNNs) with contextual bandit algorithms. This setting leverages the representation power of DNNs and insights from neural tangent kernel (NTK) theory (Jacot et al., 2018). NeuralUCB (Zhou et al., 2020) builds confidence sets using DNN-derived random features to enable UCB-style exploration. NeuralTS (Zhang et al., 2021) extends Thompson Sampling to this setting by using a neural estimator to approximate the posterior over rewards. To improve computational efficiency, Neural-LinUCB (Xu et al., 2022a) uses DNNs to learn a deep representation but only adds shallow exploration in the last layer. NeuralLCB (Nguyen-Tang et al., 2022) studies offline neural bandits and uses a neural lower confidence bound to take pessimistic decisions under uncertainty. To further reduce the compute burden of explicit exploration, NPR (Jia et al., 2022) learns a neural bandit model with perturbed rewards following PHE type of exploration (Kveton et al., 2020a, b), avoiding separate exploration updates. Subsequent work explores added networks for exploitation (Ban et al., 2022), provable guarantees with smooth activations (Salgia, 2023), and extensions to combinatorial selection (Hwang et al., 2023; Atalar and Joe-Wong, 2025; Wang et al., 2025a), where the learner selects a subset (e.g., multiple arms under constraints) each round and receives a corresponding reward.

## 3 Problem Setting

Contextual bandits form a broad class of sequential decision making problems where the player chooses an action from an observed action set based on interaction history. Each action is associated with a feature vector (context).
At round $t$, the player observes an action set $\mathcal{X}_{t}\subseteq\mathbb{R}^{d}$, where we assume for any $X\in\mathcal{X}_{t}$, $\|X\|_{2}\leq 1$.
The agent then selects an arm (action) $X_{t}\in\mathcal{X}_{t}$ and the environment immediately reveals a reward $Y_{t}$.
We consider the setting that the action set is finite with $K$ arms and fixed across different rounds.
We assume that the mean reward for a feature $X\in\mathbb{R}^{d}$ is generated by an unknown function $h(X):\mathbb{R}^{d}\rightarrow\mathbb{R}$, and the observed reward satisfies $Y=h(X)+\eta$, where $\eta$ is observation noise and is assumed to be $\sigma$-sub-gaussian.
In general, the form of $h(X)$ is unknown.
One special case is that we set reward model to be a linear function $h(X)=X^{\top}\theta^{*}$, then $h(X)$ is parameterized using a vector $\theta^{*}\in\mathbb{R}^{d}$ and we have the standard linear contextual bandit setting (Chu et al., 2011; Abbasi-Yadkori et al., 2011; Agrawal and Goyal, 2013).

In this work, we consider nonlinear contextual bandits where the reward model $h(X)$ is a nonlinear function of feature vector $X$. We focus on two most common nonlinear settings: (1) generalized linear bandits with $h(X)=\mu(X^{\top}\theta_{\text{GLM}}^{*})$, where $\theta_{\text{GLM}}^{*}\in\mathbb{R}^{d}$ is the true parameter with $\|\theta_{\text{GLM}}^{*}\|\leq S$ and $\mu(\cdot)$ is a strictly increasing link function (Li et al., 2017; Kveton et al., 2020b); (2) neural contextual bandits where no assumptions are made about $h(X)$ other than that it is bounded, we use a neural network $f(X;\theta_{\text{Neural}})$ to approximate $h(X)$, where $\theta_{\text{Neural}}$ is the concatenation of all weights and its dimension is determined by the structure of the neural network (Zhou et al., 2020; Zhang et al., 2021; Jia et al., 2022).

The goal of a bandit algorithm is to maximize the cumulative reward over a horizon $T$, equivalently to minimize the pseudo-regret (Lattimore and Szepesvári, 2020)

$$ $\displaystyle R(T)=\sum_{t=1}^{T}\big(h(X_{t}^{*})-h(X_{t})\big),$ (3.1) $$

where $X_{t}\in\mathcal{X}_{t}$ is the arm played at round $t$, and $X_{t}^{*}=\mathop{\mathrm{argmax}}_{X\in\mathcal{X}_{t}}h(X)$ is the arm with the highest expected reward at that round. To minimize the cumulative regret $R(T)$, the agent needs to collect information and learn the true reward model $h(X)$ from interactions with the environment.

#### Notations

We adopt the following standard notations throughout this paper. The set $\{1,2,...n\}$ is denoted by $[n]$.
For any positive semi-definite matrix $M$, we use $\lambda_{\text{max}}(M)$ and $\lambda_{\text{min}}(M)\geq 0$ to denote maximum and minimum eigenvalues of $M$.
The 2-norm of a symmetric matrix $M$ is defined as $||M||_{2}=|\lambda_{\text{max}}(M)|$. For any positive semi-definite matrices $M_{1}$ and $M_{2}$, $M_{1}\preceq M_{2}$ if and only if $x^{\top}M_{1}x\leq x^{\top}M_{2}x$ for all $x\in\mathbb{R}^{d}$. All vectors are column vectors. For any vector $x$, we use the following vector norms: $||x||_{2}=\sqrt{x^{\top}x}$, $||x||_{M}=\sqrt{x^{\top}Mx}$. The indicator function that event $\mathcal{E}$ occurs is $\operatorname*{\mathds{1}}\{\mathcal{E}\}$.
We use $\widetilde{\mathcal{O}}$ for the big-O notation up to logarithmic factors.

## 4 Ensemble Sampling for Nonlinear Contextual Bandits

We apply the design principle of ensemble sampling to nonlinear contextual bandits, extending previous works on linear ensemble sampling (Lin-ES) to broader applications. In this section, we first present a unified algorithm framework for ensemble sampling in nonlinear contextual bandit, then we focus on two common nonlinear cases: 1) generalized linear contextual bandits (GLM); 2) neural contextual bandits, and respectively provide algorithms GLM-ES and Neural-ES.

### 4.1 Unified Algorithm Framework

Ensemble sampling follows the randomized exploration principle and exploration is realized through adding perturbations to observed rewards.
Therefore, the perturbed history $\mathcal{D}_{t}=\{(X_{l},Y_{l}+Z_{l})\}_{l=1}^{t}$ is utilized to estimate the true reward model $h(X)$ and choose the best arm, where $\{X_{l}\}_{l=1}^{t}$ are pulled arms, $\{Y_{l}\}_{l=1}^{t}$ are observed rewards and $\{Z_{l}\}_{l=1}^{t}$ are perturbations.

In particular, we maintain an ensemble of perturbed models, each with different perturbed history $\mathcal{D}_{t}^{j}$, where $j\in[m]$ is the model index. At each round, we randomly select one model to estimate the mean reward of each arm in the arm set, then select the arm that maximizes the estimated mean reward. We use $f_{t}(X)$ to denote the estimated mean reward of arm $X$ from the chosen model in round $t$. After observing the reward $Y_{t}$ from the environment, each model in the ensemble is updated incrementally based on history $\mathcal{D}_{t+1}^{j}$.
At each round, we only sample one perturbation $Z_{t}^{j}$ for each model $j\in[m]$, the previous perturbations $\{Z_{l}^{j}\}_{l=1}^{t-1}$ do not need to be resampled.

###### Remark 4.1 .

The design of ensemble sampling is similar to that of perturb-history exploration (PHE)-based algorithms. In PHE-based algorithms (Kveton et al., 2020a, b), we only keep one model, but the entire perturbation sequence $\{Z_{l}\}_{l=1}^{t}$ is freshly sampled in each round. As a result, the per-round computational cost due to sampling increases linearly in $t$, the algorithm becomes impractical for large $T$. Ensemble sampling can significantly reduce the computational cost by keeping previous perturbations, the per-round sampling cost remains constant for any $t$.

A unified algorithmic framework is given in [Algorithm˜1](https://arxiv.org/html/2510.10730v1#alg1). For the generalized linear and neural bandit settings, we specify (i) a warm-up/initialization step (Line [2](https://arxiv.org/html/2510.10730v1#alg1.l2)) and (ii) a parameter-estimation loss $L_{\text{nonlin}}$ (Line [9](https://arxiv.org/html/2510.10730v1#alg1.l9)). The following sections detail these two algorithmic instantiations.

Figure: Algorithm 1 Ensemble Sampling for Nonlinear Contextual Bandits

###### Remark 4.1 .

### 4.2 Ensemble Sampling for Generalized Linear Model (GLM-ES)

We first consider the generalized linear model (GLM) and provide the algorithm design of GLM-ES.

#### Generalized Linear Model with Regularization:

We assume that the reward $Y$ given feature vector $X$ has an exponential-family distribution with mean $\mu(X^{\top}\theta_{\text{GLM}}^{*})$, where $\mu(\cdot)$ is the link function and $\theta_{\text{GLM}}^{*}\in\mathbb{R}^{d}$ is the (true) model parameter.
Specifically, at each round $t$, the observed reward is generated by $Y_{t}=\mu(X^{\top}\theta_{\text{GLM}}^{*})+\eta_{t}$,
where $\eta_{t}$ is the $\sigma$-sub-Gaussian random noise.
Detailed discussions on the exponential-family assumption are included in [Appendix˜A](https://arxiv.org/html/2510.10730v1#A1).
Given observed data set $\mathcal{D}_{t}=\{(X_{l},Y_{l})\}_{l=1}^{t}$, the $\lambda$-regularized negative log-likelihood of $\mathcal{D}_{t}$ under parameter $\theta$ is

$$ $\displaystyle L_{\text{GLM}}(\theta;\mathcal{D}_{t})=\frac{\lambda}{2}\|\theta\|^{2}-\sum_{l=1}^{t}\big(Y_{l}\cdot X_{l}^{\top}\theta-b(X_{l}^{\top}\theta)\big),\qquad\dot{b}(\cdot)=\mu(\cdot).$ (4.1) $$

#### Algorithm Design:

In GLM-ES, we maintain an ensemble of $m$ models (estimators), each model is parametrized by parameter $\theta_{t}^{j}$, $j\in[m]$, which is an estimation of $\theta^{*}_{\text{GLM}}$ based on perturbed history.
We use the $\lambda$-regularized negative log-likelihood to obtain the parameter estimation,

$$ $\displaystyle\theta_{t}^{j}=\text{argmin}_{\theta\in\mathbb{R}^{d}}L_{\text{GLM}}\big(\theta;\{X_{l},Y_{l}+Z_{l}^{j}\}_{l=1}^{t}\big),$ (4.2) $$

where $Z_{l}^{j}\in\mathbb{R}$ are perturbations sampled from distribution $\mathcal{P}_{R}$. In GLM-ES, we also use a warm-up procedure that approximates a G-optimal design, that is,

$$ $\displaystyle\zeta=\mathop{\mathrm{argmin}}_{\zeta\in\Delta_{\mathcal{X}}}\max_{X\in\mathcal{X}}\|X\|^{2}_{V(\zeta)^{-1}},\quad\text{where }V(\zeta)=\sum_{X\in\mathcal{X}}\zeta(x)XX^{\top}.$ $$

We then sample $X_{1},\dots,X_{\tau}$ based on G-optimal design $\zeta$ by following the rounding procedure [Algorithm˜3](https://arxiv.org/html/2510.10730v1#alg3) given in Pukelsheim (2006, Chapter 12) and detailed in Fiez et al. (2019). The complete warm-up procedure [Algorithm˜2](https://arxiv.org/html/2510.10730v1#alg2) is provided in [Section˜B.5](https://arxiv.org/html/2510.10730v1#A2.SS5).

###### Remark 4.2 .

The algorithm GLM-ES is an application of ensemble sampling in GLM settings. Compared to Lin-ES, a warm-up procedure [Algorithm˜2](https://arxiv.org/html/2510.10730v1#alg2) is required to guarantee that optimism is satisfied with constant probability. In the generalized linear bandit literature, the number of rounds in warm-up procedure is typically chosen by enforcing a lower bound on the minimum eigenvalue of the empirical feature covariance matrix (Kveton et al., 2020b; Li et al., 2017; Liu, 2023). However, most works do not specify the required order for the number of warm-up rounds — effectively treating it as an assumption. We propose a practical warm-up scheme that directly controls the uncertainty level (see [Lemma˜B.5](https://arxiv.org/html/2510.10730v1#A2.Thmtheorem5) for details). The same procedure is also used in Liu (2023). Additionally, compared to the algorithm design in Liu (2023), we removed the requirement for adapted perturbation on rewards and reduced requirements on the number of rounds in the warm-up procedure, making the algorithm simpler and more efficient.

###### Remark 4.2 .

### 4.3 Ensemble Sampling for Neural Contextual Bandit (Neural-ES)

We now introduce neural contextual bandit setting and introduce the algorithm Neural-ES.

#### Neural Contextual Bandit:

In the GLM setting, we assume the mean reward is given by $\mu(X^{\top}\theta^{*})$, where the link function $\mu(\cdot)$ is known to the agent. In neural contextual bandits, we only assume that the reward model $h(X)$ is bounded as $0\leq h(\cdot)\leq 1$.
Since we add no assumptions to $h(\cdot)$ except that it is bounded, we need to use a deep neural network (DNN) to approximate the true relation.
We adopt the following fully connected neural network $f(X;\theta)$ to approximate $h(X)$:

$$ $\displaystyle f(X;\theta)=\sqrt{N}\,W_{L}\phi\big(W_{L-1}\phi\big(\cdot\cdot\cdot\phi(W_{1}X)\big)\big),$ $$

where $N$ and $L$ are the width and depth of the neural network, $\phi(x)=\text{ReLU}(x)$, $W_{l}$ are learnable parameter matrices, and $\theta=[\text{vec}(W_{1}),\cdot\cdot\cdot,\text{vec}(W_{L})]\in\mathbb{R}^{d^{\prime}}$ is the concatenation of all learnable parameters.
The dimension of $\theta$ is $d^{\prime}=N+Nd+N^{2}(L-1)$.
For simplicity, we design the neural network such that each layer has the same width $L$.

To learn the parameters in the neural network, we define the following $\lambda$-regularized loss function:

$$ $\displaystyle L_{\text{Neural}}(\theta;\mathcal{D}_{t})=\frac{1}{2}\sum_{l=1}^{t}\big(f(X_{l};\theta)-Y_{t}\big)^{2}+\frac{1}{2}\lambda N\,||\theta-\theta_{0}||_{2}^{2},$ $$

where parameter $\theta_{0}$ is randomly sampled at initialization. The parameter $\theta$ is estimated using (stochastic) gradient descent to minimize the loss function.

#### Algorithm Design:

We follow the unified algorithm framework ([Algorithm˜1](https://arxiv.org/html/2510.10730v1#alg1)) to design Neural-ES.
We maintain $m$ different models to approximate the true mapping $h(\cdot)$, each model is a deep neural network with the same structure.
We first initialize the neural network in each model $\theta_{0}^{j}=[\text{vec}(W_{1}),\cdot\cdot\cdot,\text{vec}(W_{L})]\in\mathbb{R}^{d^{\prime}}$ using random parameters sampled from Gaussian distribution: for $1\leq l\leq L-1$, $W_{l}=(W,0;0,W)$ with each entry sampled from $\mathcal{N}(0,4/N)$; $W_{L}=(\mathbf{w}^{\top},-\mathbf{w}^{\top})$ with each entry sampled from $\mathcal{N}(0,2/N)$.

We then perform a simple warm-up by pulling each arm once.
At each round, we uniformly randomly choose one model $j_{t}$ from the ensemble and choose arm $X_{t}$ which maximizes the learned function $f(X;\theta_{t}^{j_{t}})$ and receive reward $Y_{t}$.
We use gradient descent on the $\lambda$-regularized loss function to obtain the parameter estimation:

$$ $\displaystyle\theta_{t}^{j}=\text{argmin}_{\theta\in\mathbb{R}^{d^{\prime}}}L_{\text{Neural}}(\theta;\{X_{l},Y_{l}+Z_{l}^{j}\}_{l=1}^{t}).$ (4.3) $$

###### Remark 4.3 .

The most relevant design is Neural Bandit with Perturbed Reward (NPR) proposed by (Jia et al., 2022), except that our Neural-ES keeps an ensemble of models and updates the perturbations incrementally instead of resampling the all perturbations at each round.
While this design could consume more memory, different models can be updated in parallel if we distribute the ensemble in $m$ different machines. Since the computational cost of updating one model is reduced compared to NPR, our algorithm can still accelerate the overall training process in this setting.

###### Remark 4.3 .

## 5 Theoretical Analysis

In this section, we provide theoretical analysis to the proposed algorithms.

### 5.1 Regret Bound of GLM-ES

To analyze GLM-ES, we first lay down the following assumptions commonly used in the literature or generalized linear bandits.
The assumption on the derivative of link function $\mu(\cdot)$ is standard in the GLM setting (Li et al., 2017; Kveton et al., 2020b), while the $M$-self-concordant assumption is recently proposed and applies to a broad class of functions (Liu et al., 2024).

###### Assumption 5.1 (Link function in GLM) .

The link function $\mu(\cdot)$ is *strictly increasing* and the derivative of $\mu(\cdot)$ is *bounded* as follows: $\dot{\mu}(s)>0,\forall s\in\mathbb{R}$ and $0<\dot{\mu}_{\text{min}}\leq\dot{\mu}(s)\leq\dot{\mu}_{\text{max}}$.

###### Assumption 5.2 ( $M$ -Self-concordant) .

The link function $\mu(\cdot)$ is $M$-self-concordant with a constant $M>0$ known to the agent: $|\ddot{\mu}(u)|\leq M\dot{\mu}(u),\forall u\in\mathbb{R}$.

###### Remark 5.3 .

We adopt the $M$-self-concordant assumption as a mild, notation-simplifying condition for exponential family models. In fact, for common reward distributions (Gaussian, exponential, Poisson, and Beta), it have been shown that [Assumption˜5.2](https://arxiv.org/html/2510.10730v1#S5.Thmtheorem2) automatically holds (Liu, 2023, Table 3.1). This assumption is used to get an upper bound on $H(\theta;\mathcal{D}_{t})$ in terms of $Q(\theta,\theta^{\prime};\mathcal{D}_{t})$ ([Lemmas˜A.1](https://arxiv.org/html/2510.10730v1#A1.Thmtheorem1) and [A.2](https://arxiv.org/html/2510.10730v1#A1.Thmtheorem2)).
This assumption has also been used in Janz et al. (2024b, Theorem 2).

###### Remark 5.4 (Removal of the regularity assumption) .

We use $\lambda$-regularized negative log-likelihood in ([4.1](https://arxiv.org/html/2510.10730v1#S4.E1)). This is used to remove the additional regularity assumptions in existing papers (Li et al., 2017; Kveton et al., 2020b): (i) there exists a constant $\sigma_{0}>0$ such that $\lambda_{\min}\big(\mathbb{E}[\frac{1}{K}\sum_{a\in[K]}X_{t,a}X_{t,a}^{\prime}]\big)\geq\sigma_{0}^{2}$ for all $t$, and (ii) arm context vectors $\{X_{t,a}|a\in[K]\}\subset\mathbb{R}^{d}$ are i.i.d. drawn. These two assumptions are usually used to guarantee $V_{t}$ is invertible. By deploying the $\lambda$-regularized negative log-likelihood in ([4.1](https://arxiv.org/html/2510.10730v1#S4.E1)), our analysis does not require these assumptions.

We present the frequentist regret bound of GLM-ES as follows. The complete proof and expression of the regret bound is presented in [Appendix˜A](https://arxiv.org/html/2510.10730v1#A1).

###### Theorem 5.5 (Regret Bound for GLM-ES) .

Fix $\delta\in(0,1]$. Assume $|\mathcal{X}|=K<\infty$ and run GLM-ES with regularization parameter
$\lambda=1\vee(2dM/S)\log\big(e\sqrt{1+TL/d}\vee 1/\delta\big)$, ensemble size $m=\Omega(K\text{log}T)$, perturbation distribution $\mathcal{P}_{R}=\mathcal{N}(0,\sigma_{R}^{2})$, where $\sigma_{R}=\Theta(d\,\text{log}T)$.
Then, with probability at least $1-4\delta$, the cumulative regret of GLM-ES is bounded by

$$ $\displaystyle R(T)=\widetilde{\mathcal{O}}\big(d^{\frac{3}{2}}\sqrt{T}+d^{\frac{9}{2}}\big).$ (5.1) $$

###### Remark 5.6 .

When we choose $T=\mathcal{O}(d^{6})$, the regret bound of GLM-ES becomes $\widetilde{\mathcal{O}}(d^{\frac{3}{2}}\sqrt{T})$, which matches the result of GLM-TSL, GLM-FPL (Kveton et al., 2020b), EVILL (Janz et al., 2024b) and Lin-ES (Lee and Oh, 2024), achieving a state-of-the-art theoretical guarantee for randomized exploration algorithms in the GLM setting. Compared with EVILL (Janz et al., 2024b), we also improve the number of rounds of warm-up from $d^{9}$ to $d^{9/2}$. We also develop novel analysis techniques to avoid the adapted perturbation requirement as in Liu (2023), where the distribution of perturbation changes in each round. This makes our algorithm more efficient and easier to implement.

###### Assumption 5.1 (Link function in GLM) .

###### Assumption 5.2 ( M M -Self-concordant) .

###### Remark 5.3 .

###### Remark 5.4 (Removal of the regularity assumption) .

###### Theorem 5.5 (Regret Bound for GLM-ES) .

###### Remark 5.6 .

### 5.2 Regret Bound of Neural-ES

For the regret analysis of Neural-ES, we first introduce the following notations.
A detailed introduction to neural tangent kernel is provided in (Jacot et al., 2018), here we only list the important notations for our theoretical results.
We use $\mathbf{H}$ to denote the neural tangent kernel (NTK) matrix defined on the context set $\mathcal{X}$ and $\mathbf{h}=(h(X_{1}),...,h(X_{K}))$. Then, we use notation $S_{\text{Neural}}$ as the upper bound of $\sqrt{2\mathbf{h}^{\top}\mathbf{H}^{-1}\mathbf{h}}$.
The effective dimension $\widetilde{d}$ of the neural NTK matrix is defined as

$$ $\widetilde{d}=\frac{\text{log}\,\text{det}(I+TH/\lambda)}{\text{log}(1+TK/\lambda)}.$ (5.2) $$

Now we present the frequentist regret bound of Neural-ES as follows. The complete proof and expression of the regret bound is presented in [Appendix˜C](https://arxiv.org/html/2510.10730v1#A3).

###### Theorem 5.7 (Regret Bound for Neural-ES) .

Fix $\delta\in(0,1]$.
Let $\widetilde{d}$ be the effective dimension of the neural tangent kernel matrix. Assume $|\mathcal{X}|=K<\infty$ and run Neural-ES with ensemble size $m=\Omega(K\text{log}T)$, regularization parameter $\lambda\geq\text{max}\{1,S_{\text{Neural}}^{-2}\}$, perturbation distribution $\mathcal{P}_{R}=\mathcal{N}(0,\sigma_{R}^{2})$ with $\sigma_{R}$ given by ([C.6](https://arxiv.org/html/2510.10730v1#A3.E6)).
Then, with probability at least $1-\delta$, the cumulative regret of Neural-ES is bounded by

$$ $\displaystyle R(T)=\widetilde{\mathcal{O}}\big(\widetilde{d}\sqrt{T}\big).$ (5.3) $$

###### Remark 5.8 .

The regret bound of Neural-ES matches the order of Neural-PHE (Jia et al., 2022), Neural-TS (Zhang et al., 2021) and Neural-UCB (Zhou et al., 2020), achieving the state-of-the-art theoretical guarantee in the neural bandit setting.
Compared to Neural-PHE, the computational cost per model is considerably reduced because we do not resample all perturbations in each round.
Compared to Neural-TS and Neural-UCB, we do not need to construct high-probability confidence sets for exploration, which is relatively difficult to implement and typically involves very high computational cost.

###### Theorem 5.7 (Regret Bound for Neural-ES) .

###### Remark 5.8 .

## 6 Extension to Anytime Algorithms

Ensemble sampling algorithms are inherently not anytime due to the fact that hyper-parameters such as ensemble size $m$ and reward perturbation distribution $\mathcal{P}_{R}$ explicitly depend on the number of total rounds $T$.
In the original version of ensemble sampling algorithms, these parameters need to be determined before starting the algorithm to obtain the desired regret bound.

In this section, we present how to use doubling trick (Besson and Kaufmann, 2018) to extend ensemble sampling into anytime algorithms while keeping the asymptotic behavior of regret bound.
Here we present the algorithm design and theoretical guarantee of anytime versions of ensemble sampling, the analysis of regret bound are presented in [Appendix˜E](https://arxiv.org/html/2510.10730v1#A5).

To apply doubling trick, we choose a sequence of time steps $\{T_{i}\}=\{T_{0},\,T_{1},\,T_{2},\,...\}$
and fully restart the original (non-anytime) algorithm when we reach $t=T_{i}+1$.
Therefore, after each reset, the algorithm runs from $T_{i}+1$ until $\text{min}\,\{T_{i+1},\,T\}$, and we can initialize the $T$-dependent parameters for $\tau_{i}=T_{i+1}-T_{i}$ rounds.
The number of rounds follows the sequence:

$$ $\displaystyle\{\tau_{i}\}=\{T_{0},\,T_{1}-T_{0},\,T_{2}-T_{1},\,...\}.$ $$

The doubling trick approach treats the original non-anytime algorithm as a black box, thus we can easily extend both GLM-ES and Neural-ES into anytime algorithms using the same method.

Our main theory of anytime versions of ensemble sampling is as follows.

###### Theorem 6.1 (Regret Bound of Doubling Trick) .

Set sequence $T_{i}=\lfloor T_{0}b^{i}\rfloor$, where $T_{0}\geq 100$ and $b=(3+\sqrt{5})/2\approx 2.6$.
Use $R(T,\delta)$ to denote the regret bound of non-anytime algorithms GLM-ES or Neural-ES that holds with probability at least $1-\delta$, and $R^{DT}(T,\delta)$ to denote its corresponding anytime version using doubling trick.
Then, by applying doubling trick for GLM-ES and Neural-ES, with probability at least $1-\delta$, the cumulative regret is bounded by

$$ $\displaystyle R^{DT}(T,\delta)\leq\,3.3\,R(T,\delta).$ $$

###### Remark 6.2 .

By directly applying doubling trick, we obtain the same asymptotic behavior of regret bound. By properly setting the sequence $\{T_{i}\}$, extending ensemble sampling to anytime algorithm comes with the cost of only a constant factor. This constant factor is determined by the parameters $T_{0}$ and $b$, the choice of these parameters can considerably affect the empirical performance.

###### Theorem 6.1 (Regret Bound of Doubling Trick) .

###### Remark 6.2 .

## 7 Experiments

We conduct experiments to demonstrate the practicality of ensemble sampling and its anytime variants in bandit settings.
We use linear bandit environment to test Lin-ES, logistic bandit to test GLM-ES, then distance bandit and quadratic form bandit to test Neural-ES.
Our result shows that ensemble sampling can give competitive cumulative regret with reduced computational cost.

Figure: (a) Linear Bandit.
Refer to caption: x1.png

### 7.1 Environment Setup

#### Linear Bandit

We assess the empirical performance of Lin-ES using linear bandit environment, where the reward is generated by $Y_{t}=X_{t}^{\top}\theta^{*}+\eta_{t}$.
Specifically, we set the number of arms $K=50$, dimension of feature vector $d=20$ and total steps $T=10^{4}$.
The noise of reward are generated from Gaussian distribution $\eta_{t}\sim\mathcal{N}(0,\sigma^{2})$ with $\sigma=0.5$.
In the Lin-ES algorithm, we set ensemble size $m=25$, regularization $\lambda=1.0$, and perturbation distribution $\mathcal{N}(0,\sigma_{R}^{2})$ with $\sigma_{R}=0.1$. There is no warm-up procedure in Lin-ES.

#### Generalized Linear Bandit

We assess the empirical performance of GLM-ES using logistic bandit environment, where the link function is given by $Y_{t}=1/\big(1+\text{exp}(-X_{t}^{\top}\theta^{*})\big)+\eta_{t}$.
We set the number of arms $K=50$, dimension of feature vector $d=20$, total steps $T=10^{4}$. The noise of reward are generated from Gaussian distribution $\eta_{t}\sim\mathcal{N}(0,\sigma^{2})$ with $\sigma=0.5$.

#### Neural Bandit

We test Neural-ES on two nonlinear reward models: (1) distance bandit: $h_{1}(X)=-||X-\theta^{*}||_{2}$; and (2) quadratic bandit: $h_{2}(X)=10^{-2}(X^{\top}AA^{\top}X)$,
where $A$ is a $d\times d$ matrix with each entry randomly sampled from $\mathcal{N}(0,1)$. In the experiments, we set number of arms $K=50$, dimension of feature vector $d=20$ and total steps $T=10^{4}$. The noise of reward are generated from Gaussian distribution $\eta_{t}\sim\mathcal{N}(0,\sigma^{2})$ with $\sigma=0.5$.

### 7.2 Implementations of Algorithms

#### GLM-ES

We implement GLM-ES assuming that the link function $\mu(\cdot)$ is known to the agent. The parameter $\theta$ is learned through gradient descent of the $\lambda$-regularized negative likelihood.
Specifically, we use 100 iterations of gradient descent with step size 0.01.
In the non-doubling-trick experiment, we set ensemble size $m=10$, perturbation distribution $\mathcal{N}(0,\sigma_{R}^{2})$ with $\sigma_{R}=0.1$, warm-up steps $\tau=500$ and regularization $\lambda=1.0$.
In the experiment with doubling trick, for number of rounds $\tau_{i}$, we set ensemble size $m=2\times\text{log}\tau_{i}$, perturbation distribution $\mathcal{N}(0,\sigma_{R}^{2})$ with $\sigma_{R}=0.02\times\text{log}\tau_{i}$, warm-up steps $\tau=500$ and regularization $\lambda=1.0$.

#### Neural-ES

We implement the fully connected neural network $f(X;\theta)$ using $L=3$ layers, the width is set to $N=20$ for each layer and we use ReLU as the activation function. The network structure is the same for Neural-ES, Neural-TS and Neural-UCB.
We optimize the loss function using gradient descent with 100 steps and learning rate 0.01.
Similar to GLM-ES, in the non-doubling-trick experiment, we set ensemble size $m=10$, perturbation distribution $\mathcal{N}(0,\sigma_{R}^{2})$ with $\sigma_{R}=0.1$, warm-up steps $\tau=50$ and regularization $\lambda=1.0$.
In the experiment with doubling trick, for number of rounds $\tau_{i}$, we set ensemble size $m=2\times\text{log}\tau_{i}$, perturbation distribution $\mathcal{N}(0,\sigma_{R}^{2})$ with $\sigma_{R}=0.02\times\text{log}\tau_{i}$, warm-up steps $\tau=50$ and regularization $\lambda=1.0$.

### 7.3 Results and Discussions

The empirical results are plotted in [Figure˜1](https://arxiv.org/html/2510.10730v1#S7.F1),
The cumulative regret of ensemble sampling are plotted in gray dashed lines, the results of ensemble sampling with doubling trick are also plotted in dashed lines. Specifically, “DT100” and “DT300” indicate that we choose $T_{0}=100$ and $T_{0}=300$ in doubling trick, respectively.
We set $b=(3+\sqrt{5})/2\approx 2.6$ for all doubling trick simulations.
All numerical results are averaged over 10 problem instances.

According to simulation results, the cumulative regret of ensemble sampling is competitive compared to baseline algorithms in both linear and nonlinear bandit settings, the design of keeping previous perturbations also considerably reduces per-model computational cost at large time step $t$.
Additionally, the doubling trick variants of ensemble sampling demonstrates its practicality by giving competitive cumulative regret while removing the requirement of total rounds $T$ prior to running the algorithm.
Overall, our experiment result shows that ensemble sampling is practical in both linear and nonlinear bandit settings, its cumulative regret is similar to or outperforms baseline models in different bandit environments.

## 8 Conclusion

In this work, we studied ensemble sampling in nonlinear contextual bandit settings. We proposed a general framework of algorithm design for ensemble sampling in bandit problems, then discussed two realizations GLM-ES and Neural-ES for generalized linear bandit and neural bandit, respectively. We proved high-probability regret bound $\widetilde{\mathcal{O}}(d^{3/2}\sqrt{T}+d^{9/2})$ for GLM-ES and $\widetilde{\mathcal{O}}(\widetilde{d}\sqrt{T})$ for Neural-ES, both matching the state-of-the-art result of randomized exploration algorithms in bandit problems. We used synthetic bandit environments to evaluate the performance of the proposed algorithms in terms of cumulative regret and computational cost. The empirical results demonstrate that ensemble sampling and its anytime variants can achieve competitive cumulative regret with considerably reduced computational cost. Our work establishes ensemble sampling as a provable and practical algorithm framework in bandit problems.

## Appendix A Proof of Regret Bound of GLM-ES

### A.1 Preliminary Analysis

In this section, we present basic technical lemmas directly from the definition and assumptions of the GLM setting.
The technical lemmas and notations introduced in this section are fundamental and will be extensively utilized in the following analysis.

In the GLM setting with exponential family distribution assumption, given feature vector $X\in\mathbb{R}^{d}$, the conditional distribution of reward $Y$ is given by

$$ $\displaystyle p(Y|X)=b_{0}(Y)\,\text{exp}\big[Y\cdot X^{\top}\theta-b(X^{\top}\theta)\big],$ $$

where $\theta\in\mathbb{R}^{d}$ is a fixed parameter for a given model.
We define the link function $\mu(\cdot)$ as

$$ $\displaystyle\mu(\cdot)=\dot{b}(\cdot),$ $$

the expected value of $Y$ is given by $\mu(X^{\top}\theta)$.
We make additional assumptions that the link function $\mu(\cdot)$ is *strictly increasing* and the derivative of $\mu$ is *bounded* as follows:

$$ $\displaystyle\dot{\mu}(s)>0,\quad\forall s\in\mathbb{R};\quad\quad 0<\dot{\mu}_{\text{min}}\leq\dot{\mu}(s)\leq\dot{\mu}_{\text{max}}.$ $$

Using the mean value theorem, for each pair $s_{1}<s_{2}$, we have

$$ $\displaystyle\mu(s_{2})-\mu(s_{1})=\dot{\mu}(s_{0})(s_{2}-s_{1}),\quad s_{0}\in(s_{1},s_{2}).$ $$

Therefore, we have that

$$ $\displaystyle\dot{\mu}_{\text{min}}(s_{2}-s_{1})\leq\mu(s_{2})-\mu(s_{1})\leq\dot{\mu}_{\text{max}}(s_{2}-s_{1}).$ $$

We add regularization to the algorithm design for the analysis of the warm-up procedure.
Given input data set $\mathcal{D}_{t}=\{(X_{l},Y_{l})\}_{l=1}^{t}$, we define the following $\lambda$-regularized negative log-likelihood:

$$ $\displaystyle L_{\text{GLM}}(\theta;\mathcal{D}_{t})=\frac{\lambda}{2}\|\theta\|^{2}-\sum_{l=1}^{t}\big(Y_{l}\cdot X_{l}^{\top}\theta-b(X_{l}^{\top}\theta)\big).$ (A.1) $$

Then, for time step $t$, we can define the (regularized) MLE as follows:

$$ $\displaystyle\bar{\theta}_{t}=\mathop{\mathrm{argmin}}_{\theta\in\mathbb{R}^{d}}\,L_{\text{GLM}}(\theta;\mathcal{D}_{t}).$ (A.2) $$

Based on ([A.1](https://arxiv.org/html/2510.10730v1#A1.E1)), we can compute the gradient

$$ $\displaystyle\nabla_{\theta}L_{\text{GLM}}(\theta;\mathcal{D}_{t})=\sum_{l=1}^{t}\mu(X_{l}^{\top}\theta)X_{l}+\lambda\theta-\sum_{l=1}^{t}X_{l}Y_{l}=f_{t}(\theta)-\sum_{l=1}^{t}X_{l}Y_{l},$ $$

where we define $f_{t}(\theta)$ as

$$ $\displaystyle f_{t}(\theta):=\sum_{l=1}^{t}\mu(X_{l}^{\top}\theta)X_{l}+\lambda\theta.$ (A.3) $$

Note that $\bar{\theta}_{t}=\mathop{\mathrm{argmin}}_{\theta\in\mathbb{R}^{d}}L_{\text{GLM}}(\theta;\mathcal{D}_{t})$, thus $\nabla_{\theta}L_{\text{GLM}}(\bar{\theta}_{t};\mathcal{D}_{t})=0$, we have

$$ $\displaystyle f_{t}(\bar{\theta}_{t})=\sum_{l=1}^{t}X_{l}Y_{l}.$ $$

We further define the Hessian matrix as follows

$$ $\displaystyle H(\theta;\mathcal{D}_{t})=\nabla_{\theta}^{2}L_{\text{GLM}}(\theta;\mathcal{D}_{t})=\sum_{l=1}^{t}\dot{\mu}(X_{l}^{\top}\theta)X_{l}X_{l}^{\top}+\lambda I.$ (A.4) $$

For simplicity of notation, we define the Hessian matrix at true parameter $\theta^{*}$ and MLE $\bar{\theta}_{t}$ as

$$ $\displaystyle H_{t}=H(\theta^{*};\mathcal{D}_{t}),\quad\bar{H}_{t}=H(\bar{\theta}_{t};\mathcal{D}_{t}).$ $$

Next, we introduce a “secant approximation" of Hessian matrix $H(\theta;\mathcal{D}_{t})$. We define the secant function as follows:

$$ $\displaystyle\alpha(u,u^{\prime})=\begin{cases}\dot{\mu}(u)\qquad\qquad\text{ if }u=u^{\prime},\\ \frac{\mu(u)-\mu(u^{\prime})}{u-u^{\prime}}\qquad\text{ otherwise. }\end{cases}$ $$

Note that $\lim_{u\rightarrow u^{\prime}}\alpha(u,u^{\prime})=\dot{\mu}(u)$. Then we give the following approximation of $H(\theta;\mathcal{D}_{t})$,

$$ $\displaystyle Q(\theta,\theta^{\prime};\mathcal{D}_{t})=\sum_{l=1}^{t}\alpha\big(X_{l}^{\top}\theta,X_{l}^{\top}\theta^{\prime}\big)X_{l}X_{l}^{\top}+\lambda I.$ $$

Note that $Q(\theta,\theta^{\prime};\mathcal{D}_{t})\rightarrow H(\theta;\mathcal{D}_{t})$ as $\theta\rightarrow\theta^{\prime}$.

Then, we can obtain the following technical lemma that provides upper and lower bounds for the secant function $\alpha(u,u^{\prime})$.

###### Lemma A.1 (Corollary 2 in Sun and Tran-Dinh ( 2019 ) ) .

Given that $\mu(\cdot)$ is $M$-self-concordant, for $u,u^{\prime}\in\mathbb{R}$, we have

$$ $\displaystyle\dot{\mu}(u)h_{s}(-M|u-u^{\prime}|)\leq\alpha(u,u^{\prime})\leq\dot{\mu}(u)h_{s}(M|u-u^{\prime}|),$ (A.5) $$

where we define

$$ $\displaystyle h_{s}(x)=\begin{cases}\frac{e^{x}-1}{x}\qquad\text{ if }x\neq 0,\\ 1\qquad\qquad x=0.\end{cases}$ $$

Based on [Lemma˜A.1](https://arxiv.org/html/2510.10730v1#A1.Thmtheorem1), we can obtain the following upper bound on $H(\theta;\mathcal{D}_{t})$ in terms of $Q(\theta,\theta^{\prime};\mathcal{D}_{t})$:

###### Lemma A.2 (Lemma 3.9 in Liu ( 2023 ) ) .

For any $\theta,\theta^{\prime}\in\mathbb{R}^{d}$, we have

$$ $\displaystyle H(\theta;\mathcal{D}_{t})\preceq(1+MD(\theta-\theta^{\prime}))Q(\theta,\theta^{\prime};\mathcal{D}_{t})=(1+MD(\theta-\theta^{\prime}))Q(\theta^{\prime},\theta;\mathcal{D}_{t}),$ (A.6) $$

where $D(v)$ is defined as $D(v)=\max_{X\in\mathcal{X}}|X^{\top}v|$ for input vector $v\in\mathbb{R}^{d}$.

From the definition of $D(v)$, we note the following inequality:

$$ $\displaystyle D(v)=\max_{X\in\mathcal{X}}|X^{\top}v|\leq\max_{X\in\mathcal{X}}||X||_{2}||v||_{2}\leq||v||_{2},$ $$

where we used the assumption $||X||_{2}\leq 1$.
This inequality is very useful in the following analysis.
By definition, we can directly obtain the following relation, which is critical in the later analysis:

$$ $\displaystyle f_{t}(\theta)-f_{t}(\theta^{\prime})=Q\big(\theta,\theta^{\prime};\mathcal{D}_{t}\big)(\theta-\theta^{\prime})=Q\big(\theta^{\prime},\theta;\mathcal{D}_{t}\big)(\theta-\theta^{\prime}).$ (A.7) $$

According to this relation, finding upper bound of $||\theta-\theta^{\prime}||$ can be decomposed to bounding $||f_{t}(\theta)-f_{t}(\theta^{\prime})||$ and $Q\big(\theta,\theta^{\prime};\mathcal{D}_{t}\big)$, which provides convenience in the following analysis.

We also define an auxiliary matrix $G_{t}$ as follows:

$$ $\displaystyle G_{t}=\sum_{l=1}^{t}X_{l}X_{l}^{\top}+\frac{\lambda}{\dot{\mu}_{\text{min}}}I.$ $$

Since we assumed that $\dot{\mu}_{\text{min}}\leq\dot{\mu}(\cdot)\leq\dot{\mu}_{\text{max}}$, we have

$$ $\displaystyle\dot{\mu}_{\text{min}}G_{t}\preceq H(\theta;\mathcal{D}_{t})\preceq\dot{\mu}_{\text{max}}G_{t},\quad\forall\theta\in\mathbb{R}^{d}.$ (A.8) $$

###### Lemma A.1 (Corollary 2 in Sun and Tran-Dinh ( 2019 ) ) .

###### Lemma A.2 (Lemma 3.9 in Liu ( 2023 ) ) .

### A.2 Technical Lemmas

In this section, we list the main technical lemmas required in the analysis of regret bound, these technical lemmas are proved in [Appendix˜B](https://arxiv.org/html/2510.10730v1#A2).
The main idea of analyzing GLM is that we use the lower and upper bound of $\dot{\mu}(\cdot)$ to find similarities between GLM and linear bandit.
Despite the similarities of linear bandit and generalized linear bandit settings, the GLM setting is considerably more challenging to analyze due to the fact that we do not have closed form solution for parameter estimate $\bar{\theta}_{t}$ and $\theta_{t}^{j}$.
In our analysis, we introduce the $M$-concordant assumption with novel analysis tools to overcome these difficulties.

We list the concentration results of the estimated parameters $\theta_{t}^{j}$ as follows.

###### Lemma A.3 (Concentration of MLE) .

Fix $\delta\in(0,1]$. Define the following parameters:

$$ $\displaystyle\gamma_{t}(\delta,\lambda)$ $\displaystyle=\sqrt{\lambda}\bigg(\frac{1}{2M}+S\bigg)+\frac{2M}{\sqrt{\lambda}}\bigg(d+\frac{d}{2}\,\text{log}\bigg(1+\frac{t\dot{\mu}_{\text{max}}}{d\lambda}\bigg)+\text{log}\frac{1}{\delta}\bigg),$ $\displaystyle\beta_{t}(\delta,\lambda)$ $\displaystyle=M\frac{\gamma_{t}(\delta,\lambda)^{2}}{\lambda}+\sqrt{\frac{\gamma_{t}(\delta,\lambda)^{2}}{\lambda}}.$ $$

For $t\in\mathbb{N}$, define a sequence of events

$$ $\displaystyle\bar{\mathcal{E}}_{t}:=\big\{\|\bar{\theta}_{t}-\theta^{*}\|_{H_{t}}\leq(1+M\beta_{T}(\delta,\lambda))\gamma_{T}(\delta,\lambda)\big\},$ $$

and their intersection $\bar{\mathcal{E}}=\cap_{t=1}^{T}\bar{\mathcal{E}}_{t}$. Then, we have $\mathbb{P}(\bar{\mathcal{E}})\geq 1-\delta$.

###### Lemma A.4 (Concentration of Perturbation) .

Fix $\delta\in(0,1]$ and $t\in[T]$. Define the following parameter:

$$ $\displaystyle\widetilde{\gamma}_{t}(\delta,\lambda)=\sqrt{d\log\bigg(1+\frac{t\dot{\mu}_{\text{min}}}{d\lambda}\bigg)+2\log\frac{T}{\delta}}.$ $$

For round $t$, define the following event

$$ $\displaystyle\widetilde{\mathcal{E}}_{1,t}:=\big\{\big\|\theta_{t}^{j_{t}}-\bar{\theta}_{t}\big\|_{H_{t}}\leq\dot{\mu}_{\text{max}}^{1/2}\,\dot{\mu}_{\text{min}}^{-1}\,\sigma_{R}\,\widetilde{\gamma}_{T}(\delta,\lambda)\big\}.$ $$

Then, $\widetilde{\mathcal{E}}_{1,t}$ holds with probability at least $1-\delta/T$.

Combining the concentration results [Lemma˜A.3](https://arxiv.org/html/2510.10730v1#A1.Thmtheorem3) and [Lemma˜A.4](https://arxiv.org/html/2510.10730v1#A1.Thmtheorem4), we have the following result of the concentration of $\theta_{t}^{j_{t}}$.

###### Lemma A.5 (Concentration of Estimation $\theta_{t}^{j_{t}}$ ) .

Define a sequence of events as

$$ $\displaystyle\mathcal{E}_{1,t}:=\big\{\big\|\theta_{t}^{j_{t}}-\theta^{*}\big\|_{H_{t}}\leq\gamma\big\},\quad\text{where}\,\,\gamma=(1+M\beta_{T})\gamma_{T}(\delta,\lambda)+\dot{\mu}_{\text{max}}^{1/2}\,\dot{\mu}_{\text{min}}^{-1}\,\sigma_{R}\,\widetilde{\gamma}_{T}(\delta,\lambda),$ $$

and their intersections $\mathcal{E}_{1}=\cap_{t=1}^{T}\mathcal{E}_{1,t}$. Then, $\mathcal{E}_{1}$ holds with probability at least $1-2\delta$.

Next, the following lemma demonstrates that optimism holds with constant probability in GLM-ES.

###### Lemma A.6 (Optimism) .

Let constant $p_{N}=1-\Phi(1)\approx 0.16$, and a sequence of events defined as

$$ $\displaystyle\mathcal{E}_{2,t}=\Big\{\mathbb{P}\big(X^{*\top}\theta^{*}\leq X_{t}^{\top}\theta_{t}\text{ and }\widetilde{\mathcal{E}}_{1,t}\,|\,\mathcal{F}_{t-1}\big)\geq p_{N}/4\Big\},$ $$

and their intersection $\mathcal{E}_{2}=\cap_{t=1}^{T}\mathcal{E}_{2,t}$.
Then, $\mathcal{E}_{2}$ holds with probability at least $1-\delta$.

We need the following lemma to introduce the notations of $\theta_{t}^{-}$ and $X_{t}^{-}$, which will be used in [Section˜A.3](https://arxiv.org/html/2510.10730v1#A1.SS3).

###### Lemma A.7 .

Assume the conditions of [Theorem˜5.5](https://arxiv.org/html/2510.10730v1#S5.Thmtheorem5). Let $J(\theta)=\text{sup}_{x\in\mathcal{X}}\,\mu(x^{\top}\theta)$, where $\theta\in\mathbb{R}^{d}$. Let $\Theta_{t}=\{\theta\in\mathbb{R}^{d}\,\,|\,\,||\theta-\theta^{*}||_{\bar{H}_{t-1}}\leq\gamma\}$. Define $\theta_{t}^{-}=\text{argmin}_{\theta\in\Theta_{t}}\,J(\theta)$ and $X_{t}^{-}=\text{argmax}_{x\in\mathcal{X}}\,\mu(x^{\top}\theta_{t}^{-})$. For any $\theta\in\mathbb{R}^{d}$ and an event $\mathcal{E}^{\prime}$, we introduce the following notation:

$$ $\displaystyle g_{t}(\theta,\mathcal{E}^{\prime})=(J(\theta)-J(\theta_{t}^{-}))\operatorname*{\mathds{1}}\{\mathcal{E}^{\prime}\}.$ $$

Then, $g_{t}(\theta^{*},\mathcal{E}^{\prime})\geq 0$ holds for any event $\mathcal{E}^{\prime}\in\mathcal{F}$, and $g_{t}(\theta_{t},\mathcal{E}^{\prime\prime})\geq 0$ holds almost surely for any event such that $\mathcal{E}^{\prime\prime}\subset\mathcal{E}_{1,t}$.

Finally, we need the following lemma to calculate the summation in [Section˜A.3](https://arxiv.org/html/2510.10730v1#A1.SS3).

###### Lemma A.8 (Lemma 2 in Li et al. ( 2017 ) ) .

Let $\{X_{t}\}_{t=1}^{\infty}$ be a sequence in $\mathbb{R}^{d}$ satisfying $||X_{t}||\leq 1$. Define $X_{0}=\mathbf{0}$ and $G_{t-1}=\lambda\,I+\sum_{i=0}^{t-1}X_{i}X_{i}^{\top}$. Suppose there is an integer $n$ such that $\lambda_{\text{min}}(G_{n})\geq 1$, then for all $T>n$,

$$ $\displaystyle\sum_{t=n+1}^{T}||X_{t}||_{G_{t-1}^{-1}}\leq\sqrt{2(T-n)d\,\,\text{log}\bigg(1+\frac{T}{d\lambda}\bigg)}.$ $$

###### Lemma A.3 (Concentration of MLE) .

###### Lemma A.4 (Concentration of Perturbation) .

###### Lemma A.5 (Concentration of Estimation θ t j t \theta_{t}^{j_{t}} ) .

###### Lemma A.6 (Optimism) .

###### Lemma A.7 .

###### Lemma A.8 (Lemma 2 in Li et al. ( 2017 ) ) .

### A.3 Regret Analysis

With the technical lemmas listed above, we prove [Theorem˜5.5](https://arxiv.org/html/2510.10730v1#S5.Thmtheorem5) as follows.

###### Proof of Theorem 5.5 .

Recall that the cumulative regret is defined as

$$ $\displaystyle R(T)=\sum_{t=1}^{T}\Big(\mu\big(x^{*\top}\theta^{*}\big)-\mu\big(X_{t}^{\top}\theta^{*}\big)\Big).$ $$

In the warm-up procedure, the regret for each round is bounded as

$$ $\displaystyle\Delta_{\text{max}}=\text{sup}_{x\in\mathcal{X}}\,\,\mu\big(x^{\top}\theta^{*}\big)-\text{inf}_{x\in\mathcal{X}}\,\,\mu\big(x^{\top}\theta^{*}\big).$ $$

Therefore, we have

$$ $\displaystyle R(T)\leq\tau\Delta_{\text{{max}}}+\sum_{t=\tau+1}^{T}\Big(\big(\mu(x^{*\top}\theta^{*}\big)-\mu\big(X_{t}^{\top}\theta^{*}\big)\Big).$ $$

We only consider $t\in[\tau+1,T]$ in the following discussions.

We first bound the instantaneous regret at time $t$.
Define event $\mathcal{E}$ as $\mathcal{E}=\cap_{t=1}^{T}\big(\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t}\big)$, we discuss the per-round regret under event $\mathcal{E}$.

$$ $\displaystyle\Big(\mu(x^{*\top}\theta^{*})-\mu(X_{t}^{\top}\theta^{*})\Big)\operatorname*{\mathds{1}}\{\mathcal{E}\}=\underbrace{\Big(\mu(x^{*\top}\theta^{*})-\mu(X_{t}^{\top}\theta_{t})\Big)\operatorname*{\mathds{1}}\{\mathcal{E}\}}_{I_{1}}+\underbrace{\Big(\mu(X_{t}^{\top}\theta_{t})-\mu(X_{t}^{\top}\theta^{*})\Big)\operatorname*{\mathds{1}}\{\mathcal{E}\}}_{I_{2}}.$ $$

From the expression, $I_{1}$ is related to optimism, $I_{2}$ is related to concentration of $\theta_{t}$.
$I_{2}$ is directly bounded under $\mathcal{E}$:

$$ $\displaystyle I_{2}=$ $\displaystyle\,\Big(\mu(X_{t}^{\top}\theta_{t})-\mu(X_{t}^{\top}\theta^{*})\Big)\operatorname*{\mathds{1}}\{\mathcal{E}\}$ $\displaystyle\leq$ $\displaystyle\,\dot{\mu}_{\text{max}}\big|X_{t}^{\top}\theta_{t}-X_{t}^{\top}\theta^{*}\big|\operatorname*{\mathds{1}}\{\mathcal{E}\}$ $\displaystyle\leq$ $\displaystyle\,\dot{\mu}_{\text{max}}||X_{t}||_{H_{t}^{-1}}||\theta_{t}-\theta^{*}||_{H_{t}}\operatorname*{\mathds{1}}\{\mathcal{E}\}$ $\displaystyle\leq$ $\displaystyle\,\dot{\mu}_{\text{max}}\gamma||X_{t}||_{H_{t}^{-1}}.$ $$

Now we consider $I_{1}$. Using the definitions in [Lemma˜A.7](https://arxiv.org/html/2510.10730v1#A1.Thmtheorem7), we have

$$ $\displaystyle I_{1}=$ $\displaystyle\Big(\mu(x^{*\top}\theta^{*})-\mu(X_{t}^{\top}\theta_{t})\Big)\operatorname*{\mathds{1}}\{\mathcal{E}\}$ $\displaystyle=$ $\displaystyle\Big(\mu(x^{*\top}\theta^{*})-\mu(X_{t}^{-\top}\theta_{t}^{-})\Big)\operatorname*{\mathds{1}}\{\mathcal{E}\}+\Big(\mu(X_{t}^{-\top}\theta_{t}^{-})-\mu(X_{t}^{\top}\theta_{t})\Big)\operatorname*{\mathds{1}}\{\mathcal{E}\}$ $\displaystyle=$ $\displaystyle\big(J(\theta^{*})-J(\theta_{t}^{-})\big)\operatorname*{\mathds{1}}\{\mathcal{E}\}+\big(J(\theta_{t}^{-})-J(\theta_{t})\big)\operatorname*{\mathds{1}}\{\mathcal{E}\}$ $\displaystyle=$ $\displaystyle\,g_{t}(\theta^{*},\mathcal{E})-g_{t}(\theta_{t},\mathcal{E})$ $\displaystyle\leq$ $\displaystyle\,g_{t}(\theta^{*},\mathcal{E})\leq\,g_{t}(\theta^{*},\mathcal{E}_{2,t}).$ $$

We use Markov’s inequality to bound $g_{t}(\theta^{*},\mathcal{E}_{2,t})$:

$$ $\displaystyle g_{t}(\theta^{*},\mathcal{E}_{2,t})\mathbb{P}\Big(g_{t}(\theta_{t},\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t})\geq g_{t}(\theta^{*},\mathcal{E}_{2,t})\,\,|\,\,\mathcal{F}_{t-1}\Big)\leq\mathbb{E}\big[g_{t}(\theta_{t},\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t})\,\,|\,\,\mathcal{F}_{t-1}\big].$ $$

Now we need the lower bound for $\mathbb{P}\big(g_{t}(\theta_{t},\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t})\geq g_{t}(\theta^{*},\mathcal{E}_{2,t})\,\,|\,\,\mathcal{F}_{t-1}\big)$ (we relate this to the probability of optimism) and the upper bound for $g_{t}(\theta_{t},\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t})$.

Using the assumption that $\mu(x)$ is strictly increasing, under the event $\big(x^{*\top}\theta^{*}\leq X_{t}^{\top}\theta_{t}\big)\wedge\mathcal{E}_{1,t}\wedge\mathcal{E}_{2,t}$, we have the following results:

$$ $\displaystyle x^{*\top}\theta^{*}\leq\,X_{t}^{\top}\theta_{t}\,\Leftrightarrow$ $\displaystyle\mu(x^{*\top}\theta^{*})-\mu(X_{t}^{-\top}\theta_{t}^{-})\leq\mu(X_{t}^{\top}\theta_{t})-\mu(X_{t}^{-\top}\theta_{t}^{-})$ $\displaystyle\Leftrightarrow$ $\displaystyle\,\big(\mu(x^{*\top}\theta^{*})-\mu(X_{t}^{-\top}\theta_{t}^{-})\big)\operatorname*{\mathds{1}}\{\mathcal{E}_{2,t}\}\leq\big(\mu(X_{t}^{\top}\theta_{t})-\mu(X_{t}^{-\top}\theta_{t}^{-})\big)\operatorname*{\mathds{1}}\{\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t}\}$ $\displaystyle\Leftrightarrow$ $\displaystyle\,g_{t}(\theta^{*},\mathcal{E}_{2,t})\leq g_{t}(\theta_{t},\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t}).$ $$

Therefore, we have

$$ $\displaystyle\mathbb{P}\Big(g_{t}\Big(\theta_{t},\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t}\Big)\geq g_{t}(\theta^{*},\mathcal{E}_{2,t})\,\,|\,\,\mathcal{F}_{t-1}\Big)\geq p_{N}/4.$ $$

Next, we consider the upper bound of $g_{t}(\theta_{t},\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t})$.
Using the definition, we have

$$ $\displaystyle g_{t}(\theta_{t},\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t})=$ $\displaystyle\,\big(\mu(X_{t}^{\top}\theta_{t})-\mu(X_{t}^{-\top}\theta_{t}^{-})\big)\operatorname*{\mathds{1}}\{\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t}\}$ $\displaystyle\leq$ $\displaystyle\,\big(\mu(X_{t}^{\top}\theta_{t})-\mu(X_{t}^{\top}\theta_{t}^{-})\big)\operatorname*{\mathds{1}}\{\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t}\}$ $\displaystyle\leq$ $\displaystyle\,\dot{\mu}_{\text{max}}\big|X_{t}^{\top}\theta_{t}-X_{t}^{\top}\theta_{t}^{-}\big|\,\operatorname*{\mathds{1}}\{\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t}\}$ $\displaystyle\leq$ $\displaystyle\,\dot{\mu}_{\text{max}}||X_{t}||_{H_{t-1}^{-1}}||\theta_{t}-\theta_{t}^{-}||_{H_{t-1}}\operatorname*{\mathds{1}}\{\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t}\}$ $\displaystyle\leq$ $\displaystyle\,2\gamma\dot{\mu}_{\text{max}}||X_{t}||_{H_{t-1}^{-1}}.$ $$

Using the results above, the instantaneous regret at time $t\in[\tau+1,T]$ is bounded as:

$$ $\displaystyle\Big(\mu(x^{*\top}\theta^{*})-\mu(X_{t}^{\top}\theta^{*})\Big)\operatorname*{\mathds{1}}\{\mathcal{E}\}$ $\displaystyle\leq$ $\displaystyle\,\,\gamma\dot{\mu}_{\text{max}}||X_{t}||_{H_{t-1}^{-1}}+\frac{8\gamma\dot{\mu}_{\text{max}}}{p_{N}}\mathbb{E}\Big[||X_{t}||_{H_{t-1}^{-1}}\,\,|\,\,\mathcal{F}_{t-1}\Big]$ $\displaystyle=$ $\displaystyle\,\,\gamma\dot{\mu}_{\text{max}}\bigg(1+\frac{8}{p_{N}}\bigg)||X_{t}||_{H_{t-1}^{-1}}+\frac{8\gamma\dot{\mu}_{\text{max}}}{p_{N}}\Big(\mathbb{E}\Big[||X_{t}||_{H_{t-1}^{-1}}\,\,|\,\,\mathcal{F}_{t-1}\Big]-||X_{t}||_{H_{t-1}^{-1}}\Big).$ $$

The cumulative regret is bounded as:

$$ $\displaystyle R(T)\operatorname*{\mathds{1}}\{\mathcal{E}\}\leq$ $\displaystyle\tau\Delta_{\text{max}}+\gamma\dot{\mu}_{\text{max}}\bigg(1+\frac{8}{p_{N}}\bigg)\sum_{t=\tau+1}^{T}||X_{t}||_{H_{t-1}^{-1}}$ $\displaystyle\,\,+\frac{8\gamma\dot{\mu}_{\text{max}}}{p_{N}}\sum_{t=\tau+1}^{T}\Big(\mathbb{E}\Big[||X_{t}||_{H_{t-1}^{-1}}\,\,|\,\,\mathcal{F}_{t-1}\Big]-||X_{t}||_{H_{t-1}^{-1}}\Big).$ (A.9) $$

Next, we calculate the two summations in ([A.3](https://arxiv.org/html/2510.10730v1#A1.Ex49)).
From the fact that $\dot{\mu}_{\text{min}}G_{t}\preceq H(\theta;\mathcal{D}_{t})\preceq\dot{\mu}_{\text{max}}G_{t}$, for any $x\in\mathbb{R}^{d}$, we have

$$ $\displaystyle\frac{1}{\sqrt{\dot{\mu}_{\text{max}}}}||x||_{G_{t}^{-1}}\leq||x||_{H_{t}^{-1}}\leq\frac{1}{\sqrt{\dot{\mu}_{\text{min}}}}||x||_{G_{t}^{-1}}.$ $$

Therefore, the first summation in ([A.3](https://arxiv.org/html/2510.10730v1#A1.Ex49)) is bounded by

$$ $\displaystyle\sum_{t=\tau+1}^{T}||X_{t}||_{H_{t-1}^{-1}}\leq\frac{1}{\sqrt{\dot{\mu}_{\text{min}}}}\sum_{t=\tau+1}^{T}||X_{t}||_{G_{t-1}^{-1}}.$ $$

From the fact that $\bar{H}_{t}\succeq\lambda I$, we have $\lambda_{\text{min}}(\bar{H}_{t})\geq\lambda$.
The first summation in ([A.3](https://arxiv.org/html/2510.10730v1#A1.Ex49)) is bounded as follows by using [Lemma˜A.8](https://arxiv.org/html/2510.10730v1#A1.Thmtheorem8):

$$ $\displaystyle\sum_{t=\tau+1}^{T}||X_{t}||_{G_{t-1}^{-1}}\leq\sqrt{2(T-\tau)d\,\,\text{log}\bigg(1+\frac{T\dot{\mu}_{\text{min}}}{d\lambda}\bigg)}.$ $$

Now we consider the second summation in ([A.3](https://arxiv.org/html/2510.10730v1#A1.Ex49)). Note that

$$ $\displaystyle 0\leq||X_{t}||_{H_{t-1}^{-1}}\leq\sqrt{\lambda_{\text{max}}(H_{t-1}^{-1})}||X_{t}||_{2}\leq 1,$ $$

according to Azuma-Hoeffding inequality, we can bound the second summation in ([A.3](https://arxiv.org/html/2510.10730v1#A1.Ex49)) by

$$ $\displaystyle\sum_{t=\tau+1}^{T}\Big(\mathbb{E}\Big[||X_{t}||_{H_{t-1}^{-1}}\,\,|\,\,\mathcal{F}_{t-1}\Big]-||X_{t}||_{H_{t-1}^{-1}}\Big)\leq\sqrt{\frac{T-\tau}{2}\text{log}\frac{1}{\delta}},$ $$

with probability at least $1-\delta$. Combining these results, with probability at least $1-4\delta$, we have

$$ $\displaystyle R(T)\operatorname*{\mathds{1}}\{\mathcal{E}\}$ $\displaystyle\leq\gamma\frac{\dot{\mu}_{\text{max}}}{\sqrt{\dot{\mu}_{\text{min}}}}\bigg(1+\frac{8}{p_{N}}\bigg)\sqrt{2d(T-\tau)\,\,\text{log}\bigg(1+\frac{T\dot{\mu}_{\text{min}}}{d\lambda}\bigg)}+\frac{4\gamma\dot{\mu}_{\text{max}}}{p_{N}}\sqrt{2(T-\tau)\text{log}\frac{1}{\delta}}+\tau\Delta_{\text{max}},$ $$

Combining the fact that the warm up rounds $\tau=\widetilde{\mathcal{O}}(d^{9/2})$ and set regularization $\lambda=1\vee(2dM/S)\log\big(e\sqrt{1+TL/d}\vee 1/\delta\big)$, the final regret bound is

$$ $\displaystyle R(T)\leq\widetilde{\mathcal{O}}\big(d^{3/2}\sqrt{T}+d^{9/2}\big),$ $$

with probability at least $1-4\delta$.
This completes the proof.
∎

###### Proof of Theorem 5.5 .

## Appendix B Proof of Technical Lemmas in GLM-ES

### B.1 Proof of Lemma ˜ A.3 (Concentration of MLE)

In this section, we study the distance between the MLE $\bar{\theta}_{t}$ and the true parameter $\theta^{*}$.
Our main goal is to obtain a high probability upper bound of $\|\theta^{*}-\bar{\theta}_{t}\|_{H_{t}}$.
From the previous sections, the definitions of $H_{t}$ and $\bar{H}_{t}$ are as follows:

$$ $\displaystyle H_{t}$ $\displaystyle=H(\theta^{*};\mathcal{D}_{t})=\nabla_{\theta}^{2}L(\theta^{*};\mathcal{D}_{t})=\sum_{l=1}^{t}\dot{\mu}(X_{l}^{\top}\theta^{*})X_{l}X_{l}^{\top}+\lambda I,$ $\displaystyle\bar{H}_{t}$ $\displaystyle=H(\bar{\theta}_{t};\mathcal{D}_{t})=\nabla_{\theta}^{2}L(\bar{\theta}_{t};\mathcal{D}_{t})=\sum_{l=1}^{t}\dot{\mu}(X_{l}^{\top}\bar{\theta}_{t})X_{l}X_{l}^{\top}+\lambda I.$ $$

To achieve the upper bound of $\|\theta^{*}-\bar{\theta}_{t}\|_{H_{t}}$, we first focus on upper bounding $\|f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*})\|_{H_{t}^{-1}}$. Recall from definition, we have that

$$ $\displaystyle f_{t}(\bar{\theta}_{t})=\sum_{l=1}^{t}Y_{l}X_{l},\quad f_{t}(\theta^{*})=\sum_{l=1}^{t}\mu(X_{l}^{\top}\theta^{*})X_{l}+\lambda\theta^{*}.$ $$

By defining $\epsilon_{l}=Y_{l}-\mu(X_{l}^{\top}\theta^{*})$, $S_{t}=\sum_{l=1}^{t}\epsilon_{l}X_{l}$, we have

$$ $\displaystyle f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*})=\sum_{l=1}^{t}(Y_{l}-\mu(X_{l}^{\top}\theta^{*}))X_{l}-\lambda\theta^{*}=S_{t}-\lambda\theta^{*}.$ $$

Therefore, we have the following decomposition:

$$ $\displaystyle\|f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*})\|_{H_{t}^{-1}}\leq\|S_{t}\|_{H_{t}^{-1}}+\lambda\|\theta^{*}\|_{H_{t}^{-1}}\leq\|S_{t}\|_{H_{t}^{-1}}+\sqrt{\lambda}S,$ $$

where we used the fact that $\lambda I\preceq H_{t}$ and $\|\theta^{*}\|\leq S$.

Next, we need the upper bound for $\|S_{t}\|_{H_{t}^{-1}}$.
We need the following result from Janz et al. (2024b).

###### Lemma B.1 (Theorem 2 in Janz et al. ( 2024b ) ) .

Fix $\lambda,M>0$.
Let $(X_{t})_{t\in\mathbb{N^{+}}}$ be a $B_{2}^{d}$-valued random sequence, $(\nu_{t})_{t\in\mathbb{N}}$ be a non-negative valued random sequence.
Let $\mathbb{F}^{\prime}=(\mathbb{F}^{\prime}_{t})_{t\in\mathbb{N}}$ be filtration such that (i) $(X_{t})_{t\in\mathbb{N^{+}}}$ is $\mathbb{F}^{\prime}$-predictable and (ii) $(Y_{t})_{t\in\mathbb{N^{+}}}$ and $(\nu_{t})_{t\in\mathbb{N}}$ are $\mathbb{F}^{\prime}$-adapted.
Let $\epsilon_{t}=Y_{t}-\mathbb{E}[Y_{t}\,|\,\mathbb{F}^{\prime}_{t-1}]$ and assume that the following condition holds:

$$ $\displaystyle\mathbb{E}[\text{exp}(s\epsilon_{t})\,|\,\mathbb{F}^{\prime}_{t-1}]\leq\text{exp}(s^{2}\nu_{t-1}),\quad\forall|s|\leq 1/M\text{ and }t\in\mathbb{N}^{+}.$ (B.1) $$

Then, for $\tilde{H}_{t}=\sum_{l=1}^{t}\nu_{l-1}X_{l}X_{l}^{\intercal}+\lambda I$ and $S_{t}=\sum_{l=1}^{t}\epsilon_{l}X_{l}$ and any $\delta>0$,

$$ $\displaystyle\mathbb{P}\Big(\exists t\in\mathbb{N}^{+}:||S_{t}||_{\tilde{H}_{t}^{-1}}\geq\frac{\sqrt{\lambda}}{2M}+\frac{2M}{\sqrt{\lambda}}\text{log}\Big(\frac{\text{det}(\tilde{H}_{t})^{1/2}\lambda^{-d/2}}{\delta}\Big)+\frac{2M}{\sqrt{\lambda}}d\,\text{log}(2)\Big)\leq\delta.$ $$

According to previous discussions, we choose the sequences in the lemma as follows:

$$ $\displaystyle\nu_{t-1}\rightarrow\dot{\mu}(X_{t}^{\intercal}\theta^{*}),\quad\tilde{H}_{t}\rightarrow H_{t}.$ $$

To apply [Lemma˜B.1](https://arxiv.org/html/2510.10730v1#A2.Thmtheorem1), we need to prove that $\epsilon_{t}$ satisfies the sub-exponential condition Eq. ([B.1](https://arxiv.org/html/2510.10730v1#A2.E1)).
Note that now we have $\epsilon_{t}=Y_{t}-\mu(X_{t}^{\intercal}\theta^{*})$, we need to utilize the assumption that the reward $Y$ given feature vector $X$ has an exponential-family distribution to prove this property.

From definition, we can write (we use notation $u:=X^{\intercal}\theta^{*}$ for simplicity)

$$ $\displaystyle\mathbb{E}[\text{exp}(s\epsilon_{t})\,|\,\mathbb{F}^{\prime}_{t-1}]=\int_{y}\text{exp}(s(y-\mu(u))\,p(y\,|\,u)\,\text{d}y.$ $$

From previous sections,

$$ $\displaystyle p(y\,|\,u)=h(y)\,\text{exp}[y\cdot u-b(u)]\quad\rightarrow\quad\int_{y}h(y)\,\text{exp}(uy)\,\text{d}y=\text{exp}(b(u)).$ $$

Therefore, we have

$$ $\displaystyle\mathbb{E}[\text{exp}(s\epsilon_{t})\,|\,\mathbb{F}^{\prime}_{t-1}]=$ $\displaystyle\,\text{exp}(-s\mu(u)-b(u))\int_{y}h(y)\,\text{exp}((s+u)y)\,\text{d}y$ $\displaystyle=$ $\displaystyle\,\text{exp}(-s\mu(u)-b(u)+b(s+u)).$ $$

Next, observing the expressions of ([B.1](https://arxiv.org/html/2510.10730v1#A2.E1)), we need to prove that for $|s|\leq 1/M$, we have

$$ $\displaystyle-s\mu(u)-b(u)+b(s+u)\leq s^{2}\dot{\mu}(u)\quad\rightarrow\quad b(s+u)-b(u)\leq s\mu(u)+s^{2}\dot{\mu}(u).$ $$

By definition, we have $\mu(\cdot)=\dot{b}(\cdot)$, the expression above is equivalent to

$$ $\displaystyle b(s+u)-b(u)\leq s\dot{b}(u)+s^{2}\ddot{b}(u).$ $$

Using Taylor expansion, we can write

$$ $\displaystyle b(s+u)-b(u)=s\dot{b}(u)+\frac{s^{2}}{2}\ddot{b}(c),\quad c\in[u,s+u].$ $$

By self-concordance assumption, we can bound $\ddot{b}(c)$ as

$$ $\displaystyle\ddot{b}(c)\leq\ddot{b}(u)\,\text{exp}(M|c-u|)\leq\ddot{b}(u)\,\text{exp}(M|s|)\leq e\cdot\ddot{b}(u).$ $$

Therefore, we proved that $\ddot{b}(c)\leq 2\ddot{b}(u)$, the sub-exponential condition holds in this setting.

Applying [Lemma˜B.1](https://arxiv.org/html/2510.10730v1#A2.Thmtheorem1), we have that

$$ $\displaystyle||S_{t}||_{H_{t}^{-1}}\leq\frac{\sqrt{\lambda}}{2M}+\frac{2M}{\sqrt{\lambda}}\text{log}\Big(\frac{\text{det}(H_{t})^{1/2}\lambda^{-d/2}}{\delta}\Big)+\frac{2M}{\sqrt{\lambda}}d\,\text{log}(2),\quad\forall t\in[T]$ $$

holds with probability at least $1-\delta$.
From the definition of $H_{t}$, we have

$$ $\displaystyle\text{det}(H_{t})\leq\lambda^{d}(1+\frac{t\dot{\mu}_{\text{max}}}{\lambda d})^{d}.$ $$

Therefore, we can write the high probability upper bound as

$$ $\displaystyle||S_{t}||_{H_{t}^{-1}}\leq\frac{\sqrt{\lambda}}{2M}+\frac{2M}{\sqrt{\lambda}}\Big(d+\frac{d}{2}\text{log}\Big(1+\frac{t\dot{\mu}_{\text{max}}}{\lambda d}\Big)+\text{log}\frac{1}{\delta}\Big).$ $$

We can further write the upper bound of $\|f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*})\|_{H_{t}^{-1}}$ as follows:

$$ $\displaystyle\|f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*})\|_{H_{t}^{-1}}\leq\sqrt{\lambda}(\frac{1}{2M}+S)+\frac{2M}{\sqrt{\lambda}}(d+\frac{d}{2}\text{log}(1+\frac{t\dot{\mu}_{\text{max}}}{\lambda d})+\text{log}\frac{1}{\delta})=:\gamma_{t}(\delta,\lambda)$ (B.2) $$

holds for all $t\in[T]$ with probability at least $1-\delta$.

Now we are ready to bound $\|\theta^{*}-\bar{\theta}_{t}\|_{H_{t}}$.
Recall that we have the following relation:

$$ $\displaystyle f_{t}(\theta)-f_{t}(\theta^{\prime})=Q(\theta^{\prime},\theta;\mathcal{D}_{t})(\theta-\theta^{\prime}),\quad Q(\theta,\theta^{\prime};\mathcal{D}_{t}):=\sum_{l=1}^{t}\alpha\big(X_{l}^{\top}\theta,X_{l}^{\top}\theta^{\prime}\big)X_{l}X_{l}^{\top}+\lambda I.$ $$

We denote $Q_{t}=Q(\bar{\theta}_{t},\theta^{*};\mathcal{D}_{t})$, then $\bar{\theta}_{t}-\theta^{*}=Q_{t}^{-1}(f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*}))$.
We have the following bound:

$$ $\displaystyle\big\|\bar{\theta}_{t}-\theta^{*}\big\|^{2}$ $\displaystyle=\big\|Q_{t}^{-1}(f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*}))\big\|^{2}\leq\frac{1}{\lambda}\|f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*})\|_{Q_{t}^{-1}}^{2}$ $\displaystyle\leq\big(1+MD(\bar{\theta}_{t}-\theta^{*})\big)\frac{1}{\lambda}\big\|f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*})\big\|_{H_{t}^{-1}}^{2}$ $\displaystyle\leq\big(1+M\|\bar{\theta}_{t}-\theta^{*}\|\big)\frac{1}{\lambda}\gamma_{t}(\delta,\lambda)^{2}.$ $$

The first inequality holds due to the fact $\lambda I\preceq Q_{t}$.
The second inequality holds because $H(\theta^{*};\mathcal{D}_{t})\preceq(1+MD(\theta^{*}-\bar{\theta}_{t}))Q(\theta^{*},\bar{\theta}_{t};\mathcal{D}_{t})$ ([Lemma˜A.2](https://arxiv.org/html/2510.10730v1#A1.Thmtheorem2)).
The last inequality holds because $D(v)\leq\|v\|$ for $v\in\mathbb{R}^{d}$ and is under the assumption $\|f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*})\|_{H_{t}^{-1}}\leq\gamma_{t}(\delta,\lambda)$.
Note that for any $b,c\geq 0,x\in\mathbb{R}$, if $x^{2}\leq bx+c$, we have $x\leq b+\sqrt{c}$. Based on this result, we have

$$ $\displaystyle\|\bar{\theta}_{t}-\theta^{*}\|\leq M\frac{\gamma_{t}(\delta,\lambda)^{2}}{\lambda}+\sqrt{\frac{\gamma_{t}(\delta,\lambda)^{2}}{\lambda}}=:\beta_{t}(\delta,\lambda).$ (B.3) $$

Next, we can write

$$ $\displaystyle\|\bar{\theta}_{t}-\theta^{*}\|_{H_{t}}$ $\displaystyle=\big\|Q_{t}^{-1}(f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*}))\big\|_{H_{t}}$ $\displaystyle=\sqrt{(f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*}))^{\top}Q_{t}^{-1}H_{t}Q_{t}^{-1}(f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*}))}$ $\displaystyle\leq\big(1+MD(\bar{\theta}_{t}-\theta^{*})\big)\big\|f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*})\big\|_{H_{t}^{-1}}$ $\displaystyle\leq\big(1+M\|\bar{\theta}_{t}-\theta^{*}\|\big)\gamma_{t}(\delta,\lambda)$ $\displaystyle\leq(1+M\beta_{t}(\delta,\lambda))\gamma_{t}(\delta,\lambda).$ $$

The first inequality holds because $H(\theta^{*};\mathcal{D}_{t})\preceq(1+MD(\theta^{*}-\bar{\theta}_{t}))Q(\theta^{*},\bar{\theta}_{t};\mathcal{D}_{t})$ ([Lemma˜A.2](https://arxiv.org/html/2510.10730v1#A1.Thmtheorem2)).
The second inequality holds because $D(v)\leq\|v\|$ for $v\in\mathbb{R}^{d}$ and is under the assumption $\|f_{t}(\bar{\theta}_{t})-f_{t}(\theta^{*})\|_{H_{t}^{-1}}\leq\gamma_{t}(\delta,\lambda)$.
The last inequality holds because of ([B.3](https://arxiv.org/html/2510.10730v1#A2.E3)).
Therefore, we have

$$ $\displaystyle\|\bar{\theta}_{t}-\theta^{*}\|_{H_{t}}\leq(1+M\beta_{t}(\delta,\lambda))\gamma_{t}(\delta,\lambda),\quad\forall t\in[T]$ $$

holds with probability at least $1-\delta$.

While this concentration result of MLE is valid and tight, we need $\|\bar{\theta}_{t}-\theta^{*}\|_{H_{t}}$ to be bounded by a constant to prove the regret bound.
Therefore, we need to take the upper bound of $\gamma_{t}(\delta,\lambda)$.
From the definitions, both $\gamma_{t}(\delta,\lambda)$ and $\beta_{t}(\delta,\lambda)$ increase as $t$ increases, thus $\gamma_{t}(\delta,\lambda)\leq\gamma_{T}(\delta,\lambda)$, $\beta_{t}(\delta,\lambda)\leq\beta_{T}(\delta,\lambda)$.
Therefore, we have the following concentration result:

$$ $\displaystyle\|\bar{\theta}_{t}-\theta^{*}\|_{H_{t}}\leq(1+M\beta_{T}(\delta,\lambda))\gamma_{T}(\delta,\lambda),\quad\forall t\in[T]$ $$

holds with probability at least $1-\delta$.
This completes the proof.

###### Lemma B.1 (Theorem 2 in Janz et al. ( 2024b ) ) .

### B.2 Proof of Lemma ˜ A.4 (Concentration of Perturbation)

In this section, our main goal is to find a high probability upper bound of $\|\theta_{t}^{j}-\bar{\theta}_{t}\|_{H_{t}}$, where $\theta_{t}^{j}=\mathop{\mathrm{argmin}}_{\theta\in\mathbb{R}^{d}}L(\theta;\mathcal{D}_{t}^{j})$ is the estimate of $\theta^{*}$ from ensemble element $j$, $\mathcal{D}_{t}^{j}=\{(X_{l},Y_{l}+Z_{l}^{j})\}_{l=1}^{t}$ is the perturbed dataset used by element $j$, and $Z_{l}^{j}\sim\mathcal{N}(0,\sigma_{R}^{2})$ are perturbations of rewards.
Recall from the definition, we have

$$ $\displaystyle f_{t}(\bar{\theta}_{t})$ $\displaystyle=\sum_{l=1}^{t}\mu(X_{l}^{\top}\bar{\theta}_{t})X_{l}+\lambda\bar{\theta}_{t}=\sum_{l=1}^{t}X_{l}Y_{l},$ $\displaystyle f_{t}(\theta_{t}^{j})$ $\displaystyle=\sum_{l=1}^{t}\mu(X_{l}^{\top}\theta_{t}^{j})X_{l}+\lambda\theta_{t}^{j}=\sum_{l=1}^{t}X_{l}(Y_{l}+Z_{l}^{j}).$ $$

Thus we have $f_{t}(\theta_{t}^{j})-f_{t}(\bar{\theta}_{t})=\sum_{l=1}^{t}Z_{l}^{j}X_{l}$.
We use the following lemma to provide a high probability upper bound.

###### Lemma B.2 (Lemma 8 of Lee and Oh ( 2024 ) ) .

Let $\{\mathcal{F}_{t}\}$ be a filtration. Let $\{\eta_{t}\}_{t=1}^{\infty}$ be a sequence of real-valued random variables such that $\eta_{t}$ is $\mathcal{F}_{t-1}$-conditionally $\sigma$-sub-Gaussian for some $\sigma\geq 0$. Let $\{X_{t}\}_{t=1}^{\infty}$ be a sequence of $\mathbb{R}^{d}$-valued random vectors such that $X_{t}$ is $\mathcal{F}_{t-1}$-measurable and $||X_{t}||_{2}\leq 1$ almost surely for all $t\geq 1$. Fix $\lambda\geq 1$. Let $V_{t}=\lambda I+\sum_{l=1}^{t}X_{l}X_{l}^{\top}$. Then, for any $\delta\in(0,1]$, with probability at least $1-\delta$, the following inequality holds for all $t\geq 0$:

$$ $\displaystyle\bigg\|\sum_{l=1}^{t}\eta_{l}X_{l}\bigg\|_{V_{t}^{-1}}\leq\sigma\sqrt{d\,\text{log}\bigg(1+\frac{t}{d\lambda}\bigg)+2\text{log}\frac{1}{\delta}}.$ $$

Applying [Lemma˜B.2](https://arxiv.org/html/2510.10730v1#A2.Thmtheorem2), we have that

$$ $\displaystyle\big\|f_{t}(\theta_{t}^{j})-f_{t}(\bar{\theta}_{t})\big\|_{G_{t}^{-1}}=\bigg\|\sum_{l=1}^{t}Z_{l}^{j}X_{l}\bigg\|_{G_{t}^{-1}}\leq\sigma_{R}\sqrt{d\log\bigg(1+\frac{t\dot{\mu}_{\text{min}}}{d\lambda}\bigg)+2\log\frac{T}{\delta}}=:\sigma_{R}\,\widetilde{\gamma}_{t}(\delta,\lambda)$ (B.4) $$

holds for all $t\geq 0$ with probability at least $1-\delta/T$.

Next, we use this result to prove a high probability upper bound of $\|\theta_{t}^{j}-\bar{\theta}_{t}\|_{H_{t}}$.
Recall from ([A.7](https://arxiv.org/html/2510.10730v1#A1.E7)), we have

$$ $\displaystyle f_{t}(\theta_{t}^{j})-f_{t}(\bar{\theta}_{t})=Q(\theta_{t}^{j},\bar{\theta}_{t};\mathcal{D}_{t})(\theta_{t}^{j}-\bar{\theta}_{t})=:\widetilde{Q}_{t}^{j}(\theta_{t}^{j}-\bar{\theta}_{t}).$ $$

From the definition,

$$ $\displaystyle\widetilde{Q}_{t}^{j}=Q(\theta_{t}^{j},\bar{\theta}_{t};\mathcal{D}_{t})=\sum_{l=1}^{t}\alpha\big(X_{l}^{\top}\theta_{t}^{j},X_{l}^{\top}\bar{\theta}_{t}\big)X_{l}X_{l}^{\top}+\lambda I.$ $$

Based on the definition of $\alpha(\cdot,\cdot)$ and mean value theorem, there exists $\zeta(l)=aX_{l}^{\top}\theta_{t}^{j}+(1-a)X_{l}^{\top}\bar{\theta}_{t}\in\mathbb{R}$ with $0<a<1$ such that

$$ $\displaystyle\alpha\big(X_{l}^{\top}\theta_{t}^{j},X_{l}^{\top}\bar{\theta}_{t}\big)=\frac{\mu(X_{l}^{\top}\theta_{t}^{j})-\mu(X_{l}^{\top}\bar{\theta}_{t})}{X_{l}^{\top}\theta_{t}^{j}-X_{l}^{\top}\bar{\theta}_{t}}=\dot{\mu}(\zeta(l)).$ $$

Note that we have assumed $0<\dot{\mu}_{\text{min}}\leq\dot{\mu}(\cdot)\leq\dot{\mu}_{\text{max}}$, thus we have

$$ $\displaystyle\dot{\mu}_{\text{min}}G_{t}\preceq\widetilde{Q}_{t}^{j}\preceq\dot{\mu}_{\text{max}}G_{t}.$ $$

Combining the discussions above and the fact $\dot{\mu}_{\text{min}}G_{t}\preceq H(\theta;\mathcal{D}_{t})\preceq\dot{\mu}_{\text{max}}G_{t}$, when ([B.4](https://arxiv.org/html/2510.10730v1#A2.E4)) holds, we have the following upper bound:

$$ $\displaystyle\big\|\theta_{t}^{j}-\bar{\theta}_{t}\big\|_{H_{t}}$ $\displaystyle=\big\|{(\widetilde{Q}^{j}_{t})}^{-1}(f_{t}(\theta_{t}^{j})-f_{t}(\bar{\theta}_{t}))\big\|_{H_{t}}$ $\displaystyle=\sqrt{\big(f_{t}(\theta_{t}^{j})-f_{t}(\bar{\theta}_{t})\big)^{\top}{(\widetilde{Q}^{j}_{t})}^{-1}H_{t}{(\widetilde{Q}^{j}_{t})}^{-1}\big(f_{t}(\theta_{t}^{j})-f_{t}(\bar{\theta}_{t})\big)}$ $\displaystyle\leq\dot{\mu}_{\text{max}}^{1/2}\,\dot{\mu}_{\text{min}}^{-1}\,\big\|f_{t}(\theta_{t}^{j})-f_{t}(\bar{\theta}_{t})\big\|_{G_{t}^{-1}}$ $\displaystyle\leq\dot{\mu}_{\text{max}}^{1/2}\,\dot{\mu}_{\text{min}}^{-1}\,\sigma_{R}\,\widetilde{\gamma}_{t}(\delta,\lambda).$ $$

The result above is for fixed ensemble element $j\in[m]$.
We further define the following event for each round $t$:

$$ $\displaystyle\widetilde{\mathcal{E}}_{1,t}:=\{\big\|\theta_{t}^{j_{t}}-\bar{\theta}_{t}\big\|_{H_{t}}\leq\dot{\mu}_{\text{max}}^{1/2}\,\dot{\mu}_{\text{min}}^{-1}\,\sigma_{R}\,\widetilde{\gamma}_{T}(\delta,\lambda)\}.$ $$

Since $j_{t}$ is sampled independently, we have

$$ $\displaystyle\mathbb{P}(\widetilde{\mathcal{E}}_{1,t})=\sum_{j=1}^{m}\mathbb{P}(j_{t}=j,\big\|\theta_{t}^{j}-\bar{\theta}_{t}\big\|_{H_{t}}\leq\dot{\mu}_{\text{max}}^{1/2}\,\dot{\mu}_{\text{min}}^{-1}\,\sigma_{R}\,\widetilde{\gamma}_{T}(\delta,\lambda))\geq 1-\frac{\delta}{T}.$ $$

Therefore, for each round $t\in[T]$, the concentration of perturbation holds with high probability.
This completes the proof.

###### Lemma B.2 (Lemma 8 of Lee and Oh ( 2024 ) ) .

### B.3 Sufficient Condition of Optimism

In this section, our main goal is to obtain a sufficient condition of optimism $X_{t}^{\top}\theta_{t}^{j}-X^{*\top}\theta^{*}\geq 0$.
The motivation is that we need to find a lower bound of probability of optimism for each round, while analyzing this probability directly is very challenging. Therefore, we need to find a sufficient condition for optimism using variables $\{X_{l}\}_{l=1}^{t}$ and $\{Z_{l}^{j}\}_{l=1}^{t}$ explicitly, by analyzing the probability of the sufficient condition, we obtain a lower bound of probability of optimism.
To achieve this, we consider the following inequality:

$$ $\displaystyle X_{t}^{\top}\theta_{t}^{j}-X^{*\top}\theta^{*}$ $\displaystyle\geq X^{*\top}\theta_{t}^{j}-X^{*\top}\theta^{*}$ $\displaystyle=X^{*\top}(\widetilde{\theta}_{t}^{j}+\bar{\theta}_{t}-\theta^{*})$ $\displaystyle=X^{*\top}\widetilde{\theta}_{t}^{j}+X^{*\top}(\bar{\theta}_{t}-\theta^{*}),$ (B.5) $$

where $\widetilde{\theta}_{t}^{j}=\theta_{t}^{j}-\bar{\theta}_{t}$.
Next, we introduce the following notations:

$$ $\displaystyle\mathbf{Z}_{t}^{j}=\big(\underbrace{0,\cdots,0}_{d},Z_{1}^{j},\cdots,Z_{t}^{j}\big)^{\top}\in\mathbb{R}^{d+t},\quad\Phi_{t}=\big(\sqrt{\lambda/\dot{\mu}_{\text{min}}}I_{d},X_{1},\cdots,X_{t}\big)\in\mathbb{R}^{d\times(d+t)},$ $$

then we have $\Phi_{t}\mathbf{Z}_{t}^{j}=\sum_{l=1}^{t}X_{l}Z_{l}^{j}$. Recall that we have

$$ $\displaystyle\widetilde{\theta}_{t}^{j}=\theta_{t}^{j}-\bar{\theta}_{t}={\big(\widetilde{Q}_{t}^{j}\big)}^{-1}\big(f_{t}(\theta_{t}^{j})-f_{t}(\bar{\theta}_{t})\big)={\big(\widetilde{Q}_{t}^{j}\big)}^{-1}\sum_{l=1}^{t}X_{l}Z_{l}^{j},$ $$

we obtain the relation $\widetilde{\theta}_{t}^{j}={\big(\widetilde{Q}_{t}^{j}\big)}^{-1}\Phi_{t}\mathbf{Z}_{t}^{j}$.
We further define

$$ $\displaystyle U_{t}^{\top}=x^{*\top}H_{t}^{-1}\Phi_{t}\in\mathbb{R}^{t},$ $$

then we have

$$ $\displaystyle\|X^{*}\|_{H_{t}^{-1}}^{2}={X^{*}}^{\top}H_{t}^{-1}X^{*}\leq\dot{\mu}_{\text{max}}^{2}X^{*\top}H_{t}^{-1}\Phi_{t}\Phi_{t}^{\top}H_{t}^{-1}x^{*}=\dot{\mu}_{\text{max}}^{2}\|U_{t}\|_{2}^{2}.$ $$

This relates the norm of $X^{*}$ to $U_{t}$.

With these notations and results, we can continue analyzing [B.3](https://arxiv.org/html/2510.10730v1#A2.Ex43).
First, we can use concentration to directly bound $X^{*\top}(\bar{\theta}_{t}-\theta^{*})$ as follows:

$$ $\displaystyle X^{*\top}(\bar{\theta}_{t}-\theta^{*})\geq-||X^{*}||_{H_{t}^{-1}}||\bar{\theta}_{t}-\theta^{*}||_{H_{t}}\geq-\dot{\mu}_{\text{max}}^{2}\|U_{t}\|_{2}^{2}\,||\bar{\theta}_{t}-\theta^{*}||_{H_{t}}.$ $$

Assume that $||\bar{\theta}_{t}-\theta^{*}||_{H_{t}}\leq c$, where $c>0$ is a constant, then

$$ $\displaystyle X^{*\top}(\bar{\theta}_{t}-\theta^{*})\geq-c\,\dot{\mu}_{\text{max}}^{2}\|U_{t}\|_{2}^{2}.$ $$

Next, we analyze $X^{*\top}\widetilde{\theta}_{t}^{j}$.
From previous discussions, we have the following expression:

$$ $\displaystyle X^{*\top}\widetilde{\theta}_{t}^{j}=X^{*\top}{\big(\widetilde{Q}_{t}^{j}\big)}^{-1}\Phi_{t}\mathbf{Z}_{t}^{j}.$ $$

Recall that from the definition,

$$ $\displaystyle\widetilde{Q}_{t}^{j}=Q(\theta_{t}^{j},\bar{\theta}_{t};\mathcal{D}_{t})=\sum_{l=1}^{t}\alpha\big(X_{l}^{\top}\theta_{t}^{j},X_{l}^{\top}\bar{\theta}_{t}\big)X_{l}X_{l}^{\top}+\lambda I.$ $$

Since $\widetilde{Q}_{t}^{j}$ includes the information of $\{Z_{l}^{j}\}_{l=1}^{t}$, the randomness from perturbation is not fully decoupled and we cannot directly use tail bound of the distribution of $Z_{t}^{j}$.
To overcome this difficulty, we define $W_{t}^{j}=\widetilde{Q}_{t}^{j}-H_{t}$, and we have the following relation:

$$ $\displaystyle\bigg(\widetilde{Q}_{t}^{j}\bigg)^{-1}=\bigg(H_{t}+W_{t}^{j}\bigg)^{-1}=H_{t}^{-1}-H_{t}^{-1}W_{t}^{j}\big(H_{t}+W_{t}^{j}\big)^{-1}.$ $$

Note that $H_{t}$ does not include information of perturbations.
Based on ([B.3](https://arxiv.org/html/2510.10730v1#A2.Ex43)), to guarantee that optimism holds, it suffices to satisfy that

$$ $\displaystyle\,\,X^{*\top}\widetilde{\theta}_{t}^{j}+X^{*\top}(\bar{\theta}_{t}-\theta^{*})$ $\displaystyle=$ $\displaystyle X^{*\top}H_{t}^{-1}\Phi_{t}\mathbf{Z}_{t}^{j}-X^{*\top}\big(H_{t}^{-1}W_{t}^{j}\big(H_{t}+W_{t}^{j}\big)^{-1}\big)\Phi_{t}\mathbf{Z}_{t}^{j}+X^{*\top}(\bar{\theta}_{t}-\theta^{*})\geq 0.$ $$

Then it suffices to satisfy that

$$ $\displaystyle X^{*\top}H_{t}^{-1}\Phi_{t}\mathbf{Z}_{t}^{j}\geq\bigg|X^{*\top}\bigg((H_{t}^{-1}W_{t}^{j}\big(H_{t}+W_{t}^{j}\big)^{-1}\bigg)\Phi_{t}\mathbf{Z}_{t}^{j}\bigg|+\big|X^{*\top}(\bar{\theta}_{t}-\theta^{*})\big|.$ $$

Note that in $X^{*\top}H_{t}^{-1}\Phi_{t}\mathbf{Z}_{t}^{j}$, the randomness of $\{Z_{l}^{j}\}_{l=1}^{t}$ only appears in $\mathbf{Z}_{t}^{j}$, thus we decoupled the randomness of perturbation and we can utilize the tail bound of $Z_{l}^{j}$.

Next, we need to upper bound the right-hand-side of the inequality to obtain a sufficient condition of optimism.
We already have the result

$$ $\displaystyle\big|X^{*\top}(\bar{\theta}_{t}-\theta^{*})\big|\leq c\,\dot{\mu}_{\text{max}}^{2}\|U_{t}\|_{2}^{2}.$ $$

We upper bound $\big|X^{*\top}(H_{t}^{-1}W_{t}^{j}(H_{t}+W_{t}^{j})^{-1})\Phi_{t}\mathbf{Z}_{t}^{j}\big|$ as follows.

$$ $\displaystyle\big|X^{*\top}\big(H_{t}^{-1}W_{t}^{j}(\widetilde{Q}_{t}^{j})^{-1}\big)\Phi_{t}\mathbf{Z}_{t}^{j}\big|$ $\displaystyle=\big|\big(H_{t}^{-1/2}X^{*}\big)^{\top}\big(H_{t}^{-1/2}W_{t}^{j}H_{t}^{-1/2}\big)\big(H_{t}^{1/2}\big(\widetilde{Q}_{t}^{j}\big)^{-1}\Phi_{t}\mathbf{Z}_{t}^{j}\big)\big|$ $\displaystyle\leq\big\|H_{t}^{-1/2}X^{*}\big\|_{2}\big\|H_{t}^{-1/2}W_{t}^{j}H_{t}^{-1/2}\big\|_{2}\big\|H_{t}^{1/2}\big(\widetilde{Q}_{t}^{j}\big)^{-1}\Phi_{t}\mathbf{Z}_{t}^{j}\big\|_{2}$ $\displaystyle=\|X^{*}\|_{H_{t}^{-1}}\big\|H_{t}^{-1/2}W_{t}^{j}H_{t}^{-1/2}\big\|_{2}\big\|\big(\widetilde{Q}_{t}^{j}\big)^{-1}\Phi_{t}\mathbf{Z}_{t}^{j}\big\|_{H_{t}}$ $\displaystyle=\|X^{*}\|_{H_{t}^{-1}}\big\|H_{t}^{-1/2}\big(\widetilde{Q}_{t}^{j}-H_{t}\big)H_{t}^{-1/2}\big\|_{2}\big\|\widetilde{\theta}_{t}^{j}\big\|_{H_{t}}.$ $$

According to the definition, for symmetric matrix $A$, we have

$$ $\displaystyle\|A\|_{2}=\text{max}_{\|v\|=1}\|Av\|_{2}=|\lambda_{\text{max}}(A)|.$ $$

From definition,

$$ $\displaystyle H_{t}^{-1/2}\big(\widetilde{Q}_{t}^{j}-H_{t}\big)H_{t}^{-1/2}\preceq H_{t}^{-1/2}\bigg(\sum_{l=1}^{t-1}\Big|\alpha\big(X_{l}^{\top}\bar{\theta}_{t},X_{l}^{\top}\theta_{t}^{j}\big)-\dot{\mu}(X_{l}^{\top}\theta^{*})\Big|X_{l}X_{l}^{\top}\bigg)H_{t}^{-1/2}.$ $$

From [Lemma˜A.1](https://arxiv.org/html/2510.10730v1#A1.Thmtheorem1), we have

$$ $\displaystyle\alpha\big(X_{l}^{\top}\bar{\theta}_{t},X_{l}^{\top}\theta_{t}^{j}\big)\leq\dot{\mu}\big(X_{l}^{\top}\bar{\theta}_{t}\big)\frac{\exp{(MD_{t})}-1}{MD_{t}},$ $$

where $D_{t}=\max_{l<t}|X_{l}^{\top}(\bar{\theta}_{t}-\theta_{t}^{j})|$. Then we have

$$ $\displaystyle H_{t}^{-1/2}\big(\widetilde{Q}_{t}^{j}-H_{t}\big)H_{t}^{-1/2}\preceq H_{t}^{-1/2}\bigg(\sum_{l=1}^{t-1}\Big|\alpha\big(X_{l}^{\top}\bar{\theta}_{t},X_{l}^{\top}\theta_{t}^{j}\big)-\dot{\mu}(X_{l}^{\top}\theta^{*})\Big|X_{l}X_{l}^{\top}\bigg)H_{t}^{-1/2}.$ $$

Let $R_{t}=\frac{\exp{(MD_{t})}-1}{MD_{t}}-1$, then for any $v\in\mathbb{R}^{d}$ with $\|v\|=1$, we have

$$ $\displaystyle v^{\top}\Big(\bar{H}_{t}^{-1/2}\big(\widetilde{Q}_{t}^{j}-\bar{H}_{t}\big)\bar{H}_{t}^{-1/2}\Big)v\leq R_{t}v^{\top}\bar{H}_{t}^{-1/2}(\bar{H}_{t}-\lambda I)\bar{H}_{t}^{-1/2}v\leq R_{t}.$ $$

We then obtain that

$$ $\displaystyle\big\|\bar{H}_{t}^{-1/2}\big(\widetilde{Q}_{t}^{j}-\bar{H}_{t}\big)\bar{H}_{t}^{-1/2}\big\|_{2}=\big|\lambda_{\text{max}}\big(\bar{H}_{t}^{-1/2}\big(\widetilde{Q}_{t}^{j}-\bar{H}_{t}\big)\bar{H}_{t}^{-1/2}\big)\big|\leq R_{t}.$ $$

From concentration results, under event $\mathcal{E}_{1}$, we have

$$ $\displaystyle\|\bar{\theta}_{t}-\theta^{*}\|_{H_{t}}$ $\displaystyle\leq(1+M\beta_{T})\gamma_{T},$ (B.6) $\displaystyle\|\widetilde{\theta}_{t}^{j}\|_{H_{t}}$ $\displaystyle\leq\dot{\mu}_{\text{max}}^{1/2}\,\dot{\mu}_{\text{min}}^{-1}\,\widetilde{\gamma}_{T}\sigma_{R},$ (B.7) $$

for all $t\in[T]$, and $\mathcal{E}_{1}$ holds with probability at least $1-2\delta$. Therefore, we have

$$ $\displaystyle\big|X^{*\top}\big(\bar{H}_{t}^{-1}W_{t}^{j}\big(\bar{H}_{t}+W_{t}^{j}\big)^{-1}\big)\Phi_{t}\mathbf{Z}_{t}^{j}\big|+\big|X^{*\top}\big(\bar{\theta}_{t}-\theta^{*})\big|$ $\displaystyle\leq$ $\displaystyle\big((1+M\beta_{T})\gamma_{T}+R_{t}\dot{\mu}_{\text{max}}^{1/2}\,\dot{\mu}_{\text{min}}^{-1}\,\widetilde{\gamma}_{T}\sigma_{R}\big)\|X^{*}\|_{H_{t}^{-1}}.$ $$

Finally, we obtain the sufficient condition for optimism as follows:

$$ $\displaystyle X^{*\top}\bar{H}_{t}^{-1}\Phi_{t}\mathbf{Z}_{t}^{j}\geq\big((1+M\beta_{T})\gamma_{T}+R_{t}\dot{\mu}_{\text{max}}^{1/2}\,\dot{\mu}_{\text{min}}^{-1}\,\widetilde{\gamma}_{T}\sigma_{R}\big)\|X^{*}\|_{H_{t}^{-1}}.$ (B.8) $$

Recall the definition $U_{t}^{\top}=X^{*\top}H_{t}^{-1}\Phi_{t}\in\mathbb{R}^{t}$ and the result

$$ $\displaystyle\|X^{*}\|_{H_{t}^{-1}}^{2}={X^{*}}^{\top}\bar{H}_{t}X^{*}\leq\dot{\mu}_{\text{max}}^{2}\|U_{t}\|_{2}^{2},$ $$

we obtain the final expression of the sufficient condition for optimism:

$$ $\displaystyle U_{t}^{\top}\mathbf{Z}_{t}^{j}\geq\dot{\mu}_{\text{max}}\big((1+M\beta_{T})\gamma_{T}+R_{t}\dot{\mu}_{\text{max}}^{1/2}\,\dot{\mu}_{\text{min}}^{-1}\,\widetilde{\gamma}_{T}\sigma_{R}\big)\|U_{t}\|_{2}.$ $$

To simplify the notations, define $b_{1}=\dot{\mu}_{\text{max}}(1+M\beta_{T})\gamma_{T}$ and $b_{2}=\dot{\mu}_{\text{max}}^{3/2}\dot{\mu}_{\text{min}}^{-1}\widetilde{\gamma}_{T}$, we have the following expression:

$$ $\displaystyle U_{t}^{\top}\mathbf{Z}_{t}^{j}\geq(b_{1}+b_{2}R_{t}\sigma_{R}{})\|U_{t}\|_{2}.$ $$

We summarize these discussions to the following lemma.

###### Lemma B.3 (Sufficient Condition for Optimism) .

For $t\in[T]$ and $j\in[m]$, define vector $U_{t}^{\top}=X^{*\top}H_{t}^{-1}\Phi_{t}\in\mathbb{R}^{t}$, $b_{1}=\dot{\mu}_{\text{max}}(1+M\beta_{T})\gamma_{T}$ and $b_{2}=\dot{\mu}_{\text{max}}^{3/2}\dot{\mu}_{\text{min}}^{-1}\widetilde{\gamma}_{T}$. Then, under the concentration event $\mathcal{E}_{1}$, optimism $X^{*\top}\theta^{*}\leq X_{t}^{\top}\theta_{t}$ holds if the following inequality is satisfied

$$ $\displaystyle U_{t}^{\top}\mathbf{Z}_{t}^{j}\geq(b_{1}+b_{2}R_{t}\sigma)\|U_{t}\|_{2}.$ (B.9) $$

###### Lemma B.3 (Sufficient Condition for Optimism) .

### B.4 Proof of Lemma ˜ A.6 (Probability of Optimism)

With the sufficient condition of optimism [Lemma˜B.3](https://arxiv.org/html/2510.10730v1#A2.Thmtheorem3) and the fact that perturbations only appear in $\mathbf{Z}_{t}^{j}$, we can apply the tail bound of perturbations to obtain the probability of optimism.
We use Gaussian noise $Z_{l}^{j}\sim\mathcal{N}(0,\sigma_{R}^{2})$ for reward perturbation, thus we can apply the following tail bound: for any $u\in\mathbb{R}^{n}$ and $\mathbf{Z}\sim\mathcal{N}(0,\sigma_{R}^{2}I_{n})$, we have the following inequality

$$ $\displaystyle\mathbb{P}\big(u^{\top}\mathbf{Z}\geq\sigma_{R}\|u\|_{2}\big)\geq p_{N},$ $$

where $p_{N}$ is a constant and $p_{N}\geq 0.15$.
Based on this result, if we fix the sequence of pulled arms $\{X_{l}\}_{l=1}^{t}$ and element $j\in[m]$, ([B.9](https://arxiv.org/html/2510.10730v1#A2.E9)) in [Lemma˜B.3](https://arxiv.org/html/2510.10730v1#A2.Thmtheorem3) holds with probability at least $p_{N}$ if we choose $\sigma$ that satisfies

$$ $\displaystyle\sigma\geq b_{1}+b_{2}R_{t}\sigma.$ (B.10) $$

Next, we define the indicator function $I_{t}^{j}:=\operatorname*{\mathds{1}}\{(U_{t}^{\top}\mathbf{Z}_{t}^{j}\geq(b_{1}+b_{2}R_{t}\sigma)\|U_{t}\|_{2})\cap\widetilde{\mathcal{E}}_{1,t}\}$.
We proved that $\widetilde{\mathcal{E}}_{1,t}$ holds with probability at least $1-\delta/T$, thus we have

$$ $\displaystyle\mathbb{P}\big(I_{t}^{j}=1\big)\geq\mathbb{P}\big(U_{t}^{\top}\mathbf{Z}_{t}^{j}\geq(b_{1}+b_{2}R_{t}\sigma)\|U_{t}\|_{2}\big)-\frac{\delta}{T}\geq\frac{p_{N}}{2}.$ $$

Now we add the randomness of choosing arm $j_{t}$ at round $t$, the probability of optimism after uniformly randomly choosing arm $j_{t}$ is given by $\sum_{j=1}^{m}\mathbb{P}(I_{t}^{j}=1)/m$.
Using Azuma-Hoeffding inequality, we have the following result:

$$ $\displaystyle\mathbb{P}\Big(\frac{1}{m}\sum_{j=1}^{m}I_{t}^{j}<\frac{p_{N}}{4}\Big)\leq\text{exp}\Big(-\frac{p_{N}^{2}m}{8}\Big).$ $$

The results above are obtained under fixed sequence of pulled arms $\{X_{l}\}_{l=1}^{t}$, we use the following result to count equivalent permutations of $\{X_{l}\}_{l=1}^{t}$.

###### Lemma B.4 (Claim 1 in Lee and Oh ( 2024 ) ) .

There exists an event $\mathcal{E}^{*}$ such that under $\mathcal{E}^{*}$, $\frac{1}{m}\sum_{j=1}^{m}I_{t}^{j}\geq p_{N}/4$ holds for all $t\in[T]$, and $\mathbb{P}\big(\bar{\mathcal{E}}^{*}\big)\leq T^{K}\text{exp}\big(-p_{N}^{2}m/8\big)$.

Therefore, by choosing ensemble size

$$ $\displaystyle m\geq\frac{8}{p_{N}^{2}}\Big(K\text{log}T+\text{log}\frac{1}{\delta}\Big),$ $$

we have $\mathbb{P}\big(\bar{\mathcal{E}}^{*}\big)\leq 1-\delta$, with high probability, optimism holds with constant probability.
This completes the proof.

###### Lemma B.4 (Claim 1 in Lee and Oh ( 2024 ) ) .

### B.5 Warm-up Procedure

In the analysis of optimism, we assumed that ([B.10](https://arxiv.org/html/2510.10730v1#A2.E10)) has a solution. In this section, we analyze how to guarantee that solution of ([B.10](https://arxiv.org/html/2510.10730v1#A2.E10)) exists.
From the expression, we need to set warm-up parameter $\tau$ to make sure that $R_{t}$ is sufficiently small, so that the solution is approximately $\sigma_{R}=b_{1}$. Recall from the definition of $R_{t}$, we have

$$ $\displaystyle R_{t}=\frac{\exp{(MD_{t})}-1}{MD_{t}}-1\leq\frac{1+MD_{t}+(MD_{t})^{2}-1}{MD_{t}}-1=MD_{t},$ $$

where the inequality holds when $MD_{t}\leq 1$.
Therefore, we should use warm-up procedure to reduce $D_{t}$ until sufficiently small.
Note that

$$ $\displaystyle D_{t}=\max_{s<t}\big|X_{s}^{\top}(\bar{\theta}_{t}-\theta_{t}^{j})\big|\leq\max_{s<t}\|X_{s}\|_{\bar{H}_{t}^{-1}}\|\bar{\theta}_{t}-\theta_{t}^{j}\|_{\bar{H}_{t}},$ $$

where the inequality holds due to Cauchy-Schwarz inequality.
Therefore, we should focus on upper bounding $\max_{x\in\mathcal{X}}\|x\|_{\bar{H}_{t}}$.
This is achieved by the following warm-up procedures.

Figure: Algorithm 2 Warm-up of GLM-ES

Figure: Algorithm 3 Rounding procedure of [Algorithm˜2](https://arxiv.org/html/2510.10730v1#alg2)

In GLM-ES, [Algorithm˜1](https://arxiv.org/html/2510.10730v1#alg1) is initialized by calling a warm-up procedure [Algorithm˜2](https://arxiv.org/html/2510.10730v1#alg2) that approximates a G-optimal design. This is necessary to guarantee the sufficient condition for optimism ([B.9](https://arxiv.org/html/2510.10730v1#A2.E9)) happens with constant probability.
Here, $\zeta\in\Delta_{\mathcal{X}}$ is a probability measure over arm set $\mathcal{X}$, which is set to minimize

$$ $\displaystyle\max_{x\in\mathcal{X}}\|x\|^{2}_{V(\zeta)^{-1}},\quad\text{where }V(\zeta)=\sum_{x\in\mathcal{X}}\zeta(x)xx^{\top}.$ $$

We then sample $x_{1},\dots,x_{\tau}$ based on G-optimal design $\zeta$ by following the rounding procedure (Line [2](https://arxiv.org/html/2510.10730v1#alg2.l2) in [Algorithm˜2](https://arxiv.org/html/2510.10730v1#alg2)). The complete rounding procedure is given in [Algorithm˜3](https://arxiv.org/html/2510.10730v1#alg3), which is proposed in Chapter 12 of Pukelsheim (2006) and is detailed in Fiez et al. (2019).

We provide a theoretical guarantee for the warm-up procedure as follows.

###### Lemma B.5 (Warm-up) .

Let $\zeta$ be the $G$-optimal design solution over a compact feature set $\mathcal{X}$ whose span is $\mathbb{R}^{d}$. Let $\iota>0$ and $\epsilon=0.5$. By setting the number of warm-up rounds as $\tau=\lceil 1.5\iota^{2}d/\dot{\mu}_{\text{min}}\rceil$, [Algorithm˜2](https://arxiv.org/html/2510.10730v1#alg2) returns a dataset $\{(x_{s},y_{s})\}_{s=1}^{\tau}$ such that for all $t>\tau$, we have

$$ $\displaystyle\max_{x\in\mathcal{X}}\|x\|_{\bar{H}_{t}}\leq 1/\iota.$ (B.11) $$

###### Proof of Lemma ˜ B.5 .

The proof mainly follows the proof of (Liu, 2023, Lemma 4.10), we write it here for completeness. Note that for all $t>\tau$, we have $H_{t}^{-1}(\bar{\theta}_{t})\preceq H_{\tau}^{-1}(\bar{\theta}_{t})$ where $H_{t}(\theta)$ is $H(\theta,\mathcal{D}_{t})$ defined in ([A.4](https://arxiv.org/html/2510.10730v1#A1.E4)). Then we have

$$ $\displaystyle\max_{x}\|x\|_{H_{t}^{-1}(\bar{\theta}_{t})}^{2}\leq\max_{x}\|x\|_{H_{\tau}^{-1}(\bar{\theta}_{t})}^{2}.$ $$

We further define $H(\zeta,\theta)=\sum_{x\in\mathcal{X}}\zeta(x)\dot{\mu}(x^{\top}\theta)xx^{\top}$ where $\zeta$ is a probability measure over $\mathcal{X}$. Then it is sufficient to prove that for all $t>\tau$, $\max_{x}\|x\|_{H_{\tau}^{-1}(\bar{\theta}_{t})}\leq 1/\iota$ holds.

$$ $\displaystyle\max_{x}\|x\|_{H_{\tau}^{-1}(\bar{\theta}_{t})}^{2}$ $\displaystyle\leq\frac{1+\epsilon}{\tau}\max_{x}\|x\|_{H^{-1}(\zeta,\bar{\theta}_{t})}^{2}$ $\displaystyle\leq\frac{1+\epsilon}{\tau\dot{\mu}_{\text{min}}}\max_{x}\|x\|_{V^{-1}(\zeta)}^{2}$ $\displaystyle\leq\frac{d(1+\epsilon)}{\tau\dot{\mu}_{\text{min}}},$ $$

where the first inequality holds because of (Jun et al., 2021, Lemma 13), the second inequality holds because $H(\zeta,\bar{\theta}_{t})\succeq\dot{\mu}_{\text{min}}V(\zeta)$ and the last inequality holds due to (Lattimore and Szepesvári, 2020, Theorem 21.1 (Kiefer–Wolfowitz)). The proof is completed by setting $\tau=\iota^{2}d(1+\epsilon)/\dot{\mu}_{\text{min}}$.
∎

To guarantee that ([B.10](https://arxiv.org/html/2510.10730v1#A2.E10)) holds, we desire to have $R_{t}\leq MD_{t}\leq\sigma_{R}^{-\varepsilon}<1$ where $\varepsilon\in(0,1)$. Therefore, it suffices to have

$$ $\displaystyle\iota\geq Mb_{2}\dot{\mu}_{\text{max}}^{-1}\sigma_{R}^{1+\varepsilon}.$ $$

Also note that the solution for $\sigma_{R}\geq b_{1}+b_{2}\sigma_{R}^{1-\varepsilon}$ satisfies ([B.10](https://arxiv.org/html/2510.10730v1#A2.E10)), and we have $\sigma_{R}\gtrsim(d\log T)^{\frac{1}{2\varepsilon}}$.

Recall that $\tau=\lceil 1.5\iota^{2}d/\dot{\mu}_{\text{min}}\rceil$, then we can obtain the order of warm-up parameter $\tau$ as follows

$$ $\displaystyle\tau\gtrsim Cd^{2}\log T(d\log T)^{\frac{1+\varepsilon}{\varepsilon}},$ $$

where $C$ is a constant with respect to $(M,\dot{\mu}_{\text{max}},\dot{\mu}_{\text{min}})$. By setting $\varepsilon=\frac{2}{3}$, we can obtain

$$ $\displaystyle\tau=\widetilde{O}\big(d^{\frac{9}{2}}\big).$ (B.12) $$

Note that in Liu (2023), the warm-up parameter $\tau=\widetilde{O}(d^{9})$, which is much larger than ([B.12](https://arxiv.org/html/2510.10730v1#A2.E12)) that we derive.

In summary, to guarantee that ([B.10](https://arxiv.org/html/2510.10730v1#A2.E10)) has a solution, we should set warm-up rounds $\tau=\widetilde{O}\big(d^{9/2}\big)$ with [Algorithm˜2](https://arxiv.org/html/2510.10730v1#alg2).
Accordingly, the variance of perturbation $\sigma_{R}$ should satisfy $\sigma_{R}\geq b_{1}+b_{2}\sigma_{R}^{1/3}$, we should set $\sigma_{R}=\Theta\big(b_{1}+b_{2}^{3/2}\big)$.

###### Lemma B.5 (Warm-up) .

###### Proof of Lemma ˜ B.5 .

## Appendix C Proof of Regret Bound of Neural-ES

### C.1 Preliminary Analysis

Recall that we adopt a fully connected neural network $f(X;\theta):\mathbb{R}^{d}\rightarrow\mathbb{R}$ to approximate the true reward model $h(X)$:

$$ $\displaystyle f(X;\theta)=\sqrt{N}\,W_{L}\phi\bigg(W_{L-1}\phi\big(\cdot\cdot\cdot\phi(W_{1}X)\big)\bigg),$ $$

where $N$ is the width of each layer, $\theta=[\text{vec}(W_{1}),\cdot\cdot\cdot,\text{vec}(W_{L})]\in\mathbb{R}^{d^{\prime}}$ is the concatenation of all learnable parameters.
We use $g(X;\theta_{0})=\nabla_{\theta}f(X;\theta_{0})\in\mathbb{R}^{d^{\prime}}$ to denote the gradient of the initial neural network.
For convenience and comparison with linear contextual bandit, we define the following mapping:

$$ $\psi(X)=\frac{g(X;\theta_{0})}{\sqrt{N}}:\quad\mathbb{R}^{d}\rightarrow\mathbb{R}^{d^{\prime}}.$ (C.1) $$

As we will see in the following analysis, after we map the $d$-dimensional feature vector $X$ into the $d^{\prime}$-dimensional $\psi(X)$, the analysis of Neural-ES is similar to that of Lin-ES.

We define the covariance matrix $A_{t}$ at round $t$ as

$$ $A_{t}=\frac{1}{N}\sum_{l=1}^{t-1}g(X_{l};\theta_{0})g(X_{l};\theta_{0})^{\top}+\lambda\,I_{d^{\prime}}=\sum_{l=1}^{t-1}\psi(X)\psi(X)^{\top}+\lambda I_{d^{\prime}},$ (C.2) $$

and the following auxiliary vectors

$$ $\displaystyle\bar{\mathbf{b}}_{t}$ $\displaystyle=\frac{1}{\sqrt{N}}\sum_{l=1}^{t-1}Y_{l}\,g(X_{l};\theta_{0})=\sum_{l=1}^{t-1}Y_{l}\,\psi(X_{l}),$ $\displaystyle\mathbf{b}_{t}^{j}$ $\displaystyle=\frac{1}{\sqrt{N}}\sum_{l=1}^{t-1}(Y_{l}+Z_{l}^{j})\,g(X_{l};\theta_{0})=\sum_{l=1}^{t-1}(Y_{l}+Z_{l}^{j})\,\psi(X_{l}).$ $$

Then, similar to linear contextual bandit, the MLE without perturbation is $\bar{\theta}_{t}=A_{t}^{-1}\,\bar{\mathbf{b}}_{t}$, the least square solution for parameter $\theta_{t}^{j}$ (of model $j\in[m]$) is $A_{t}^{-1}\,\mathbf{b}_{t}^{j}$.
These notations and results will be utilized extensively in the following analysis.

### C.2 Technical Lemmas

In this section, we list the main technical lemmas required to obtain the high-probability regret bound of Neural-ES. We present the proof of these technical lemmas in Appendix [D](https://arxiv.org/html/2510.10730v1#A4).

First, we need the following common assumption and well-known result to demonstrate that our neural network $f(X;\theta)$ and its gradient $g(X;\theta_{0})$ can accurately approximate the true reward model $h(X)$.

###### Assumption C.1 .

We use $\mathbf{H}$ to denote the neural tangent kernel (NTK) matrix on the context set. We assume that $\mathbf{H}\succeq\lambda_{0}I$.
Moreover, for any $X\in\mathcal{X}$, $||X||_{2}\leq 1$ and $[X]_{j}=[X]_{j+d/2}$.

###### Lemma C.2 .

(Lemma 4.1 in Jia et al. (2022))
There exists a positive constant $\bar{C}$ such that for any $\delta\in(0,1)$, with probability at least $1-\delta$, when $N\geq\bar{C}K^{4}L^{6}\,\text{log}(K^{2}L/\delta)/\lambda_{0}^{4}$, there exists a $\theta^{*}\in\mathbb{R}^{d^{\prime}}$ such that for all $X\in\mathcal{X}$,

$$ $\displaystyle h(X)=\langle g(X;\theta_{0}),\theta^{*}-\theta_{0}\rangle=\langle\psi(X),\sqrt{N}(\theta^{*}-\theta_{0})\rangle,\quad\sqrt{N}||\theta^{*}-\theta_{0}||_{2}\leq\sqrt{2\mathbf{h}^{\top}\mathbf{H}^{-1}\mathbf{h}}\leq S,$ $$

where $\mathbf{H}$ is the NTL matrix defined on the context set $\mathcal{X}$ and $\mathbf{h}=\big(h(X_{1}),...,h(X_{K})\big)$, $S$ is the upper bound of $\sqrt{2\mathbf{h}^{\top}\mathbf{H}^{-1}\mathbf{h}}$.

Compare this result with linear contextual bandit, where the mean reward is given by $X^{\top}\theta^{*}$, we can see that when the neural network is wide enough, the mean reward at contexts $X\in\mathcal{X}$ can be well approximated by a linear function of $\psi(X)$.
If our learned parameter $\theta_{t}$ is close to $\theta^{*}$, the distance between neural network approximation $f(X;\theta_{t})$ and true mean reward $h(X)$ can be controlled by the distance $\big|f(X_{t};\theta_{t})-\langle g(X_{t};\theta_{0}),\bar{\theta}_{t}\rangle\big|$ and $\big|\langle g(X_{t};\theta_{0}),\bar{\theta}_{t}\rangle-h(X_{t})\big|$.
Following these intuitions, we need the following lemmas to provide concentration of these distances.

###### Lemma C.3 .

(Lemma 4.2 in Jia et al. (2022))
Define a sequence of events $\mathcal{E}_{t,1}$ as follows:

$$ $\displaystyle\mathcal{E}_{1,t}:=\Big\{\forall X_{t}\in\mathcal{X},\big|\langle g(X_{t};\theta_{0}),A_{t}^{-1}\bar{\mathbf{b}}_{t}/\sqrt{N}\rangle-h(X_{t})\big|\leq\alpha_{t}||g(X_{t};\theta_{0})||_{A_{t}^{-1}}\Big\},$ $$

where $\alpha_{t}$ is a scalar scale of deviation.
Then, for any $t\in[T]$, $\lambda>0$ and $\delta>0$, with $\alpha_{t}$ set as

$$ $\alpha_{t}=\sqrt{\sigma^{2}\,\text{log}\big(\text{det}(A_{t})/(\delta^{2}\text{det}(\lambda I))\big)}+\sqrt{\lambda}S,$ (C.3) $$

where $S$ is the upper bound of $\sqrt{2\mathbf{h}^{\top}\mathbf{H}^{-1}\mathbf{h}}$, we have $\mathbb{P}(\mathcal{E}_{1,t}\,|\,\mathcal{F}_{t-1})\geq 1-\delta$.

Under event $\mathcal{E}_{t,1}$, the distance $\big|\langle\psi(X_{t}),\bar{\theta}_{t}\rangle-h(X_{t})\big|$ is bounded by $\alpha_{t}||g(X_{t};\theta_{0})||_{A_{t}^{-1}}$.
Recall that we assume the random noise $\eta_{t}$ is $\sigma$-sub-Gaussian, thus $\alpha_{t}$ reflects the deviation caused by the noise in the observed reward.
This result is valid for any algorithms in the neural contextual bandit setting, as it does not involve any perturbations.
The estimate $\bar{\theta}_{t}$ is only based on the sequence of pulled arms $\{X_{l}\}_{l=1}^{t-1}$ and observed rewards $\{Y_{l}\}_{l=1}^{t-1}$.
Next, we need the following lemma to upper bound the distance between neural network output and linear approximation $\big|f(X_{t};\theta_{t-1}^{j})-\langle\psi(X_{t}),\bar{\theta}_{t}\rangle\big|$.
The following lemma is adapted from Lemma 4.3 in Jia et al. (2022) and the proof is mostly the same. Note that in our lemma, the probability $\mathbb{P}\big(\mathcal{E}_{2,t}^{j}\big)$ is not conditioned on the history of the perturbations.

###### Lemma C.4 .

For each model $j\in[m]$, define a sequence of events $\mathcal{E}_{2,t}^{j}$ as follows:

$$ $\displaystyle\mathcal{E}_{2,t}^{j}=\Big\{\forall X_{t}\in\mathcal{X},\big|f(X_{t};\theta_{t-1}^{j})-\langle g(X_{t};\theta_{0}),A_{t}^{-1}\bar{\mathbf{b}}_{t}/\sqrt{N}\rangle\big|\leq\epsilon(N)+\beta_{t}||g(X_{t};\theta_{0})||_{A_{t}^{-1}}\Big\},$ $$

where $\beta_{t}$ is a scalar scale of the deviation, and $\epsilon(N)$ is defined as

$$ $\displaystyle\epsilon(N)=$ $\displaystyle C_{\epsilon,1}N^{-1/6}T^{2/3}\lambda^{-2/3}L^{3}\sqrt{\text{log}\,N}+C_{\epsilon,2}(1-\eta N\lambda)^{J}\sqrt{TL/\lambda}$ (C.4) $\displaystyle+C_{\epsilon,3}N^{-1/6}T^{5/3}\lambda^{-5/3}L^{4}\sqrt{\text{log}\,N}\big(1+\sqrt{T/\lambda}\big),$ $$

where $\eta$ is learning rate, $J$ is the number of steps for gradient descent in neural network learning, $\{C_{i}\}_{i=1}^{3}$ are constants.
Then, there exist positive constants $\{C_{i}\}_{i=1}^{3}$, such that with step size $\eta$ and the neural network satisfy the following conditions:

$$ $\displaystyle\eta$ $\displaystyle=C_{1}(N\lambda+NLT)^{-1},$ $\displaystyle N$ $\displaystyle\geq C_{2}\sqrt{\lambda}L^{-3/2}\big[\text{log}(TKL^{2}/\delta)\big]^{3/2},$ $\displaystyle N[\text{log}N]^{-3}$ $\displaystyle\geq C_{3}\,\text{max}\big\{TL^{12}\lambda^{-1},T^{7}\lambda^{-8}L^{18}(\lambda+LT)^{6},L^{21}T^{7}\lambda^{-7}(1+\sqrt{T/\lambda})^{6}\big\},$ $$

and set $\beta_{t}$ as

$$ $\beta_{t}=\sigma_{R}\sqrt{4\text{log}t+2\text{log}K},$ (C.5) $$

where $A_{K}$ is the covariance matrix constructed after the initial $K$-round arm pulling, and $\lambda_{K}(A_{K})$ represents the $K$-th largest eigenvalue of matrix $A_{K}$,
we have $\mathbb{P}\big(\mathcal{E}_{2,t}^{j}\big)\geq 1-t^{-2}$.

Recall that the perturbations $Z_{t}^{j}$ are sampled from $\mathcal{N}(0,\sigma_{R})$, thus $\beta_{t}$ reflects the deviation caused by perturbations.
After uniformly randomly choosing model $j_{t}\in[m]$ from the ensemble, we further define the event for round $t$:

$$ $\displaystyle\mathcal{E}_{2,t}=\Big\{\forall X_{t}\in\mathcal{X},\big|f(X_{t};\theta_{t-1}^{j_{t}})-\langle g(X_{t};\theta_{0}),A_{t}^{-1}\bar{\mathbf{b}}_{t}/\sqrt{N}\rangle\big|\leq\epsilon(N)+\beta_{t}||g(X_{t};\theta_{0})||_{A_{t}^{-1}}\Big\},$ $$

Then, at round $t$, we have the probability for $\mathcal{E}_{2,t}$ as:

$$ $\displaystyle\mathbb{P}\big(\mathcal{E}_{2,t}\big)=\sum_{j=1}^{m}\mathbb{P}\big(j_{t}=j,\mathcal{E}_{2,t}^{j}\big)\geq 1-\frac{1}{t^{2}}.$ $$

Next, we present the optimism condition (anti-concentration) in the following two lemmas.
First, we fix the sequence of pulled arms $\{X_{l}\}_{l=1}^{t}$ and model $j\in[m]$, the only source of randomness is the perturbations $\{Z_{l}^{j}\}$, we can apply tail bound of Gaussian distribution to lower bound the probability of optimism.
Next, we add randomness of choosing arm $j_{t}$ at round $t$, and apply the Azuma-Hoeffding inequality.
Finally, we count equivalent sequences of $\{X_{l}\}_{l=1}^{t}$ and prove the probability of optimism considering all randomness of the procedure.

###### Lemma C.5 .

Fix the model $j\in[m]$.
For any $t\in[T]$, fix the sequence of pulled arms $\{X_{l}\}_{l=1}^{t}$.
Define a sequence of events $\mathcal{E}_{3,t}^{j}$ as follows:

$$ $\displaystyle\mathcal{E}_{3,t}^{j}:=\Big\{f(X_{t};\theta_{t-1}^{j})\geq h(X^{*})-\epsilon(N)\Big\}.$ $$

Then, by choosing variance of perturbations $\sigma_{R}$ as

$$ $\displaystyle\sigma_{R}=\alpha_{T}(1-\lambda\lambda_{K}^{-1}(A_{K}))^{-1/2},$ (C.6) $$

we have $\mathbb{P}\big(\mathcal{E}_{t,3}^{j}\big)\geq(4e\sqrt{\pi})^{-1}=:p_{N}^{\prime}$.

###### Lemma C.6 .

Fix the ensemble size $m$ as

$$ $\displaystyle m\geq\frac{2}{p_{N}^{\prime 2}}\Big(K\text{log}T+\text{log}\frac{1}{\delta}\Big).$ $$

Define a sequence of events $\mathcal{E}_{3,t}$ as follows:

$$ $\displaystyle\mathcal{E}_{3,t}:=\Big\{f(X_{t};\theta_{t-1}^{j_{t}})\geq h(X^{*})-\epsilon(N)\Big\}.$ $$

Then, for any $t\in[T]$, we have $\mathbb{P}\big(\mathcal{E}_{3,t}\big)\geq p_{N}^{\prime}/2$.

Finally, we need the following lemma to calculate the summation.

###### Lemma C.7 (Lemma 4.6 in Jia et al. ( 2022 ) ) .

With $\widetilde{d}$ as the effective dimension of the NTK matrix $\mathbf{H}$, we have

$$ $\sum_{t=1}^{T}\text{min}\Big\{\ ||g(X_{t};\theta_{0})/\sqrt{N}||_{A_{t-1}^{-1}}^{2},1\Big\}\leq 2\big(\widetilde{d}\,\text{log}(1+TK/\lambda)+1\big).$ (C.7) $$

###### Assumption C.1 .

###### Lemma C.2 .

###### Lemma C.3 .

###### Lemma C.4 .

###### Lemma C.5 .

###### Lemma C.6 .

###### Lemma C.7 (Lemma 4.6 in Jia et al. ( 2022 ) ) .

### C.3 Regret Analysis

From the design of the algorithm, we use the first $K$ rounds to pull each arm once, thus the cumulative regret can be decomposed as

$$ $\displaystyle R(T)\leq\sum_{t=K+1}^{T}\big(h(X^{*})-h(X_{t})\big)+K.$ $$

Next, we analyze the per-round regret bound for $t\in[K+1,T]$.
We assume that $\mathcal{E}_{1,t}$ holds for the rest of the analysis.
For each round $t$, the regret can be written as

$$ $\displaystyle h(X^{*})-h(X_{t})\leq\big(h(X^{*})-h(X_{t})\big)\operatorname*{\mathds{1}}\{\mathcal{E}_{t,2}\}+\mathbb{P}\big(\bar{\mathcal{E}}_{t,2}\big),$ $$

where we used the assumption that $h(X)$ in bounded in $[0,1]$.
From the technical lemmas, $\mathbb{P}\big(\bar{\mathcal{E}}_{t,2}\big)\sim t^{-2}$, thus we only need to focus on $\big(h(X^{*})-h(X_{t})\big)$ under events $\mathcal{E}_{t,1}\cap\mathcal{E}_{t,2}$.

For the following analysis, we introduce the set of sufficiently sampled arms in round $t$:

$$ $\displaystyle\Omega_{t}=\big\{\forall X_{t}\in{\mathcal{X}}:2\epsilon(N)+(\alpha_{t}+\beta_{t})||g(X_{t};\theta_{0})||_{A_{t}^{-1}}\leq h(X^{*})-h(X_{t})\big\}.$ $$

We also define the set of under-sampled arms $\bar{\Omega}_{t}=\mathcal{X}\backslash\Omega_{t}$.
From the definition, the per-round regret of $X_{t}\in\bar{\Omega}_{t}$ is bounded by $\big(2\epsilon(N)+(\alpha_{t}+\beta_{t})||g(X_{t};\theta_{0})||_{A_{t}^{-1}}\big)$, we expect that the pulled arm $X_{t}$ should come from $\bar{\Omega}_{t}$ with high probability as the algorithm proceeds.
We further define the least uncertain and under-sampled arm $X_{t}^{(e)}$ at round $t$ as

$$ $X_{t}^{(e)}=\text{argmin}_{X\in\bar{\Omega}_{t}}||g(X;\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}.$ (C.8) $$

Now we can write the per-round regret

$$ $\displaystyle\big(h(X^{*})-h(X_{t})\big)\operatorname*{\mathds{1}}\{\mathcal{E}_{2,t}\}$ $\displaystyle=$ $\displaystyle\big(h(X^{*})-h(X_{t}^{(e)})+h(X_{t}^{(e)})-h(X_{t})\big)\operatorname*{\mathds{1}}\{\mathcal{E}_{2,t}\}$ $\displaystyle\leq$ $\displaystyle\bigg(2\epsilon(N)+(\alpha_{t}+\beta_{t})||g(X_{t};\theta_{0})||_{A_{t}^{-1}}\bigg)+\bigg(h(X_{t}^{(e)})-h(X_{t})\bigg)\operatorname*{\mathds{1}}\{\mathcal{E}_{2,t}\}$ $\displaystyle\leq$ $\displaystyle\,4\epsilon(N)+(\alpha_{t}+\beta_{t})\big(2||g(X_{t}^{(e)};\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}+||g(X_{t};\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}\big)$ $$

From the per-round regret bound, we should upper bound $||g(X_{t}^{(e)};\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}$ using expression of $||g(X_{t};\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}$, then we can apply [Lemma˜C.7](https://arxiv.org/html/2510.10730v1#A3.Thmtheorem7) to compute the cumulative regret.
We have the following result

$$ $\displaystyle||g(X_{t};\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}\geq||g(X_{t}^{(e)};\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}\mathbb{P}\big(X_{t}\in\bar{\Omega}_{t}\big),$ $\displaystyle\Rightarrow$ $\displaystyle||g(X_{t}^{(e)};\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}\leq\frac{||g(X_{t};\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}}{\mathbb{P}(X_{t}\in\bar{\Omega}_{t})}.$ $$

As mentioned previously, we should lower bound the probability of $\mathbb{P}(X_{t}\in\bar{\Omega}_{t})$.

$$ $\displaystyle\mathbb{P}(X_{t}\in\bar{\Omega}_{t})\geq$ $\displaystyle\,\mathbb{P}\big(\exists X\in\bar{\Omega}_{t}:f(X;\theta_{t})>\text{max}_{X^{\prime}\in\Omega_{t}}f(X^{\prime};\theta_{t})\big)$ $\displaystyle\geq$ $\displaystyle\,\mathbb{P}\big(f(X^{*};\theta_{t})>\text{max}_{X^{\prime}\in\Omega_{t}}f(X^{\prime};\theta_{t}),\mathcal{E}_{2,t}\big)$ $\displaystyle\geq$ $\displaystyle\,\mathbb{P}\big(f(X^{*};\theta_{t})>h(X^{*})-\epsilon(N)\big)-\mathbb{P}\big(\bar{\mathcal{E}}_{2,t}\big)$ $\displaystyle\geq$ $\displaystyle\,\mathbb{P}\big(\mathcal{E}_{3,t}\big)-\mathbb{P}\big(\bar{\mathcal{E}}_{2,t}\big).$ $$

Therefore, the per-round regret can be bounded as

$$ $\displaystyle h(X^{*})-h(X_{t})\leq\mathbb{P}\big(\bar{\mathcal{E}}_{2,t}\big)+4\epsilon(N)+(\alpha_{t}+\beta_{t})\Big(1+\frac{2}{\mathbb{P}\big(\mathcal{E}_{3,t}\big)-\mathbb{P}\big(\bar{\mathcal{E}}_{2,t}\big)}\Big)||g(X_{t};\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}.$ $$

Now we sum up the per-round regret bound and compute the cumulative regret $R(T)$.
From [Lemma˜C.3](https://arxiv.org/html/2510.10730v1#A3.Thmtheorem3), $\mathcal{E}_{1,t}$ holds for all $t\in[T]$ with probability at least $1-\delta$, thus we can compute the summation under $\cap_{t=1}^{T}\mathcal{E}_{1,t}$ as follows.

$$ $\displaystyle R(T)\operatorname*{\mathds{1}}\{\cap_{t=1}^{T}\mathcal{E}_{1,t}\}$ $\displaystyle\leq$ $\displaystyle\,K+4T\epsilon(N)+\sum_{t=K+1}^{T}\mathbb{P}\big(\bar{\mathcal{E}}_{2,t}\big)+(\alpha_{t}+\beta_{t})\Big(1+\frac{2}{\mathbb{P}\big(\mathcal{E}_{3,t}\big)-\mathbb{P}\big(\bar{\mathcal{E}}_{2,t}\big)}\Big)||g(X_{t};\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}$ $$

For $\mathbb{P}\big(\bar{\mathcal{E}}_{2,t}\big)$, we have the following bound:

$$ $\displaystyle\sum_{t=K+1}^{T}\mathbb{P}\big(\bar{\mathcal{E}}_{2,t}\big)\leq\sum_{t=K+1}^{T}\frac{1}{t^{2}}\leq\frac{\pi^{2}}{6}.$ $$

From $\mathbb{P}\big(\mathcal{E}_{3,t}\big)\geq p_{N}^{\prime}/2$, we have

$$ $\displaystyle 1+\frac{2}{\mathbb{P}\big(\mathcal{E}_{3,t}\big)-\mathbb{P}\big(\bar{\mathcal{E}}_{2,t}\big)}\leq 1+\frac{8}{p_{N}^{\prime}}.$ $$

Combining these results, we have

$$ $\displaystyle R(T)\leq$ $\displaystyle\,K+4T\epsilon(N)+\frac{\pi^{2}}{6}+\Big(1+\frac{8}{p_{N}^{\prime}}\Big)(\alpha_{T}+\beta_{T})\sum_{t=K+1}^{T}||g(X_{t};\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}$ $\displaystyle\leq$ $\displaystyle\,K+4T\epsilon(N)+\frac{\pi^{2}}{6}+2\Big(1+\frac{8}{p_{N}^{\prime}}\Big)(\alpha_{T}+\beta_{T})\big(\widetilde{d}\,\text{log}(1+TK/\lambda)+1\big)$ $\displaystyle=$ $\displaystyle\,\widetilde{\mathcal{O}}(\widetilde{d}\sqrt{T}),$ $$

with probability at least $1-\delta$.

## Appendix D Proof of Technical Lemmas in Neural-ES

### D.1 Proof of Lemma ˜ C.5

Under event $\mathcal{E}_{1,t}\cap\mathcal{E}_{2,t}^{j}$, we have

$$ $\displaystyle h(X_{t})\geq\langle g(X_{t};\theta_{0}),A_{t}^{-1}\bar{\mathbf{b}}_{t}/\sqrt{N}\rangle-\alpha_{t}||g(X_{t};\theta_{0})||_{A_{t}^{-1}},$ $$

Therefore, we have the following sufficient condition for optimism $f(X_{t};\theta_{t}^{j})>h(X^{*})-\epsilon(N)$:

$$ $\langle g(X_{t};\theta_{0}),A_{t}^{-1}\mathbf{b}_{t}/\sqrt{N}\rangle\geq\langle g(X_{t};\theta_{0}),A_{t}^{-1}\bar{\mathbf{b}}_{t}/\sqrt{N}\rangle+\alpha_{t}||g(X_{t};\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}.$ (D.1) $$

From the definitions of covariance matrix and auxiliary vectors, we have

$$ $\langle g(X_{t};\theta_{0}),A_{t}^{-1}(\mathbf{b}_{t}-\bar{\mathbf{b}}_{t})/\sqrt{N}\rangle=\frac{1}{N}\sum_{l=1}^{t}Z_{l}^{j}g(X_{l};\theta_{0})^{\top}A_{t}^{-1}g(X_{l};\theta_{0})=:U_{t}.$ (D.2) $$

Fix the sequence of pulled arms $\{X_{l}\}_{l=1}^{t}$, then the only randomness comes from the perturbation sequence $\{Z_{l}^{j}\}_{l=1}^{t}$.
Since the perturbations are i.i.d., we can use the following tail bound:

$$ $\displaystyle\mathbb{P}\Big(\frac{X-\mu}{\sigma}>\beta\Big)\geq\frac{\text{exp}(-\beta^{2})}{4\sqrt{\pi}\beta}.$ $$

The mean of $U_{t}$ is zero, the variance is bounded by

$$ $\displaystyle\text{Var}[U_{t}]\geq\sigma_{R}^{2}(1-\lambda\lambda_{K}^{-1}(A_{K}))||g(X_{t};\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}^{2}.$ $$

Therefore, by choosing variance of perturbation

$$ $\displaystyle\sigma_{R}=\alpha_{t}\big(1-\lambda\lambda_{K}^{-1}(A_{K})\big)^{-1/2},$ $$

we have the probability of optimism:

$$ $\mathbb{P}\bigg(f(X_{t};\theta_{t})>h(X^{*})-\epsilon(N)\bigg)\geq\mathbb{P}\bigg(U_{t}>\alpha_{t}||g(X_{t};\theta_{0})/\sqrt{N}||_{A_{t}^{-1}}\bigg)\geq\frac{1}{4e\sqrt{\pi}}.$ (D.3) $$

### D.2 Proof of Lemma ˜ C.6

Define random variable $I_{t}^{j}$ for round $t$ and model $j$ as $I_{t}^{j}=\operatorname*{\mathds{1}}\{\mathcal{E}_{3,t}^{j}\}$. Then, from previous technical lemmas, we have $\mathbb{P}\big(I_{t}^{j}=1)\geq p_{N}^{\prime}$.
For each round $t$, we further define $I_{t}=I_{t}^{j_{t}}$. After uniformly choosing the model $j\in[m]$, we have

$$ $\mathbb{P}\big(I_{t}=1\big)=\frac{1}{m}\sum_{j=1}^{m}\mathbb{P}\big(I_{t}^{j}=1).$ (D.4) $$

Apply Azuma-Hoeffding inequality, we have the following probability of optimism:

$$ $\mathbb{P}\Big(\frac{1}{m}\sum_{j=1}^{m}I_{t}^{j}<\frac{p_{N}^{\prime}}{2}\Big)\leq\text{exp}\Big(-\frac{p_{N}^{\prime 2}m}{2}\Big).$ (D.5) $$

Following the discussions in Lee and Oh (2024), we have the following lemma, which is adapted from Claim 1 in their paper.

###### Lemma D.1 .

There exists an event $\mathcal{E}^{*}$ such that under $\mathcal{E}^{*}$, $\frac{1}{m}\sum_{j=1}^{m}I_{t}^{j}\geq p_{N}^{\prime}/2$ holds for all $t\in[T]$, and $\mathbb{P}\big(\bar{\mathcal{E}}^{*}\big)\leq T^{K}\text{exp}\big(-p_{N}^{\prime 2}m/2\big)$.

Therefore, setting ensemble size as follows:

$$ $\displaystyle m\geq\frac{2}{p_{N}^{\prime 2}}\Big(K\text{log}T+\text{log}\frac{1}{\delta}\Big),$ $$

then we have $\mathbb{P}(\mathcal{E}^{*})\geq 1-\delta$.
In summary, by setting the ensemble size $m=\Omega(K\text{log}T)$, we have

$$ $\mathbb{P}(\mathcal{E}_{3,t})=\mathbb{P}\big(f(X_{t};\theta_{t-1}^{j_{t}})\geq h(X^{*})-\epsilon(N)\,|\,\mathcal{F}_{t-1},\mathcal{E}_{t,1}\big)\geq p_{N}^{\prime}/2.$ (D.6) $$

###### Lemma D.1 .

## Appendix E Analysis of Doubling Trick

In this section, we provide theoretical analysis of regret bound with doubling trick.
To preserve the asymptotic regret bound of ensemble sampling, we need to properly set the schedule $\{T_{i}\}$.
We need the following result of the regret bound of doubling trick.

###### Lemma E.1 (Theorem 4 in Besson and Kaufmann ( 2018 ) ) .

If an algorithm $\mathcal{A}$ satisfies $R_{T}(\mathcal{A}_{T})\leq cT^{\gamma}(\text{log}T)^{\delta}+f(T)$, for $0<\gamma<1$, $\delta\geq 0$ and for $c>0$, and an increasing function $f(t)=o(t^{\gamma}(\text{log}t)^{\delta})$ (at $t\rightarrow\infty$), then the anytime version $\mathcal{A^{\prime}}:=\mathcal{DT}(\mathcal{A},(T_{i})_{i\in\mathbb{N}})$ with the geometric sequence $(T_{i})_{i\in\mathbb{N}}$ of parameters $T_{0}\in\mathbb{N}^{*}$, $b>1$ (i.e., $T_{i}=\lfloor T_{0}b^{i}\rfloor$) with the condition $T_{0}(b-1)>1$ if $\delta>0$, satisfies,

$$ $\displaystyle R_{T}(\mathcal{A}^{\prime})\leq l(\gamma,\delta,T_{0},b)cT^{\gamma}(\text{log}T)^{\delta}+g(T),$ $$

with a increasing function $g(t)=o(t^{\gamma}(\text{log}t)^{\delta})$, and a constant loss $l(\gamma,\delta,T_{0},b)>1$,

$$ $\displaystyle l(\gamma,\delta,T_{0},b):=\bigg(\frac{\text{log}(T_{0}(b-1)+1)}{\text{log}(T_{0}(b-1))}\bigg)^{\delta}\times\frac{b^{\gamma}(b-1)^{\gamma}}{b^{\gamma}-1}.$ $$

With [Lemma˜E.1](https://arxiv.org/html/2510.10730v1#A5.Thmtheorem1), the regret bound analysis is straightforward.
From the regret bound of ensemble sampling, the dependency on $T$ is given by $\mathcal{O}\Big((\text{log}T)^{\frac{3}{2}}\sqrt{T}\Big)$.
Therefore, apply [Lemma˜E.1](https://arxiv.org/html/2510.10730v1#A5.Thmtheorem1) to ensemble sampling algorithms (GLM-ES or Neural-ES), we have $\gamma=1/2$, $\delta=3/2$.
We can minimize the expression of $l(\gamma,\delta,T_{0},b)$ by properly selecting the parameter of the doubling sequence $T_{0}$ and $b$.
The optimal choice of $b$ is $(3+\sqrt{5})/2\approx 2.6$ and we can choose $T_{0}$ large enough to reduce the other factor.
For example, if we choose $T_{0}=100$, the extra factor $l(\gamma,\delta,T_{0},b)\approx 3.3$.

From the discussions above, we can choose the sequence

$$ $\displaystyle\{T_{i}\}=\{T_{0},\,T_{0}b,\,T_{0}b^{2},...\}.$ $$

The number of rounds follows the sequence:

$$ $\displaystyle\{\tau_{i}\}=\{T_{0},\,T_{0}(b-1),\,T_{0}(b-1)b,\,T_{0}(b-1)b^{2},...\}.$ $$

From the discussions above, by directly applying doubling trick, we obtain the same asymptotic regret bound with the cost of a constant factor.

###### Lemma E.1 (Theorem 4 in Besson and Kaufmann ( 2018 ) ) .

## References

- Abbasi-Yadkori et al. (2011)
Abbasi-Yadkori, Y., Pál, D. and Szepesvári, C. (2011).
Improved algorithms for linear stochastic bandits.
Advances in Neural Information Processing Systems 24 2312–2320.
- Abeille and Lazaric (2017)
Abeille, M. and Lazaric, A. (2017).
Linear thompson sampling revisited.
In International Conference on Artificial Intelligence and Statistics.
- Agrawal and Goyal (2013)
Agrawal, S. and Goyal, N. (2013).
Thompson sampling for contextual bandits with linear payoffs.
In International Conference on Machine Learning. PMLR.
- Agrawal and Goyal (2017)
Agrawal, S. and Goyal, N. (2017).
Near-optimal regret bounds for thompson sampling.
Journal of the ACM (JACM) 64 1–24.
- Atalar and Joe-Wong (2025)
Atalar, B. and Joe-Wong, C. (2025).
Neural combinatorial clustered bandits for recommendation systems.
In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 39.
- Ban et al. (2022)
Ban, Y., Yan, Y., Banerjee, A. and He, J. (2022).
EE-net: Exploitation-exploration neural networks in contextual bandits.
In International Conference on Learning Representations.
- Besson and Kaufmann (2018)
Besson, L. and Kaufmann, E. (2018).
What doubling tricks can and can’t do for multi-armed bandits.
arXiv preprint arXiv:1803.06971 .
- Chu et al. (2011)
Chu, W., Li, L., Reyzin, L. and Schapire, R. (2011).
Contextual bandits with linear payoff functions.
In International Conference on Artificial Intelligence and Statistics.
- Clavier et al. (2024)
Clavier, P., Huix, T. and Oliviero Durmus, A. (2024).
$\mathtt{VITS}$ : Variational inference thompson sampling for contextual bandits.
In International Conference on Machine Learning. Proceedings of Machine Learning Research, PMLR.
- Ding et al. (2021)
Ding, Q., Hsieh, C.-J. and Sharpnack, J. (2021).
An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling.
In International Conference on Artificial Intelligence and Statistics. PMLR.
- Fan and Ming (2021)
Fan, Y. and Ming, Y. (2021).
Model-based reinforcement learning for continuous control with posterior sampling.
In International Conference on Machine Learning. PMLR.
- Fiez et al. (2019)
Fiez, T., Jain, L., Jamieson, K. G. and Ratliff, L. (2019).
Sequential experimental design for transductive linear bandits.
Advances in Neural Information Processing Systems 32.
- Filippi et al. (2010)
Filippi, S., Cappe, O., Garivier, A. and Szepesvári, C. (2010).
Parametric bandits: The generalized linear case.
Advances in Neural Information Processing Systems 23.
- Hsu et al. (2024)
Hsu, H.-L., Wang, W., Pajic, M. and Xu, P. (2024).
Randomized exploration in cooperative multi-agent reinforcement learning.
Advances in Neural Information Processing Systems 37 74617–74689.
- Hwang et al. (2023)
Hwang, T., Chai, K. and Oh, M.-h. (2023).
Combinatorial neural bandits.
In International Conference on Machine Learning. PMLR.
- Ishfaq et al. (2021)
Ishfaq, H., Cui, Q., Nguyen, V., Ayoub, A., Yang, Z., Wang, Z., Precup, D. and Yang, L. (2021).
Randomized exploration in reinforcement learning with general value function approximation.
In International Conference on Machine Learning. PMLR.
- Ishfaq et al. (2024a)
Ishfaq, H., Lan, Q., Xu, P., Mahmood, A. R., Precup, D., Anandkumar, A. and Azizzadenesheli, K. (2024a).
Provable and practical: Efficient exploration in reinforcement learning via langevin monte carlo.
In International Conference on Learning Representations.
- Ishfaq et al. (2024b)
Ishfaq, H., Tan, Y., Yang, Y., Lan, Q., Lu, J., Mahmood, A. R., Precup, D. and Xu, P. (2024b).
More efficient randomized exploration for reinforcement learning via approximate sampling.
Reinforcement Learning Journal 3 1211–1235.
- Jacot et al. (2018)
Jacot, A., Gabriel, F. and Hongler, C. (2018).
Neural tangent kernel: Convergence and generalization in neural networks.
Advances in Neural Information Processing Systems 31.
- Janz et al. (2024a)
Janz, D., Litvak, A. and Szepesvári, C. (2024a).
Ensemble sampling for linear bandits: small ensembles suffice.
Advances in Neural Information Processing Systems 37 23679–23704.
- Janz et al. (2024b)
Janz, D., Liu, S., Ayoub, A. and Szepesvári, C. (2024b).
Exploration via linearly perturbed loss minimisation.
In International Conference on Artificial Intelligence and Statistics. PMLR.
- Jia et al. (2022)
Jia, Y., ZHANG, W., Zhou, D., Gu, Q. and Wang, H. (2022).
Learning neural contextual bandits through perturbed rewards.
In International Conference on Learning Representations.
- Jin et al. (2021)
Jin, T., Xu, P., Shi, J., Xiao, X. and Gu, Q. (2021).
Mots: Minimax optimal thompson sampling.
In International Conference on Machine Learning. PMLR.
- Jin et al. (2023)
Jin, T., Yang, X., Xiao, X. and Xu, P. (2023).
Thompson sampling with less exploration is fast and optimal.
In International Conference on Machine Learning. PMLR.
- Jun et al. (2021)
Jun, K.-S., Jain, L., Mason, B. and Nassif, H. (2021).
Improved confidence bounds for the linear logistic model and applications to bandits.
In International Conference on Machine Learning. PMLR.
- Kveton et al. (2020a)
Kveton, B., Szepesvári, C., Ghavamzadeh, M. and Boutilier, C. (2020a).
Perturbed-history exploration in stochastic linear bandits.
In Uncertainty in Artificial Intelligence. PMLR.
- Kveton et al. (2020b)
Kveton, B., Zaheer, M., Szepesvari, C., Li, L., Ghavamzadeh, M. and Boutilier, C. (2020b).
Randomized exploration in generalized linear bandits.
In International Conference on Artificial Intelligence and Statistics. PMLR.
- Lattimore and Szepesvári (2020)
Lattimore, T. and Szepesvári, C. (2020).
Bandit algorithms.
Cambridge University Press.
- Lee and Oh (2024)
Lee, H. and Oh, M.-h. (2024).
Improved regret of linear ensemble sampling.
Advances in Neural Information Processing Systems 37 92803–92831.
- Lee et al. (2024)
Lee, J., Yun, S.-Y. and Jun, K.-S. (2024).
A unified confidence sequence for generalized linear models, with applications to bandits.
In Advances in Neural Information Processing Systems.
- Li et al. (2017)
Li, L., Lu, Y. and Zhou, D. (2017).
Provably optimal algorithms for generalized linear contextual bandits.
In International Conference on Machine Learning. PMLR.
- Liu (2023)
Liu, S. (2023).
Perturbed history exploration in stochastic subgaussian generalized linear bandits.
URL [https://doi.org/10.7939/r3-qyft-hk37](https://doi.org/10.7939/r3-qyft-hk37)
- Liu et al. (2024)
Liu, S., Ayoub, A., Sentenac, F., Tan, X. and Szepesvári, C. (2024).
Almost free: Self-concordance in natural exponential families and an application to bandits.
Advances in Neural Information Processing Systems 37 70828–70874.
- Lu and Van Roy (2017)
Lu, X. and Van Roy, B. (2017).
Ensemble sampling.
Advances in Neural Information Processing Systems 30.
- Mazumdar et al. (2020)
Mazumdar, E., Pacchiano, A., Ma, Y., Jordan, M. and Bartlett, P. (2020).
On approximate thompson sampling with langevin algorithms.
In International Conference on Machine Learning. PMLR.
- Nguyen-Tang et al. (2022)
Nguyen-Tang, T., Gupta, S., Nguyen, A. T. and Venkatesh, S. (2022).
Offline neural contextual bandits: Pessimism, optimization and generalization.
In International Conference on Learning Representations.
- Osband et al. (2016)
Osband, I., Blundell, C., Pritzel, A. and Van Roy, B. (2016).
Deep exploration via bootstrapped dqn.
Advances in Neural Information Processing Systems 29.
- Osband et al. (2013)
Osband, I., Russo, D. and Van Roy, B. (2013).
(more) efficient reinforcement learning via posterior sampling.
Advances in Neural Information Processing Systems 26.
- Pukelsheim (2006)
Pukelsheim, F. (2006).
Optimal design of experiments.
SIAM.
- Qin et al. (2022)
Qin, C., Wen, Z., Lu, X. and Van Roy, B. (2022).
An analysis of ensemble sampling.
Advances in Neural Information Processing Systems 35 21602–21614.
- Salgia (2023)
Salgia, S. (2023).
Provably and practically efficient neural contextual bandits.
In International Conference on Machine Learning. PMLR.
- Sasso et al. (2023)
Sasso, R., Conserva, M. and Rauber, P. (2023).
Posterior sampling for deep reinforcement learning.
In International Conference on Machine Learning. PMLR.
- Sawarni et al. (2024)
Sawarni, A., Das, N., Barman, S. and Sinha, G. (2024).
Generalized linear bandits with limited adaptivity.
Advances in Neural Information Processing Systems 37 8329–8369.
- Sun and Tran-Dinh (2019)
Sun, T. and Tran-Dinh, Q. (2019).
Generalized self-concordant functions: a recipe for newton-type methods.
Mathematical Programming 178 145–213.
- Thompson (1933)
Thompson, W. R. (1933).
On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.
Biometrika 25 285–294.
- Varatharajah and Berry (2022)
Varatharajah, Y. and Berry, B. (2022).
A contextual-bandit-based approach for informed decision-making in clinical trials.
Life 12 1277.
- Wang et al. (2025a)
Wang, S., Bian, S., Liu, X. and Shao, Z. (2025a).
Neural constrained combinatorial bandits.
IEEE Transactions on Networking 33 1543–1558.
- Wang et al. (2025b)
Wang, W., Zheng, H., Lin, G., Deng, W. and Xu, P. (2025b).
Rethinking langevin thompson sampling from a stochastic approximation perspective.
arXiv preprint arXiv:2510.05023 .
- Xu et al. (2022a)
Xu, P., Wen, Z., Zhao, H. and Gu, Q. (2022a).
Neural contextual bandits with deep representation and shallow exploration.
In International Conference on Learning Representations.
- Xu et al. (2022b)
Xu, P., Zheng, H., Mazumdar, E. V., Azizzadenesheli, K. and Anandkumar, A. (2022b).
Langevin monte carlo for contextual bandits.
In International Conference on Machine Learning. PMLR.
- Zhang et al. (2021)
Zhang, W., Zhou, D., Li, L. and Gu, Q. (2021).
Neural thompson sampling.
In International Conference on Learning Representations.
- Zhang et al. (2025)
Zhang, Y.-J., Xu, S.-A., Zhao, P. and Sugiyama, M. (2025).
Generalized linear bandits: Almost optimal regret with one-pass update.
arXiv preprint arXiv:2507.11847 .
- Zheng et al. (2024)
Zheng, H., Deng, W., Moya, C. and Lin, G. (2024).
Accelerating approximate thompson sampling with underdamped langevin monte carlo.
In International Conference on Artificial Intelligence and Statistics. PMLR.
- Zhou et al. (2020)
Zhou, D., Li, L. and Gu, Q. (2020).
Neural contextual bandits with ucb-based exploration.
In International Conference on Machine Learning. PMLR.
- Zhu and Van Roy (2023)
Zhu, Z. and Van Roy, B. (2023).
Deep exploration for recommendation systems.
In Proceedings of the 17th ACM Conference on Recommender Systems.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 4
presentation: 3
questions: 1.Could the authors provide a more systematic sensitivity and ablation analysis covering ensemble size, regularization, perturbation variance, and the anytime schedule (e.g., base segment length and growth factor), including both regret and runtime/memory effects?
2.For Neural-ES, do the computational and theoretical advantages extend beyond small MLPs to wider/deeper networks commonly used in practice (e.g., larger MLPs or transformer backbones), and what concrete width/optimization regimes are required for the stated guarantees to remain valid?

The evaluation uses synthetic environments, which is standard for this area but leaves open how the approach behaves in more complex or real-world contexts (e.g., with changing action sets, larger feature spaces, or modern neural architectures).
soundness: 3
strengths: The framework unifies randomized exploration across linear and nonlinear bandits with a single, conceptually clean recipe that reuses historical perturbations to keep updates inexpensive. The theory is clearly presented and provides high-probability guarantees, together with an anytime extension that is simple and practical. The GLM instantiation reduces the warm-up complexity relative to prior perturb-and-estimate methods, and the paper is generally well written and organized.
summary: This paper introduces Provable Anytime Ensemble Sampling, a unified framework for ensemble sampling in nonlinear contextual bandits with two concrete instantiations: Generalized Linear Model Ensemble Sampling (GLM-ES) and Neural Ensemble Sampling (Neural-ES), and extends both to the anytime setting via a doubling-trick schedule. The core mechanism is randomized exploration through reward perturbation while reusing past perturbations so that per-round computation remains constant. Under a fixed and finite action set with bounded features, the authors derive high-probability regret guarantees for GLM-ES (under M-self-concordance and a positive lower bound on the link derivative over the working domain) and for Neural-ES (under neural tangent kernel conditions for sufficiently wide networks). The anytime variants achieve the same asymptotic regret up to a constant factor, and experiments on linear, logistic, distance, and quadratic synthetic environments show competitive cumulative regret with noticeably reduced computational cost and no need to know the time horizon in advance.
weaknesses: The empirical setup lists hyper-parameter choices and network sizes but gives little justification for why these values were selected, and it lacks systematic sensitivity/ablation results for ensemble size, regularization, perturbation variance, or the anytime schedule. Neural experiments are limited to a small multilayer perceptron, so it remains unclear whether the computational and statistical behavior persists for wider/deeper architectures used in practice. 

Several modeling assumptions that are central to the guarantees (fixed finite action set, bounded features, GLM regularity, and wide-network/NTK-style training for Neural-ES) are not emphasized in the discussion of applicability. The paper would also benefit from clarifying the data-generation details in the synthetic environments (e.g., how the unknown parameter and action features are sampled) and from commenting on the ensemble size scaling with the number of actions, which may be large in real applications.

---

confidence: 4
contribution: 3
initial_rating: 4
presentation: 2
questions: 1. In Remark 5.4, the authors state that the expected Gram matrix is not necessarily assumed to have a positive minimum eigenvalue. However, under this case, how is the existence of the optimal design distribution (\zeta) guaranteed?

2. Neural-ES employs a different warm-up procedure from GLM-ES. What allows Neural-ES—despite dealing with a more general reward model—to avoid the complex warm-up required in the GLM-ES setting?

3. How does the MLE concentration result in Lemma A.3 differ from Lemma A.2 in Sawarni et al. (2024)?

4. The doubling trick (Besson & Kaufmann, 2018) is a well-established approach in online learning to handle unknown $T$, with known regret bounds. How does the result in this paper differ from the standard doubling-trick analyses already available in the literature?

5. In line 1244t, the sufficient condition for optimism is written by $H_t$, but it was changed to $\bar{H}_t$ in Eq. (B.8). Could you explain the process in a little detail?
soundness: 3
strengths: 1. Ensemble sampling has shown strong empirical performance in practice but has primarily been analyzed under linear reward models. This work extends the analysis to more general settings, including GLM and RKHS-bounded reward models, and demonstrates that the proposed algorithm achieves regret bounds matching those of existing linear or randomized algorithms.

2. The paper is clearly written and easy to follow. The literature review and discussion of related work are well-organized and help position the contribution effectively.
summary: This paper proposes an ensemble sampling algorithm for K-armed contextual bandits with non-linear reward models.
Specifically, the authors develop a unified framework that covers both cases where the reward follows a generalized linear model (GLM) with respect to the arm’s context and where the reward function lies in a reproducing kernel Hilbert space (RKHS) with a bounded norm under the neural tangent kernel.
The proposed algorithm achieves regret bounds of $O(d^{3/2} \sqrt{T})$ for GLM rewards, and $O(\tilde{d} \sqrt{T})$ for RKHS-bounded rewards, given an ensemble of size $\Omega(K \log T)$.
Moreover, the paper addresses the case where the total number of rounds $T$ is unknown, employing a doubling trick to establish asymptotic regret guarantees.
The superiority of the proposed algorithm is validated through synthetic experiments.
weaknesses: 1. The notation throughout the paper should be carefully reviewed. For example, 
- context feature is denoted by both $x$ and $X$ in different places
- $H_t$ is defined as the Hessian of the loss function at time $t$, yet the term $ \|| X_t \|_{H_t^{-1}}$ is used later as a bonus term, which may lead to confusion
- Does this work allow the context to change over time? The main theorem (Thm. 5.5 & 5.7) assumes a fixed arm set ($|\mathcal{X}| \le K$, but the problem setting (line 157) uses a varying arm set.
- Definition of $\theta_t$ in appendix seems missing. 
- By definition, $\theta^\{j\_t}\_t$ is an estimator estimated using data up to time $t$. Then, shouldn't the behavior of $X_t^\top \theta^{j\_t}\_{t-1}$ be analyzed in optimism?

2. The description of the warm-up phase could be expanded. In Remark 4.2, the authors note that while previous GLM-bandit studies use warm-up rounds to ensure the invertibility of the empirical Gram matrix, the proposed method employs them to guarantee constant-probability optimism. Since the purpose differs, it would be helpful to elaborate on how the rounding procedure in Algorithm 3 operates—for example, how it differs from exploring for $\tau$ rounds using the G-optimal design solution $\zeta$ as the policy.

3. Although this issue is not unique to this paper, the neural network size required for Neural-ES appears to be very large (see the condition in Lemma C.4), which may limit the practical applicability of the algorithm.

---

confidence: 4
contribution: 2
initial_rating: 2
presentation: 1
questions: Minor typos:

- Line 284 width L -> width N

- Lines 1266, 1275 are identical, when I think a different equation is intended for line 1275.

- In the proof for Neural-ES, I think $\theta_ 0$ should be replaced by $\theta_ 0^j$.
soundness: 1
strengths: This is the first theoretical analysis of ensemble sampling beyond the linear contextual bandit setting.
summary: The paper proposes an application of ensemble sampling (Lu & Van Roy, 2017) to GLM bandits and neural bandits.
For the bandit problems with a fixed arm set of size $K$, the proposed method uses $O(K \log T)$ estimators in the ensemble and achieves a $\tilde{O}(d^{3/2}\sqrt{T} + d^{4.5})$ regret bound for GLM bandits and a $\tilde{O}(\tilde{d}\sqrt{T})$ regret bound for neural bandits.
weaknesses: ### 1. Proof requires further clarification

For GLM-ES:

- In Section B.3, the analysis begins with $H_ t$ but ends with $\bar{H}_ t$. The switch happens in line 1280 without any justification. Until line 1280, the analysis requires properties of $H_ t$, and after line 1280, the analysis requires $\bar{H}_ t$, so it doesn't seem to be a simple typo.

- The analysis, especially in Appendix B.4, requires $\sigma_ R \ge b_ 1 + b_ 2 R_ t \sigma_ R$. Tracking the definitions, it seems like $b_ 1 = \tilde{\mathcal{O}}(d)$ and hence $\sigma_ R \gtrsim d$ must hold. However, line 1433 assumes $\sigma_ R \approx (d \log T)^{\frac{1}{2\varepsilon}}$ with $\varepsilon = \frac{2}{3}$, which implies $\sigma_ R \approx (d \log T)^{\frac{3}{4}}$.
The choice of $\varepsilon = \frac{2}{3}$ is also curious, since from Eq. in line 1436, $\varepsilon \rightarrow 1$ would yield a better bound on the warm-up time, although it is still invalid due to the reason above.

- For analyses that use stochastic optimism, one has to show that the conditional probability of optimism is bounded below, conditioned on the history up to the previous time step. However, this paper only shows the lower bound of the total probability. Especially in Appendix B.4, I think the relationship between the shown facts and the conditional probability of optimism should be explained more clearly.

- Lemma A.7 is not proved.

- In line 1055, while the previous equation proves $\ddot{b}(c) \le e \ddot{b}(u)$, it suddenly claims $\ddot{b}(c) \le 2 \ddot{b}(u)$.

- In line 1330, I don't see why $\mathbb{P}(U_ t^\top \mathbf{Z}_ t^j \ge (b_ 1 + b_ 2 R_ t \sigma) \lVert U_ t \rVert_ 2) - \frac{\delta}{T} \ge \frac{p_ N}{2}$ should be true when no relationship between $\delta, T$ and $p_ N$ is given.

For Neural-ES:

- I don't think the proof of Lemma C.4 would be mostly the same as Jia et al. (2022), since the perturbation is not sampled freshly as in Jia et al. (2022).

- The last steps of Appendix C require corrections. $\sum_ {t=K+1}^T \lVert g(X_ t; \theta_ 0) / \sqrt{N} \rVert_ {A_ t^{-1}}$ is not bounded by $\tilde{d}(\log (1 + TK / \lambda) + 1)$.
In the next step, the inequality suddnely jumps to $\tilde{O}(\tilde{d}\sqrt{T})$.
The relationship between $\alpha_ T, \beta_ T$ and $\tilde{d}$ is not clearly shown.

- Line 1617  would make sense only when there is a conditional expectation on the left-hand side with conditional probability on the right-hand side. Even under the expectation, only the lower bound on the total probability is provided and not on the conditional probability.

- Eq. in line 1680 is given without any justification.

- In the proof of Lemma C.5, Eq in line 1666 should present the upper bound of $h(X_ t)$ not the lower bound for the following logic that ensures optimism.

Due to these issues, I am not convinced that the theorems are true.

---

### 2. Slightly misleading presentation

While I acknowledge that some terms could be used loosely, I find the current title, abstract, and the introduction slightly misleading.

- "Contextual bandits" commonly refers to the setting where the reward of the arm, or the arm set itself, changes at every time step. For instance, "linear bandits" would refer to the fixed-arm-set case and "linear contextual bandits" would refer to the changing arm-set case (Lattimore and Szepesvari, 2020). In this work, the contextual setting is introduced as the changing arm-set setting with the arm set denoted as $\mathcal{X}_ t$ in Section 3 Problem Setting. However, it is suddenly replaced by $\mathcal{X}$ starting from line 255, where the G-optimal design is defined, then Theorems 5.5 and 5.7 also assume a fixed finite arm set $|\mathcal{X}| = K$. I don't think the paper should state that they consider the contextual setting. 

- One of the contributions of the paper is proposing an anytime version of ensemble sampling using the doubling trick. However, using the doubling trick for ensemble sampling is already discussed in Remark 3 of Janz et al. (2024a).

- While a lot of works use the term "nonlinear" for the setting with a general function class, this work is limited to GLMs and functions with a small NTK norm. I acknowledge that this point is clear in the abstract and the introduction, and the term could be used flexibly, so this is a minor concern compared to the previous ones.

---

### 3. Missing/misstated definitions

- $\mathcal{X}$ (without the subscript $t$) is not defined.

- $\mathcal{F}_ t$ is not defined within the paper.

- $\eta$ and $J$ are not defined in Lemma C.4. This is because the lemma is adapted from Jia et al. (2022) which trains the neural network with $J$ gradient descents of step size $\eta$, whereas this paper simply finds the minimizer of the loss function.

- The problem setting for GLM states that $Y_ t = \mu(X_ t^\top \theta^* ) + \eta$ with sub-Gaussian $\eta$, however the analysis seems to require that $Y_ t$ follows the natural exponential family distribution and not any sub-Gaussian noise, especially in Appendix A.1.

- At the end of Lemma C.4 (line 1539-1540), the definitions of $A_ K$ and $\lambda_ K$ are given, but are not used within the lemma. I think they should be at the end of Lemma C.5, or the defintion of $\sigma_ R$ in Lemma C.5 should be moved to Lemma C.4.

---

In addition, I see a lot of resemblance to Janz et al. (2024a), Lee & Oh (2024), and Jia et al. (2022) in the appendix, but in some parts, the authors do not mention these papers and proceed. I recommend the authors clearly state where the analysis originally came from, and cite proved results in these papers whenever possible, not just occasionally.

---

confidence: 5
contribution: 2
initial_rating: 6
presentation: 3
questions: 1. Anytime hyperparameters: For the doubling-trick variants, how sensitive are results to $T_0$ and base $b$? Any rule-of-thumb for choosing them beyond the theory constant?

2. Scalability with large $K$ or even continuous actions: Can the framework extend to large or continuous action sets (e.g., via approximate maximization or feature maps), and would the regret proofs still go through?

3. Warm-up guidance (GLM-ES): Beyond the theoretical construction, what’s a simple recipe (iterations, step sizes) that preserves optimism with high probability in practice?
soundness: 3
strengths: 1. Clear problem setting, unified algorithm template (Alg. 1), and concrete GLM/Neural instantiations.

2. The anytime design: Doubling-trick conversion with constant-factor loss, addressing unknown horizon.
summary: This paper presents a unified ensemble sampling framework for nonlinear contextual bandits under two settings: GLM-ES for generalized linear bandits and Neural-ES for neural bandits. The authors provide regret analysis and empirical results on the proposals.
weaknesses: Some over-claims or lack of novelty. The algorithms adapt known ensemble-/perturbed-history ideas to GLM/neural settings; much of the value is synthesis + anytime conversion rather than a fundamentally new exploration principle. (Claims of “first” high-probability bounds are credible but incremental.)


Decision: Reject