1 Introduction↩︎

Contextual bandits form the foundation of modern sequential decision-making problems, driving applications such as recommendation systems, advertising, and interactive information retrieval [1]. Although upper confidence bound (UCB)–based linear contextual bandit algorithms achieve near‑optimal guarantees when rewards are linear in the feature vector [2], many real‑world scenarios exhibit nonlinear reward structures that demand more expressive models. Motivated by this, several approaches have been developed to capture complex reward functions that go beyond the linear case, such as those based on generalized linear models [3], [4], reproducing kernel Hilbert space [5], [6], and deep neural networks [7], [8].

Among these settings, logistic bandits are particularly relevant when the reward is binary (e.g., click vs. no-click); the random reward in each round follows a Bernoulli distribution, whose parameter is determined by the chosen action. Extending logistic bandits via a neural network-based approximation framework, we consider neural logistic bandits and address two significant challenges: (i) handling the nonlinearity of the reward function, characterized by the worst-case variance of a reward distribution \(1/\kappa\) where \(\kappa\) scales exponentially with the size of the decision set, and (ii) controlling the dependence on the feature dimension \(d\), which can be extremely large due to the substantial number of parameters in deep neural networks.

For logistic bandits, [9] introduced a variance-adaptive analysis by incorporating the true reward variance of each action into the design matrix. This avoids using a uniform worst-case variance bound of \(1/\kappa\) for all actions, thus reducing the dependency of the final regret on \(\kappa\). Building on this, [10] achieved the best-known \(\kappa\) dependence. However, both algorithms explicitly rely on the ambient feature dimension \(d\), so their direct extensions to the neural bandit setting induce poor regret performance. On the other hand, [11] derived a regret upper bound for the neural logistic bandit that scales with a data-adaptive effective dimension \(\widetilde{d}\) rather than the full ambient dimension \(d\). This approach offers an improved performance measure as \(d\) increases with the number of parameters in the neural network, often deliberately overparameterized to avoid strong assumptions about the reward function. However, their method still relies on a pessimistic variance estimate, and integrating the variance-aware analysis of [9] into a data-adaptive regret framework remains challenging, resulting in a suboptimal dependence on \(\kappa\).

Motivated by these limitations, we propose algorithms that do not require worst-case estimates in both the variance of the reward distribution and the feature dimension, thus achieving the most favorable regret bound for neural logistic bandits. Central to this approach is our new Bernstein-type self-normalized inequality for vector-valued martingales, which allows us to derive a regret upper bound that scales with the effective dimension \(\widetilde{d}\), and at the same time, matches the best-known dependency on \(\kappa\). Our main contributions are summarized below:

• We tackle the two main challenges in neural logistic bandits: (i) a practical regret upper bound should avoid a direct dependence on \(d\), the ambient dimension of the feature vector, and (ii) it needs to minimize the factor of \(\kappa\), a problem-dependent constant that increases exponentially with the size of the decision set. To address these challenges, we propose a new Bernstein-type tail inequality for self-normalized vector-valued martingales that yields a bound of order \(\widetilde{\mathcal{O}}(\sqrt{\widetilde{d}})\), where \(\widetilde{d}\) is a data-adaptive effective dimension. This is the first tail inequality that achieves favorable results in both respects, while the previous bound of [9] is \(\widetilde{\mathcal{O}}(\sqrt{d})\) which directly depends on \(d\), and that of [11] is \(\widetilde{\mathcal{O}}(\sqrt{\kappa \widetilde{d}})\) that includes an additional factor of \(\sqrt{\kappa}\).

• Based on our tail inequality, we develop our first algorithm, NeuralLog-UCB-1 which guarantees a regret upper bound of order \(\widetilde{O}(\widetilde{d}\sqrt{\kappa T})\). This improves upon the regret upper bound of order \(\widetilde{\mathcal{O}}(\kappa \widetilde{d}\sqrt{T})\) due to [11]. Furthermore, we provide a fully data-adaptive UCB on \(\widetilde{d}\) by adaptively controlling the regularization term of our loss function according to previous observations. Our choice of UCB also avoids the projection step required in the previous approach of [9], which was to constrain the parameters to a certain set during training.

• We propose our second algorithm, NeuralLog-UCB-2, as a refined variant of NeuralLog-UCB-1. We show that NeuralLog-UCB-2 achieves a regret upper bound of \(\widetilde{O}(\widetilde{d}\sqrt{T/\kappa^*})\). This result matches the best-known dependency on \(\kappa\) while avoiding the direct dependence on \(d\) seen in \(\widetilde{O}(d\sqrt{T/\kappa^*})\) given by [10]. The improvement comes from the fact that NeuralLog-UCB-2 replaces the true reward variance within the design matrix with a neural network estimated variance, thereby maintaining sufficient statistics for our variance-adaptive UCB in each round and completely removing the worst-case estimate of variance \(\kappa\). Our numerical results show that NeuralLog-UCB-2 outperforms all baselines, thus validating our theoretical framework.

2 Preliminaries↩︎

Logistic bandits. We consider the contextual logistic bandit problem. Let \(T\) be the total number of rounds. In each round \(t \in [T]\), the agent observes an action set \(\mathcal{X}_t\), consisting of \(K\) contexts drawn from a feasible set \(\mathcal{X}\subset \mathbb{R}^d\). The agent then selects an action \(x_t \in \mathcal{X}_t\) and observes a binary (random) reward \(r_t \in \{0,1\}\). This reward is generated by the logistic model governed by the unknown latent reward function \(h:\mathbb{R}^d \to \mathbb{R}\). Specifically, we define a sigmoid function \(\mu(x) = (1+\exp(-x))^{-1}\) and denote its first and second derivatives as \(\dot{\mu}\) and \(\ddot{\mu}\). Then, the probability distribution of the reward \(r_t\) under action \(x\) is given by \(r_t\sim\text{Bern}(\mu(h(x_t))\). Let \(x_t^*\) be an optimal action in round \(t\), i.e., \(x_t^*=\mathop{\mathrm{arg\,max}}_{x\in\mathcal{X}_t}\mu(h(x))\). Then the agent’s goal is to minimize the cumulative regret, defined as \(\text{Regret}(T) = \sum_{t=1}^T\mu(h(x_t^*)) - \sum_{t=1}^T\mu(h(x_t))\). Finally, we introduce the standard assumption on the problem-dependent parameters \(\kappa\) and \(R\) [9], [11]:

The formal definition of \(\kappa\) and \(R\) for the arm set \(\mathcal{X}\) and the parameter set \(\Theta\) is deferred to Assumption 4. Notice that for the sigmoid link function, we have \(\mu(\cdot)\), \(R\leq1/4\).

Neural bandits. Neural contextual bandit methods address the limitation of traditional (generalized) linear reward models [3], [9] by approximating \(h(\cdot)\) with a fully connected deep neural network \(f(x;\theta)\), which allows them to capture complex, possibly nonlinear, reward structures. In this work, we consider a neural network given by \(f(x;\theta) = \sqrt{m} W_L \text{ReLU}\left(W_{L-1} \text{ReLU}\left(\cdots \text{ReLU}\left( W_1 x \right)\right)\right)\), where \(L \geq 2\) is the depth of the neural network, \(\text{ReLU}(x)=\max\{x,0\}\), \(W_1\in\mathbb{R}^{m\times d}\), \(W_i\in\mathbb{R}^{m\times m}\) for \(2\leq i\leq L-1\), and \(W_L\in\mathbb{R}^{1\times m}\). The flattened parameter vector is given by \(\theta=[\text{vec}(W_1)^\top,\dots, \text{vec}(W_L)^\top]^\top\in\mathbb{R}^p\), where \(p\) is the total number of parameters, i.e., \(p=m+md+m^2(L-1)\). We denote the gradient of the neural network by \(g(x;\theta)=\nabla_\theta f(x;\theta)\in\mathbb{R}^{p}\).

Notation. For a positive integer \(n\), let \([n] = \{1, \dots, n\}\). For any \(x \in \mathbb{R}^d\), \(\|x\|_2\) denotes the \(\ell_2\) norm, and \([x]_i\) denotes its \(i\)-th coordinate. Given \(x \in \mathbb{R}^d\) and a positive-definite matrix \(A \in \mathbb{R}^{d \times d}\), we define \(\|x\|_A = \sqrt{x^\top A x}\). We use \(\widetilde{O}(\cdot)\) to hide the logarithmic factors.

3 Variance- and Data-Adaptive Self-Normalized Martingale Tail Inequality↩︎

In this section, we first introduce our new Bernstein-type tail inequality for self-normalized martingales, which leads to a regret analysis that is variance- and data-adaptive. Then we compare it with some existing tail inequalities from prior works.

Our proof of Theorem 1 is given in Section 12. The second inequality in Theorem 1 follows from Assumption 1 which states that \(\dot{\mu}(\cdot)\leq R\leq 1/4\). Notice that the tail inequality is data‑adaptive, as it does not explicitly depend on \(d\). Moreover, the term \(\log\frac{\det H_t}{\det\lambda\mathbf{I}}\) can decrease depending on the observed feature vectors (e.g., it becomes \(0\) if \(\{x_i\}_{i=1}^t\) are all \(\mathbf{0}\)). By incorporating non‑uniform variances when defining \(H_t\), our design matrix enables a variance-adaptive analysis and drops the worst‑case variance dependency \(\kappa\).

The seminal work of [2] provided a variant of the Azuma-Hoeffding tail inequality for vector-valued martingales, under the assumption that the martingale difference \(\eta_t\) is \(M\)-sub-Gaussian. Their tail bound shows that \(\|s_t\|_{\widetilde{V}_t^{-1}} = \widetilde{\mathcal{O}}(M\sqrt{d})\), where \(\widetilde{V}_t = \sum_{i=1}^t x_i x_i^\top + \lambda \mathbf{I}\). Extending this result to (neural) logistic bandits, [11] incorporated the worst‑case variance \(\kappa\) into the design matrix \(V_t = \sum_{i=1}^t x_i x_i^\top + \kappa \lambda I\) to deduce\[\begin{align} \big\|s_t\big\|_{H_t^{-1}} \leq \sqrt{\kappa}\big\|s_t\big\|_{V_t^{-1}} \leq M\sqrt{\kappa\log \frac{\det V_t}{\det \kappa\lambda\mathbf{I}}+2\kappa\log\frac{1}{\delta}}. \end{align}\] Here, the first inequality is a consequence of \(H_t \succeq (1/\kappa) V_t\), and this step incurs the factor \(\sqrt{\kappa}\). Note that this bound is also data-adaptive, yielding an overall order of \(\widetilde{\mathcal{O}}(\sqrt{\kappa \tilde{d}})\).

Another line of work by [9] provided a Bernstein-type tail inequality for the same setting considered in Theorem 1, using \(|\eta_t|\leq M(=1)\), \(\mathbb{E}[\eta_t^2|\mathcal{G}_t]=\sigma_t^2\), and \(\|x_t\|_2\leq N(=1)\) for all \(t\geq 1\). Their analysis directly takes the design matrix \(H_t\), and they deduce the following inequality avoiding the \(\sqrt{\kappa}\) factor: \[\begin{align} \big\|s_t\big\|_{H_t^{-1}} \leq \frac{2MN}{\sqrt{\lambda}}\Big(\log\frac{\det H_t}{\delta\det \lambda\mathbf{I}} + d \log(2) \Big)+ \frac{\sqrt{\lambda}}{2MN}. \nonumber \end{align}\] The inequality requires a specific \(\lambda\) value for the regularization term, given by \(\lambda = \widetilde{\mathcal{O}}(dM^2N^2)\), to achieve the final order of \(\widetilde{\mathcal{O}}(\sqrt{d})\). Although \(\log \frac{\det H_t}{\det \lambda\mathbf{I}}\) is data-adaptive, the term \(d\log(2)\) introduces an explicit dependence on \(d\) that cannot be removed (even with a different choice of \(\lambda\)). The tail bound has been used in subsequent works [10], [12], making a dependence on \(d\) inherent. Hence, we need a new variance-adaptive analysis for neural logistic bandits.

Compared with [9], our tail inequality in Theorem 1 is derived from a different technique based on Freedman’s inequality ([13], Lemma 14), which is the key factor behind our improvement. Unlike [9], which works with a \(d\)-dimensional martingale and thereby incurs an explicit dependence on \(d\), we instead use a one-dimensional martingale to track the growth of the self-normalized error \(\|s_t\|_{H_t^{-1}}\), bypassing this vector-level issue. As a result, we obtain a data- and variance-adaptive inequality whose leading term depends on the effective dimension \(\widetilde{d}\), together with an improved dependence on \(\kappa\), thanks to the variance sensitivity of Freedman’s inequality.

4 Neural Logistic Bandits with Improved UCB↩︎

This section introduces our first algorithm, NeuralLog-UCB-1, described in Algorithm 1. In the initialization step, we set the initial parameter \(\theta_0\) of the neural network according to the standard initialization process described in [8]. For \(1\leq l\leq L-1\), \(W_l\) is set as \(\left[\begin{smallmatrix} W & \mathbf{0} \\ \mathbf{0} & W \end{smallmatrix}\right]\), where each entry of \(W\) is independently sampled from \(N(0,4/m)\) while \(W_L\) is set to \([w, -w]\), where each entry of \(w\) is independently sampled from \(N(0,2/m)\). Next, we set the initial regularization parameter as \(\lambda_0=8\sqrt{2}C_1L^{1/2}S^{-1}\log(4/\delta)\) for some absolute constant \(C_1>0\). The value of \(\lambda_0\) is chosen so that \(\lambda_0\) is less than the minimum value among \(\lambda_1,\dots,\lambda_T\), where \(\lambda_t\) is updated as in 3 . We can verify this by showing that \(\lambda_0\leq \min \lambda_1\) and that \(\{\lambda_t\}_{t\geq1}\) is monotonically non-decreasing in \(t\), which implies \(\lambda_0 \leq \min\{\lambda_t\}_{t\geq1}\).

After the initialization step, in each round \(t\), the agent receives the context set \(\mathcal{X}_t\subset{X}\) and calculates \(\text{UCB}_t(x) = \mu(f(x;\theta_{t-1})) + R\sqrt{\kappa}\nu_{t-1}^{(1)} \|g(x;\theta_0)/\sqrt{m}\|_{V_{t-1}^{-1}}\) for every action \(x\in\mathcal{X}_t\), where \[\begin{align} &\nu^{(1)}_t = C_6\big(1+\sqrt{L}S+ LS^2\big)\iota_t + 1, \tag{1}\\ &\iota_t = 16 \sqrt{\log \det \bigg(\sum_{i=1}^t\frac{g(x_i;\theta_0)g(x_i;\theta_0)^\top}{4m\lambda_0} + \mathbf{I} \bigg)\log\frac{4t^2}{\delta}} \nonumber \\ &\quad + 8C_1\sqrt{\frac{L}{\lambda_0}}\log\frac{4t^2}{\delta}, \tag{2} \end{align}\] where \(\delta\in(0,1)\) is a confidence parameter, and \(S\) is a norm parameter of the parameter set defined in Definition 2 for some absolute constants \(C_1,C_6>0\). The first term, \(\mu(f(x;\theta_{t-1}))\), estimates the expected value of the reward, and the second term can be viewed as the exploration bonus. Then, we choose our action \(x_t\) optimistically by maximizing the UCB value, i.e., \(x_t = \mathop{\mathrm{arg\,max}}_{x\in\mathcal{X}_t} \text{UCB}_t(x)\), and receive a reward \(r_t\). At the end of each round, we update the parameters based on the observations \(\{x_i, r_i\}_{i=1}^{t}\) collected so far. We set the regularization parameter \(\lambda_t\), with an absolute constant \(C_1>0\), as follows: \[\begin{align} \lambda_t&\leftarrow\frac{64}{S^2} \log\det \bigg(\sum_{i=1}^t\frac{g(x_i;\theta_0) g(x_i;\theta_0)^\top}{4m\lambda_0} + \mathbf{I}\bigg) \log\frac{4t^2}{\delta} \nonumber \\ &\quad + \frac{16C_1^2L}{S^2\lambda_0} \log^2\frac{4t^2}{\delta}. \label{eq:lambda} \end{align}\tag{3}\] Then we update \(\iota_t\), \(\nu_t^{(1)}\), and \(V_t\). Lastly, as described in Subroutine TrainNN, we update the parameters of the neural network through gradient descent to minimize the regularized negative log-likelihood loss function \(\mathcal{L}_t(\theta)\) and obtain \(\theta_t\). In contrast to [11], which used a constant regularization parameter \(\lambda\), we adaptively control the regularization parameter \(\lambda_t\) and employ it in both our design matrix \(V_t\) and our loss function \(\mathcal{L}_t(\theta)\). This yields a fully data-adaptive concentration inequality between \(\theta_t\) and the desired parameter, as will be shown in Lemma 1.

Now, we present our theoretical results for Algorithm 1. Let \(\mathbf{H}\) denote the neural tangent kernel (NTK) matrix computed on all \(TK\) context–arm feature vectors over \(T\) rounds. Its formal definition is deferred to Definition 3. Define \(\mathbf{h}=[h(x)]_{x\in\mathcal{X}_t,t\in[T]}\in\mathbb{R}^{TK}\). We begin with the following assumptions.

Both assumptions are mild and standard in the neural bandit literature [8], [14]. Assumption 2 states that the NTK matrix is nonsingular, which holds if no two context vectors are parallel. Assumption 3 ensures that \(f(x^i;\theta_0)=0\) for all \(i\in[TK]\) at initialization. This assumption is made for analytical convenience and can be ensured by building a new context \(x'=[x^\top,x^\top]^\top/\sqrt{2}\).

Next, define \(\widetilde{\mathbf{H}}=\sum_{t=1}^T\sum_{x\in\mathcal{X}_t} \frac{1}{m}g(x_i;\theta_0) g(x_i;\theta_0)^\top\), which is the design matrix containing all possible context-arm feature vectors over the \(T\) rounds. Then, we can use the following definition:

We mention that previous works [8], [11] for neural contextual bandits have defined the effective dimension \(\widetilde{d}\) in slightly different ways. [8] set \(\widetilde{d} = \log\det(\frac{1}{\lambda}\mathbf{H}+\mathbf{I})/\log(1+TK/\lambda)\) for neural contextual linear bandits, while [11] defined \(\widetilde{d} = \log\det(\frac{1}{\kappa\lambda}\widetilde{\mathbf{H}}+\mathbf{I})\). However, these definitions have the same asymptotic order as ours in Definition 1 up to logarithmic factors.

Next, to improve readability, we summarize the conditions for the upcoming theorems and lemmas:

In particular, when \(m\) is sufficiently large, we observe that the true reward function \(h(x)\) behaves like a linear function (see Lemma 3). Then, using the tail inequality given in Theorem 1 and the update rule for \(\lambda_t\), we obtain the following data‑ and variance-adaptive concentration inequality between \(\theta_t\) and \(\theta^*\):

The proof is deferred to 13.1. We now present 3, which gives the desired regret upper bound of Algorithm 1.

5 Refined Algorithm with Neural Network-Estimated Variance↩︎

In this section, we explain NeuralLog‑UCB‑2, which guarantees the tightest regret upper bounds. Although Lemma 1 establishes a variance-adaptive concentration inequality with \(H_t(\theta^*)\), the agent lacks full knowledge of \(\theta^*\) and must therefore use the crude bound \(H_t(\theta^*)\preceq\kappa^{-1}V_t\), which incurs an extra factor of \(\sqrt{\kappa}\). In this section, we introduce NeuralLog-UCB-2, which replaces \(H_t(\theta^*)\) with a neural network–estimated variance-adaptive design matrix. We begin by stating a concentration result for \(\theta^*\) around \(\theta_t\) using the new design matrix \(W_t\).

We give the proof of the lemma in 14.1. The matrix \(W_t\) maintains sufficient statistics via the neural network-estimated variance, and the ellipsoidal confidence set \(\mathcal{W}_{t}\) changes the original problem into a closed-form optimistic formulation. Specifically, after the same initialization step as for Algorithm 1, the agent selects action \(x_t\) in each round \(t\) according to the following rule: \[\begin{align} &x_t \leftarrow \mathop{\mathrm{arg\,max}}_{x\in\mathcal{X}_t, \theta\in\mathcal{W}_{t-1}} \langle g(x;\theta_0),(\theta-\theta_0)\rangle \nonumber \\ &= \mathop{\mathrm{arg\,max}}_{x\in\mathcal{X}_t}g(x;\theta_0)^\top(\theta_{t-1}-\theta_0) + \nu_{t-1}^{(2)}\|x\|_{W_{t-1}^{-1}}. \label{eq:opt2} \end{align}\tag{5}\] For the regret upper bound of Algorithm 3, we define another problem-dependent quantity \(\kappa^*\) as \(1/\kappa^* =\frac{1}{T}\sum_{t=1}^T\dot{\mu}(h(x_t^*))\), consistent with the definition in [10]. Both \(\kappa^*\) and \(\kappa\) scale exponentially with \(S\). We now state our regret upper bound for NeuralLog-UCB-2 and provide a proof outline.

6 Regret Analyses↩︎

This section outlines the regret analysis for [alg:1,alg:2] and provides proof sketch for Theorems 3 and 5. Let us start by stating some basic results on the NTK analysis and logistic bandits. The following lemma shows that for all \(x\in\mathcal{X}_t\) and \(t\in[T]\), the true reward function \(h(x)\) can be expressed as a linear function.

Based on Lemma 3, we define the parameter set \(\Theta\) and the parameters \(\kappa\) and \(R\), which is consistent with the standard logistic bandits literature [9]:

6.1 Proof sketch of 3↩︎

Let \(|\mu(h(x)) - \mu(f(x;\theta_{t-1}))|\) denote the prediction error of \(x\) in round \(t\), which is the estimation error between the true reward and our trained neural network. We show that with Lemma 1 and large enough \(m\), the prediction error is upper bounded as follows:

Based on the results so far, we can upper bound the per-round regret in round \(t\) as follows: \[\begin{align} &\mu(h(x_t^*))-\mu(h(x_t)) \\ &\leq \mu(f(x_t^*;\theta_{t-1})) + R\sqrt{\kappa}\nu^{(1)}_t \|g(x_t^*;\theta_0)/\sqrt{m}\|_{V^{-1}_{t-1}} \\ &\quad + \epsilon_{3,t-1} -\mu(h(x_t)) \\ &\leq \mu(f(x_t;\theta_{t-1})) + R\sqrt{\kappa}\nu^{(1)}_t \|g(x_t;\theta_0)/\sqrt{m}\|_{V^{-1}_{t-1}} \\ &\quad+ \epsilon_{3,t-1} -\mu(h(x_t)) \\ &\leq 2R\sqrt{\kappa}\nu^{(1)}_t \|g(x_t;\theta_0)/\sqrt{m}\|_{V^{-1}_{t-1}} + 2\epsilon_{3,t-1}, \end{align}\] where the first and last inequalities follow from Lemma 4, and the second inequality holds due to the optimistic rule of Algorithm 1. The cumulative regret can be decomposed as \(\text{Regret}(T) =\sum_{t=1}^T \mu(h(x_t^*))-\mu(h(x_t)) \leq 2 R \sqrt{\kappa} \nu_T^{(1)}\sqrt{T\sum_{t=1}^T \big\| g(x_t;\theta_0)/\sqrt{m}\big\|_{V_{t-1}^{-1}}^2} + 2T\epsilon_{3,T}\), for which we use the Cauchy-Schwarz inequality. We have \(\nu_T^{(1)}=\widetilde{O}(\sqrt{\widetilde{d}})\), and using the elliptical potential lemma (Lemma 15) on \(\sum_{t=1}^T\|g(x_t;\theta_0)/\sqrt{m}\|^2_{V_{t-1}^{-1}}\) gives \(\widetilde{O}(\widetilde{d})\). Finally, setting \(m\) large enough under Condition 2, the approximation error term gives \(T\epsilon_{3,T}=\mathcal{O}(1)\). See 15.1 for details.

6.2 Proof sketch of 5↩︎

Let \((x_t,\widetilde{\theta}_{t-1})\in \mathcal{X}_t\times\mathcal{W}_{t-1}\) be selected by the optimistic rule at time \(t\). The per-round regret can be decomposed with a second-order Taylor expansion as follows: \[\begin{align} &\mu(h(x_t^*))-\mu(h(x_t)) \\ &\leq \mu(g(x_t;\theta_0)^\top (\widetilde{\theta}_{t-1}-\theta_0))-\mu(g(x_t;\theta_0)^\top(\theta^*-\theta_0)) \\ &\leq \dot{\mu}(h(x_t)) g(x_t;\theta_0)^\top (\widetilde{\theta}_{t-1} - \theta^*) \\ &\quad + 1\cdot\big[g(x_t;\theta_0)^\top(\widetilde{\theta}_{t-1}-\theta^*)\big]^2, \end{align}\] where the first inequality follows from the optimistic rule of Algorithm 3, and we use \(\ddot{\mu}(\cdot)\leq 1\) for the second one. To analyze the first term on the right-hand side of the second inequality, we compare \(\dot{\mu}(h(x_t))\) and \(\dot{\mu}(f(x_t;\theta_t))\) and rewrite the term as \(\sqrt{\dot{\mu}(h(x_t))}\|\sqrt{\dot{\mu}(f(x_t;\theta_t)}g(x_t;\theta_0)\|_{W_{t-1}} \|\widetilde{\theta}_{t-1}-\theta^*\|_{W_{t-1}^{-1}}\). Summing this for \(t=1,\dots,T\), we apply the elliptical potential lemma (Lemma 15) and Lemma 2. For the second term, since we do not enforce any projection or constraint during training, \(\theta_{t-1}\) may stay outside \(\Theta\). We show that the number of such rounds is \(\widetilde{\mathcal{O}}(\kappa\,\widetilde{d}^2)\). Applying Assumption 4 then yields a crude bound of \(\kappa\|g(x_t;\theta_0)\|_{V_{t-1}}^2 \|\widetilde{\theta}_{t-1}-\theta^*\|_{W_t}^2\). Based on this, the second term can be bounded from above in a similar way. Details are covered in Section 15.2.

7 Experiments↩︎

In this section, we empirically evaluate the performance of our algorithms. Additional results along with further details are deferred to 9 due to space constraints.

Synthetic dataset. We begin our experiments with a synthetic dataset. We use three nonlinear synthetic latent reward functions: \(h_1(x) = 0.2(x^\top\theta)^4\), \(h_2(x) = 20\cos (x^\top \theta)\), \(h_3(x) = 5x^\top\boldsymbol{\theta} x\), where \(x\) represents the features of a context-arm pair, and \(\theta\in\mathbb{R}^d\) and \(\boldsymbol{\theta}\in\mathbb{R}^{d\times d}\) are parameters whose elements are independently sampled from \(\text{Unif}(-1,1)\). Subsequently, the agent receives a reward generated by \(r_t \sim \text{Bern}(\mu(h_i(x)))\), for \(i\in\{1,2,3\}\). We set the feature vector dimension to \(d=20\) and the number of arms to \(K=5\). We compare our method against five baseline algorithms in 1: (1) NCBF-UCB [11]; (2) Logistic-UCB-1 [9]; (3) ada-OFU-ECOLog [12]; (4) NeuralLog-UCB-1; and (5) NeuralLog-UCB-2. For brevity, we will denote algorithms by their number (e.g. algorithm (1)).

Following practical adjustments from previous neural bandits experiments [8], [11], [14], for algorithms (1,4,5), we use the gradient of the current neural network \(g(x;\theta_t)\) instead of \(g(x;\theta_0)\). We replace \(g(x;\theta_t)/\sqrt{m}\) with \(g(x;\theta_t)\) and \(m\lambda\|\theta-\theta_0\|_2^2/2\) with \(\lambda\|\theta\|_2^2\). Previous works simplify the UCB estimation process by fixing parameters for the exploration bonus for practical reasons. In this work, however, we consider the time-varying data-adaptive values of the exploration bonus, characterized by \(\text{UCB}_t(x) = \boldsymbol{\mu}(x;\theta_{t-1}) + \boldsymbol{\sigma}(x;\nu, \{x_i,\theta_{i-1}\}_{i=1}^{t-1},\lambda,S,\kappa)\). Here, \(\boldsymbol{\mu}\) is the mean estimate and \(\boldsymbol{\sigma}\) is the exploration bonus, parameterized by an exploration parameter \(\nu\), previous observations \(\{x_i,\theta_{i-1}\}_{i=1}^{t-1}\), \(\lambda\), \(S\), and \(\kappa\). Details of UCB for each algorithm are deferred to 5. We use \(S=1\), \(\kappa=10\) and fixed values of \(\nu\) and \(\lambda\) with the best parameter values using grid search over \(\{0.01, 0.1, 1,10,100\}\).

We use a two-layer neural network \(f(x;\theta)\) with a width of \(m=20\). As in [8], to reduce the computational burden of the high-dimensional design matrices \(V_t\) and \(W_t\), we approximated these matrices with diagonal matrices. We update the parameters every 50 rounds, using 100 gradient descent steps per update with a learning rate of 0.01. For each algorithm, we repeat the experiments 10 times over \(T=2000\) timesteps and compare the average cumulative regret with a 96% confidence interval.

Real-world dataset. In the real-world experiments, we use three datasets from \(K\)-class classification tasks: mnist [17], mushroom, and shuttle from the UCI Machine Learning Repository [18]. To adapt these datasets to the \(K\)-armed logistic bandit setting, we construct \(K\) context–arm feature vectors in each round \(t\) as follows: given a feature vector \(x\in\mathbb{R}^d\), we define \(x^{(1)} = [x, \mathbf{0}, \dots, \mathbf{0}], \dots, x^{(K)} = [\mathbf{0}, \dots, \mathbf{0}, x] \in \mathbb{R}^{dK}\). The agent receives a reward of 1 if it selects the correct class, and 0 otherwise. All other adjustments for the neural bandit experiments and the neural network training process follow the simulation setup. Details, including data preprocessing, are deferred to 9.

Regret comparison. [fig:1,fig:2] summarize the average cumulative regret for the five baseline algorithms (1–5) tested with the synthetic and real-world datasets, respectively. We observe that the algorithms using linear assumptions on the latent reward function \(h(x)\), namely (2) and (3), exhibit the lowest performance, as the true function is nonlinear. Although algorithm (1) can handle nonlinear reward functions and achieves moderate performance, our proposed methods, especially (5), yield the best results by reducing the dependence on \(\kappa\).

8 Conclusion and Future Work↩︎

In this paper, we study the neural logistic bandit problem. We identify the unique challenges of this setting and propose a novel approach based on a new tail inequality for martingales. This inequality enables an analysis that is both variance- and data-adaptive, yielding improved regret bounds for neural logistic bandits. We introduce two algorithms: NeuralLog-UCB-1 that achieves a regret bound of \(\widetilde{\mathcal{O}}(\widetilde{d}\sqrt{\kappa T})\) and NeuralLog-UCB-2 that attains a tighter bound of \(\widetilde{\mathcal{O}}(\widetilde{d}\sqrt{T/\kappa^*})\) by leveraging the neural network–estimated variance. Our experimental results validate these theoretical findings and demonstrate that our methods outperform the existing approaches.

One potential direction for future work is to improve the dependence on the norm of the unknown parameter \(S\). Although recent frameworks due to [15], [16] have removed the dependence on \(S\) from the leading term, they require an additional training step or impose additional constraints. Such requirements are undesirable when trying to integrate neural bandit frameworks. Hence, it is a promising future research direction to eliminate the dependence on \(S\) without additional computations. Additional future directions are deferred to Section 19.

Acknowledgements↩︎

We thank the review team for their careful review and valuable feedback. This work was supported by the National Research Foundation of Korea (NRF) grant (No. RS-2024-00350703) and the Institute of Information & communications Technology Planning & evaluation (IITP) grants (No. IITP-2026-RS-2024-00437268) and (No. RS-2021-II211343, Artificial Intelligence Graduate School Program (Seoul National University)) funded by the Korea government (MSIT).

Impact Statement↩︎

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

9 Deferred Experiments from 7↩︎

Here we introduce the deferred details and experiments from 7. All experiments were conducted on a server equipped with an Intel Xeon Gold 6248R 3.00GHz CPU (32 cores), 512GB of RAM, and 4 GeForce RTX 4090 GPUs.

Details of UCB. We define the UCB value as \(\boldsymbol{\mu}(x;\theta_{t-1}) + \boldsymbol{\sigma}(x;\nu,\{x_i,\theta_{i-1}\}_{i=1}^{t-1},\lambda,S,\kappa)\). For the exploration bonus \(\boldsymbol{\sigma}\), we match the orders of \(\lambda\), \(S\), \(\kappa\), and the effective dimension \(\widetilde{d}\) for each algorithm and then multiply by the exploration parameter \(\nu\). Specifically, the effective dimension is defined as follows: for algorithm (1), we use \(\log\det(\sum \frac{1}{\kappa}g(x;\theta)g(x;\theta)^\top + \mathbf{I})\); for algorithms (2) and (3), we use \(\log\det(\sum R x x^\top + \mathbf{I})\); and for algorithms (4) and (5) we use \(\log\det(\sum R g(x;\theta)g(x;\theta)^\top + \mathbf{I})\).

Although algorithms (2) and (3) require an additional step (e.g., nonconvex projection) to ensure that \(\theta_t\) remains in the desired set, empirical observations from [9], [12] indicate that \(\theta_t\) almost always satisfies this condition. Consequently, we streamline all baseline algorithms into two steps: (i) choose the action with the highest UCB and (ii) update the parameters via gradient descent.

Preprocessing for real‑world datasets. For consistency with the synthetic environment, we rescale each component of every feature vector \(x\in\mathbb{R}^d\) to the range \([-1,1]\) by applying a normalization of \(2\frac{[x]_j - \min(x)}{\max(x) - \min(x)}-1\) for all \(j\in[d]\). In the mnist dataset, we resize each \(28\times 28\) image to \(7\times 7\), flatten it, and treat the result as a 196‑dimensional feature vector. The mushroom dataset provides 22 categorical features. We assign each character a random value in \([-1,1]\) for normalization and set the label to 1 for edible (‘e’) and 0 for poisonous (‘p’) mushrooms. The shuttle dataset consists of 7 numerical features, to which we apply the same min–max normalization as used for mnist.

Varying effective dimension \(\widetilde{d}\). To evaluate the influence of \(\widetilde{d}\) on data‑adaptive algorithms, we compare cumulative regret across different values of \(\widetilde{d}\). We control \(\widetilde{d}\) by limiting the total number of context–arm feature vectors during training. Allowing redundant vectors reduces \(\widetilde{d}\). For a low effective dimension ([fig:3-1,fig:3-4,fig:3-7]), we use only 10 feature vectors randomly placed across the training. For a medium \(\widetilde{d}\) ([fig:3-2,fig:3-5,fig:3-8]), we use 50 vectors. For a high \(\widetilde{d}\) ([fig:3-3,fig:3-6,fig:3-9]), we use 10000 distinct vectors. Note that [fig:1,fig:2] use 2500 vectors. 6 shows that our algorithm, especially algorithm (5), performs best across all those settings and adapts effectively to different environments of the effective dimensions.

10 Related Work↩︎

Logistic bandits. [3] introduced the generalized linear bandit framework and derived a regret bound of \(\widetilde{\mathcal{O}}(\kappa d\sqrt{T})\), laying the groundwork for modeling logistic bandits. Subsequent work, starting with [9], has focused on reducing the dependence on \(\kappa\) through variance-aware analyses (see also [10], [19]). In particular, [10] established a lower bound of \(\Omega(d\sqrt{T/\kappa^{*}})\), statistically closing the gap. However, there is still room for improvement in algorithmic efficiency [12], [20], [21] and in mitigating the influence of the norm parameter \(S\), with several recent advances addressing this issue [15], [16], [22], [23]. Another line of research investigates the finite‑action setting. When feature vectors are drawn i.i.d.from an unknown distribution whose covariance matrix has a strictly positive minimum eigenvalue, [4] achieved a regret of \(\widetilde{\mathcal{O}}(\kappa\sqrt{dT})\), while [24] and [25] further improved it to \(\widetilde{\mathcal{O}}(\sqrt{\kappa dT})\) and \(\widetilde{\mathcal{O}}(\sqrt{dT})\), respectively.

Neural bandits. Advances in deep neural networks have spurred numerous methods that integrate deep learning with contextual bandit algorithms [7], [26], [27]. [8] was among the first to formalize neural bandits, proposing the NeuralUCB algorithm, which attains a regret bound of \(\widetilde{\mathcal{O}}(\widetilde{d}\sqrt{T})\) by leveraging neural tangent kernel theory [28]. Building on this foundation, many studies have extended linear contextual bandit algorithms to the neural setting [14], [29]–[32]. The work most closely related to ours is [11], which first addressed both logistic and dueling neural bandits and proposed UCB‑ and Thompson‑sampling‑based algorithms with a regret bound of \(\widetilde{\mathcal{O}}(\kappa\widetilde{d}\sqrt{T})\).

11 Useful Lemmas for Neural Bandits↩︎

In this section, we present several lemmas that enable the neural bandit analysis to quantify the approximation error incurred when approximating the unknown reward function \(h(x)\) with the neural network \(f(x;\theta)\). We begin with the definition of the neural tangent kernel (NTK) matrix [28]:

Next, we introduce a condition on the neural network width \(m\), which is crucial for ensuring that the approximation error remains sufficiently small.

We assume that \(m\) satisfies Condition 7 throughout. For readability, we denote the error probability by \(\delta\) in all probabilistic statements. We now restate Lemma 3, which shows that, for every \(x \in \mathcal{X}_t\) and \(t \in [T]\), the true reward function \(h(x)\) can be represented as a linear function:

Assuming \(\theta_t\) remains close to its initialization \(\theta_0\), we can apply the following lemmas: Lemma 6 provides upper bounds on the norms \(\|g(x;\theta)\|_2\) and \(\|g(x;\theta) - g(x;\theta_0)\|_2\), while Lemma 7 bounds the approximation error between \(f(x;\theta)\) and its linearization \(g(x;\theta_0)^\top (\theta-\theta_0)\).

Finally, we state a lemma that establishes an upper bound on the distance between \(\theta_t\) and \(\theta_0\). It also shows that, although the loss function \(\mathcal{L}_t(\theta)\) is non-convex and hence the iterate \(\theta_t\) obtained after \(J\) steps of gradient descent may differ from the ideal maximum likelihood estimator, this discrepancy remains sufficiently small. The proof is deferred to 11.1:

11.1 Proof of Lemma 8↩︎

For simplicity, we omit the subscript \(t\) by default. First, recall the definition of the auxiliary sequence \(\{\widetilde{\theta}^{(j)}\}_{j=1}^J\) associated with the auxiliary loss \(\widetilde{L}(\theta)\); its update rule is given by: \[\begin{align} \widetilde{\theta}^{(j+1)} &= \widetilde{\theta}^{(j)} - \eta \nabla \widetilde{L}(\widetilde{\theta}^{(j)}) \\ &=\widetilde{\theta}^{(j)} - \eta\Big[m\lambda \widetilde{\theta}^{(j)} - \sum_{i=1}^t (\mu(g(x_i;\theta_0)^\top (\widetilde{\theta}^{(j)} - \theta_0)) - r_i)g(x_i;\theta_0)\Big]. \end{align}\] Similarly, the update rule for \(\theta^{(j)}\) is given by: \[\begin{align} \theta^{(j+1)} = \theta^{(j)} - \eta\Big[m\lambda \theta^{(j)} - \sum_{i=1}^t (\mu(f(x;\theta^{(j)})) - r_i)g(x_i;\theta^{(j)})\Big]. \end{align}\] Also notice that \[\begin{align} \nabla^2\widetilde{L}(\theta) = \sum_{i=1}^t \mu(g(x_i;\theta_0)^\top(\theta-\theta_0))(1-\mu(g(x_i;\theta_0)^\top(\theta-\theta_0)))g(x_i;\theta_0) g(x_i;\theta_0)^\top + m\lambda \mathbf{I}. \label{eq:Hessian} \end{align}\tag{6}\] Now, we start the proof with \[\begin{align} \|\theta^{(j+1)} - \hat{\theta}\|_2 &\leq \underbrace{\|\widetilde{\theta}^{(j+1)} - \hat{\theta}\|_2}_{\boldsymbol{(term 1)}} + \underbrace{\|\theta^{(j+1)} - \widetilde{\theta}^{(j+1)}\|_2}_{\boldsymbol{(term 2)}} \label{eq:0} \end{align}\tag{7}\]

For (term 1), observe from 6 that \(\widetilde{\mathcal{L}}\) is \((m\lambda)\)-strongly convex, since \((m\lambda)\mathbf{I} \preceq \nabla^2\widetilde{L}(\theta)\). Moreover, \(\widetilde{\mathcal{L}}\) is a \(C_5(tmL+m\lambda)\)-smooth function for some absolute constant \(C_5>0\), because \[\begin{align} \nabla^2\widetilde{L}(\theta) &\preceq \sum_{i=1}^t \frac{1}{2} \cdot \frac{1}{2}\cdot g(x_i;\theta_0) g(x_i;\theta_0)^\top + m\lambda \mathbf{I} \\ &\preceq \Big(\sum_{i=1}^t \frac{1}{4}\|g(x_i;\theta_0)\|_2^2 +m\lambda\Big)\mathbf{I} \\ &\preceq C_5(tmL+m\lambda)\mathbf{I}, \end{align}\] where the first inequality follows from \(\mu(\cdot)\bigl(1-\mu(\cdot)\bigr)\le 1/4\), the second follows because for any \(u,x\in\mathbb{R}^d\), \(u^\top x\,x^\top u \le \|u\|_2^2\,\|x\|_2^2 \le u^\top\bigl(\|x\|_2^2 I\bigr)u\), and the last inequality follows from Lemma 6.

Then, with our choice of \(\eta = C_5(tmL + m\lambda)\), standard results for gradient descent on \(\widetilde{L}\) imply that \(\widetilde{\theta}^{(j)}\) converges to \(\hat{\theta}_t\) at the rate as \[\begin{align} \big\|\widetilde{\theta}^{(j)} - \hat{\theta} \big\|_2^2 &\leq \frac{2}{m\lambda}\cdot (\widetilde{\mathcal{L}}(\widetilde{\theta}^{(j)})-\widetilde{\mathcal{L}}(\hat{\theta}))\\ &\leq (1-\eta m \lambda)^j \cdot \frac{2}{m\lambda}\cdot \big(\mathcal{\widetilde{L}}(\theta_0) - \mathcal{\widetilde{L}}( \hat{\theta})\big) \\ &\leq (1-\eta m \lambda)^j \cdot \frac{2}{m\lambda}\cdot \mathcal{\widetilde{L}}(\theta_0), \end{align}\] where the first and the second inequalities follow from the strong convexity and the smoothness of \(\widetilde{L}\). Furthermore, we have \[\begin{align} \widetilde{\mathcal{L}}(\theta_0) &= -\sum_{i=1}^t r_i \log \mu\big(0\big) + (1-r_i)\log(1-\mu\big( 0)\big) + \frac{m\lambda_t}{2}\|\theta_0-\theta_0\|_2^2 = -\sum_{i=1}^t\log 0.5 \leq t, \end{align}\] Plugging this back gives \[\begin{align} \big\|\widetilde{\theta}^{(j)} - \hat{\theta} \big\|_2 \leq (1-\eta m \lambda)^{j/2} \sqrt{2t/(m\lambda)}. \label{eq:1} \end{align}\tag{8}\] Next, consider (term 2). From the definition of the update rule, it follows that: \[\begin{align} \boldsymbol{(term 2)} &\leq (1-\eta m\lambda)\|\theta^{(j)} - \widetilde{\theta}^{(j)}\|_2 \nonumber \\ &\quad+ \eta \Big\|\sum_{i=1}^t (\mu(f(x;\theta^{(j)}) - r_i)g(x_i;\theta^{(j)}) - \sum_{i=1}^t (\mu(g(x_i;\theta_0)^\top (\widetilde{\theta}^{(j)} - \theta_0)) - r_i)g(x_i;\theta_0)\Big\|_2 \nonumber\\ &\leq (1-\eta m\lambda)\|\theta^{(j)} - \widetilde{\theta}^{(j)}\|_2 + \underbrace{\eta \sum_{i=1}^t \Big\| (\mu(f(x;\theta^{(j)}) - r_i) [g(x_i;\theta^{(j)}) - g(x_i;\theta_0)]\Big\|_2}_{\boldsymbol{(term 3)}} \nonumber\\ &\quad+ \underbrace{\eta\sum_{i=1}^t \Big\|[\mu(f(x;\theta^{(j)})) - \mu(g(x;\theta_0)^\top(\widetilde{\theta}^{(j)}-\theta_0))]g(x_i;\theta_0)\Big\|_2}_{\boldsymbol{(term 4)}}. \label{eq:13} \end{align}\tag{9}\] Considering each term of 9 , there exist absolute constants \(C_1, C_2, C_3 > 0\) such that \[\begin{align} \boldsymbol{(term 3)} &\leq \eta \sum_{i=1}^t \Big\| 1\cdot [g(x_i;\theta^{(j)}) - g(x_i;\theta_0)]\Big\|_2 \leq C_2 \eta m^{1/3}\sqrt{\log m} t^{7/6}\lambda^{-1/6} L^{7/2} \tag{10} \\ \boldsymbol{(term 4)} &\leq \eta \sum_{i=1}^t \Big\| R [f(x;\theta^{(j)}) - g(x;\theta_0)^\top (\widetilde{\theta}^{(j)}-\theta_0)]g(x_i;\theta_0)\Big\|_2 \nonumber \\ &\leq \eta R \sum_{i=1}^t \Big\| f(x;\theta^{(j)}) - g(x;\theta_0)^\top (\widetilde{\theta}^{(j)}-\theta_0) \Big\|_2 \cdot \|g(x_i;\theta_0)\|_2 \nonumber \\ &\leq C_3 \eta R \sum_{i=1}^t m^{-1/6}\sqrt{\log m} L^3 t^{2/3} \lambda^{-2/3} \|g(x_i;\theta_0)\|_2 \nonumber \\ &\leq C_1 C_3 \eta R m^{1/3}\sqrt{\log m} L^{7/2} t^{5/3} \lambda^{-2/3}. \tag{11} \end{align}\] For (term 3), we apply Lemma 6. For (term 4), the first inequality follows from the \(R\)‑Lipschitz continuity of \(\mu(\cdot)\), the second follows from the Cauchy–Schwarz inequality, the third follows from Lemma 7, and the final inequality follows from Lemma 6 after summing over \(t\).

Substituting [eq:11,eq:12] into 9 yields \[\begin{align} \|\theta^{(j+1)} - \widetilde{\theta}^{(j+1)}\|_2 &\leq (1-\eta m\lambda)\|\theta^{(j)} - \widetilde{\theta}^{(j)}\|_2 \nonumber \\ &\quad+ C_2 \eta m^{1/3}\sqrt{\log m} t^{7/6}\lambda^{-1/6} L^{7/2} + C_1C_3 \eta R m^{1/3}\sqrt{\log m} L^{7/2} t^{5/3} \lambda^{-2/3} \label{eq:2} \end{align}\tag{12}\] By iteratively applying 12 from \(0\) to \(j\), we obtain \[\begin{align} \|\theta^{(j+1)} - \widetilde{\theta}^{(j+1)}\|_2 &\leq \frac{C_2\eta m^{1/3}\sqrt{\log m} t^{7/6}\lambda^{-1/6} L^{7/2}+ C_1C_3\eta R m^{1/3}\sqrt{\log m} L^{7/2} t^{5/3} \lambda^{-2/3} }{\eta m \lambda} \nonumber \\ &\leq C_2 m^{-2/3}\sqrt{\log m} t^{7/6}\lambda^{-7/6} L^{7/2}+ C_1C_3 R m^{-2/3}\sqrt{\log m} L^{7/2} t^{5/3} \lambda^{-5/3}. \label{eq:3} \end{align}\tag{13}\] By substituting [eq:1,eq:3] into 7 and setting \(j = J-1\), we complete the proof of the upper bound for \(\|\theta_t - \hat{\theta}_2\|_2\). Likewise, from 13 , setting \(j = J-1\) and following the width condition in Condition 2 yields \[\begin{align} \|\theta_t-\widetilde{\theta}_t\|_2&\leq \sqrt{\frac{t}{m\lambda_t}} \Big(C_2 m^{-1/6}\sqrt{\log m} t^{2/3}\lambda_t^{-2/3} L^{7/2}+ C_1C_3 R m^{-1/6}\sqrt{\log m} L^{7/2} t^{7/6} \lambda_t^{-7/6} \Big) \nonumber \\ &\leq \sqrt{\frac{t}{m\lambda_t}} \Big(C_2 m^{-1/6}\sqrt{\log m} T^{2/3}\lambda_0^{-2/3} L^{7/2}+ C_1C_3 R m^{-1/6}\sqrt{\log m} L^{7/2} T^{7/6} \lambda_0^{-7/6} \Big) \nonumber \\ &\leq \sqrt{\frac{t}{m\lambda}}, \label{eq:34} \end{align}\tag{14}\] which completes the bound on \(\|\theta_t - \widetilde{\theta}_t\|_2\). Finally, observe that \[\begin{align} \|\theta_t-\theta_0\|_2 \leq \|\theta_t - \widetilde{\theta}_t\|_2 + \|\widetilde{\theta}_t -\theta_0\|_2, \end{align}\] where 14 gives \(\|\theta_t - \widetilde{\theta}_t\|_2 \le \tau/3\), and for the second term \[\begin{align} \frac{m\lambda_t}{2}\|\theta_t-\theta_0\|_2^2 \leq \widetilde{L}(\widetilde{\theta}_t)\leq \widetilde{L}(\theta_0) = \sum_{i=1}^t r_i \log \mu\big(0\big) + (1-r_i)\log(1-\mu\big( 0)\big) \leq t\log2, \end{align}\] which implies \(\|\widetilde{\theta}_t - \theta_0\|_2 \le 2\sqrt{t/(m\lambda_t)} = 2\tau/3\). Combining these results completes the proof of the bound on \(\|\theta_t - \theta_0\|_2\).

12 Proof of Theorem 1↩︎

Our proof technique is primarily inspired by the recent work of [33], which integrates non‑uniform variance into the analysis of linear bandits. For brevity, let \(\sigma_t^2 = \dot{\mu}(x_t^\top \theta^*)\), which yields \[\begin{align} H_t = \sum_{i=1}^t\dot{\mu}(x_i^\top\theta^*)x_ix_i^\top + \lambda \mathbf{I} = \sum_{i=1}^t \sigma_i^2x_i x_i^\top + \lambda \mathbf{I}. \end{align}\] We introduce the following additional definitions: \[\begin{align} &\beta_t = 8\sqrt{\log\frac{\det H_t}{\det \lambda I}\log(4t^2/\delta)} + \frac{4MN}{\sqrt{\lambda}}\log(4t^2/\delta) \nonumber \\ &s_t=\sum_{i=1}^{t} x_i\eta_i,~ Z_t=\|s_t\|_{H_t^{-1}}, ~ w_t = \|x_t\|_{H_{t-1}^{-1}}, ~ \mathcal{E}_t = \mathbb{1} \{0\leq s \leq t, Z_s\leq \beta_s\} \label{def} \end{align}\tag{15}\] for \(t\geq 1\), where we set \(s_0 = 0, Z_0=0, \beta_{0}=0\).

Since \(H_t = H_{t-1} + \sigma_t^2 x_t x_t^\top\), by the matrix inversion lemma, \[\begin{align} H_t^{-1} &=H_{t-1}^{-1} - \frac{ H_{t-1}^{-1} (\sigma_t x_t) (\sigma_t x_t)^\top H_{t-1}^{-1}}{1+(\sigma_t x_t)^\top H_{t-1}^{-1} (\sigma_t x_t)} \nonumber \\ &= H_{t-1}^{-1} - \frac{\sigma_t^2 H_{t-1}^{-1} x_t x_t^\top H_{t-1}^{-1}}{1+\sigma_t^2w_t^2} . \label{b461} \end{align}\tag{16}\] We begin by establishing a crude upper bound on \(Z_t\). In particular, we have \[\begin{align} Z_t^2 = \|s_t\|_{H_t^{-1}}^2 &= (s_{t-1} + x_t \eta_t)^\top H_t^{-1}(s_{t-1} + x_t\eta_t) \\ &=s_{t-1}^\top H_t^{-1} s_{t-1} + 2\eta_t x_t^\top H_t^{-1} s_{t-1} + \eta_t^2 x_t^\top H_t^{-1} x_t \\ &\leq Z_{t-1}^2 + \underbrace{2\eta_t x_t^\top H_t^{-1} s_{t-1}}_{\boldsymbol{(term 1)}} + \underbrace{\eta_t^2 x_t^\top H_t^{-1} x_t}_{\boldsymbol{(term 2)}} , \end{align}\] where the inequality follows from the fact that \(H_t\succeq H_{t-1}\). For (term 1), from the matrix inversion lemma 16 , we have \[\begin{align} \boldsymbol{(term 1)} &= 2\eta_t\bigg(x_t^\top H_{t-1}^{-1} s_{t-1} - \frac{\sigma_t^2 x_t^\top H_{t-1}^{-1} x_t x_t^\top H_{t-1}^{-1} s_{t-1}}{1+\sigma_t^2 w_t^2}\bigg) \\ &= 2\eta_t\bigg(x_t^\top H_{t-1}^{-1} s_{t-1} - \frac{\sigma_t^2 w_t^2 x_t^\top H_{t-1}^{-1} s_{t-1}}{1+\sigma_t^2 w_t^2}\bigg) \\ &= \frac{2\eta_t x_t^\top H_{t-1}^{-1} s_{t-1}}{1+\sigma_t^2 w_t^2} . \end{align}\] For (term 2), again from the matrix inversion lemma 16 , we have \[\begin{align} \boldsymbol{(term 2)} = \eta_t^2 \bigg(x_t^\top H_{t-1}^{-1} x_t - \frac{\sigma_t^2 x_t^\top H_{t-1}^{-1} x_t x_t^\top H_{t-1}^{-1} x_t}{1+\sigma_t^2 w_t^2}\bigg) = \eta_t^2\bigg(w_t^2 - \frac{\sigma_t^2 w_t^4}{1+\sigma_t^2w_t^2}\bigg) = \frac{\eta_t^2 w_t^2}{1+\sigma_t^2w_t^2} . \end{align}\] Therefore, we have \[\begin{align} Z_t^2 \leq Z_{t-1}^2 + \frac{2\eta_t x_t^\top H_{t-1}^{-1} s_{t-1}}{1+\sigma_t^2 w_t^2} + \frac{\eta_t^2 w_t^2}{1+\sigma_t^2w_t^2} , \end{align}\] and by summing this up from \(i=1\) to \(t\) gives, \[\begin{align} Z_t^2 \leq \sum_{i=1}^t\frac{2\eta_i x_i^\top H_{i-1}^{-1} s_{i-1}}{1+\sigma_i^2 w_i^2} + \sum_{i=1}^t \frac{\eta_i^2 w_i^2}{1+\sigma_i^2w_i^2} . \label{b4612} \end{align}\tag{17}\] We give two lemmas to upper bound each term.

Now consider the event \(\mathcal{E}\) in which the conclusions of Lemma 9 and Lemma 10 hold. We claim that, on this event, for any \(i \geq 0\), \(Z_i \leq \beta_{i}\). We prove this by induction on \(i\). For the base case \(i = 0\), the claim holds by definition, since \(\beta_{0} = 0 = Z_0\). Now fix any \(t \geq 1\) and assume that for all \(0 \leq i < t\) we have \(Z_i \leq \beta_{i}\). Under this induction hypothesis, it follows that \(\mathcal{E}_1 = \mathcal{E}_2 = \cdots = \mathcal{E}_{t-1} = 1\). Then by 17 , we have \[\begin{align} Z_t^2 \leq \sum_{i=1}^t\frac{2\eta_i x_i^\top H_{i-1}^{-1} s_{i-1}}{1+\sigma_i^2 w_i^2} + \sum_{i=1}^t \frac{\eta_i^2 w_i^2}{1+\sigma_i^2w_i^2} = \sum_{i=1}^t\frac{2\eta_i x_i^\top H_{i-1}^{-1} s_{i-1}}{1+\sigma_i^2 w_i^2} \mathcal{E}_{i-1} + \sum_{i=1}^t \frac{\eta_i^2 w_i^2}{1+\sigma_i^2w_i^2} . \label{b4613} \end{align}\tag{18}\] Since on the event \(\mathcal{E}\) the conclusion of Lemma 9 and Lemma 10 hold, we have \[\begin{align} \sum_{i=1}^t\frac{2\eta_i x_i^\top H_{i-1}^{-1} s_{i-1}}{1+\sigma_i^2 w_i^2} \mathcal{E}_{i-1} \leq \frac{3}{4}{\beta_{t}}^2,\quad \sum_{i=1}^t \frac{\eta_i^2 w_i^2}{1+\sigma_i^2w_i^2} \leq \frac{1}{4}{\beta_{t}}^2 . \label{b4614} \end{align}\tag{19}\] Therefore, substituting 19 into 18 yields \(Z_t \le \beta_{t}(\delta)\), which completes the induction. By a union bound, the events in Lemma 9 and Lemma 10 both hold with probability at least \(1 - \delta\). Hence, with probability at least \(1 - \delta\), for all \(t\), \(Z_t \le \beta_{t}\).

12.1 Proof of Lemma 9↩︎

We now proceed to apply Freedman’s inequality, as stated in Lemma 14. We have \[\begin{align} \left| \frac{2x_i^\top H_{i-1}^{-1} s_{i-1}}{1 + \sigma_i^2 w_i^2}\mathcal{E}_{i-1}\right| \leq \frac{2 \|x_i\|_{H_{i-1}^{-1}} \big[\| s_{i-1}\|_{H_{i-1}^{-1}}\mathcal{E}_{i-1}\big]}{1 + \sigma_i^2 w_i^2} \leq \frac{2 w_i \beta_{i-1}}{1 + \sigma_i^2 w_i^2} \leq \min\{1/\sigma_i, 2w_i\} \beta_{i-1}. \label{b463} \end{align}\tag{20}\] Here, the first inequality follows from the Cauchy–Schwarz inequality, the second follows from the definition of \(\mathcal{E}_{i-1}\), and the final inequality follows by simple algebra. For simplicity, let \(\ell_i\) denote \[\begin{align} \ell_i = \frac{2\eta_i x_i^\top H_{i-1}^{-1} s_{i-1}}{1 + \sigma_i^2 w_i^2}\mathcal{E}_{i-1} . \end{align}\] We now apply Freedman’s inequality from Lemma 14 to the sequences \((\ell_i)_i\) and \((\mathcal{G}_i)_i\). First, note that \(\mathbb{E}[\ell_i | \mathcal{G}_i] = 0\). Moreover, by 20 , the following inequalities hold almost surely: \[\begin{align} |\ell_i|\leq M \beta_{i-1} \min\{1/\sigma_i,2w_i\} \leq \frac{2MN}{\sqrt{\lambda}}{\beta_{t}}, \label{b465} \end{align}\tag{21}\] where the last inequality follows since \((\beta_{i})_i\) is non-decreasing in \(i\) and by the fact that \[\begin{align} w_i = \|x_i\|_{H_{i-1}^{-1}} \leq \|x_i\|_2 /\sqrt{\lambda} \leq N /\sqrt{\lambda}. \label{eq:w} \end{align}\tag{22}\] We also have \[\begin{align} \sum_{i=1}^t \mathbb{E}[\ell_i^2| \mathcal{G}_i] &\leq \sum_{i=1}^t \sigma_i^2 \bigg( \frac{2 x_i^\top H_{i-1}^{-1} s_{i-1}}{1 + \sigma_i^2 w_i^2}\mathcal{E}_{i-1} \bigg)^2 \nonumber \\ &\leq \sum_{i=1}^t \sigma_i^2 \left( \min \{1/\sigma_i, 2w_i\} \beta_{i-1}\right)^2 \nonumber \\ &=\sum_{i=1}^t \left( \min \{1, 2w_i \sigma_i\}\beta_{i-1}\right)^2 \nonumber \\ &\leq 4 {\beta_{t}}^2 \sum_{i=1}^t \min \{1, (w_i \sigma_i)^2\}, \nonumber \end{align}\] where the first inequality holds by the definition of \(\sigma_i\), the second inequality follows from 20 , the third inequality holds since \((\beta_{i})_i\) is non-decreasing. Since \[\begin{align} \sum_{i=1}^t \min \{1, (w_i \sigma_i)^2\} = \sum_{i=1}^t \min \{1, \| \sigma_i x_i\|_{H_{i-1}^{-1}}^2\} \leq 2 \log\frac{\det H_t}{\det \lambda\mathbf{I}}, \label{eq:y1} \end{align}\tag{23}\] where the last inequality follows from Lemma 15. Substituting this back yields, \[\begin{align} \sum_{i=1}^t \mathbb{E}[\ell_i^2| \mathcal{G}_i] \leq 8 {\beta_{t}}^2 \log \det \bigg(\sum_{i=1}^t \frac{\sigma_i^2}{\lambda} x_i x_i^\top + \mathbf{I}\bigg). \label{b466} \end{align}\tag{24}\] Therefore, by [b.5,b.6], using Lemma 14, we know that for any \(t\), with probability at least \(1-\delta/(4t^2)\), we have \[\begin{align} \sum_{i=1}^t \ell_i &\leq \sqrt{16{\beta_{t}}^2 \log \det \bigg(\sum_{i=1}^t \frac{\sigma_i^2}{\lambda} x_i x_i^\top + \mathbf{I} \bigg) \log(4t^2/\delta)} + \frac{2}{3} \cdot \frac{2MN}{\sqrt{\lambda}} {\beta_{t}} \log(4t^2/\delta) \nonumber \\ &\leq \frac{{\beta_{t}}^2}{4} + 16 \log \det \bigg(\sum_{i=1}^t \frac{\sigma_i^2}{\lambda} x_i x_i^\top + \mathbf{I} \bigg) \log(4t^2/\delta) + \frac{{\beta_{t}}^2}{4} + \frac{4M^2N^2}{\lambda} \log^2(4t^2/\delta) \nonumber \\ &\leq \frac{{\beta_{t}}^2}{2} + \frac{1}{4}\left[8\sqrt{\log \det \bigg(\sum_{i=1}^t \frac{\sigma_i^2}{\lambda} x_i x_i^\top + \mathbf{I}\bigg) \log(4t^2/\delta)} + \frac{4MN}{\sqrt{\lambda}} \log(4t^2/\delta)\right]^2 \nonumber \\ &= \frac{3}{4}{\beta_{t}}^2 , \label{b467} \end{align}\tag{25}\] where the second inequality follows from the fact that \(2\sqrt{|ab|}\le |a|+|b|\), and the final equality follows from the definition of \(\beta_{t}\). Applying a union bound to 25 from \(t=1\) to \(\infty\) and using the fact that \(\sum_{t=1}^\infty t^{-2}<2\) completes the proof.

12.2 Proof of Lemma 10↩︎

Similarly to Lemma 9, we apply Freedman’s inequality from Lemma 14 to the sequences \((\ell_i)_i\) and \((\mathcal{G}_i)_i\), where now \[\begin{align} \ell_i = \frac{\eta_i^2 w_i^2}{1+\sigma_i^2w_i^2} - \mathbb{E}\left[\frac{\eta_i^2 w_i^2}{1+\sigma_i^2w_i^2} \Bigg| \mathcal{G}_i\right] . \end{align}\]

First, with 22 , we derive a crude upper bound for the following term: \[\begin{align} \left|\frac{\eta_i^2 w_i^2}{1+\sigma_i^2w_i^2}\right| \leq |\eta_i^2 w_i^2| \leq \frac{M^2N^2}{\lambda}. \label{eq:cb} \end{align}\tag{26}\] Now, for any \(i\), we have \(\mathbb{E}[\ell_i| \mathcal{G}_i] = 0\) almost surely. Furthermore, we can see that \[\begin{align} \sum_{i=1}^t \mathbb{E}[\ell_i^2| \mathcal{G}_i] &\leq \sum_{i=1}^t \mathbb{E}\left[\frac{\eta_i^4 w_i^4}{(1+\sigma_i^2w_i^2)^2} \Bigg| \mathcal{G}_i\right] \nonumber \\ & \leq \frac{M^2N^2}{\lambda}\sum_{i=1}^t \mathbb{E}\left[\frac{\eta_i^2 w_i^2}{1+\sigma_i^2w_i^2} \Bigg| \mathcal{G}_i\right] \nonumber \\ & \leq \frac{M^2N^2}{\lambda} \sum_{i=1}^t \frac{\sigma_i^2 w_i^2}{1+\sigma_i^2w_i^2} \nonumber \\ & \leq \frac{2M^2N^2}{\lambda} \log\det\bigg(\sum_{i=1}^t \frac{\sigma_i^2}{\lambda}x_ix_i^\top + \mathbf{I} \bigg), \label{b469} \end{align}\tag{27}\] where the first inequality follows from the fact that \(\mathbb{E}(X - \mathbb{E}[X])^2 \le \mathbb{E}[X^2]\), the second follows from 26 , the third follows from the definition of \(\eta_i\), and the fourth follows from the bound \(\sigma_i^2 w_i^2/(1 + \sigma_i^2 w_i^2) \le \min\{1, \sigma_i^2 w_i^2\}\) together with the result in 23 . Furthermore, applying 26 again gives \[\begin{align} |\ell_i|\leq \left|\frac{\eta_i^2 w_i^2}{1+\sigma_i^2 w_i^2} \right| + \left|\mathbb{E}\left[\frac{\eta_i^2 w_i^2}{1+\sigma_i^2 w_i^2} \Bigg| \mathcal{G}_i \right]\right| \leq \frac{2M^2N^2}{\lambda}, \label{b4610} \end{align}\tag{28}\] almost surely. Therefore by 27 and 28 , using Lemma 14, we know that for any \(t\), with probability at least \(1-\delta/(4t^2)\), we have \[\begin{align} &\sum_{i=1}^t \frac{\eta_i^2 w_i^2}{1+\sigma_i^2 w_i^2} \nonumber \\ &\quad\leq \sum_{i=1}^t \mathbb{E}\left[ \frac{\eta_i^2 w_i^2}{1+\sigma_i^2 w_i^2} \Bigg| \mathcal{G}_i \right] + \sqrt{\frac{4M^2N^2}{\lambda} \log\det\bigg(\sum_{i=1}^t \frac{\sigma_i^2}{\lambda}x_ix_i^\top + \mathbf{I} \bigg) \log(4t^2/\delta)} \nonumber\\ &\quad\quad +\frac{2}{3}\cdot\frac{2M^2N^2}{\lambda}\log(t^2/\delta) \nonumber \\ &\quad\leq \sum_{i=1}^t \frac{\sigma_i^2 w_i^2}{1+\sigma_i^2 w_i^2}+\sqrt{\frac{4M^2N^2}{\lambda} \log\det\bigg(\sum_{i=1}^t \frac{\sigma_i^2}{\lambda}x_ix_i^\top + \mathbf{I} \bigg) \log(4t^2/\delta)} \nonumber \\ &\quad\quad+ \frac{4M^2N^2}{\lambda}\log(4t^2/\delta) \nonumber \\ &\quad\leq 2\log\det\bigg(\sum_{i=1}^t \frac{\sigma_i^2}{\lambda}x_ix_i^\top + \mathbf{I}\bigg)+ \sqrt{\frac{4M^2N^2}{\lambda} \log\det\bigg(\sum_{i=1}^t \frac{\sigma_i^2}{\lambda}x_ix_i^\top + \mathbf{I}\bigg) \log(4t^2/\delta)} \nonumber \\ &\quad\quad + \frac{4M^2N^2}{\lambda}\log(4t^2/\delta) \nonumber \\ &\quad\leq \frac{1}{4} \cdot \left[8\sqrt{\log\det\bigg(\sum_{i=1}^t \frac{\sigma_i^2}{\lambda}x_ix_i^\top + \mathbf{I} \bigg) \log(4t^2/\delta)} + \frac{4MN}{\sqrt{\lambda}} \log(4t^2/\delta)\right]^2 \nonumber \\ &\quad=\frac{1}{4}{\beta_{t}}^2 , \label{b4611} \end{align}\tag{29}\] where the second inequality follows from the definition of \(\sigma_i^2\), the third follows from the bound \(\sigma_i^2 w_i^2/(1+\sigma_i^2 w_i^2)\leq\min\{1,\sigma_i^2 w_i^2\}\) together with the result in 23 , and the final inequality follows from the definition of \(\beta_{t}\). Applying a union bound to 29 for \(t=1\) to \(\infty\) and using the fact that \(\sum_{t=1}^\infty t^{-2}<2\) completes the proof.

13 Proof of Lemmas in 6↩︎

For clarity, we assume that Condition 2 always holds. We then define the quantity \(\alpha(z',z'')\) via the mean-value theorem, and introduce two additional analogous definitions for brevity as follows: \[\begin{align} \alpha(z',z'') &= \frac{\mu(z')-\mu(z'')}{z'-z''} = \int_{v=0}^1 \dot{\mu}\big(z' + v(z''-z')\big) dv, \nonumber \\ \alpha(x, \theta',\theta'') &= \alpha\Big(g(x;\theta_0)^\top(\theta'-\theta_0), g(x;\theta_0)^\top(\theta''-\theta_0) \Big), \nonumber \\ \alpha(x', x'', \theta) &= \alpha\Big(g(x';\theta_0)^\top(\theta-\theta_0), g(x'';\theta_0)^\top(\theta-\theta_0) \Big). \label{eq:alpha} \end{align}\tag{30}\] For the design matrix \(X_t\) associated with the time-varying regularization parameter \(\lambda_t\), we denote by \(\widetilde{X}_t\) the corresponding matrix formed using the initial regularization parameter \(\lambda_0\). For example, \[\begin{align} \widetilde{V}_t &= \sum_{i=1}^t \frac{1}{m} g(x_i;\theta_0) g(x_i;\theta_0)^\top + \kappa\lambda_0 \mathbf{I}, \nonumber \\ \widetilde{H}_t(\theta) &= \sum_{i=1}^t \frac{1}{m} \dot{\mu}(g(x_i;\theta_0)^\top(\theta_i-\theta_0)) g(x_i;\theta_0) g(x_i;\theta_0)^\top + \lambda_0 \mathbf{I} \nonumber \\ \widetilde{W}_t &= \sum_{i=1}^t \frac{1}{m} \dot{\mu}(f(x_i;\theta_i))g(x_i;\theta_0) g(x_i;\theta_0)^\top + \lambda_0 \mathbf{I}. \label{eq:tilde} \end{align}\tag{31}\]

13.1 Proof of Lemma 1↩︎

First, we define the auxiliary loss \(\widetilde{L}_t(\theta)\) \[\begin{align} \widetilde{\mathcal{L}}_t(\theta) &= -\sum_{i=1}^t r_i \log \mu(g(x_i;\theta_0)^\top(\theta-\theta_0)) + (1-r_i)\log(1-\mu(g(x_i;\theta_0)^\top(\theta-\theta_0))) \\ &\quad + \frac{m\lambda_t}{2}\|\theta-\theta_0\|_2^2, \end{align}\] and its maximum likelihood estimator \(\hat{\theta}_t = \mathop{\mathrm{arg\,min}}_\theta \widetilde{\mathcal{L}}_t(\theta)\). Then, we use the following definitions: \[\begin{align} \gamma_t(\theta)&=\sum_{i=1}^t\frac{1}{m}\mu(g(x_i;\theta_0)^\top(\theta-\theta_0))g(x_i;\theta_0) + \lambda_t(\theta-\theta_0)\\ \Gamma_t(\theta',\theta'') &= \sum_{i=1}^t \frac{1}{m}\alpha(x_i,\theta',\theta'')g(x_i;\theta_0)g(x_i;\theta_0)^\top + \lambda_t \mathbf{I}, \end{align}\] where \(\alpha(x_i,\theta',\theta'')\) is defined at 30 . We can see that \[\begin{align} &\gamma_t(\theta) - \gamma_t(\theta^*) \\ &\quad= \sum_{i=1}^t \frac{1}{m} \Big( \mu(g(x_i;\theta_0)^\top(\theta-\theta_0)) - \mu(g(x_i;\theta_0)^\top(\theta^*-\theta_0))\Big)g(x_i;\theta_0)+ \lambda_t(\theta-\theta^*)\\ &\quad= \sum_{i=1}^t \frac{1}{m}\alpha(x_i,\theta,\theta^*) g(x_i;\theta_0) g(x_i;\theta_0)^\top (\theta - \theta^*)+ \lambda_t(\theta-\theta^*) \\ &\quad=\Gamma_t(\theta,\theta^*)(\theta- \theta^*), \end{align}\] which implies that \[\begin{align} \|\theta - \theta^* \|_{\Gamma_t(\theta,\theta^*)} = \|\gamma(\theta) - \gamma(\theta^*)\|_{\Gamma_t^{-1}(\theta,\theta^*)}. \label{eq:4} \end{align}\tag{32}\]

Now we provide the following two lemmas:

Now we are ready to start the proof.

13.2 Proof of Lemma 11↩︎

Recall the definition of \(\widetilde{\mathcal{L}}_t(\theta)\), \(\hat{\theta}_t\), \(\gamma_t(\theta)\), and \(\Gamma_t(\theta',\theta'')\) from 13.1. Since \(\hat{\theta}_t\) is a maximum likelihood estimator, \(\widetilde{L}_t(\hat{\theta}_t)=0\), which gives \[\begin{align} \sum_{i=1}^t \frac{1}{m}\mu(g(x_i;\theta_0)^\top (\hat{\theta}_t-\theta_0))g(x_i;\theta_0) + \lambda_t (\hat{\theta}_t-\theta_0) = \sum_{i=1}^t \frac{1}{m}r_i g(x_i;\theta_0). \label{eq:6} \end{align}\tag{36}\] Therefore, we can see that \[\begin{align} &\sqrt{m}\|\gamma(\hat{\theta}_t)-\gamma(\theta^*)\|_{H_t^{-1}(\theta^*)} \nonumber \\ &\quad=\sqrt{m}\left\|\sum_{i=1}^t \frac{1}{m}[\mu(g(x_i;\theta_0)^\top (\hat{\theta}_t - \theta_0))-\mu(g(x_i;\theta)^\top(\theta^*-\theta_0))]g(x_i;\theta_0) + \lambda_t\hat{\theta}_t - \lambda_t\theta^* \right\|_{H_t^{-1}(\theta^*)} \nonumber \\ &\quad =\sqrt{m}\left\|\sum_{i=1}^t \frac{1}{m} [r_i - \mu(g(x_i;\theta_0)^\top(\theta^*-\theta_0)]g(x_i;\theta_0) - \lambda_t (\theta^*-\theta_0) \right\|_{H_t^{-1}(\theta^*)} \nonumber \\ &\quad \leq \underbrace{\left\| \sum_{i=1}^t \frac{1}{\sqrt{m}} [r_i - \mu(g(x_i;\theta_0)^\top(\theta^*-\theta_0)]g(x_i;\theta_0)\right\|_{H_t^{-1}(\theta^*)}}_{\boldsymbol{(term 1)}} + \underbrace{\sqrt{\lambda_t m }\|\theta^*-\theta_0\|_2}_{\boldsymbol{(term 2)}}, \label{eq:8} \end{align}\tag{37}\] where the first equality follows from the definition, the second equality is due to 36 , and the first inequality follows from triangle inequality, and the fact that \(\lambda_{\max}(H_t^{-1}(\theta^*))\leq 1/\sqrt{\lambda_t}\).

For (term 1), we are going to use our new tail inequality for martingales in Theorem 1. Define \(\eta_i = r_i - \mu(g(x_i;\theta_0)^\top(\theta^*-\theta_0))=r_i-\mu(h(x_i))\). Then, we can see the following conditions are satisfied: \[\begin{align} |\eta_i|\leq 1,~\mathbb{E}[\eta_i|\mathcal{G}_i]=0,~\mathbb{E}[\eta_i^2|\mathcal{G}_i]=\dot{\mu}(g(x_i;\theta_0)^\top(\theta^*-\theta_0)). \end{align}\] By Lemma 6 we have \(\|g(x_i;\theta_0)/\sqrt{m}\|_2\leq C_1\sqrt{L}\) for some absolute constant \(C_1>0\). Therefore, applying Theorem 1 gives \[\begin{align} &\left\|\sum_{i=1}^t \frac{1}{\sqrt{m}}\eta_t g(x_i;\theta_0)\right\|_{H_t^{-1}(\theta^*)} \nonumber \\ &\quad\leq\left\|\sum_{i=1}^t \frac{1}{\sqrt{m}}\eta_t g(x_i;\theta_0)\right\|_{\widetilde{H}_t^{-1}(\theta^*)} \nonumber \\ &\quad\leq 8 \sqrt{\log \det \left(\sum_{i=1}^t\frac{1}{4m\lambda_0}g(x_i;\theta_0)g(x_i;\theta_0)^\top + I\right)\log\frac{4t^2}{\delta}} + 4C_1\sqrt{\frac{L}{\lambda_0}}\log\frac{4t^2}{\delta}, \label{eq:7} \end{align}\tag{38}\] with probability at least \(1-\delta\). Substituting 38 into 37 gives \[\begin{align} &\sqrt{m}\|\gamma(\hat{\theta}_t)-\gamma(\theta^*)\|_{H_t^{-1}(\theta^*)} \nonumber \\ &\quad \leq 8 \sqrt{\log \det \left(\sum_{i=1}^t\frac{1}{4m\lambda_0}g(x_i;\theta_0)g(x_i;\theta_0)^\top + \mathbf{I} \right)\log\frac{4t^2}{\delta}} + 4C_1\sqrt{\frac{L}{\lambda_0}}\log\frac{4t^2}{\delta} + S\sqrt{\lambda_t} \nonumber \\ &\quad\leq 16 \sqrt{\log \det \left(\sum_{i=1}^t\frac{1}{4m\lambda_0}g(x_i;\theta_0)g(x_i;\theta_0)^\top + \mathbf{I} \right)\log\frac{4t^2}{\delta}} + 8C_1\sqrt{\frac{L}{\lambda_0}}\log\frac{4t^2}{\delta} \nonumber \\ &\quad= \iota_t.\label{eq:10} \end{align}\tag{39}\] where the last inequality is due to the update rule of \(\lambda_t\) and the fact that \(\sqrt{a+b}\leq \sqrt{a}+\sqrt{b}\). We finish the proof.

13.3 Proof of Lemma 12↩︎

We modified the previous results of [10] (Lemma 2), and [12] (proof of Lemma 1), proper to our settings.

The proof is deferred to 13.4. Following the proof of Lemma 13, from 40 , we have \[\begin{align} \Gamma_t(\theta,\hat{\theta}_t) &\geq \Big(1 + C_1 L^{1/2}\lambda_t^{-1/2} \cdot \sqrt{m} \|\gamma_t(\theta) - \gamma_t(\hat{\theta}_t)\|_{\Gamma_t^{-1}(\theta,\hat{\theta}_t)} \Big)^{-1} H_t(\theta) \\ &\geq \left(1 + C_1^2\frac{L}{\lambda_t}\iota_t^2 + C_1\sqrt{\frac{L}{\lambda_t}}\iota_t \right)^{-1} H_t(\theta) \end{align}\] where the last inequality follows from applying Lemma 13 again.

One can achieve the same result for \(H_t(\hat{\theta}_t)\) in a similarly way by starting the proof of Lemma 13 with \[\begin{align} \Gamma_t(\theta,\hat{\theta}_t) &= \sum_{i=1}^t \alpha(x_i,\theta,\hat{\theta}_t)g(x_i;\theta_0)g(x_i;\theta_0)^\top + \lambda_t \mathbf{I} \\ &\geq \sum_{i=1}^t\big(1+|g(x_i;\theta_0)^\top(\theta-\hat{\theta}_t)|\big)^{-1} \dot{\mu}(g(x_i;\theta_0)^\top(\hat{\theta}_t-\theta_0))g(x_i;\theta_0)g(x_i;\theta_0)^\top + \lambda_t \mathbf{I} \\ &\geq \bigg(1 + C_1 \sqrt{\frac{L}{\lambda_t}} \cdot \sqrt{m} \|\gamma_t(\theta) - \gamma_t(\hat{\theta}_t)\|_{\Gamma_t^{-1}(\theta,\hat{\theta}_t)} \bigg)^{-1} H_t(\hat{\theta}_t) \\ &\geq \bigg(1 + C_1^2\frac{L}{\lambda_t}\iota_t^2 + C_1\sqrt{\frac{L}{\lambda_t}}\iota_t \bigg)^{-1} H_t(\hat{\theta}_t), \end{align}\] where the first inequality follows from Lemma 16, the second inequality follows the same process of 40 , and the last inequality follows from Lemma 13, finishing the proof.

13.4 Proof of Lemma 13↩︎

Recall the definition of \(\Gamma_t\) and \(\alpha(x,\theta',\theta'')\) from 30 . We start with \[\begin{align} \Gamma_t(\theta,\hat{\theta}_t) &= \sum_{i=1}^t \alpha(x_i,\theta,\hat{\theta}_t)g(x_i;\theta_0)g(x_i;\theta_0)^\top + \lambda_t \mathbf{I} \\ &\geq \sum_{i=1}^t\big(1+\underbrace{|g(x_i;\theta_0)^\top(\theta-\hat{\theta}_t)|}_{\boldsymbol{(term 1)}}\big)^{-1} \dot{\mu}(g(x_i;\theta_0)^\top(\theta-\theta_0))g(x_i;\theta_0)g(x_i;\theta_0)^\top + \lambda_t \mathbf{I}, \end{align}\] where the inequality follows from Lemma 16. For (term 1), we have, \[\begin{align} \boldsymbol{(term 1)} &\leq \|g(x_i;\theta_0)/\sqrt{m}\|_{\Gamma_t^{-1}(\theta,\hat{\theta}_t)}\cdot \sqrt{m} \|\theta-\hat{\theta}_t\|_{\Gamma_t(\theta,\hat{\theta}_t)} \\ & \leq C_1 L^{1/2}\lambda_t^{-1/2} \cdot \sqrt{m} \|\theta-\hat{\theta}_t\|_{\Gamma_t(\theta,\hat{\theta}_t)} \\ & \leq C_1 L^{1/2}\lambda_t^{-1/2} \cdot \sqrt{m} \|\gamma_t(\theta) - \gamma_t(\hat{\theta}_t)\|_{\Gamma_t^{-1}(\theta,\hat{\theta}_t)}, \end{align}\] where the first inequality follows from the Cauchy-Schwarz inequality, the second inequality follows from the fact that \(\lambda_{\max}(\Gamma(\cdot)^{-1})\leq \lambda_t^{-1}\) and Lemma 6, and the last inequality follows from 32 . Substituting (term 1) back gives, \[\begin{align} \Gamma_t(\theta,\hat{\theta}_t) &\geq \Big(1 + C_1 L^{1/2}\lambda_t^{-1/2} \cdot \sqrt{m} \|\gamma_t(\theta) - \gamma_t(\hat{\theta}_t)\|_{\Gamma_t^{-1}(\theta,\hat{\theta}_t)} \Big)^{-1} \nonumber \\ &\quad \times\sum_{i=1}^t \dot{\mu}(g(x_i;\theta_0)^\top(\theta-\theta_0))g(x_i;\theta_0)g(x_i;\theta_0)^\top + \lambda_t \mathbf{I} \nonumber \\ &\geq \Big(1 + C_1 L^{1/2}\lambda_t^{-1/2} \cdot \sqrt{m} \|\gamma_t(\theta) - \gamma_t(\hat{\theta}_t)\|_{\Gamma_t^{-1}(\theta,\hat{\theta}_t)} \Big)^{-1} \nonumber \\ &\quad \times \Big( \sum_{i=1}^t \dot{\mu}(g(x_i;\theta_0)^\top(\theta-\theta_0))g(x_i;\theta_0)g(x_i;\theta_0)^\top + \lambda_t \mathbf{I}\Big) \nonumber \\ &= \Big(1 + C_1 L^{1/2}\lambda_t^{-1/2} \cdot \sqrt{m} \|\gamma_t(\theta) - \gamma_t(\hat{\theta}_t)\|_{\Gamma_t^{-1}(\theta,\hat{\theta}_t)} \Big)^{-1} H_t(\theta) \label{eq:26} \end{align}\tag{40}\] Using this results, we can further obtain \[\begin{align} &\sqrt{m}\|\gamma_t(\theta)-\gamma_t(\hat{\theta}_t)\|_{\Gamma_t^{-1}(\theta,\hat{\theta}_t)}^2 \\ &\quad \leq \Big(1 + C_1 L^{1/2}\lambda_t^{-1/2} \cdot \sqrt{m} \|\gamma_t(\theta) - \gamma_t(\hat{\theta}_t)\|_{\Gamma_t^{-1}(\theta,\hat{\theta}_t)} \Big) \cdot \sqrt{m}\|\gamma_t(\theta) - \gamma_t(\hat{\theta}_t)\|_{H_t^{-1}(\theta)}^2 \\ &\quad \leq \iota_t^2 + C_1L^{1/2}\lambda_t^{-1/2}\iota_t^2 \cdot \sqrt{m} \|\gamma_t(\theta) - \gamma_t(\hat{\theta}_t)\|_{\Gamma_t^{-1}(\theta,\hat{\theta}_t)}, \end{align}\] where the last inequality follows from Lemma 11. We solve the polynomial inequality in \(\sqrt{m}\|\gamma_t(\theta)-\gamma_t(\hat{\theta}_t)\|_{\Gamma_t^{-1}(\theta,\hat{\theta}_t)}\) using a fact that for \(b,c>0\) and \(x\in\mathbb{R}\), following implication holds: \(x^2\leq bx+c \Longrightarrow x\leq b+ \sqrt{c}\), which finally gives \[\begin{align} \sqrt{m}\|\gamma_t(\theta)-\gamma_t(\hat{\theta}_t)\|_{\Gamma_t^{-1}(\theta,\hat{\theta}_t)}\leq C_1\sqrt{\frac{L}{\lambda_t}} \iota_t^2 + \iota_t \end{align}\]

13.5 Proof of Lemma 4↩︎

First, we show that we can upper bound on the prediction error for all \(x\in\mathcal{X}_t\), \(t\in[T]\), which is the difference between the true reward \(\mu(h(x))\) with our prediction with the neural network \(\mu(f(x;\theta_t))\). For \(x\in\mathcal{X}_{t+1}\) and the absolute constant \(C_3>0\), the prediction error is defined as \[\begin{align} &|\mu(h(x)) - \mu(f(x;\theta_t))| \nonumber \\ &\quad \leq R [h(x) - f(x;\theta_t)] \nonumber \\ &\quad = R[g(x;\theta_0)^\top(\theta^*-\theta_0) - f(x;\theta_t)] \nonumber \\ &\quad \leq R[\underbrace{g(x;\theta_0)^\top(\theta^*-\theta_0) - g(x;\theta_0)^\top (\theta_t-\theta_0)}_{\boldsymbol{(term 1)}} + C_3 m^{-1/6}\sqrt{\log m} L^3 t^{2/3} \lambda_t^{-2/3}], \label{eq:17} \end{align}\tag{41}\] where the first inequality is due to the fact that \(\mu(\cdot)\) is \(R\)-Lipschitz function, the equality follows from Lemma 3, and the last inequality follows from Lemma 7. For (term 1), we have \[\begin{align} \boldsymbol{(term 1)} &= g(x;\theta_0)^\top (\theta^* - \theta_t) \nonumber \\ &= \frac{1}{\sqrt{m}}g(x;\theta_0)^\top\cdot H^{-1/2}_t(\theta^*) \cdot H^{1/2}_t(\theta^*)\cdot\sqrt{m}(\theta^* - \theta_t) \nonumber \\ &\leq \|g(x;\theta_0)/\sqrt{m}\|_{H^{-1}_t(\theta^*)} \cdot \sqrt{m}\|\theta^* - \theta_t\|_{H_t(\theta^*)} \nonumber\\ &\leq \sqrt{\kappa}\|g(x;\theta_0)/\sqrt{m}\|_{V^{-1}_t} \cdot \sqrt{m}\|\theta^* - \theta_t\|_{H_t(\theta^*)} \nonumber \\ &\leq \sqrt{\kappa} \|g(x;\theta_0)/\sqrt{m}\|_{V^{-1}_t} \cdot \big(C_6(1 + \sqrt{L}S + LS^2)\iota_t + 1\big) \label{eq:16}, \end{align}\tag{42}\] where the first inequality follows from the Cauchy-Schwarz inequality, the second inequality is due to the Assumption 4 that \(\frac{1}{\kappa}V_t\preceq H_t^{-1}(\theta^*)\), and the last inequality follows from Lemma 1. Plugging 42 into 41 gives \[\begin{align} &|\mu(h(x)) - \mu(f(x;\theta_t))| \nonumber \\ &\quad \leq R\sqrt{\kappa}\big(C_6(1 + \sqrt{L}S + LS^2)\iota_t + 1\big) \|g(x;\theta_0)/\sqrt{m}\|_{V^{-1}_t} + C_3R m^{-1/6}\sqrt{\log m} L^3 t^{2/3} \lambda_t^{-2/3} \nonumber \\ &\quad\leq R\sqrt{\kappa}\big(C_6(1 + \sqrt{L}S + LS^2)\iota_t + 1\big) \|g(x;\theta_0)/\sqrt{m}\|_{V^{-1}_t} + \epsilon_{3,t}, \label{eq:18} \end{align}\tag{43}\] where the second inequality follows from the fact that \(\lambda_0\leq\min\{\lambda_t\}_{t\geq 1}\) and the definition of \(\epsilon_{3,t}\).

14 Proof of lemmas in 5↩︎

14.1 Proof of Lemma 2↩︎

Recall the definition of \(\widetilde{L}_t(\theta)\), \(\hat{\theta}_t\), \(\gamma_t(\theta)\), \(\Gamma_t(\theta',\theta'')\), \(\iota_t\), and \(\lambda_t\) from 13.1. We also use \[\begin{align} W_t &= \sum_{i=1}^t \frac{\dot{\mu}(f(x_i;\theta_i))}{m} g(x_i;\theta_0) g(x_i;\theta_0)^\top + \lambda_t \mathbf{I} \\ H_t(\hat{\theta}_t) &= \sum_{i=1}^t \frac{\dot{\mu}(g(x_i;\theta_0)^\top(\hat{\theta}_t-\theta_0))}{m} g(x_i;\theta_0) g(x_i;\theta_0)^\top + \lambda_t \mathbf{I} \\ Z_t & = \sum_{i=1} \frac{|\dot{\mu}(f(x_i;\theta_i)) - \dot{\mu}(g(x_i;\theta_0)^\top(\hat{\theta}_t-\theta_0))|}{m} g(x_i;\theta_0) g(x_i;\theta_0)^\top + \lambda_t \mathbf{I} \end{align}\] By the definition of \(Z_t\), for any \(x\in\mathbb{R}^p\), we have \[\begin{align} \|x\|_{W_t} \leq \|x\|_{H_t(\hat{\theta}_t) + Z_t} \leq \|x\|_{H_t(\hat{\theta}_t)} + \|x\|_{Z_t}. \end{align}\]

Now with the above inequality, we can start with \[\begin{align} \sqrt{m} \|\theta_t-\theta^*\|_{W_t} \leq \underbrace{\sqrt{m} \|\theta_t - \theta^*\|_{H_t(\hat{\theta}_t)}}_{\boldsymbol{(term 1)}} + \underbrace{\sqrt{m}\|\theta_t-\theta^*\|_{Z_t}}_{\boldsymbol{(term 2)}}. \label{eq:25} \end{align}\tag{44}\] For (term 1), we directly follow the proof of Lemma 1 in 13.1. Therefore, for the absolute constants \(\{C_i\}_{i=1}^3\), we have \[\begin{align} &\sqrt{m} \|\theta_t - \theta^*\|_{H_t(\hat{\theta}_t)} \\ &\quad \leq \sqrt{m}\|\hat{\theta}_t-\theta^*\|_{H_t(\hat{\theta}_t)} + \sqrt{m} \|\theta_t-\hat{\theta}_t\|_{H_t(\hat{\theta}_t)} \\ &\quad \leq \underbrace{\sqrt{m}\|\hat{\theta}_t - \theta^*\|_{H_t(\hat{\theta}_t)}}_{\boldsymbol{(term 3)}}+\underbrace{2(\lambda_t + C_1 t L)(1-\eta m \lambda_t)^{J/2} t^{1/2}\lambda_t^{-1/2}}_{\boldsymbol{(term 4)}} \nonumber \\ &\quad\quad + \underbrace{(\lambda_t + C_1 t L)\Big[C_2 m^{-1/6}\sqrt{\log m}t^{7/6}\lambda_t^{-7/6}L^{7/2} + C_1 C_3 R m^{-1/6}\sqrt{\log m} L^{7/2} t^{5/3} \lambda_t^{-5/3}\Big]}_{\boldsymbol{(term 5)}}. \end{align}\] Using the same argument as in 13.1, we can see that \[\begin{align} \boldsymbol{(term 4)} \leq 2S\sqrt{\lambda_t} \leq \iota_t,\quad \boldsymbol{(term 5)} \leq 1/2. \end{align}\] Note that the upper bound for (term 5) has been changed from \(1\) to \(1/2\) solely to unify the constant in the concentration inequalities of Lemma 1 and Lemma 2. For (term 3), we have \[\begin{align} \sqrt{m}\Big\|\hat{\theta}_t - \theta^*\Big\|_{H_t(\hat{\theta}_t)}&\leq \sqrt{m(1+2\sqrt{2}C_1 \sqrt{L}S + 8C_1^2 L S^2)}\Big\|\hat{\theta}_t-\theta^*\Big\|_{\Gamma_t(\hat{\theta}_t,\theta^*)} \nonumber \\ &= \sqrt{m(1+2\sqrt{2}C_1 \sqrt{L}S + 8C_1^2 L S^2)}\Big\|\gamma(\hat{\theta}_t)-\gamma(\theta^*)\Big\|_{\Gamma_t^{-1}(\hat{\theta}_t,\theta^*)} \nonumber \\ &\leq (1+2\sqrt{2}C_1 \sqrt{L}S + 8C_1^2 L S^2)\sqrt{m}\Big\|\gamma(\hat{\theta}_t)-\gamma(\theta^*)\Big\|_{H_t^{-1}(\theta^*)} \\ &\leq (1+2\sqrt{2}C_1 \sqrt{L}S + 8C_1^2 L S^2) \iota_t, \end{align}\] where the first and the second inequalities follow from Lemma 12, the equality follows from 35 , and the last inequality follows from Lemma 11. Plugging (term 3-5) into (term 1) gives \[\begin{align} \boldsymbol{(term 1)} \leq (2+C_1 \sqrt{L}S + C_1 L S^2)\iota_t + 1/2. \end{align}\]

Now, moving on to (term 2), we have \[\begin{align} \sqrt{m} \| \theta_t - \theta^* \|_{Z_t} &\leq \underbrace{\sqrt{m} \|\theta_t-\theta^*\|_2}_{\boldsymbol{(term 6)}} \times \underbrace{\lambda^{1/2}_{\max}(Z_t}_{\boldsymbol{(term 7)}}). \end{align}\]

For (term 7), we have \[\begin{align} \lambda_{\max}^{1/2}(Z_t) &= \lambda_{\max}^{1/2}\left( \sum_{i=1}^t\frac{|\dot{\mu}(f(x_i;\theta_i)) - \dot{\mu}(g(x_i;\theta_0)^\top(\hat{\theta}_t-\theta_0))|}{m}g(x_i;\theta_0)g(x_i;\theta_0)^\top\right) \\ & \leq \lambda_{\max}^{1/2}\left( \sum_{i=1}^t\frac{C_3 R m^{-1/6} \sqrt{\log m}L^3t^{2/3}\lambda_t^{-2/3}}{m}g(x_i;\theta_0)g(x_i;\theta_0)^\top\right) \\ &\leq C_3 R^{1/2} m^{-1/12} (\log m)^{1/4} t^{5/6} L^2 \lambda_t^{-1/3}. \end{align}\] Here, the first inequality follows from the Lipschitz continuity of \(\dot{\mu}\), the bounds \(|\ddot\mu|\le\dot{\mu}\le R\), and Lemma 7, while the final inequality follows from \(\lambda_{\max}(\sum_{i=1}^t x_ix_i^\top) \leq\sum_{i=1}^t\|x_i\|_2^2\) and used Lemma 6. For (term 6) we have \[\begin{align} \sqrt{m}\|\theta_t-\theta^*\|_2 &\leq \sqrt{m}\|\theta_t-\theta_0\|_2 + \sqrt{m} \|\theta^* - \theta_0\|_2 \leq 3 t^{1/2} \lambda_t^{-1/2} + S, \end{align}\] where the last inequality follows from Lemmas 8 and 3. Plugging (term 6-7) back to (term 2) gives, \[\begin{align} \boldsymbol{(term 2)}&\leq C_3 R^{1/2} m^{-1/12} (\log m)^{1/4} t^{4/3} L^2 \lambda_t^{-5/6} + C_3 S R^{1/2} m^{-1/12} (\log m)^{1/4} t^{5/6} L^2 \lambda_t^{-1/3} \\ &\leq C_3 R^{1/2} m^{-1/12} (\log m)^{1/4} T^{4/3} L^2 \lambda_0^{-5/6} + C_3 S R^{1/2} m^{-1/12} (\log m)^{1/4} T^{5/6} L^2 \lambda_0^{-1/3} \\ &\leq 1/2 + 2S \lambda_t^{1/2}\\ &\leq 1/2 + \iota_t, \end{align}\] where the third inequality is followed by the condition on \(m\) in Condition 7, and the last inequality is due to the update rule of \(\lambda_t\). Finally, substituting (term 1-2) into 44 gives \[\begin{align} \sqrt{m} \|\theta_t-\theta^*\|_{W_t} &\leq (3+2\sqrt{2}C_1 \sqrt{L}S + 8C_1^2 L S^2)\iota_t + 1 \\ &\leq C_7(1+ \sqrt{L}S + L S^2)\iota_t + 1, \end{align}\] for some absolute constant \(C_7>0\), finishing the proof.

15 Regret Analyses↩︎

15.1 Proof of 3↩︎

We start with a proposition for the per-round regret:

With Proposition 8, we have \[\begin{align} \mu(h(x_t^*)) - \mu(h(x_t)) &\leq \min\Big\{2R\sqrt{\kappa}\nu_{t-1}^{(1)} \|g(x_t;\theta_0)/\sqrt{m}\|_{V^{-1}_{t-1}} + 2\epsilon_{3,t-1}, 1\Big\} \nonumber \\ &\leq \min\Big\{2R\sqrt{\kappa}\nu_{t-1}^{(1)} \|g(x_t;\theta_0)/\sqrt{m}\|_{V^{-1}_{t-1}} , 1\Big\}+ 2\epsilon_{3,t-1} \nonumber \\ &\leq 2R\sqrt{\kappa}\nu_{t-1}^{(1)}\min\Big\{ \|g(x_t;\theta_0)/\sqrt{m}\|_{V^{-1}_{t-1}}, 1\Big\} + 2\epsilon_{3,t-1}\\ &\leq 2R\sqrt{\kappa}\nu_{T}^{(1)}\min\Big\{ \|g(x_t;\theta_0)/\sqrt{m}\|_{V^{-1}_{t-1}}, 1\Big\} + 2\epsilon_{3,T}. \end{align}\] Here, the first inequality follows from \(0 \le |\mu(\cdot) - \mu(\cdot)| \le 1\), the second from the bound \(\min\{a+b,1\}\leq\min\{a,1\}+b\) for \(b>0\), the third from the facts that \(2R\sqrt{\kappa} \geq 1\) and \(\nu_{t}^{(1)}\geq1\) for all \(t\), thereby using \(\min\{ab,1\}\leq a\min\{b,1\}\) if \(a\geq 1\), and the last inequality follows from the fact that both \(\nu_t\) and \(\epsilon_{3,t}\) are monotonically non-decreasing in \(t\).

Now, we can proceed as \[\begin{align} \text{Regret}(T) &= \sum_{t=1}^T \mu(h(x_t^*)) - \mu(h(x_t)) \\ &\leq 2R\sqrt{\kappa}\nu_{T}^{(1)}\sum_{t=1}^T\min\Big\{ \|g(x_t;\theta_0)/\sqrt{m}\|_{V^{-1}_{t-1}}, 1\Big\} + 2T\epsilon_{3,T}, \end{align}\] where we can see that by the condition of \(m\) in Condition 7, \[\begin{align} T\epsilon_{3,T} = C_3R m^{-1/6}\sqrt{\log m} L^3 T^{5/3} \lambda_0^{-2/3} \leq 1, \end{align}\] plugging this back gives, \[\begin{align} \text{Regret}(T) &\leq 2R\sqrt{\kappa}\nu_{T}^{(1)}\sum_{t=1}^T\min\Big\{ \|g(x_t;\theta_0)/\sqrt{m}\|_{V^{-1}_{t-1}}, 1\Big\} +1 \\ &\leq 2R\sqrt{\kappa}\nu_{T}^{(1)} \sqrt{T\sum_{i=1}^T \min\Big\{ \|g(x_t;\theta_0)/\sqrt{m}\|^2_{\widetilde{V}^{-1}_{t-1}}, 1\Big\}} + 1 \\ &\leq 2R\sqrt{\kappa}\nu_{T}^{(1)} \sqrt{2T \log \det \left(\sum_{t=1}^T \frac{1}{\kappa m\lambda_0} g(x_t;\theta_0)g(x_t;\theta_0)^\top + \mathbf{I}\right)} + 1 \\ &\leq 2R\sqrt{\kappa}\nu_{T}^{(1)} \sqrt{2T \widetilde{d}} + 1 , \end{align}\] where the second inequality follows from the Cauchy–Schwarz inequality and the relation \(V_{t-1}\succeq \widetilde{V}_{t-1}\), the third follows from Lemma 15, and the final inequality follows from the definition of \(\widetilde{d}\). Notice that \[\begin{align} \iota_T &=16 \sqrt{\log \det \left(\sum_{t=1}^T\frac{1}{4m\lambda_0}g(x_t;\theta_0)g(x_t;\theta_0)^\top + \mathbf{I} \right)\log\frac{4T^2}{\delta}} + 8C_1\sqrt{\frac{L}{\lambda_0}}\log\frac{4T^2}{\delta}\\ &\leq 16\sqrt{\widetilde{d}\log(4T^2/\delta)} + \sqrt{4C_1(2L)^{1/2}S\log^{-1}(4/\delta)} \log (4T^2/\delta), \end{align}\] where the last inequality follows from the definition of \(\widetilde{d}\) and the initialization rule of \(\lambda_0\), which gives \(\nu_{T}^{(1)} = \widetilde{\mathcal{O}}(S^2\sqrt{\widetilde{d}}+S^{2.5})\). Finally, plugging \(\nu_{T}^{(1)}\) in gives, \[\begin{align} \text{Regret}(T) = \widetilde{\mathcal{O}}\Big( S^2\widetilde{d}\sqrt{\kappa T} + S^{2.5} \sqrt{\kappa\widetilde{d} T} \Big), \end{align}\] finishing the proof.

15.2 Proof of 5↩︎

First, for each \(t\in\mathbb{N}\), define the set of timesteps \[\begin{align} \mathcal{T}_1(t) & = \Big\{t'\in[t]: \left|f(x_{t'};\theta_{t'}) - g(x_{t'};\theta_0)^\top(\theta^*-\theta_0))\right|\geq 1\Big\}. \label{eq:event1} \end{align}\tag{45}\] This set contains exactly those timesteps where \(\theta_{t'}\) lies outside the parameter set (when \(\|\theta_{t'}-\theta_0\|_2 > S\)). Based on this, we form a pruned design matrix by removing the corresponding feature vectors while preserving their original order. In particular, for the regularized covariance matrix \(V_t\), we obtain \[\begin{align} \underline{V}_t = \sum_{i=1}^t \frac{1}{m}\mathbb{1}\{i\notin \mathcal{T}_1\} g(x_i;\theta_0) g(x_i;\theta_0)^\top + \lambda_t \mathbf{I} = \sum_{i=1}^{t-|\mathcal{T}_1(t)|} \frac{1}{m}g(x_{\tau(i)};\theta_0)g(x_{\tau(i)};\theta_0)^\top + \lambda_t \mathbf{I}. \end{align}\] Here, \(\tau: \{1,\dots,t-|\mathcal{T}_1(t)|\}\to\{1,\dots,t\}\) maps each \(j\) to the \(j\)-th smallest element of \([t]\setminus\mathcal{T}_1(t)\). Similarly, we define \(H_t(\theta)\) and \(W_t\) as: \[\begin{align} \underline{H}_t(\theta) &=\sum_{i=1}^{t-|\mathcal{T}_1(t)|} \frac{\dot{\mu}(g(x_{\tau(i)};\theta_0)^\top(\theta-\theta_0))}{m}g(x_{\tau(i)};\theta_0)g(x_{\tau(i)};\theta_0)^\top + \lambda_t \mathbf{I},\\ \underline{W}_t &=\sum_{i=1}^{t-|\mathcal{T}_1(t)|} \frac{\dot{\mu}(f(x_{\tau(i)};\theta_{\tau(i)}))}{m}g(x_{\tau(i)};\theta_0)g(x_{\tau(i)};\theta_0)^\top + \lambda_t \mathbf{I}. \end{align}\] Same way as before, we will denote \(\widetilde{\underline{V}}_t\), \(\widetilde{\underline{H}}_t(\theta)\), \(\widetilde{\underline{W}}_t\) as the design matrix where the regularization parameter \(\lambda_t\) is replaced to \(\lambda_0\).

Using our new design matrices and the self‐concordant property of the logistic function (see Lemma 16; cf.Lemma 9 of [9], Lemma 7 of [10], and Lemma 5 of [25]), we can show that the true‐variance design matrix \(\underline{H}(\theta^*)\) is bounded by the empirical‐variance design matrix \(\underline{W}_t\).

Next, we define three additional sets of timesteps derived from \(\mathcal{T}_1\): \[\begin{align} \mathcal{T}_2 &= \Big\{t\in[T-|\mathcal{T}_1(T)|] : \big|g(x_{\tau(t)};\theta_0)^\top(\widetilde{\theta}_{\tau(t)-1}-\theta^*)\big| \geq 1 \Big\}, \nonumber \\ \mathcal{T}_3 &= \Big\{t\in[T-|\mathcal{T}_1(T)|]: \Big\|g(x_{\tau(t)};\theta_0)/\sqrt{m}\Big\|_{\underline{\widetilde{V}}_{{\tau(t-1)}}^{-1}} \geq 1 \Big\}, \nonumber \\ \mathcal{T}_4 &= \Big\{t\in[T-|\mathcal{T}_1(T)|]: \Big\|\sqrt{\dot{\mu}(f(x_{\tau(t)};\theta_{\tau(t)}))}g(x_{\tau(t)};\theta_0)/\sqrt{m}\Big\|_{\underline{\widetilde{W}}_{{\tau(t-1)}}^{-1}} \geq 1 \Big\}. \label{eq:event23} \end{align}\tag{46}\]

We define \(\mathcal{T}_2\) to measure the distance between \(g(x_{\tau(t)};\theta_0)^\top\widetilde{\theta}_{\tau(t)-1}\) and \(h(x_{\tau(t)})\) and control the estimation error of the neural network. We introduce \(\mathcal{T}_3,\mathcal{T}_4\) to control the value of \(\|g(x_{\tau(t)};\theta_0)/\sqrt{m}\|_{\underline{\widetilde{V}}_{{\tau(t-1)}}^{-1}}\) and \(\|\sqrt{\dot{\mu}(f(x_{\tau(t)};\theta_{\tau(t)}))}g(x_{\tau(t)};\theta_0)/\sqrt{m}\|_{\underline{\widetilde{W}}_{{\tau(t-1)}}^{-1}}\) in order to apply the elliptical potential lemma (Lemma 15).

Next, we introduce two propositions to bound the cardinality of \(\mathcal{T}_1(T)\), \(\mathcal{T}_2\), \(\mathcal{T}_3\) and \(\mathcal{T}_4\):

For Proposition 10, we use the concentration inequalities between \(\theta_{\tau(t)}\) and \(\theta^*\), and \(\widetilde{\theta}_{\tau(t)-1}\) and \(\theta^*\) using Lemmas 1 and 2. For Proposition 11 we modified previous results appropriate to our setting called the elliptical potential count lemma (Lemma 7 of [34], Lemma 4 of [35]).

Now we can start the proof of 5.

15.3 Proof of Proposition 9↩︎

We suitably modify Lemma 5 of [25] for our setting. Define \(d(t) = \left|f(x_t;\theta_t) - g(x_t;\theta_0)^\top(\theta^*-\theta_0))\right|\). By the definition of \(\mathcal{T}_1\), for all \(t\notin\mathcal{T}_1(T)\), \(d(t)\leq 1\). Recall the definition of \(\alpha(z',z'')\) at 30 . Then for all \(t\notin\mathcal{T}_1(T)\), we have \[\begin{align} \dot{\mu}(f(x_t;\theta_t)) &\geq \frac{d(t)}{\exp(d(t))-1}\cdot \alpha\Big(f(x_t;\theta_i),g(x_t;\theta_0)^\top(\theta^*-\theta_0)\Big) \\ &\geq \frac{d(t)}{\exp(d(t))-1} \cdot \frac{1-\exp(-d(t))}{d(t)} \dot{\mu}(g(x_t;\theta_0)^\top(\theta^*-\theta_0)) \\ & =\frac{1}{\exp(d(t))}\cdot \mu(g(x_t;\theta_0)^\top(\theta^*-\theta_0))\\ &\geq \frac{1}{d(t)^2 +d(t) + 1} \cdot \mu(g(x_t;\theta_0)^\top(\theta^*-\theta_0))\\ &\geq \frac{1}{2d(t)+1} \cdot \mu(g(x_t;\theta_0)^\top(\theta^*-\theta_0)), \end{align}\] where the first and the second inequalities follow from the self-concordant property in Lemma 16, the third and the fourth inequalities hold since \(d(t)\leq 1\). This implies that \[\begin{align} \underline{W}_{t}\succeq \frac{1}{2\max\{d(t')\}_{(t'\in[t])\cap(t'\notin\mathcal{T}_1(t))}+1} \underline{H}_{t}(\theta^*) \succeq \frac{1}{3} \underline{H}_{t}(\theta^*), \end{align}\] In a similar way, we can have \[\begin{align} \underline{H}_{t}(\theta^*)\succeq \frac{1}{2\max\{d(t')\}_{(t'\in[t])\cap(t'\notin\mathcal{T}_1(t))}+1} \underline{W}_{t}\succeq \frac{1}{3} \underline{W}_{t}. \end{align}\] Combining these results, we finish the proof.

15.4 Proof of Proposition 10↩︎

We start with the upper bound of \(|\mathcal{T}_1|\). For an absolute constant \(C_3>0\), we have: \[\begin{align} |\mathcal{T}_1| \cdot \min\{1,1^2\} &\leq \sum_{t=1}^T\min\Big\{1,|f(x_t;\theta_t) - g(x_t;\theta_0)^\top (\theta^*-\theta_0)|^2\Big\} \\ &\leq \sum_{t=1}^T\min\Big\{1,2|f(x_t;\theta_t) - g(x_t;\theta_0)^\top(\theta_t-\theta_0)|^2 + 2|g(x_t;\theta_0)^\top (\theta_t-\theta^*)|^2\Big\}, \end{align}\] For \(2|f(x_t;\theta_t) - g(x_t;\theta_0)^\top(\theta_t-\theta_0)|^2\), we have \(|f(x_t;\theta_t) - g(x_t;\theta_0)^\top(\theta_t-\theta_0)| \leq C_3 m^{-1/6} \sqrt{\log m} L^3 t^{2/3} \lambda_t^{-2/3}\) using Lemma 7. Since the error term is positive, we can take it out of the \(\min\{1,\cdot\}\) term, which gives \[\begin{align} |\mathcal{T}_1| &\leq \sum_{t=1}^T\min\Big\{1,2|g(x_t;\theta_0)^\top (\theta_t - \theta^*) |^2\Big\} + C_3^2 m^{-1/3} (\log m) L^6 T^{7/3}\lambda_0^{-4/3} \\ &\leq 2\sum_{t=1}^T\min\Big\{1,|g(x_t;\theta_0)^\top (\theta_t - \theta^*) |^2 \Big\} + 1, \end{align}\] where the last inequality is due to the condition of \(m\) at Condition 2, and the fact that \(\min\{1,ab\}\leq a \min\{1,b\}\) if \(a\geq 1\). We further proceed as \[\begin{align} |\mathcal{T}_1| &\leq 2\sum_{t=1}^T \min\Big\{1,\|g(x_t;\theta_0)/\sqrt{m}\|_{H_{t-1}^{-1}(\theta^*)}^2 \cdot m\|\theta_{t}-\theta^*\|_{H_{t-1}(\theta^*)}^2\Big\} + 1. \end{align}\] For \(m\|\theta_{t}-\theta^*\|_{H_{t-1}(\theta^*)}^2\), we have \[\begin{align} m\|\theta_{t}-\theta^*\|_{H_{t-1}(\theta^*)}^2 \leq m\|\theta_{t}-\theta^*\|_{H_{t}(\theta^*)}^2 \leq \big(\nu_t^{(1)}\big)^2. \end{align}\] Since \(\nu_t^{(1)}\geq 1\) we can take out of the \(\min\{1,\cdot\}\) term, and by the monotonicity of \(\nu_t^{(1)}\) in \(t\), we have \[\begin{align} |\mathcal{T}_1| &\leq 2 \big(\nu_T^{(1)}\big)^2 \sum_{t=1}^T \min \Big\{1, \|g(x_t;\theta_0)/\sqrt{m}\|_{H_{t-1}^{-1}(\theta^*)}^2\Big\} + 1 \\ &\leq 2 \kappa \big(\nu_T^{(1)}\big)^2 \sum_{t=1}^T \min \Big\{1, \|g(x_t;\theta_0)/\sqrt{m}\|_{\widetilde{V}_{t-1}^{-1}}^2\Big\} + 1 \\ &\leq 4 \kappa \big(\nu_T^{(1)}\big)^2 \log \frac{\det \widetilde{V}_T}{\det \kappa \lambda_0\mathbf{I}} + 1 \\ &\leq 4 \kappa \widetilde{d} \big(\nu_T^{(1)}\big)^2+ 1, \end{align}\] where the second inequality follows from \(\kappa\geq 1\), and \(H_t(\theta^*)\succeq (1/\kappa)V_t \succeq (1/\kappa)\widetilde{V}_t\), the third inequality follows from Lemma 15, and the last inequality follows from the definition of \(\widetilde{d}\).

Next we can show the upper bound of \(|\mathcal{T}_2|\) in a similar way: \[\begin{align} |\mathcal{T}_2| \cdot \min\{1,1^2\} &\leq \sum_{t=1}^{T-|\mathcal{T}_1(T)|} \min\Big\{1,|g(x_{\tau(t)};\theta_0)^\top(\widetilde{\theta}_{\tau(t)-1}-\theta^*)|^2\Big\} \\ &\leq \sum_{t=1}^{T-|\mathcal{T}_1(T)|} \min\Big\{1,\|g(x_\tau(t);\theta_0)/\sqrt{m}\|^2_{\underline{W}_{\tau(t-1)}^{-1}}\cdot m\|\widetilde{\theta}_{\tau(t)-1}-\theta^*\|^2_{\underline{W}_{\tau(t-1)}}\Big\} \end{align}\] We have \(\|g(x_{\tau(t)};\theta_0)/\sqrt{m}\|^2_{\underline{W}_{\tau(t-1)}^{-1}}\leq \sqrt{3\kappa} \|g(x_{\tau(t)};\theta_0)/\sqrt{m}\|^2_{\underline{V}_{\tau(t-1)}^{-1}}\) using the result of 50 . Also, we have \(m\|\widetilde{\theta}_{\tau(t)-1}-\theta^*\|^2_{\underline{W}_{\tau(t-1)}}\leq 4\big(\nu_{\tau(t)-1}^{(2)}\big)^2\) using the result of 51 . Since \(\nu_{t}^{(2)}\) is non-decreasing in \(t\), substituting results back gives \[\begin{align} |\mathcal{T}_2| &\leq 12\kappa\big(\nu_{T}^{(2)}\big)^2 \sum_{t=1}^{T-|\mathcal{T}_1(T)|} \min\Big\{1,\|g(x_\tau(t);\theta_0)/\sqrt{m}\|^2_{\underline{V}_{\tau(t-1)}^{-1}}\Big\} \\ &\leq 24\kappa\big(\nu_{T}^{(2)}\big)^2 \log \frac{\det \underline{\widetilde{V}}_{\tau(T-|\mathcal{T}_1|)}}{\det \kappa\lambda_0 \mathbf{I}}\\ &\leq 24 \kappa \widetilde{d} \big(\nu_{T}^{(2)}\big)^2, \end{align}\] where the second inequality follows from Lemma 15, and the last inequality follows from the definition of \(\widetilde{d}\), finishing the proof.

15.5 Proof of Proposition 11↩︎

We begin with the case of \(\mathcal{T}_3\). We define a new design matrix that consists of all feature vectors of \(\underline{V}_t\) up to time \(t\), in their original order, including only those corresponding to timesteps in \(\mathcal{T}_3(t)\): \[\begin{align} \undertilde{\widetilde{V}}_t = \sum_{i=1}^{t-|\mathcal{T}_1(t)|} \frac{1}{m} \mathbb{1}\{i\in \mathcal{T}_3\} g(x_{\tau(i)};\theta_0) g(x_{\tau(i)};\theta_0)^\top + \lambda_0 \mathbf{I} \end{align}\] For brevity we define \(j(t) = \tau(t-|\mathcal{T}_1(t)|)\). Then we have \[\begin{align} \det(\undertilde{\widetilde{V}}_T) &= \det \Big( \sum_{i=1}^{j(T)} \frac{1}{m} \mathbb{1}\{i\in \mathcal{T}_3\} g(x_{\tau(i)};\theta_0) g(x_{\tau(i)};\theta_0)^\top + \lambda_0 \mathbf{I} \Big) \\ &= \det \Big( \underline{\widetilde{V}}_{\tau(j(T)-1)} + \frac{1}{m} \mathbb{1}\{\tau(j(T))\in \mathcal{T}_3\} g(x_{\tau(j(T))};\theta_0) g(x_{\tau(j(T))};\theta_0)^\top\Big) \\ &= \det \Big( \underline{\widetilde{V}}_{\tau(j(T)-1)}\Big)\Big(1 + \mathbb{1}\{\tau(j(T))\in \mathcal{T}_3\} \|g(x_{\tau(j(T))};\theta_0)/\sqrt{m}\|_{\underline{\widetilde{V}}_{\tau(j(T)-1)}^{-1}}^2\Big) \\ &\geq \det \Big( \underline{\widetilde{V}}_{\tau(j(T)-1)}\Big)\Big(1 + \mathbb{1}\{\tau(j(T))\in \mathcal{T}_3\} \Big), \end{align}\] where the third equality follows from the matrix determinant lemma, and the inequality follows from the definition of \(\mathcal{T}_3\). Repeating inequalities to \(\underline{V}_\tau(0)\) gives \[\begin{align} \det(\undertilde{\widetilde{V}}_T) \geq \det \Big( \underline{\widetilde{V}}_{\tau(0)}\Big) \cdot \Big(1 + \mathbb{1}\{\tau(j(T))\in \mathcal{T}_3\} \Big)^{T-|\mathcal{T}_1(T)|} = \det(\kappa \lambda_0 \mathbf{I}) \cdot (1+1)^{|\mathcal{T}_3|}. \end{align}\] Therefore, we can rewrite as \[\begin{align} |\mathcal{T}_3| &\leq \frac{1}{\log 2} \cdot \log \frac{\det \undertilde{\widetilde{V}}_T}{\det \kappa \lambda_0 \mathbf{I}} \leq \frac{1}{\log 2} \cdot \log \frac{\det \widetilde{V}_T}{\det \kappa \lambda_0 \mathbf{I}} \leq 2 \widetilde{d}, \end{align}\] where the last inequality follows from the definition of \(\widetilde{d}\). We can prove \(|\mathcal{T}_4|\leq 2\widetilde{d}\) in a similar way, starting by defining \(\undertilde{\widetilde{W}}_t = \sum_{i=1}^{t-|\mathcal{T}_1(t)|} \frac{\dot{\mu}(f(x_{\tau(i)};\theta_0)}{m} \mathbb{1}\{i\in \mathcal{T}_4\} g(x_{\tau(i)};\theta_0) g(x_{\tau(i)};\theta_0)^\top + \lambda_0 \mathbf{I}\) and following the above process.

16 Auxiliary Lemmas↩︎

17 Thompson Sampling-based Variants↩︎

In this section, we introduce the Thompson sampling-based variants of Algorithm 1, which we call NeuralLog-TS-1. The proof for the regret of Neural-TS-1 can be obtained by exactly following the proof of Theorem 3.5 of [14]. To reuse the result of previous work, we match the notations by using the following definitions: \[\begin{align} \sigma_{t}(x)^2 &:= \kappa \lambda_{t} \| g(x;\theta_0)/\sqrt{m}\|_{V_{t}^{-1}}^2 \\ \nu_{t} &:= \nu_{t}^{(1)}\lambda_{t}^{-1/2} = C_6 \lambda_{t}^{-1/2} (1+\sqrt{L} S + L S^2) \iota_t + \lambda_{t}^{-1/2} \\ c_{t} &:= \nu_T(1 + \sqrt{2\log(Kt^2)}) \end{align}\] and denote \(\mathcal{F}_{t}\) as a filtration containing the history of observations up to iteration \(t\). Also define the set of saturated points as \[\begin{align} \mathcal{S}_t = \{x\in\mathcal{X}_t:~\Delta_t(x) > c_{t-1} \sigma_{t-1}(x) + 2 \epsilon_{t-1}'\}, \label{eq:saturated} \end{align}\tag{58}\] where \(\Delta_t(x) = h(x_t^*) - h(x)\) and \(\epsilon_{t}' = R^{-1} \epsilon_{3,t}\). Note that \(x_t^*\notin \mathcal{S}_t\).

In round \(t\), for each \(x\in\mathcal{X}_t\), we sample a latent reward \(\widetilde{r}_t(x)\) from the normal distribution \[\begin{align} \forall x\in\mathcal{X}_t, \quad \widetilde{r}_t(x) \sim \mathcal{N}(f(x;\theta_{t-1}), \nu_T^2 \sigma_{t-1}^2(x)), \end{align}\] and choose an arm following \[\begin{align} x_t = \mathop{\mathrm{arg\,max}}_{x\in\mathcal{X}_t} \widetilde{r}_t(x). \end{align}\]

Now we introduce two good events: First, define the event \(\mathcal{E}_1(t)\) when the following inequality holds for all \(x\in\mathcal{X}_t\): \[\begin{align} |h(x) - f(x;\theta_{t-1})| \leq \nu_T \sigma_{t-1}(x) + {\epsilon}_{t-1}' . \label{eq:ev1} \end{align}\tag{59}\] Then, by the direct result of Lemma 4, \(\mathbb{P}(\mathcal{E}_1(t)) \geq 1-\delta\). Next, define the event \(\mathcal{E}_2(t)\) when the following inequality holds for all \(x\in\mathcal{X}_t\): \[\begin{align} |\widetilde{r}_t(x) - f(x;\theta_{t-1})| \leq \nu_T\sqrt{2\log(Kt^2)}\sigma_{t-1}(x). \label{eq:ev2} \end{align}\tag{60}\] Since \(\widetilde{r}_t(x)\) is sampled from \(\mathcal{N}(f(x;\theta_{t-1}), \nu_T^2 \sigma_{t-1}^2(x))\), we can use the concentration inequality on Gaussian distributions to obtain \(\mathbb{P}(\mathcal{E}_2(t)|\mathcal{F}_{t-1}) \geq 1- 1/t^2\) for any possible filtration \(\mathcal{F}_{t-1}\).

Next, recall the definition of the set of saturated points in Equation (58 ). We reuse the result of Lemma 4.5 of [14] as follows \[\begin{align} &\mathbb{P}(x_t \in\mathcal{X}_t \setminus \mathcal{S}_t \mid \mathcal{F}_{t-1}, \mathcal{E}_1(t)) \geq (4e\sqrt{\pi})^{-1} - 1/t^2. \label{eq:usa} \end{align}\tag{61}\] We skip the proof as the same argument can be found in Section B.4 of [14]. Instead, we give a high-level intuition. By construction, saturated arms are those whose posterior mean reward is significantly worse than that of the optimal arm. Under the good events \(\mathcal{E}_1(t)\) and \(\mathcal{E}_2(t)\), this gap is reflected both in their true means and in their posterior samples, so with high probability a saturated arm cannot catch up to the optimal arm in terms of the sampled reward.

On the other hand, the posterior for the optimal arm enjoys an anti-concentration property, which is, with constant probability, its sample exceeds its mean by a suitable margin. This is where the factor \((4e\sqrt{\pi})^{-1}\) comes from. Combining these facts, with constant probability the sampled reward of the optimal arm is larger than the samples of all saturated arms, so the arm selected by Thompson sampling must be unsaturated. The \(1/t^2\) term accounts for the small probability that one of the good events \(\mathcal{E}_1(t)\) or \(\mathcal{E}_2(t)\) fails.

Now, with the previous results in place, we derive an upper bound on the expected instantaneous regret. Define \(d_t = h(x_t^*) - h(x_t)\). Again, we reuse the result of Lemma 4.6 of [14] as follows: \[\begin{align} \mathbb{E}[d_t \mid \mathcal{F}_{t-1}, \mathcal{E}_1(t)] \leq 44e\sqrt{\pi}\, C_1 c_t \sqrt{L}\, \mathbb{E}\bigl[\min\{1, \sigma_t(x_t)\} \mid \mathcal{F}_{t-1}, \mathcal{E}_1(t)\bigr] + 4\epsilon_{t-1}' + 2/t^2, \end{align}\] where \(C_1>0\) is the same absolute constant that appears in Lemma 6. By Equation (61 ), Neural-TS-1 selects an unsaturated arm with constant probability, so in expectation the posterior standard deviation of the played arm is comparable to that of the best unsaturated arm. Under the good events, the posterior means stay close to the true means and saturated arms have very small gaps, which allows us to bound the instantaneous regret \(d_t\) by a constant multiple of \(\min\{1,\sigma_t(x_t)\}\) plus the approximation terms \(4\epsilon_{t-1}' + 2/t^2\). Taking the conditional expectation and using a global control on the posterior variances over time then yields the stated bound.

Now we are ready to start the proof for the regret. Define a stochastic process \((Y_t)_{t=0}^T\) where \[\begin{align} \bar d_t &= d_t \boldsymbol{1} \{\mathcal{E}_1(t)\} \\ X_t &= \bar d_t - 44e\sqrt{\pi} C_1 c_t \sqrt{L} \min\{1, \sigma_t(x_t)\} - 4\epsilon_{t-1}' - 2/t^2 \\ Y_t &= \sum_{i=1}^t X_i, \quad Y_0 =0 \end{align}\] We can see that \((Y_t)\) is a supermartingale with respect to \(\mathcal{F}_t\) since \(\mathbb{E}[Y_t-Y_{t-1}\mid\mathcal{F}_{t-1}] = \mathbb{E}[X_t\mid \mathcal{F}_{t-1}] \leq 0\). Now we prepare to apply the Azuma-Hoeffding inequality for a supermartingale:

To derive an upper bound on \(|Y_t-Y_{t-1}|\), we have \[\begin{align} |Y_t-Y_{t-1}| &= |X_t| \leq |\bar d_t| + 44e\sqrt{\pi} C_1 c_t \sqrt{L} \min\{1, \sigma_t(x_t)\} + 4\epsilon_{t-1}' + 2/t^2\\ &\leq 4 + 44e\sqrt{\pi} C_1^2 c_t L + 4 \epsilon_{t-1}'. \end{align}\] where the last inequality follows from Lemma 6, and \(1/t^2\leq 1\). Now, applying Lemma 17 with \(B_t = 4 + 44e\sqrt{\pi}C_1^2 c_t L + 4\epsilon_{t-1}'\) to \((Y_t)\), with probability at least \(1-\delta\), we have \[\begin{align} \sum_{t=1}^T \bar d_t &\leq \underbrace{\sum_{t=1}^T 44e\sqrt{\pi} C_1 c_t \sqrt{L} \min\{1, \sigma_t(x_t)\}}_{\boldsymbol{(term 1)}} + \underbrace{\sum_{t=1}^T 4 \epsilon_{t-1}' + \sum_{t=1}^T 2/t^2}_{\boldsymbol{(term 2)}} \nonumber \\ &\quad + \underbrace{\sqrt{2\log(1/\delta) \sum_{t=1}^T \left(4 + 44e\sqrt{\pi} C_1^2 c_t L + 4 \epsilon_{t-1}'\right)^2}}_{\boldsymbol{(term 3)}}. \label{eq:ts1} \end{align}\tag{62}\] For (term 1), applying Cauchy-Schwarz inequality, \[\begin{align} \boldsymbol{(term 1)} &\leq 44 e \sqrt{\pi} C_1 \nu_T^{(1)}(1+\sqrt{2\log(KT^2)})\sqrt{\kappa L} \sqrt{T \sum_{t=1}^T \min\{1, \|g(x_t;\theta_0)/\sqrt{m}\|_{V_{t-1}^{-1}}^2\}} \\ & = \widetilde{\mathcal{O}} \left(S^2 \widetilde{d} \sqrt{\kappa T} + S^{2.5} \sqrt{\kappa \widetilde{d} T}\right) \end{align}\] For (term 2), by the condition of \(m\) in Condition 2, \(\sum_{t=1}^T 4 {\epsilon}_{t-1}' \leq 1\), and \(\sum_{t=1}^T 2/t^2 \leq \pi^2/3\). For (term 3), since \(\nu_T^{(1)} = \widetilde{\mathcal{O}}(S^2\sqrt{\widetilde{d}} + S^{2.5})\), and \(\lambda_0^{-1/2}=\mathcal{O} (S^{0.5})\) \[\begin{align} \boldsymbol{(term 3)} &\leq (4 + 44 e \sqrt{\pi} C_1^2 \nu_T^{(1)}\lambda_0^{-1/2}(1+\sqrt{2\log(KT^2)}) + 4\epsilon_T')\sqrt{2 \log(1/\delta) T} \\ &= \widetilde{\mathcal{O}}\left( S^{2.5} \sqrt{\widetilde{d} T} + S^{3}\sqrt{T}\right) \end{align}\] Combining results, we have \[\begin{align} \sum_{t=1}^T \widetilde{d}_t \leq \widetilde{\mathcal{O}}\left( S^2 \widetilde{d} \sqrt{\kappa T} + S^{2.5} \sqrt{\kappa \widetilde{d} T} + S^{3}\sqrt{T} \right) \end{align}\] with probability at least \(1-\delta\). Notice that \(\text{Regret}(T) \leq \sum_{t=1}^T R |h(x_t^*) - h(x_t)|\). Therefore \(R \sum_{t=1}^T \widetilde{d}_t\) upper bounds the regret with probability at least \(1-\delta\). Finally, replacing \(\delta\) by \(\delta/2\) for both cases and applying the union bound finishes the proof.

As we have seen in Remark 12, although NeuralLog-TS-2 does not attain a regret bound with the same dependence on \(\kappa\) as NeuralLog-UCB-2, the algorithm itself is well defined, just like NeuralLog-TS-1. In Section 18, we present additional experiments including these two algorithms and demonstrate their practical performance.

18 Additional Experiments↩︎

We compare five baseline algorithms with our algorithms including the Thompson sampling-based variants introduced in Section 17. Where NeuralLog-TS-1 and NeuralLog-TS-2 both choose the arm with best sampled reward where \[\begin{align} &\text{For NeuralLog-TS-1},\quad \widetilde{r}_t(x) \sim \mathcal{N}(f(x;\theta_{t-1}), \nu_T^2 \sigma_{t-1}^2(x)), \\ &\text{For NeuralLog-TS-2},\quad\widetilde{r}_t'(x) \sim\mathcal{N}(g(x;\theta_0)^\top(\theta_{t-1} - \theta_0) , \nu_T'^2 \sigma_{t-1}'^2(x)). \end{align}\] We include the synthetic latent reward functions which are also used in [8]: \(h_4(x)= 10(x^\top \theta)^2\), \(h_5(x) = x^\top \Theta^\top \Theta x\), \(h_6(x) = \cos (3 x^\top \theta)\). All other experimental parameters and details follow the same as described in Section 7.

Next, we include 3 more \(K\)-class classification tasks from [18]: We reuse the same min–max normalization to \([-1,1]\) as described in Section 9. In the magic dataset (MAGIC Gamma Telescope), we convert all features to real-valued variables, impute any missing entries with \(0\), and then map the original class labels to a binary label by setting \(y=1\) for gamma (‘g’) events and \(y=0\) for hadron (‘h’) events. In the banknote dataset (UCI Banknote Authentication), we use the four real-valued attributes provided in the repository and keep the original binary labels \(y\in\{0,1\}\). For the phoneme dataset (Connectionist Bench (Nettalk Corpus)), we treat any categorical fields as numeric by casting them to an appropriate numeric type, and replace missing values with \(0\).

Figures 7 and 8 summarize the average cumulative regret of the five baseline algorithms together with our two Thompson sampling-based variants. Consistent with the results already observed in Figures 4 and 5, our NeuralLog-UCB-2 algorithm steadily achieves the best performance across the considered settings. Moreover, the two Thompson sampling-based variants also exhibit competitive performance compared to the baselines. Figure 9 demonstrates the influence of \(\widetilde{d}\) on data-adaptive algorithms by comparing cumulative regret across different values of \(\widetilde{d}\).

18.1 Open Bandit Dataset Replay Experiments↩︎

We further evaluate the algorithms on the Open Bandit Dataset (OBD) [36], a large-scale public logged bandit dataset collected from a fashion e-commerce platform. This experiment complements the classification-based real-world experiments in [sec:exp,sec:exp2]. While the classification-to-bandit protocol gives access to the reward of every action in each round, logged bandit data provide a more realistic feature distribution and feedback structure. At the same time, as in most real-world bandit evaluations, the assumptions used in the theory are not guaranteed to hold exactly and the problem-dependent quantities such as \(S\) and \(\kappa\) cannot be identified tightly from the data. We therefore use OBD as a practical robustness test under several choices of the theory-motivated parameters.

Open Bandit Dataset setup. We use the random/all split of OBD and run replay evaluation. In each logged event, the agent receives a reduced action set consisting of the logged action and four alternative actions chosen by the highest user-item affinity scores, yielding a \(K=5\)-armed problem. Feedback is used only when the action selected by the agent matches the logged action; otherwise, the event is skipped. Thus the horizontal axis in [fig:obd_m,fig:obd_kappa,fig:obd_S] denotes the number of accepted logged events. Since counterfactual rewards for unchosen actions are not available in OBD, we report cumulative reward and final click-through rate (CTR), rather than cumulative regret.

For the context-arm feature vector, we combine compressed user features, item features from item_context.csv, the display position, the action-specific user-item affinity score, and an interaction feature between user features and the affinity score. The categorical user and item features are one-hot encoded and compressed using truncated SVD, with user embedding dimension 16 and item embedding dimension 8. The affinity scores are log-transformed, scaled to \([-1,1]\), and then used both as an action-specific scalar feature and as part of the interaction feature. We use \(T=2000\) accepted timesteps, batch size 50, and 5 repeated runs. The neural network is updated every 50 accepted events using 100 gradient descent steps with learning rate 0.01. For all algorithms, we use the same exploration and regularization parameters as in the synthetic and classification-based real-world experiments, except for the displayed choices of \(m\), \(S\), and \(\kappa\).

Results. [fig:obd_m,fig:obd_kappa,fig:obd_S] and 2 summarize the OBD replay results. Across the considered values of \(m\), the Thompson sampling-based variants, NeuralLog-TS-1 and NeuralLog-TS-2, consistently achieve the highest final CTR, and one of NeuralLog-UCB-1 or NeuralLog-UCB-2 is also among the top three methods. This indicates that the proposed neural logistic bandit algorithms remain competitive even when the network width is much smaller than the sufficient width required by the NTK-based theory. The same qualitative behavior is observed when varying \(\kappa\): NeuralLog-TS-1, NeuralLog-TS-2, and NeuralLog-UCB-2 are the top three methods for all tested values. Finally, when varying \(S\), the two Thompson sampling-based variants remain the strongest performers, while one of the UCB-based variants remains competitive. These results support the empirical robustness of our methods on real logged bandit data, where the model assumptions and the exact values of the theory-motivated parameters are necessarily misspecified.

19 Additional Future Directions↩︎

Although we successfully remove the direct dependence on \(p\) from the regret bound, a direct dependence on \(p\) reappears when we examine the per-round computational complexity. This is problematic in neural bandit settings where \(p\) scales with the horizon \(T\), making the resulting algorithm computationally inefficient.

Let us briefly analyze the computational complexity of our algorithms. Since Algorithms 1 and 3 have the same order of complexity, we focus on Algorithm 1. For action selection, we must compute \(f(x;\theta_{t-1})\) for \(K\) actions, which costs \(\mathcal{O}(p)\) per action, and the quantity \(\|g(x;\theta_0)/\sqrt{m}\|_{V_{t-1}^{-1}}\), which costs \(\mathcal{O}(p^2)\) per action. Hence, the action-selection step has complexity \(\mathcal{O}(Kp^2)\). The updates of the parameters \(\lambda_t\), \(\iota\), and \(\nu_t^{(1)}\) cost \(\mathcal{O}(p^2)\) by their definitions. For neural network training, at round \(t\) we apply gradient steps over the full dataset of size \(t\), which costs \(\mathcal{O}(tp)\) per gradient step. Performing \(J_t\) iterations therefore costs \(\mathcal{O}(J_t t p)\), where \(J_t = \widetilde{\mathcal{O}}(TL/\lambda_t)\). Finally, updating the design matrix \(V_t\) costs \(\mathcal{O}(p^2)\). Altogether, the per-round computational complexity is \(\mathcal{O}(J_t t p + Kp^2 + p^2)\). Moreover, [11] can be seen to have essentially the same computational complexity, as their algorithm and training pipeline are close to ours.

In contrast, in the classical logistic bandit literature the algorithms operate directly in the feature space of dimension \(d\), which is typically much smaller than \(p\). For example, [3], [9] obtain overall complexity on the order of \(\mathcal{O}(d^2K + d^2T)\), and there has been significant recent progress on designing computationally efficient algorithms for logistic bandits: [10] achieve \(\mathcal{O}(d^2KT)\), and [12] even propose an algorithm with complexity \(\widetilde{\mathcal{O}}(d^2K)\). However, these favorable guarantees rely crucially on the strong assumption that the latent reward model is linear in the feature representation. From the perspective of practical applications, it is therefore important to develop neural bandit algorithms that retain the modeling flexibility of neural networks while achieving comparable computational efficiency, which we view as an important direction for future work.

As one illustrative example, in light of the connection between NTK-based neural bandits and kernelized bandits, one could consider importing techniques such as Nyström approximation as in [37] to reduce the effective computational cost in the neural bandit setting. Another approach is to adapt the method proposed in [31] where an NTK-based neural bandit formulation is also used, but the neural network is trained so that its output is not the reward itself, but instead a new \(d\)-dimensional feature vector. The problem is then reduced to solving a linear bandit in this learned feature space with respect to an unknown parameter \(\theta^*\). This strategy can substantially reduce computational complexity and is attractive from an applied viewpoint, but it requires an additional Lipschitz-type assumption on the neural network on the theoretical side.

References↩︎