Proof. At round \(t \in \mathcal{T}_m\), let \(\boldsymbol{x}_{t,\star}\) be the optimal slate, i.e, \[\boldsymbol{x}_{t,\star} = \mathop{\mathrm{arg\,max}}_{\boldsymbol{x} \in \mathcal{X}_t} \boldsymbol{x}^\top \boldsymbol{\theta}^\star.\] Then, the expected regret for Algorithm 1, \(R(T)\) can be written as \[R(T) \leq \mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i_t \sim \mathcal{D}^i\}_{i=1}^N} \left[\sum_{m \in [M]} \sum_{t \in \mathcal{T}_m} \left\lvert \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star)\right\rvert \right].\] We choose our batch lengths as follows: \[|\mathcal{T}_0| = \lfloor \sqrt{T} \rfloor \quad \text{ and } \quad |\mathcal{T}_m| = \lfloor T^{1 - 2^{-m}} \rfloor , m \geq 1.\] We now make a few observations regarding these batch lengths. First, we obtain a total of \(M = \mathcal{O}(\log \log T)\) batches. We also obtain the following inequalities: \[\frac{|\mathcal{T}_m|}{\sqrt{|\mathcal{T}_{m-1}|}} \leq \frac{T^{1 - 2^{-m}}}{\sqrt{\lfloor T^{1 - 2^{1-m}} \rfloor}} = \frac{\sqrt{T} \cdot T^{\frac{1-2^{1-m}}{2}}}{\sqrt{\lfloor T^{1- 2^{1-m}} \rfloor}} \leq \sqrt{T}, \quad \frac{|\mathcal{T}_m|^2}{|\mathcal{T}_{m-1}|} \leq \frac{T^{2 - 2^{1-m}}}{\lfloor T^{1 - 2^{1-m}} \rfloor} = \frac{T \cdot T^{1 - 2^{1-m}}}{\lfloor T^{1- 2^{1-m}} \rfloor} \leq T.\] Now, to use Lemma 10, we require that \(|\mathcal{T}_0| \geq T(\boldsymbol{V)}\) and \(|\mathcal{T}_k| \geq T(\boldsymbol{H})\) for all \(k \in [M]\). Using the definitions of \(T(\boldsymbol{V})\) and \(T(\boldsymbol{H})\) from Section 7.1 and the chosen batch lengths, we get: \[\sqrt{T} \geq \frac{(48 + 8 N \rho)(N-1)^2}{3\rho^2} \log \left(\frac{2dN T}{\delta} \right) \quad \text{ and } \quad \sqrt{T} \geq \frac{(48 L_\mu^2 + 8 L_\mu N \rho)(N-1)^2}{3\rho^2} \log \left(\frac{2dN T}{\delta} \right).\] Now, since \(L_\mu \geq 1\), the assumptions \[\sqrt{\frac{2dN}{\delta}}\frac{(48 + 8 N \rho)(N-1)^2}{3\rho^2} \geq \frac{e}{2}\] and \[T \geq 2 \geq \frac{\delta}{2dN} \exp\left(\frac{1}{2} \right)\] ensures that we can use Lemma 15 to satisfy the conditions for Lemma 10 giving us \[\begin{align} T &\geq \frac{\delta}{2dN} \exp \left( \max \left\{-2 W_{-1} \left( \frac{-3\rho^2\sqrt\delta}{2\sqrt{2dN} (48 + 8N \rho) (N-1)^2}\right) , -2 W_{-1} \left( \frac{-3\rho^2\sqrt\delta}{2\sqrt{2dN} (48 L_\mu^2 + 8 L_\mu N \rho) (N-1)^2}\right) \right\}\right) \\ &= T_0:= \frac{\delta}{2dN} \exp \left( -2 W_{-1} \left( \frac{-3\rho^2\sqrt\delta}{2\sqrt{2dN} (48 L_\mu^2 + 8 L_\mu N \rho) (N-1)^2}\right)\right) \end{align}\] where we use the fact that \(\exp(-x)\) is decreasing, \(W_{-1}(x)\) is decreasing on \((-e^{-1} , 0)\) (Lemma 15) and \(L_\mu \geq 1\).

Thus, assuming \(T \geq T_0\), using Lemma 10 for \(m \geq 2\), as well as, a trivial regret bound of \(R\) for each round \(t \in \mathcal{T}_0 \cup \mathcal{T}_1\), we get that \[\begin{align} &R(T) \leq R\left(|\mathcal{T}_0| + |\mathcal{T}_1| \right) + \sum_{m \in [2,M]} \sum_{t \in \mathcal{T}_m} \mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i_t \sim \mathcal{D}^i_m\}_{i=1}^N}\left\lvert \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star)\right\rvert. \\ &\leq R\left(|\mathcal{T}_0| + |\mathcal{T}_1| \right) + \sum_{m=2}^M \left[ \frac{320 e^{3S} \gamma^2 N^2 d^2 \sqrt{\kappa L_\mu} }{S} \frac{|\mathcal{T}_m|}{\sqrt{|\mathcal{T}_{m-1}||\mathcal{T}_0|}} + 8 \gamma \sqrt{\mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N} \dot{\mu}(\boldsymbol{x}_{\star}^\top \boldsymbol{\theta}^\star)} \sqrt{\frac{8d^2 N |\mathcal{T}_m|^2}{|\mathcal{T}_{m-1}|} + \frac{4 L_\mu N |\mathcal{T}_m|}{\rho}} \right]. \end{align}\]

Substituting the values of \(|\mathcal{T}_m|\), \(\frac{|\mathcal{T}_m|}{\sqrt{|\mathcal{T}_{m-1}|}}\), \(\frac{|\mathcal{T}_m|^2}{|\mathcal{T}_{m-1}|}\), and using the facts that \(|\mathcal{T}_m| \leq T\) and \(|\mathcal{T}_0| = \lfloor \sqrt{T} \rfloor \geq \sqrt{T}/2\), we get \[\begin{align} R(T) &\leq \left( 8 \gamma \sqrt{\mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i =1}^N} \dot{\mu}(\boldsymbol{x}_{\star}^\top \boldsymbol{\theta}^\star)} \sqrt{8d^2 N + 4L_\mu N \rho^{-1}} \log \log T + 2R \right)\sqrt{T} + \tilde{\mathcal{O}}\left( e^{3S}\sqrt\kappa T^{1/4} \right). \end{align}\] Substituting \(\gamma = \mathcal{O}\left(S R \sqrt{Nd \log (T \delta^{-1})} \right)\) from Lemma 2 gives us \[R(T) = \tilde{\mathcal{O}}\left( RS N d^{3/2} \sqrt{T \cdot \mathop{\mathrm{\mathbb{E}}}_{ \{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N} \dot{\mu}(\boldsymbol{x}_{\star}^\top \boldsymbol{\theta}^\star)} \right).\] ◻

Proof. For the sake of this proof, define \[\boldsymbol{H}_0^\star = \lambda\boldsymbol{I} + \sum_{t \in \mathcal{T}_0} \dot{\mu}(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) \boldsymbol{x}_t\boldsymbol{x}_t^\top.\] Then, using the definition of \(\kappa\), we have that \(\dot{\mu}(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) \geq \kappa^{-1}\). Thus, \[\begin{align} \boldsymbol{H}_0^\star &\succeq \lambda \boldsymbol{I} + \kappa^{-1} \sum_{t \in \mathcal{T}_0} \boldsymbol{x}_t\boldsymbol{x}_t^\top \\ &= \kappa^{-1} \left(\kappa \lambda \boldsymbol{I} + \sum_{t \in \mathcal{T}_0}\boldsymbol{x}_t\boldsymbol{x}_t^\top \right) \\ &\succeq \kappa^{-1} \boldsymbol{V}_0 \end{align}\] where the last inequality uses the fact that \(\lambda \geq 1\) and \(\kappa \geq 1\). Hence, we can write that \[\begin{align} \boldsymbol{x}^\top (\boldsymbol{\theta}^ \star - \widehat{\boldsymbol{\theta}}_0) & \leq \lVert \boldsymbol{\theta}^ \star - \widehat{\boldsymbol{\theta}}_0 \rVert_{\boldsymbol{H}^\star_0} \lVert \boldsymbol{x}\rVert_{{\boldsymbol{H}^\star_0}^{-1}} \\ & \leq \sqrt{\kappa}\gamma \left\lVert \boldsymbol{x} \right \rVert_{\boldsymbol{V}_0^{-1}} \\ & \leq 2 \sqrt\kappa \gamma \sum_{i=1}^N \left\lVert \boldsymbol{x}^i \right \rVert_{(\boldsymbol{V}_0^i)^{-1}} \end{align}\] where the second inequality follows from Lemma 2 and the final inequality follows from Lemma 14. ◻

Proof. Using the triangle inequality, we can write \[\left\lvert (\boldsymbol{x} - \boldsymbol{y})^\top \widehat{\boldsymbol{\theta}}_0 \right\rvert \leq \sum_{i=1}^N \left\lvert (\boldsymbol{x}^i - \boldsymbol{y}^i)^\top \widehat{\boldsymbol{\theta}}^i_0 \right\rvert.\] Now, since both \(\boldsymbol{x}\) and \(\boldsymbol{y}\) survive the elimination, their respective components \(\boldsymbol{x}^i\) and \(\boldsymbol{y}^i\) for all \(i \in [N]\) also do not get eliminated. Thus, for a fixed \(i\), we have \[\textrm{UCB}^{i,0}(\boldsymbol{x}^i) \geq \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \textrm{LCB}^{i,0}(\boldsymbol{z}^i) \geq \textrm{LCB}^{i,0}(\boldsymbol{y}^i).\] Using the definitions of \(\textrm{UCB}^{i,0}(\boldsymbol{z})\) and \(\textrm{LCB}^{i,0}(\boldsymbol{z})\) (Section 7.1), we get \[(\boldsymbol{y}^i - \boldsymbol{x}^i)^\top \widehat{\boldsymbol{\theta}}^i_0 \leq 2 \sqrt\kappa\gamma \lVert \boldsymbol{x}^i \rVert_{(\boldsymbol{V}^i_0)^ {-1}} + 2 \sqrt\kappa\gamma \lVert \boldsymbol{y}^i \rVert_{(\boldsymbol{V}^i_0)^ {-1}}.\] A symmetric argument gives us \[(\boldsymbol{x}^i - \boldsymbol{y}^i)^\top \widehat{\boldsymbol{\theta}}^i_0 \leq 2 \sqrt\kappa\gamma \lVert \boldsymbol{x}^i \rVert_{(\boldsymbol{V}^i_0)^ {-1}} + 2 \sqrt\kappa\gamma \lVert \boldsymbol{y}^i \rVert_{(\boldsymbol{V}^i_0)^ {-1}}.\] Thus, combining both the inequalities, we get \[\begin{align} \left\lvert (\boldsymbol{x}^i - \boldsymbol{y}^i)^\top \widehat{\boldsymbol{\theta}}^i_0 \right\rvert &\leq 2 \sqrt\kappa\gamma \lVert \boldsymbol{x}^i \rVert_{(\boldsymbol{V}^i_0)^ {-1}} + 2 \sqrt\kappa\gamma \lVert \boldsymbol{y}^i \rVert_{(\boldsymbol{V}^i_0)^ {-1}} \\ &\leq 4 \sqrt\kappa \gamma \max_{z \in \mathcal{X}^i_t} \lVert \boldsymbol{z} \rVert_{(\boldsymbol{V}^i_0)^ {-1}} \end{align}\] Substituting this back and using the definition of \(\boldsymbol{b}^i_t\) gives us \[\left\lvert (\boldsymbol{x} - \boldsymbol{y})^\top \widehat{\boldsymbol{\theta}}_0 \right\rvert \leq 4\sqrt\kappa \gamma \sum_{i=1}^N\lVert \boldsymbol{b}^i \rVert_{(\boldsymbol{V}_0^i)^{-1}}.\] ◻

Proof. Recall the definition of \(\boldsymbol{b}_t\) from Section 7.1. From the self-concordance property of GLMs, we have \[\dot{\mu}(\boldsymbol{b}_t^\top\widehat{\boldsymbol{\theta}}_0) \leq \dot{\mu}(\boldsymbol{x}^\top\boldsymbol{\theta}^\star) \exp(\lvert \boldsymbol{b}_t^\top\widehat{\boldsymbol{\theta}}_0 - \boldsymbol{x}^\top \boldsymbol{\theta}^ \star \rvert).\] We can bound \(\lvert \boldsymbol{b}_t^\top\widehat{\boldsymbol{\theta}}_0 - \boldsymbol{x}^\top \boldsymbol{\theta}^\star \rvert\) as follows: \[\lvert \boldsymbol{b}_t^\top\widehat{\boldsymbol{\theta}}_0 - \boldsymbol{x}^\top \boldsymbol{\theta}^\star \rvert \leq \lvert \boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0 \rvert + \lvert \boldsymbol{x}^\top \boldsymbol{\theta}^\star\rvert \leq 2S.\]

Also, using Lemma 3 and Lemma 4, we have \[\begin{align} \lvert \boldsymbol{b}^\top\widehat{\boldsymbol{\theta}}_0 - \boldsymbol{x}^\top \boldsymbol{\theta}^\star \rvert &\leq \lvert \boldsymbol{x}^\top \boldsymbol{\theta}^\star - \boldsymbol{x}^\top \widehat{\boldsymbol{\theta}}_0\rvert + \lvert \boldsymbol{b}^\top\widehat{\boldsymbol{\theta}}_0 - \boldsymbol{x}^\top \widehat{\boldsymbol{\theta}}_0 \rvert \\ &\leq 6\sqrt{\kappa} \gamma \sum_{i=1}^N\lVert \boldsymbol{b}^i \rVert_{(\boldsymbol{V}_0^i)^ {-1}} . \end{align}\]

Thus, combining both the inequalities results in \[\dot{\mu}(\boldsymbol{b}^\top \widehat{\boldsymbol{\theta}}_0) \leq \dot{\mu}(\boldsymbol{x}^\top \boldsymbol{\theta}^\star) \exp\left(\min\left\{2S , 6 \sqrt{\kappa} \gamma \sum_{i=1}^N\lVert \boldsymbol{b}^i \rVert_{(\boldsymbol{V}_0^i)^ {-1}}\right\}\right).\]

Noting that the multiplicative factor on the right side is precisely \(\beta_t\) (refer Section 7.1), we get that: \[\begin{align} \boldsymbol{H}^\star_m &= \lambda \boldsymbol{I}_{Nd} + \sum_{t \in \mathcal{T}_m} \dot{\mu}(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) \boldsymbol{x}_t\boldsymbol{x}_t^\top \\ &\succeq \lambda \boldsymbol{I}_{Nd} + \sum_{t \in \mathcal{T}_m} \dot{\mu}(\boldsymbol{b}^\top \widehat{\boldsymbol{\theta}}_0) \beta_t^{-1} \boldsymbol{x}_t \boldsymbol{x}_t^\top = \boldsymbol{H}_m. \end{align}\] This completes the proof for the first part. For the second part, we have \[\begin{align} \boldsymbol{x}^\top (\boldsymbol{\theta}^ \star - \widehat{\boldsymbol{\theta}}_m) &\leq \lVert \boldsymbol{\theta}^ \star - \widehat{\boldsymbol{\theta}}_m \rVert_{\boldsymbol{H}^\star_m} \lVert \boldsymbol{x}\rVert_{{\boldsymbol{H}^\star_m}^{-1}} \\ &\leq 2 \gamma \sum_{i=1}^N \left\lVert \boldsymbol{x}^i \right \rVert_{(\boldsymbol{H}_m^i)^{-1}}. \end{align}\] where the final inequality follows from Lemma 2 and Lemma 13. ◻

Proof. Using the triangle inequality, we can write \[\left\lvert (\boldsymbol{x} - \boldsymbol{y})^\top \widehat{\boldsymbol{\theta}}_k \right\rvert \leq \sum_{i=1}^N \left\lvert (\boldsymbol{x}^i - \boldsymbol{y}^i)^\top \widehat{\boldsymbol{\theta}}^i_k \right\rvert.\] Now, since both \(\boldsymbol{x}\) and \(\boldsymbol{y}\) survive the elimination, for an arbitrary but fixed slot \(i \in [N]\), their respective components \(\boldsymbol{x}^i\) and \(\boldsymbol{y}^i\) also do not get eliminated. Thus, we have \[\textrm{UCB}^{i,k}(\boldsymbol{x}^i) \geq \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \textrm{LCB}^{i,k}(\boldsymbol{z}^i) \geq \textrm{LCB}^{i,k}(\boldsymbol{y}^i).\] Using the definitions of \(\textrm{UCB}^{i,k}(\boldsymbol{z})\) and \(\textrm{LCB}^{i,k}(\boldsymbol{z})\) (Section 7.1), we get \[(\boldsymbol{y}^i - \boldsymbol{x}^i)^\top \widehat{\boldsymbol{\theta}}^i_k \leq 2 \gamma \lVert \boldsymbol{x}^i \rVert_{(\boldsymbol{H}^i_k)^ {-1}} + 2 \gamma \lVert \boldsymbol{y}^i \rVert_{(\boldsymbol{H}^i_k)^ {-1}}.\] A symmetric argument gives us \[(\boldsymbol{x}^i - \boldsymbol{y}^i)^\top \widehat{\boldsymbol{\theta}}^i_k \leq 2 \gamma \lVert \boldsymbol{x}^i \rVert_{(\boldsymbol{H}^i_k)^ {-1}} + 2 \gamma \lVert \boldsymbol{y}^i \rVert_{(\boldsymbol{H}^i_k)^ {-1}}.\] Thus, combining both the inequalities gives us \[\begin{align} \left\lvert (\boldsymbol{x}^i - \boldsymbol{y}^i)^\top \widehat{\boldsymbol{\theta}}^i_k \right\rvert &\leq 2 \gamma \lVert \boldsymbol{x}^i \rVert_{(\boldsymbol{H}^i_k)^ {-1}} + 2 \gamma \lVert \boldsymbol{y}^i \rVert_{(\boldsymbol{H}^i_k)^ {-1}} \\ &\leq 4\gamma \max_{z \in \mathcal{X}^i_t} \lVert \boldsymbol{z} \rVert_{(\boldsymbol{H}^i_k)^ {-1}}. \end{align}\] Summing over all slots \(i \in [N]\) finishes the proof. ◻

Proof. First, note that since \(\boldsymbol{x}_{t,\star} = \mathop{\mathrm{arg\,max}}_{\boldsymbol{x} \in \mathcal{X}_t} \boldsymbol{x}^\top \boldsymbol{\theta}^\star\), it is easy to see that \(\boldsymbol{x}_{t,\star}^i = \mathop{\mathrm{arg\,max}}_{\boldsymbol{z} \in \mathcal{X}^i_t} \boldsymbol{z}^\top {\boldsymbol{\theta}^\star}^i\), or, in other words \(\tilde{\boldsymbol{x}}^i_{t,\star} = \mathop{\mathrm{arg\,max}}_{\boldsymbol{z} \in \mathcal{X}^i_t}\tilde{\boldsymbol{z}}^\top \boldsymbol{\theta}^ \star\).

Fix \(i \in [N]\). Then, for some arbitrary \(\boldsymbol{z} \in \mathcal{X}^i_t\), we have that \[\begin{align} 0 &\leq \left( \tilde{\boldsymbol{x}}^i_{t,\star} - \tilde{\boldsymbol{z}}\right)^\top \boldsymbol{\theta}^ \star \\ &= \left( \tilde{\boldsymbol{x}}^i_{t,\star} - \tilde{\boldsymbol{z}} \right)^\top \left( \boldsymbol{\theta}^ \star - \widehat{\boldsymbol{\theta}}_0 \right) + \left( \tilde{\boldsymbol{x}}^i_{t,\star} - \tilde{\boldsymbol{z}} \right)^\top \widehat{\boldsymbol{\theta}}_0 \\ &\leq 2 \sqrt\kappa \gamma \lVert {\boldsymbol{x}}^i_{t,\star} \rVert_{(\boldsymbol{V}_0^i)^ {-1}} + 2 \sqrt\kappa \gamma \lVert \boldsymbol{z} \rVert_{(\boldsymbol{V}_0^i)^{-1}} + \left( \tilde{\boldsymbol{x}}^i_{t,\star} - \tilde{\boldsymbol{z}} \right)^\top \widehat{\boldsymbol{\theta}}_0 \\ &= \textrm{UCB}^{i,0}(\boldsymbol{x}^i_{t,\star}) - \textrm{LCB}^{i,0}(\boldsymbol{z}), \end{align}\] where the second inequality follows from Lemma 3. Since this is true \(\forall \boldsymbol{z} \in \mathcal{X}^i_t\), we get \[\textrm{UCB}^{i,0}(\boldsymbol{x}^i_{t,\star}) \geq \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \textrm{LCB}^{i,0}(\boldsymbol{z}),\] or in other words, \[\textrm{UCB}^{i,0}(\boldsymbol{x}^i_{t,\star}) - \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \textrm{LCB}^{i,0}(\boldsymbol{z}) \geq 0.\]

Since this holds for a fixed but arbitrary \(i \in [N]\), the above inequality holds for all \(i \in [N]\).

Similarly, for all \(k \in [1,m-1]\) and \(i \in [N]\), we can show that \[\textrm{UCB}^{i,k}(\boldsymbol{x}^i_{t,\star}) - \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \textrm{LCB}^{i,k}(\boldsymbol{z}) \geq 0.\] Thus, the components of the optimal slate, and hence, the optimal slate never gets eliminated. ◻

Proof. The proof only relies on the manner in which the sequence of distributions \(\{\mathcal{D}^i_j\}_{j \in [M]}\) is constructed. In particular, the pruning step ensures that the set of items that survive the pruning with respect to \(\widehat{\boldsymbol{\theta}}_m\) is always a smaller set than the set of items that survive the pruning with respect to \(\widehat{\boldsymbol{\theta}}_j\) for \(j \leq m-1\). Thus, for some slot \(i \in [N]\), the pruning step gives rise to the following chain of subsets: \[\mathcal{D}^i_m \subseteq \mathcal{D}^i_{m-1} \subseteq \ldots \subseteq \mathcal{D}^i_1 \subseteq \mathcal{D}^i_0 \subseteq \mathcal{D}^i.\] Note that this result is a generalization of Claim A.11 from [13] to the slate setting. Hence, the claim follows. ◻

Proof. Using a first-order Taylor series expansion, for some \(z_t \in [\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star, \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star]\), we have that \[\left\lvert \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) \right\rvert \leq \dot{\mu}(z_t) \left\lvert\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star \right\rvert.\]

Further, using Lemma 5 and Lemma 6, we have \[\begin{align} \dot{\mu}(z_t) \left\lvert \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star \right\rvert &\leq \dot{\mu}(z_t) \lvert\boldsymbol{x}_{t,\star}^ \top \boldsymbol{\theta}^ \star - \boldsymbol{x}_{t,\star}^ \top \widehat{\boldsymbol{\theta}}_{m-1} \rvert + \dot{\mu}(z_t) \lvert\boldsymbol{x}_{t}^ \top \boldsymbol{\theta}^ \star - \boldsymbol{x}_{t}^ \top \widehat{\boldsymbol{\theta}}_{m-1} \rvert + \dot{\mu}(z_t) \lvert\boldsymbol{x}_{t,\star}^ \top \widehat{\boldsymbol{\theta}}_{m-1} - \boldsymbol{x}_{t}^ \top \widehat{\boldsymbol{\theta}}_{m-1} \rvert \\ &\leq 8\gamma \sum_{i=1}^N \dot{\mu}(z_t) \max_{\boldsymbol{u} \in \mathcal{X}^i_t}\lVert \boldsymbol{u} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}}. \end{align}\]

Define \(\breve{\boldsymbol{x}} := \sqrt{\dot{\mu}(\boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0) \beta_t^{-1}} \boldsymbol{x}\), then, we have \[\left\lvert \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) \right\rvert \leq 8\gamma \sum_{i=1}^N \sqrt{\frac{\dot{\mu}(z_t)^2 \beta_t}{\dot{\mu}(\boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0)}} \max_{\boldsymbol{u} \in \mathcal{X}^i_t}\lVert \breve{\boldsymbol{u}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}}.\] Using the self-concordance property of GLMs, we have that \[\frac{\dot{\mu}(z_t)}{\dot{\mu}(\boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0)} \leq \exp\left(R \left\lvert z_t - \boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0 \right\rvert \right).\] Since \(z_t \in [\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star , \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star]\), a trivial bound using \(\lVert \boldsymbol{x} \rVert \leq 1\) and \(\lVert \boldsymbol{\theta}^\star \rVert \leq S\) gives us \[\lvert z_t - \boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0 \rvert \leq 2S.\] Also, since the optimal slate \(\boldsymbol{x}_{t,\star}\) never gets eliminated (Lemma 7), using Lemma 3 and Lemma 4 gives us \[\begin{align} \lvert z_t - \boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0 \rvert &\leq \lvert \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0 \rvert + \lvert \boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0 - \boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0 \rvert + \lvert \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star - z_t \rvert \\ &\overset{}{\leq} 6\sqrt{\kappa} \gamma \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}} + \lvert \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star \rvert \end{align}\] and again, using Lemma 3, Lemma 4, and Lemma 7, we have \[\begin{align} \left\lvert \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star \right\rvert &\leq \lvert\boldsymbol{x}_{t,\star}^ \top \boldsymbol{\theta}^ \star - \boldsymbol{x}_{t,\star}^ \top \widehat{\boldsymbol{\theta}}_{0} \rvert + \lvert\boldsymbol{x}_{t}^ \top \boldsymbol{\theta}^ \star - \boldsymbol{x}_{t}^ \top \widehat{\boldsymbol{\theta}}_{0} \rvert + \lvert\boldsymbol{x}_{t,\star}^ \top \widehat{\boldsymbol{\theta}}_{0} - \boldsymbol{x}_{t}^ \top \widehat{\boldsymbol{\theta}}_{0} \rvert \\ &\leq 8\sqrt{\kappa} \gamma \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}}. \end{align}\]

Thus, we get \[\frac{\dot{\mu}(z_t)}{\dot{\mu}(\boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0)} \leq \exp\left(R \min \left\{2S , 14\sqrt{\kappa} \gamma \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}} \right\} \right).\]

Similarly, we also have \[\dot{\mu}(z_t) \leq \dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) \exp \left(R \lvert z_t - \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star \rvert \right),\] where the argument of the exponent can be bounded as \[\lvert z_t - \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star \rvert \leq \lvert \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star \rvert \leq 8\sqrt{\kappa} \gamma \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}},\] and hence, \[\dot{\mu}(z_t) \leq \dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) \exp \left(R \min \left\{2S , 8\sqrt{\kappa} \gamma \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}} \right\} \right).\] Using the definition of \(\beta_t\) (Section 7.1), we get \[\sqrt{\frac{\dot{\mu}(z_t)^2 \beta_t}{\dot{\mu}(\boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0)}} \leq \exp\left(R \min \left\{3S , 14\sqrt{\kappa} \gamma \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}} \right\} \right) \sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)}.\] Finally, using Claim A.8 from [13], we get \[\sqrt{\frac{\dot{\mu}(z_t)^2 \beta_t}{\dot{\mu}(\boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0)}} \leq \left(\frac{5 e^{3S} \sqrt{\kappa} \gamma}{S} \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}} + 1\right)\sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)}.\] Substituting this back, we get \[\left\lvert \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) \right\rvert \leq 8 \gamma \sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} \left( \sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \right) \left(\frac{5 e^{3S} \sqrt{\kappa} \gamma}{S} \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}} + 1\right).\] ◻

Proof. Define \(\breve{\boldsymbol{x}} := \sqrt{\dot{\mu}(\boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0) \beta_t^{-1}} \boldsymbol{x}\) and \(\mathop{\mathrm{\mathbb{E}}}\limits_{\{\mathcal{X}^i_t \sim \mathcal{D}^i_m\}_{i=1}^N} \left[.\right]\) as \(\mathop{\mathrm{\mathbb{E}}}\limits_{t,m}[.]\). Then, using Lemma 9, we wish to bound the following two terms (excluding constants):

\[1. \mathop{\mathrm{\mathbb{E}}}_{t,m} \sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} \left( \sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \right) \left( \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}} \right)\] \[2. \mathop{\mathrm{\mathbb{E}}}_{t,m} \sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} \left( \sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \right) \phantom{\left( \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}} \right)}\]

Note that we can write \[\boldsymbol{H}_m^i = \lambda\boldsymbol{I} + \sum_{t \in \mathcal{T}_m} \breve{\boldsymbol{x}}^i_t(\breve{\boldsymbol{x}}^i_t)^\top,\] and hence, using Lemma 11 and Lemma 12 in tandem, we get \[\mathop{\mathrm{\mathbb{E}}}_{\mathcal{X}^i \sim \mathcal{D}^i} \max_{\boldsymbol{z} \in \mathcal{X}^i} \lVert \boldsymbol{z} \rVert^2_{(\boldsymbol{V}_0^i)^{-1}} \leq \frac{8 d^2}{|\mathcal{T}_0|},\] \[\mathop{\mathrm{\mathbb{E}}}_{\mathcal{X}^i \sim \mathcal{D}_{m}^i} \max_{\boldsymbol{z} \in \mathcal{X}^i} \lVert \breve{\boldsymbol{z}} \rVert^2_{(\boldsymbol{H}_m^i)^{-1}} \leq \frac{8 d^2}{|\mathcal{T}_m|}.\] Using these bounds as well as the trivial bound of \(\sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} \leq \sqrt{L_\mu}\), we upper bound the first term as follows: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{t,m} \sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} \left( \sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}} \right) &\leq \mathop{\mathrm{\mathbb{E}}}_{t,m} \sqrt{L_\mu \cdot N^2 \left( \sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert^2_{(\boldsymbol{H}^i_{m-1})^{-1}} \right) \left( \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert^2_{(\boldsymbol{V}_0^i)^ {-1}} \right)} \\ &\leq \sqrt{L_\mu \cdot N^2 \sum_{i=1}^N \mathop{\mathrm{\mathbb{E}}}_{\mathcal{X}^i_t \sim \mathcal{D}^i_m} \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert^2_{(\boldsymbol{H}^i_{m-1})^{-1}} \sum_{i=1}^N \mathop{\mathrm{\mathbb{E}}}_{\mathcal{X}^i_t \sim \mathcal{D}^i_m} \lVert \boldsymbol{b}^i_t \rVert^2_{(\boldsymbol{V}_0^i)^ {-1}} } \\ &\leq \sqrt{L_\mu \cdot N^2 \sum_{i=1}^N \mathop{\mathrm{\mathbb{E}}}_{\mathcal{X}^i_t \sim \mathcal{D}^i_{m-1}} \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert^2_{(\boldsymbol{H}^i_{m-1})^{-1}} \sum_{i=1}^N \mathop{\mathrm{\mathbb{E}}}_{\mathcal{X}^i_t \sim \mathcal{D}^i} \lVert \boldsymbol{b}^i_t \rVert^2_{(\boldsymbol{V}_0^i)^ {-1}} } \\ &\leq \sqrt{L_\mu \cdot N^2 \cdot \sum_{i=1}^N \frac{8 d^2}{ |\mathcal{T}_{m-1}|} \cdot \sum_{i=1}^N \frac{8 d^2}{ |\mathcal{T}_{0}|}} \\ &\leq \frac{8 N^2 d^2 \sqrt{L_\mu}}{\sqrt{|\mathcal{T}_{m-1}||\mathcal{T}_0|}}. \end{align}\] Here, the first inequality uses the Cauchy-Schwarz inequality, and the second inequality uses Jensen’s inequality. The third inequality is a consequence of Lemma 8 while the second-to-last inequality follows from the bounds we showed above.

Hence, summing over all \(t \in \mathcal{T}_m\), we get that: \[\sum_{t \in \mathcal{T}_m}\mathop{\mathrm{\mathbb{E}}}_{t,m} \sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} \left( \sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}} \right) \leq \frac{8 N^2 d^2 \sqrt{L_\mu} |\mathcal{T}_m|}{\sqrt{|\mathcal{T}_{m-1}||\mathcal{T}_0|}}.\]

We now upper bound the second term using the Cauchy-Schwarz inequality as: \[\begin{align} &\sum_{t \in \mathcal{T}_m}\mathop{\mathrm{\mathbb{E}}}_{t , m} \sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} \sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \leq \sum_{t \in \mathcal{T}_m}\sqrt{\left(\mathop{\mathrm{\mathbb{E}}}_{t , m} \dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) \right) \mathop{\mathrm{\mathbb{E}}}_{t , m} \left(\sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \right)^2 } \end{align}\] Now, since the optimal slate never gets eliminated (Lemma 7), we can write \[\sqrt{\mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i_t \sim \mathcal{D}^i_m\}_{i=1}^N} \dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} = \sqrt{\mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i_t \sim \mathcal{D}^i\}_{i=1}^N} \dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} = \sqrt{\mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N} \dot{\mu}(\boldsymbol{x}_{\star}^\top \boldsymbol{\theta}^\star)}\] where \(\boldsymbol{x}_\star = \mathop{\mathrm{arg\,max}}_{\boldsymbol{x} \in \mathcal{X}} \boldsymbol{x}^\top \boldsymbol{\theta}^\star\). Hence, this quantity is independent of \(t\). We thus get \[\begin{align} &\sum_{t \in \mathcal{T}_m}\mathop{\mathrm{\mathbb{E}}}_{t , m} \sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} \sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \leq \sqrt{\mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N} \dot{\mu}(\boldsymbol{x}_{\star}^\top \boldsymbol{\theta}^\star)} \underbrace{\sum_{t \in \mathcal{T}_m} \sqrt{\mathop{\mathrm{\mathbb{E}}}_{t , m} \left(\sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \right)^2 }}_{\text{Term A}}. \end{align}\] Expanding the square in Term A gives us \[\text{Term A} \leq \sum_{t \in \mathcal{T}_m} \sqrt{ \underbrace{\sum_{i=1}^N \mathop{\mathrm{\mathbb{E}}}_{\mathcal{X}^i_t \sim \mathcal{D}^i_m} \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert^2_{(\boldsymbol{H}^i_{m-1})^{-1}}}_{\text{Term A1}} + \underbrace{2 \mathop{\mathrm{\mathbb{E}}}_{t,m} \sum_{i=1}^N \sum_{\substack{j =1 \\ j \neq i}}^N \max_{\substack{\boldsymbol{z} \in \mathcal{X}^i_t \\ \boldsymbol{u} \in \mathcal{X}^j_t}}\lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \lVert \breve{\boldsymbol{u}} \rVert_{(\boldsymbol{H}^j_{m-1})^{-1}}}_{\text{Term A2}} }.\]

Upper-bounding Term A1, we get \[\begin{align} \text{Term A1} = \sum_{i=1}^N \mathop{\mathrm{\mathbb{E}}}_{\mathcal{X}^i_t \sim \mathcal{D}^i_m} \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert^2_{(\boldsymbol{H}^i_{m-1})^{-1}} &\leq \sum_{i=1}^N \mathop{\mathrm{\mathbb{E}}}_{\mathcal{X}^i_t \sim \mathcal{D}^i_{m-1}} \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert^2_{(\boldsymbol{H}^i_{m-1})^{-1}} \\ &\leq \frac{8 d^2 N}{|\mathcal{T}_{m-1}|} \end{align}\] where the first inequality follows from Lemma 8, while the second inequality follows from using Lemma 11 and Lemma 12 in tandem as shown above.

We now upper bound Term A2 as follows: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{t,m} \sum_{i=1}^N \sum_{\substack{j =1 \\ j \neq i}}^N \max_{\substack{\boldsymbol{z} \in \mathcal{X}^i_t \\ \boldsymbol{u} \in \mathcal{X}^j_t}} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \lVert \breve{\boldsymbol{u}} \rVert_{(\boldsymbol{H}^j_{m-1})^{-1}} &\leq 2 \mathop{\mathrm{\mathbb{E}}}_{t,m} \sum_{i=1}^N \sum_{\substack{j =1 \\ j \neq i}}^N \max_{\substack{\boldsymbol{z} \in \mathcal{X}^i_t \\ \boldsymbol{u} \in \mathcal{X}^j_t}} \frac{\lVert \breve{\boldsymbol{z}} \rVert \lVert \breve{\boldsymbol{u}} \rVert}{\sqrt{\lambda_{\min} (\boldsymbol{H}^i_{m-1}) \lambda_{\min} (\boldsymbol{H}^j_{m-1})}} \\ &\leq 2 \mathop{\mathrm{\mathbb{E}}}_{t,m} \sum_{i=1}^N \sum_{\substack{j =1 \\ j \neq i}}^N \frac{L_\mu}{N(\lambda + 0.5 \rho |\mathcal{T}_m|)} \end{align}\] where the first inequality follows from Rayleigh’s quotient, while the second inequality follows from the fact that \(\lVert \breve{\boldsymbol{z}} \rVert \leq \sqrt{L_\mu N^{-1}}\). The second inequality also uses the linear growth of eigenvalues of the slot-level matrices, shown in Lemma 13. Further simplification gives us a bound on Term A2 as \[\text{Term A2} = 2 \mathop{\mathrm{\mathbb{E}}}_{t,m} \sum_{i=1}^N \sum_{\substack{j =1 \\ j \neq i}}^N \max_{\substack{\boldsymbol{z} \in \mathcal{X}^i_t \\ \boldsymbol{u} \in \mathcal{X}^j_t}} \lVert \breve{\boldsymbol{z}} \rVert^2_{(\boldsymbol{H}^i_{m-1})^{-1}} \lVert \breve{\boldsymbol{u}} \rVert^2_{(\boldsymbol{H}^j_{m-1})^{-1}} \leq \frac{4 L_\mu N}{\rho |\mathcal{T}_m|}.\] Putting these bounds together, we get a bound on TermA as \[\sum_{t \in \mathcal{T}_m}\sqrt{\mathop{\mathrm{\mathbb{E}}}_{t , m} \left(\sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \right)^2 } \leq \sqrt{\frac{8d^2 N |\mathcal{T}_m|^2}{|\mathcal{T}_{m-1}|} + \frac{4 L_\mu N |\mathcal{T}_m|}{\rho}}.\] Using Lemma 9 and assembling all the bounds, we get that \[\begin{align} \sum_{t \in \mathcal{T}_m} &\mathop{\mathrm{\mathbb{E}}}_{t,m} \left\lvert \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) \right\rvert \\ &\leq \frac{320 e^{3S} \gamma^2 N^2 d^2 \sqrt{\kappa L_\mu} }{S} \frac{|\mathcal{T}_m|}{\sqrt{|\mathcal{T}_{m-1}||\mathcal{T}_0|}} + 8 \gamma \sqrt{\mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N} \dot{\mu}(\boldsymbol{x}_{\star}^\top \boldsymbol{\theta}^\star)} \sqrt{\frac{8d^2 N |\mathcal{T}_m|^2}{|\mathcal{T}_{m-1}|} + \frac{4 L_\mu N |\mathcal{T}_m|}{\rho}}. \end{align}\] ◻

Proof. Define \(\overline{\boldsymbol{x}}_t := \sqrt{\dot{\mu}(\boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0)\beta_t^{-1}} \boldsymbol{x}_t\) and \(\overline{\boldsymbol{x}}^i_t := \sqrt{\dot{\mu}(\boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0)\beta_t^{-1}} \boldsymbol{x}^i_t\). Then, note that \(\lVert \overline{\boldsymbol{x}}^i_t \rVert \leq \sqrt{L_\mu N^{-1}}\). Also, we can write \[\boldsymbol{H}_m = \lambda \boldsymbol{I}_{Nd} + \sum_{t \in \mathcal{T}_m} \overline{\boldsymbol{x}}_t \overline{\boldsymbol{x}}_t^\top \quad \text{and} \quad \boldsymbol{H}^i_m = \lambda \boldsymbol{I} + \sum_{t \in \mathcal{T}_m} \overline{\boldsymbol{x}}^i_t {\overline{\boldsymbol{x}}^i_t}^\top.\]

Also, for the sake of the proof, define \(\boldsymbol{U}_m := \textrm{diag}(\boldsymbol{H}^1_m , \ldots , \boldsymbol{H}^N_m)\). Then, using Lemma B.1 from [6], we have that \[\boldsymbol{U}_m^{-1/2}\boldsymbol{H}_m \boldsymbol{U}_m^{-1/2}= \boldsymbol{I}_{Nd} + \boldsymbol{G}_m.\] where \((\boldsymbol{G}_m)_{ij} = \mathbb{1}\{i \neq j\} (\boldsymbol{H}^i_m)^{-1/2} \boldsymbol{H}_m^{(i,j)} (\boldsymbol{H}^j_m)^{-1/2}\) and \(\boldsymbol{H}^{(i,j)}_m = \sum_{t \in \mathcal{T}_m} \overline{\boldsymbol{x}}^i_t {\overline{\boldsymbol{x}}^j_t}^\top\). We now bound the norm of \(\boldsymbol{H}^{(i,j)}_m \;\forall i \in [N]\) and \(j \in [i+1,N]\). A straightforward application of Lemma D.2 from [6] shows that for fixed \(i \in [N]\) and \(j > i\) with the quantities \(m_1 = m_2 = \sqrt{L_\mu N^{-1}}\), \(d_1 = d_2 = d\) and \(\delta = \frac{2 \delta}{N(N-1)}\), \[\mathbb{P}\left\{\exists t \geq 1 : \left\lVert \sum_{s \in [t]} \overline{\boldsymbol{x}}^i_s {\overline{\boldsymbol{x}}_s^j}^\top \right\rVert \geq \sqrt{\frac{8 L_\mu^2}{N^2} t \log \left( \frac{d N(N-1)}{\delta} \right)}\right\} \leq \frac{2\delta}{N(N-1)}.\] Taking a union bound over all \(i \in [N]\) and \(j \in [i+1 , N]\) gives us the result for all pairs of \((i,j)\) where \(j > i\). In particular, setting \(t = |\mathcal{T}_m|\) gives us the result that for all pairs of \((i,j)\) where \(j > i\), with high probability \[\lVert \boldsymbol{H}^{(i,j)}_m \rVert \leq \sqrt{\frac{8 L_\mu^2}{N^2} |\mathcal{T}_m| \log \left( \frac{d N (N-1)}{\delta} \right)}.\]

Now, using the diversity conditions, we know that \[\mathop{\mathrm{\mathbb{E}}}[\boldsymbol{x}^i_t {\boldsymbol{x}^i_t}^\top \mid \mathcal{F}_{t-1}] \succeq \rho \boldsymbol{I}.\] Using the definition of \(\kappa\), we can say that \[\mathop{\mathrm{\mathbb{E}}}[\overline{\boldsymbol{x}}^i_t {\overline{\boldsymbol{x}}^i_t}^\top\mid \mathcal{F}_{t-1}] = \mathop{\mathrm{\mathbb{E}}}[\dot{\mu}(\boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0)\beta_t^{-1} \boldsymbol{x}^i_t {\boldsymbol{x}^i_t}^\top \mid \mathcal{F}_{t-1}] \succeq \rho \kappa^{-1} \beta_t^{-1} \boldsymbol{I} .\] Applying Lemma 30 using the quantities \(\alpha = \kappa^{-1} \beta_t^{-1} (\leq 1)\), \(m = \sqrt{L_\mu N^{-1}}\), \(\gamma = \lambda\), \(\delta = \frac{\delta}{N}\), and \(c = 0.5\), for some fixed \(i \in [N]\), with probability \(1 - \frac{\delta}{N}\), \[\lambda_{\min} \left(\lambda \boldsymbol{I} + \sum_{s \in [t]} \overline{\boldsymbol{x}}^i_s {\overline{\boldsymbol{x}}_s^i}^\top \right) \geq \lambda + \frac{\rho t}{2} \; \forall t \geq \frac{48 L_\mu^2 + 8 L_\mu N \rho}{3\rho^2 N^2} \log \left(\frac{2dN T}{\delta} \right).\] Using the fact that \((N-1)^2 \geq N^{-2}\), we also have that, with probability \(1 - \frac{\delta}{N}\), \[\lambda_{\min} \left(\lambda \boldsymbol{I} + \sum_{s \in [t]} \overline{\boldsymbol{x}}^i_s {\overline{\boldsymbol{x}}_s^i}^\top \right) \geq \lambda + \frac{\rho t}{2} \; \forall t \geq T(\boldsymbol{H}) := \frac{48 L_\mu^2 + 8 L_\mu N \rho}{3\rho^2}(N-1)^2 \log \left(\frac{2dN T}{\delta} \right).\] A union bound over all slots gives us this result for all \(i \in [N]\). In particular, let \(|\mathcal{T}_m| \geq T(\boldsymbol{H})\). Then, setting \(t = |\mathcal{T}_m|\) gives us the result that for all \(i \in [N]\), with high probability, \[\lambda_{\min} \left(\boldsymbol{H}^i_m \right) \geq \lambda + \frac{\rho |\mathcal{T}_m|}{2}.\] Now, for \(i \in [N-1]\), define \(\boldsymbol{Z}_m^i \in \mathbb{R}^{d \times id}\) as the following matrix: for \(j \in [i]\), the \(j^{th}\) \(d \times d\) block of \(\boldsymbol{Z}_m^i\) is given by \((\boldsymbol{H}^{N-i}_m)^{-1/2} \boldsymbol{H}^{(N-i,N-i+j)}_m (\boldsymbol{H}^{N-i+j}_m)^{-1/2}\).

Then, using Lemma B.7 from [6], we have that, \[\begin{align} \lVert \boldsymbol{Z}_m^i \rVert &\leq \sum_{j \in [i]} \frac{\lVert \boldsymbol{H}_m^{N-i,N-i+j} \rVert}{\sqrt{\lambda_{\min}(\boldsymbol{H}^{N-i}_m) \lambda_{\min} (\boldsymbol{H}_m^{N-i +j})}} \\ &\leq \sum_{j \in [i]} \frac{\sqrt{\frac{8 L_\mu^2}{N^2} |\mathcal{T}_m| \log \left( \frac{d N(N-1)}{\delta} \right)}}{\lambda + 0.5 \rho |\mathcal{T}_m|} \\ &\leq \sum_{j \in [i]} \sqrt{\frac{32 L_\mu^2 \log \left( \frac{d N(N-1)}{\delta} \right)}{N^2 \rho^2 |\mathcal{T}_m|}}. \end{align}\]

Using the fact that \(|\mathcal{T}_m| \geq T(\boldsymbol{H})\), we get that \[\lVert \boldsymbol{Z}_m^i \rVert \leq \sum_{j \in [i]} \sqrt{\frac{96 L_\mu^2 \log \left( \frac{d N(N-1)}{\delta} \right)}{N^2 (48 L_\mu^2 + 8 L_\mu N \rho) (N-1)^2 \log \left(\frac{2dN T}{\delta} \right) } } \leq \frac{3i}{2 N(N-1)}\] where the last inequality follows from the fact that \(\sqrt{2} \leq \frac{3}{2}\).

Finally, recall the definition of the matrix \(\boldsymbol{G}_m\): \[(\boldsymbol{G}_m)_{ij} = \mathbb{1}\{i \neq j\} (\boldsymbol{H}^i_m)^{-1/2} \boldsymbol{H}_m^{i,j} (\boldsymbol{H}^j_m)^{-1/2}.\] It is easy to see that we can write \(\boldsymbol{G}_m\) as the following matrix recurrence relation: for \(i \in [1,N-1]\), define \[\boldsymbol{G}_m^1 = \begin{bmatrix} \boldsymbol{0} & \boldsymbol{Z}^1_m \\ (\boldsymbol{Z}^1_m)^\top & \boldsymbol{0} \end{bmatrix} , \quad \boldsymbol{G}_m^i = \begin{bmatrix} \boldsymbol{0} & \boldsymbol{Z}^i_m \\ (\boldsymbol{Z}^i_m)^\top & \boldsymbol{G}_m^{i-1}. \end{bmatrix}\] Then, \(\boldsymbol{G}_m = \boldsymbol{G}_m^{N-1}\). Using Lemma B.2 from [6] gives us: \[\lambda_{\max}(\boldsymbol{G}_m) \leq \sum_{i \in [N-1]} \lVert \boldsymbol{Z}^i_m \rVert = \frac{3}{2} \sum_{i \in [N-1]} \frac{i}{N(N-1)} = \frac{3}{4},\] \[\lambda_{\min}(\boldsymbol{G}_m) \geq -\sum_{i \in [N-1]} \lVert \boldsymbol{Z}^i_m \rVert = -\frac{3}{2} \sum_{i \in [N-1]} \frac{i}{N(N-1)} = -\frac{3}{4}.\] Substituting \(\boldsymbol{G}_m = \boldsymbol{U}_m^{-1/2}\boldsymbol{H}_m \boldsymbol{U}_m^{-1/2} - \boldsymbol{I}_{Nd}\), we get that \[\frac{1}{4} \boldsymbol{U}_m \preceq \boldsymbol{H}_m \preceq \frac{7}{4} \boldsymbol{U}_m.\] This finishes the first part of the proof. For the second part, notice that, \[\boldsymbol{H}_m^{-1} \preceq 4 \; \textrm{diag} ((\boldsymbol{H}^1_m)^{-1} , \ldots , (\boldsymbol{H}^N_m)^{-1}).\] Also, note that \(\boldsymbol{x} = \sum_{i=1}^N (\boldsymbol{x}^i \otimes \boldsymbol{e}_i)\) (Section 7.1) and hence, an application of the triangle inequality gives us: \[\lVert \boldsymbol{x} \rVert_{\boldsymbol{H}_m^{-1}} \leq 2 \sum_{i\in [N]} \lVert \boldsymbol{x}^i \otimes \boldsymbol{e}_i \rVert_{\textrm{diag} \left((\boldsymbol{H}^1_m)^{-1} , \ldots , (\boldsymbol{H}^N_m)^{-1} \right)} \leq 2 \sum_{i=1}^N \lVert \boldsymbol{x}^i \rVert_{(\boldsymbol{H}^i_m)^{-1}}.\] which finishes the proof for the second part. ◻

Proof. The proof follows on the same lines as that of Lemma 13. First, we have that \(\lVert \boldsymbol{x}^i_t \rVert \leq N^{-1/2}\). Also, for the sake of the proof, define \(\boldsymbol{W}_0 := \textrm{diag}(\boldsymbol{V}^1_0 , \ldots , \boldsymbol{V}^N_0)\). Then, using Lemma B.1 from [6], we have that \[\boldsymbol{W}_0^{-1/2}\boldsymbol{V}_0 \boldsymbol{W}_0^{-1/2}= \boldsymbol{I}_{Nd} + \boldsymbol{G}_0.\] where \((\boldsymbol{G}_0)_{ij} = \mathbb{1}\{i \neq j\} (\boldsymbol{V}^i_0)^{-1/2} \boldsymbol{V}_0^{(i,j)} (\boldsymbol{V}^j_0)^{-1/2}\) and \(\boldsymbol{V}^{(i,j)}_0 = \sum_{t \in \mathcal{T}_0} \boldsymbol{x}^i_t {\boldsymbol{x}^j_t}^\top\). A straightforward application of Lemma D.2 from [6] shows that for fixed \(i \in [N]\) and \(j > i\) with the quantities \(m_1 = m_2 = N^{-1/2}\), \(d_1 = d_2 = d\) and \(\delta = \frac{2 \delta}{N(N-1)}\), \[\mathbb{P}\left\{\exists t \geq 1 : \left\lVert \sum_{s \in [t]} \boldsymbol{x}^i_s {\boldsymbol{x}_s^j}^\top \right\rVert \geq \sqrt{\frac{8t}{N^2} \log \left( \frac{d N(N-1)}{\delta} \right)}\right\} \leq \frac{2\delta}{N(N-1)}.\] Taking a union bound over all \(i \in [N]\) and \(j \in [i+1 , N]\) gives us the result for all pairs of \((i,j)\) where \(j > i\). In particular, setting \(T = |\mathcal{T}_0|\) gives us the result that for all pairs of \((i,j)\) where \(j > i\), with high probability \[\lVert \boldsymbol{V}^{(i,j)}_0 \rVert \leq \sqrt{\frac{8 |\mathcal{T}_0|}{N^2} \log \left( \frac{d N (N-1)}{\delta} \right)}.\]

Now, using the diversity conditions, we know that \[\mathop{\mathrm{\mathbb{E}}}[\boldsymbol{x}^i_t {\boldsymbol{x}^i_t}^\top \mid \mathcal{F}_{t-1}] \succeq \rho \boldsymbol{I}.\] Similar to Lemma 13, an application of Lemma 30 for a fixed \(i \in [N]\) using the quantities \(\alpha = 1\), \(m = N^{-1/2}\), \(\gamma = \lambda\), \(\delta = \frac{\delta}{N}\) and \(c = 0.5\) , followed by the utilization of the fact that \((N-1)^2 \geq N^{-2}\), and finishing with a union bound over all \(i \in [N]\) gives us that for all \(i \in [N]\), with high probability, \[\lambda_{\min} \left(\lambda \boldsymbol{I} + \sum_{s \in [t]} \boldsymbol{x}^i_s {\boldsymbol{x}_s^i}^\top \right) \geq \lambda + \frac{\rho t}{2} \; \forall t \geq T(\boldsymbol{V}) := \frac{48 + 8 N \rho}{3\rho^2} (N-1)^2 \log \left(\frac{2dN T}{\delta} \right).\] In particular, let \(|\mathcal{T}_0| \geq T(\boldsymbol{V})\). Then, setting \(t = |\mathcal{T}_0|\) gives us the result that for all \(i \in [N]\), with high probability, \[\lambda_{\min} \left(\boldsymbol{V}^i_0 \right) \geq \lambda + \frac{\rho |\mathcal{T}_0|}{2}.\] Now, for \(i \in [N-1]\), define \(\boldsymbol{Z}_0^i \in \mathbb{R}^{d \times id}\) as the following matrix: for \(j \in [i]\), the \(j^{th}\) \(d \times d\) block of \(\boldsymbol{Z}_0^i\) is given by \((\boldsymbol{V}^{N-i}_0)^{-1/2} \boldsymbol{V}^{(N-i,N-i+j)}_0 (\boldsymbol{V}^{N-i+j}_0)^{-1/2}\).

Then, using Lemma B.7 from [6] and following a similar approach to that shown in Lemma 13, we have that,

\[\lVert \boldsymbol{Z}_0^i \rVert \leq \sum_{j \in [i]} \sqrt{\frac{96 \log \left( \frac{d N(N-1)}{\delta} \right)}{N^2 (48 + 8 N \rho) (N-1)^2 \log \left(\frac{2dN T}{\delta} \right) } } \leq \frac{3i}{2 N(N-1)}.\]

Writing \(\boldsymbol{G}_0\) as a matrix recurrence relation as in Lemma 13 and using Lemma B.2 from [6] gives: \[\lambda_{\max}(\boldsymbol{G}_0) \leq \frac{3}{4} \quad \text{ and } \quad \lambda_{\min}(\boldsymbol{G}_0) \geq -\frac{3}{4}.\] Substituting \(\boldsymbol{G}_0 = \boldsymbol{W}_0^{-1/2}\boldsymbol{V}_0 \boldsymbol{W}_0^{-1/2} - \boldsymbol{I}_{Nd}\), we get that \[\frac{1}{4} \boldsymbol{W}_0 \preceq \boldsymbol{V}_0 \preceq \frac{7}{4} \boldsymbol{W}_0.\] This finishes the proof for the first part. The second part of the proof is exactly the same as in Lemma 13. ◻

Proof. Define the function \(f(x) = xe^x\). Note that \(f^\prime(x) = e^x(x+1)\), and hence, \(f^\prime\) is non-negative for \(x \geq -1\). In other words, \(f\) is increasing in the domain \([-1,\infty)\) and decreasing in the domain \((-\infty , -1]\).

Now, let us consider the function \(f^{-1}(x)\). \(f^{-1}\) is increasing in the domain \([f(-1) , \lim_{x \rightarrow \infty} f(x)) = [-e^{-1} , \infty)\); we denote this branch of \(f^{-1}\) as \(W_0\). The other branch \(W_{-1}\) is decreasing in the domain \([-e^{-1}, \lim_{x \rightarrow -\infty} f(x)) = (-e^{-1}, 0)\).

Now, rearranging the terms of \(X^\alpha \geq k^\prime \log (kX)\) and dividing both sides by \(k^\alpha\) gives us, \[\frac{1}{k^\alpha k^\prime} \geq \exp(- \alpha \log (k X)) \log (k X).\] Setting \(Y = -\alpha \log(k X)\), we get \[-\frac{\alpha}{k^\alpha k^\prime} \leq Y \cdot \exp(Y).\] Now, to apply the function \(W_{-1}\) to both sides of the inequality, we require \(-\alpha (k^\alpha k^\prime)^{-1} \in [-e^{-1},0)\) and \(Y \exp(Y) \in [-e^{-1} , 0)\), and more particularly, \(Y \leq -1\).

First, since \(k,k^\prime > 0\), we have that \(-\alpha (k^\alpha k^\prime)^{-1} < 0\). Also, since \(k^\alpha k^\prime \geq \alpha e\), we have that \(-\alpha (k^\alpha k^\prime)^{-1} \geq -e^{-1}\). Thus, we have that \(-\alpha (k^\alpha k^\prime)^{-1} \in [-e^{-1},0)\).

For the second requirement, note that \(Y \exp(Y) \in [-e^{-1},0)\) is satisfied for all \(Y < 0\). However, since the range of \(W_{-1}\) is \((-\infty , -1]\), we have that \(W_{-1}(Y \exp(Y)) = Y\) if and only if \(Y \leq -1\). The condition \(X \geq k^{-1}\exp(\alpha^{-1})\) ensures \(Y \leq -1\), thus, satisfying the second requirement.

Thus, applying \(W_{-1}\) to both sides of the inequality, and using the fact that \(W_{-1}\) is decreasing gives us: \[W_{-1} \left( -\frac{\alpha}{k^\alpha k^\prime} \right) \geq Y = - \alpha \log(k X).\] Rearranging once again results in \[X \geq \frac{1}{k} \exp \left(- \frac{1}{\alpha} W_{-1} \left( -\frac{\alpha}{k^\alpha k^\prime}\right) \right).\] ◻

Proof. The proof follows on the same lines as the proof for Theorem 3. However, the use of distributional optimal designs prompts a change in the way we bound the regret for batches \(m \geq 2\) (Lemma 16). Define the optimal slate \(\boldsymbol{x}_{t,\star}\) as \[\boldsymbol{x}_{t,\star} = \mathop{\mathrm{arg\,max}}_{\boldsymbol{x} \in \mathcal{X}_t} \boldsymbol{x}^\top \boldsymbol{\theta}^\star.\] The regret for Algorithm 5 can be written as: \[R(T) \leq \mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i_t \sim \mathcal{D}^i\}_{i=1}^N} \left[\sum_{m \in [M]} \sum_{t \in \mathcal{T}_m} \left\lvert \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top\boldsymbol{\theta}^\star) \right\rvert \right].\] Similar to the proof in Theorem 3, we choose the batch lengths as \[|\mathcal{T}_0| = \lfloor \sqrt{T} \rfloor \quad \text{ and } \quad |\mathcal{T}_m| = \lfloor T^{1-2^{-m}} \rfloor, m\geq 1.\] Also, for \(T \geq T_0\), the conditions of Lemma 16 are satisfied. Thus, using Lemma 16 for batches \(m \geq 2\) as well as a trivial regret bound of R for each round \(t \in \{\mathcal{T}_0 , \mathcal{T}_1\}\) to obtain \[\begin{align} &R(T) \leq R(|\mathcal{T}_0| + |\mathcal{T}_1) + \sum_{m \in [2,M]} \frac{320 e^{3S} \gamma^2 N^2 d^2 \sqrt{\kappa L_\mu} }{S} \frac{|\mathcal{T}_m|}{\sqrt{|\mathcal{T}_{m-1}||\mathcal{T}_0|}} + \\ & \sum_{m \in [2,M]} 8\gamma \min\left\{ \sqrt{\mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N} \dot{\mu}(\boldsymbol{x}_{\star}^\top \boldsymbol{\theta}^\star)} \sqrt{\frac{16d^2 N |\mathcal{T}_m|^2}{|\mathcal{T}_{m-1}|} + \frac{4 L_\mu N |\mathcal{T}_m|}{\rho}} , 4N \sqrt{\max_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N }\dot{\mu}(\boldsymbol{x}_\star^\top \boldsymbol{\theta}^\star) \cdot d \log d} \frac{|\mathcal{T}_m|}{\sqrt{|\mathcal{T}_{m-1}|}}\right\} . \end{align}\]

Substituting the values of \(|\mathcal{T}_m|\), \(\frac{|\mathcal{T}_m|}{\sqrt{|\mathcal{T}_{m-1}|}}\), \(\frac{|\mathcal{T}_m|^2}{|\mathcal{T}_{m-1}|}\) from Theorem 3, and using \(|\mathcal{T}_m| \leq T\) and \(|\mathcal{T}_0| = \lfloor \sqrt{T} \rfloor \geq \sqrt{T}/2\), we get \[\begin{align} R(T) &\leq 320 \sqrt{2} e^{3S} S^{-1} \gamma^2 N^2 d^2 \sqrt{\kappa L_\mu} T^{1/4} \log \log T + 2R \sqrt{T} + \\ &8\gamma \min\left\{ \sqrt{\mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N} \dot{\mu}(\boldsymbol{x}_{\star}^\top \boldsymbol{\theta}^\star)} \sqrt{16d^2 N + 4 L_\mu N \rho^{-1}} , 4N \sqrt{\max_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N }\dot{\mu}(\boldsymbol{x}_\star^\top \boldsymbol{\theta}^\star) \cdot d \log d}\right\} \sqrt{T} \log \log T. \end{align}\] Substituting the value of \(\gamma = \mathcal{O}\left( S R \sqrt{Nd \log (T\delta^{-1})} \right)\) from Lemma 2 gives us \[R(T) = \tilde{O} \left( RSNd\sqrt{T} \cdot \min\left\{\sqrt{d \cdot \mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N} \dot{\mu}(\boldsymbol{x}_{\star}^\top \boldsymbol{\theta}^\star)} , \sqrt{N \cdot \max_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N }\dot{\mu}(\boldsymbol{x}_\star^\top \boldsymbol{\theta}^\star)} \right\} \right).\] ◻

Proof. The proof follows on the lines of Lemma 10. Define \(\breve{\boldsymbol{x}} := \sqrt{\dot{\mu}(\boldsymbol{b}_t^\top \widehat{\boldsymbol{\theta}}_0) \beta_t^{-1}} \boldsymbol{x}\) and \(\mathop{\mathrm{\mathbb{E}}}\limits_{\{\mathcal{X}^i_t \sim \mathcal{D}^i_m\}_{i=1}^N} \left[.\right]\) as \(\mathop{\mathrm{\mathbb{E}}}\limits_{t,m}[.]\). Then, using Lemma 9, we wish to bound the following two terms (excluding constants):

\[1. \mathop{\mathrm{\mathbb{E}}}_{t,m} \sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} \left( \sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \right) \left( \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}} \right)\] \[2. \mathop{\mathrm{\mathbb{E}}}_{t,m}\sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} \left( \sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \right) \phantom{\left( \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}} \right)}\]

Using Lemma 11 and Lemma 17 in tandem, we get \[\mathop{\mathrm{\mathbb{E}}}_{\mathcal{X}^i \sim \mathcal{D}^i} \max_{\boldsymbol{z} \in \mathcal{X}^i} \lVert \boldsymbol{z} \rVert^2_{(\boldsymbol{V}_0^i)^{-1}} \leq \frac{8 d^2}{|\mathcal{T}_0|},\] \[\mathop{\mathrm{\mathbb{E}}}_{\mathcal{X}^i \sim \mathcal{D}_{m}^i} \max_{\boldsymbol{z} \in \mathcal{X}^i} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}_m^i)^{-1}} \leq \sqrt{\frac{8 d \log d}{|\mathcal{T}_m|}}.\] Also, since the Distributional Optimal Design samples according to a G-Optimal Design with half probability (see Lemma A.14, [13]), we have \[\mathop{\mathrm{\mathbb{E}}}_{\mathcal{X}^i \sim \mathcal{D}_{m}^i} \max_{\boldsymbol{z} \in \mathcal{X}^i} \lVert \breve{\boldsymbol{z}} \rVert^2_{(\boldsymbol{H}_m^i)^{-1}} \leq \frac{16d^2}{|\mathcal{T}_m|}.\] Using the same steps as Lemma 10 to bound the first term, and substituting the optimal design bounds above results in: \[\sum_{t \in \mathcal{T}_m}\mathop{\mathrm{\mathbb{E}}}_{t,m} \sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} \left( \sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \sum_{i=1}^N\lVert \boldsymbol{b}^i_t \rVert_{(\boldsymbol{V}_0^i)^ {-1}} \right) \leq \frac{12 N^2 d^2 \sqrt{L_\mu} |\mathcal{T}_m|}{\sqrt{|\mathcal{T}_{m-1}||\mathcal{T}_0|}}.\]

The second term can be upper-bounded in two different ways. First, using the Cauchy-Schwarz inequality allows us to bound the second term with respect to the average reward sensitivity of the optimal slates, similar to Lemma 10, i.e, \[\begin{align} \sum_{t \in \mathcal{T}_m}\mathop{\mathrm{\mathbb{E}}}_{t , m} \sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} \sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} &\leq \sqrt{\mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N }\dot{\mu}(\boldsymbol{x}_\star^\top \boldsymbol{\theta}^\star)} \sum_{t \in \mathcal{T}_m} \sqrt{\mathop{\mathrm{\mathbb{E}}}_{t,m} \left(\sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}}\right)^2} \\ &\leq \sqrt{\mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N} \dot{\mu}(\boldsymbol{x}_{\star}^\top \boldsymbol{\theta}^\star)} \sqrt{\frac{16d^2 N |\mathcal{T}_m|^2}{|\mathcal{T}_{m-1}|} + \frac{4 L_\mu N |\mathcal{T}_m|}{\rho}}. \end{align}\] where \(\boldsymbol{x}_\star = \mathop{\mathrm{arg\,max}}_{\boldsymbol{x} \in \mathcal{X}} \boldsymbol{x}^\top \boldsymbol{\theta}^\star\) and \(\mathcal{X} = \mathcal{X}^1 \times \ldots \times \mathcal{X}^N\). Here, the second inequality follows from Lemma 10.

On the other hand, to leverage the advantage of Distributional Optimal design, we can avoid using the Cauchy-Schwartz inequality, resulting in \[\begin{align} \sum_{t \in \mathcal{T}_m}\mathop{\mathrm{\mathbb{E}}}_{t , m} \sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star)} \sum_{i=1}^N \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} &\leq \sqrt{\max_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N }\dot{\mu}(\boldsymbol{x}_\star^\top \boldsymbol{\theta}^\star)}\sum_{t \in \mathcal{T}_m} \sum_{i=1}^N \mathop{\mathrm{\mathbb{E}}}_{\mathcal{X}^i_t \sim \mathcal{D}^i_m}\max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \\ &\leq \sqrt{\max_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N }\dot{\mu}(\boldsymbol{x}_\star^\top \boldsymbol{\theta}^\star)} \sum_{t \in \mathcal{T}_m} \sum_{i=1}^N \mathop{\mathrm{\mathbb{E}}}_{\mathcal{X}^i_t \sim \mathcal{D}^i_{m-1}} \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \lVert \breve{\boldsymbol{z}} \rVert_{(\boldsymbol{H}^i_{m-1})^{-1}} \\ &\leq 4N \sqrt{\max_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N }\dot{\mu}(\boldsymbol{x}_\star^\top \boldsymbol{\theta}^\star) \cdot d \log d} \frac{|\mathcal{T}_m|}{\sqrt{|\mathcal{T}_{m-1}|}}. \end{align}\] where the second inequality follows from Lemma 8 and the final inequality follows from the optimal design bound given above.

Using Lemma 9 and assembling all the bounds, we get that \[\begin{align} &\sum_{t \in \mathcal{T}_m} \mathop{\mathrm{\mathbb{E}}}_{t,m} \left\lvert \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) \right\rvert \leq \frac{320 e^{3S} \gamma^2 N^2 d^2 \sqrt{\kappa L_\mu} }{S} \frac{|\mathcal{T}_m|}{\sqrt{|\mathcal{T}_{m-1}||\mathcal{T}_0|}} + \\ & 8\gamma \min\left\{ \sqrt{\mathop{\mathrm{\mathbb{E}}}_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N} \dot{\mu}(\boldsymbol{x}_{\star}^\top \boldsymbol{\theta}^\star)} \sqrt{\frac{16d^2 N |\mathcal{T}_m|^2}{|\mathcal{T}_{m-1}|} + \frac{4 L_\mu N |\mathcal{T}_m|}{\rho}} , 4N \sqrt{\max_{\{\mathcal{X}^i \sim \mathcal{D}^i\}_{i=1}^N }\dot{\mu}(\boldsymbol{x}_\star^\top \boldsymbol{\theta}^\star) \cdot d \log d} \frac{|\mathcal{T}_m|}{\sqrt{|\mathcal{T}_{m-1}|}}\right\} . \end{align}\] ◻

Proof. At round \(t \in [T]\), let \(\boldsymbol{x}_{t,\star}\) be the optimal slate, i.e, \[\boldsymbol{x}_{t,\star} = \mathop{\mathrm{arg\,max}}_{\boldsymbol{x} \in \mathcal{X}_t} \boldsymbol{x}^\top \boldsymbol{\theta}^\star.\] Then, the regret of Algorithm 2 can be written as \[R(T) = \sum_{t \in [T]} \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star).\] In Lemma 24, we bound this exact quantity. However, we require that \(|\mathcal{T}_0| \geq \max\{T(0) , 8\gamma^2 R^2 \rho^{-1} \kappa N\}\). We set \(|\mathcal{T}_0| = \lfloor \sqrt{T} \rfloor\) resulting in the inequality: \[\sqrt{T} \geq \max \left\{\frac{(48 + 8 N \rho)(N-1)^2}{3\rho^2} \log \left(\frac{2dN T}{\delta} \right) , 8\gamma^2 R^2 \rho^{-1} \kappa N \right\}.\] Since, \[\sqrt{\frac{2dN}{\delta}}\frac{(48 + 8 N \rho)(N-1)^2}{3\rho^2} \geq \frac{e}{2} \quad \text{ and } \quad \frac{16 R^ 6 S^{7/2} N^ 2 \kappa d}{\sqrt\delta \rho} \geq e,\] and also \[T \geq 2 \geq \frac{\delta}{S} \exp\left(\frac{1}{2} \right), \quad \text{ and }\quad T \geq 2 \geq \frac{\delta}{2dN} \exp\left(\frac{1}{2} \right),\] we can use Lemma 15 and the definition of \(\gamma\) (Section 9.1) to get \[T \geq \max \left\{ \frac{\delta}{2dN} \exp \left(-2W_{-1} \left( \frac{-3\rho^2 \sqrt\delta}{2\sqrt{2dN}(48 + 8N\rho)(N-1)^2} \right) \right) , \frac{\delta}{S} \exp\left(-2W_{-1}\left( \frac{-\sqrt\delta \rho}{32 R^ 6 S^{7/2} N^ 2\kappa d}\right)\right) \right\}.\] From Lemma 24, we also have \(|\mathcal{T}^{<t}_{\neg 0}| \geq T(\neg 0)\). Now, let \(t^\prime\) be such that \(|\mathcal{T}^{<t^\prime}_{\neg 0}| = \lfloor \sqrt{T} \rfloor\). Such a \(t^\prime\) exists because \(T \geq 2\) and hence, \(T \geq |\mathcal{T}_0| + |\mathcal{T}^{<t^\prime}_{\neg 0}| = 2 \lfloor \sqrt{T} \rfloor\). Let \(|\mathcal{T}^{<t^\prime}_{\neg 0}| \geq T(\neg 0)\), then, we have \[\sqrt{T} \geq \frac{(48 L_\mu^2 + 8 L_\mu N \rho)(N-1)^2}{3\rho^2} \log \left(\frac{2dN T}{\delta} \right)\] resulting in the bound (using Lemma 15) \[T \geq \frac{\delta}{2dN} \exp \left(-2W \left( \frac{-3\rho^2 \sqrt\delta}{2\sqrt{2dN}(48 L_\mu^2 + 8N L_\mu \rho)(N-1)^2} \right) \right).\] Using the fact that both \(\exp(-x)\) and \(W_{-1}(x)\) are decreasing (in the domain \((-e^{-1} , 0)\) Lemma 15) and \(L_\mu \geq 1\), we get the final bound on \(T\) as \[\begin{align} &T \geq \\ &T_0 := \max \left\{ \frac{\delta}{2dN} \exp \left(-2W_{-1} \left( \frac{-3\rho^2 \sqrt\delta}{2\sqrt{2dN}(48 L_\mu^2 + 8N L_\mu \rho)(N-1)^2} \right) \right) , \frac{\delta}{S} \exp\left(-2W_{-1}\left( \frac{-\sqrt\delta \rho}{32 R^ 6 S^{7/2} N^ 2\kappa d}\right) \right) \right\}. \end{align}\] Now, assuming \(T \geq T_0\), we can split \(R(T)\) as \[\begin{align} R(T) &= \sum_{t \in \mathcal{T}_0} \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) + \sum_{t \in \mathcal{T}^{<t^\prime}_{\neg 0}} \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) + \sum_{t = t^\prime}^T \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) \\ &\leq 2R\sqrt{T} + \sum_{t = t^\prime}^T \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) \end{align}\] where we use a trivial regret bound of \(R\) for \(t \in \mathcal{T}_0 \cup \mathcal{T}^{< t^\prime}_{\neg 0}\) alongside the fact that \(|\mathcal{T}_0| = |\mathcal{T}^{< t^\prime}_{\neg 0}| = \lfloor \sqrt{T} \rfloor\).

Now, using Lemma 24, we have \[\begin{align} &\sum_{t = t^\prime}^T \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) \leq 4 \sqrt{2} e^5 \beta \sum_{t = t^\prime}^T \sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \theta^\star)\cdot e^{-1} \dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)}\sum_{i=1}^N \lVert \boldsymbol{x}^i_t \rVert_{(\boldsymbol{H}^i_t)^{-1}} \\ & \phantom{ \sum_{t = t^\prime}^T \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star)} \leq 4 \sqrt{2} e^5 \beta \sqrt{\sum_{t = t^\prime}^T \dot{\mu}(\boldsymbol{x}_{t,\star}^\top \theta^\star) \cdot \sum_{t = t^\prime}^T \frac{\dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)}{e} \left( \sum_{i=1}^N \lVert \boldsymbol{x}^i_t \rVert_{(\boldsymbol{H}^i_t)^{-1}}\right)^2} \\ &\leq 4 \sqrt{2} e^5 \beta \sqrt{\sum_{t = t^\prime}^T \dot{\mu}(\boldsymbol{x}_{t,\star}^\top \theta^\star) \cdot \left( \underbrace{\sum_{i=1}^N \sum_{t = t^\prime}^T \left\lVert \sqrt{\frac{\dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)}{e} } \boldsymbol{x}^i_t \right\rVert^2_{(\boldsymbol{H}^i_t)^{-1}}}_{\text{Term A}} + \underbrace{\sum_{i=1}^N \sum_{\substack{j=1 \\ j \neq i}}^N \sum_{t = t^\prime}^T \frac{\dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)}{e} \lVert \boldsymbol{x}^i_t \rVert_{(\boldsymbol{H}^i_t)^{-1}} \lVert \boldsymbol{x}^j_t \rVert_{(\boldsymbol{H}^j_t)^{-1}}}_{\text{Term B}}\right)} \end{align}\]

Bounding Term A, we get \[\sum_{i=1}^N \sum_{t = t^\prime}^T \left\lVert \sqrt{\frac{\dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)}{e} } \boldsymbol{x}^i_t \right\rVert^2_{(\boldsymbol{H}^i_t)^{-1}} \leq 2Nd \log \left(1 + \frac{L_\mu \cdot t}{e \cdot N \lambda d} \right) \leq 2Nd \log T.\] Here, we use Lemma 28 with the vectors \(\breve{\boldsymbol{x}}^i_t := \sqrt{\frac{\dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)}{e} } \boldsymbol{x}^i_t\), resulting in \(\lVert \breve{\boldsymbol{x}}^i_t \rVert \leq \sqrt{L_\mu e^{-1} \cdot N^{-1}}\).

Bounding Term B, we get \[\sum_{i=1}^N \sum_{\substack{j=1 \\ j \neq i}}^N \sum_{t = t^\prime}^T \frac{\dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)}{e} \lVert \boldsymbol{x}^i_t \rVert_{(\boldsymbol{H}^i_t)^{-1}} \lVert \boldsymbol{x}^j_t \rVert_{(\boldsymbol{H}^j_t)^{-1}} \leq \sum_{i=1}^N \sum_{\substack{j=1 \\ j \neq i}}^N \sum_{t = t^\prime}^T L_\mu \frac{\lVert \boldsymbol{x}^i_t \rVert \lVert \boldsymbol{x}^j_t \rVert}{\sqrt{\lambda_{\min}(\boldsymbol{H}^i_t) \lambda_{\min}(\boldsymbol{H}^j_t)}},\] where the inequality uses Rayleigh’s quotient. Since, for all \(t \in [t^\prime , T]\), \(|\mathcal{T}^{<t}_{\neg 0}| \geq |\mathcal{T}^{<t^\prime}_{\neg 0}| \geq T(\neg 0)\), using Lemma 26, for all \(i \in [N]\) \[\lambda_{\min} (\boldsymbol{H}^i_t) \geq \lambda + \frac{\rho |\mathcal{T}^{<t}_{\neg 0}|}{2}.\] Substituting this back, we get

\[\begin{align} \sum_{i=1}^N \sum_{\substack{j=1 \\ j \neq i}}^N \sum_{t = t^\prime}^T \frac{\dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)}{e} \lVert \boldsymbol{x}^i_t \rVert_{(\boldsymbol{H}^i_t)^{-1}} \lVert \boldsymbol{x}^j_t \rVert_{(\boldsymbol{H}^j_t)^{-1}} &\leq \sum_{i=1}^N \sum_{\substack{j=1 \\ j \neq i}}^N \sum_{t = t^\prime}^T L_\mu \frac{\lVert \boldsymbol{x}^i_t \rVert \lVert \boldsymbol{x}^j_t \rVert}{\lambda + 0.5 \rho |\mathcal{T}^{<t}_{\neg 0}|} \\ &\leq \sum_{i=1}^N \sum_{\substack{j=1 \\ j \neq i}}^N \frac{2 L_\mu}{\rho} \lVert \boldsymbol{x}^i_t \rVert \lVert \boldsymbol{x}^j_t\rVert \left( \sum_{s \in [|\mathcal{T}_{\neg 0}|]} \frac{1}{s} \right). \end{align}\] Using the sum of the Harmonic series, alongside the fact that \(\forall i \in [N], \lVert \boldsymbol{x}^i \rVert \leq \sqrt{N^{-1}}\), we get a bound on Term B as \[\sum_{i=1}^N \sum_{\substack{j=1 \\ j \neq i}}^N \sum_{t = t^\prime}^T \frac{\dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)}{e} \lVert \boldsymbol{x}^i_t \rVert_{(\boldsymbol{H}^i_t)^{-1}} \lVert \boldsymbol{x}^j_t \rVert_{(\boldsymbol{H}^j_t)^{-1}} \leq 2 N L_\mu \rho^{-1} \log T.\] Combining all the bounds, we get \[R(T) \leq 2R \sqrt{T} + 4\sqrt{2}e^5 \beta \sqrt{\left(\sum_{t = t^\prime}^T \dot{\mu}(\boldsymbol{x}_{t,\star}^\top \theta^\star) \right) \cdot \left(2Nd + 2N l_\mu \rho^{-1} \right) \log T }.\] Substituting the value of \(\beta = \mathcal{O}\left(R \sqrt{Nd S \log (ST \delta^{-1})} \right)\) from Section 9.1, we get \[R(T) = \tilde{\mathcal{O}}\left( R\sqrt{T} + RS^{1/2}Nd \sqrt{\sum_{t \in T_{\neg 0}} \dot{\mu}(\boldsymbol{x}_{t,\star}^\top \theta^\star)} \right).\] ◻

Proof. For the sake of this proof, define \[\boldsymbol{H}_0^\star = \lambda \boldsymbol{I}_{Nd} + \sum_{t \in \mathcal{T}_0} \dot{\mu}(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) \boldsymbol{x}_t \boldsymbol{x}_t^\top.\] Then, we have \[\begin{align} \left \lvert \boldsymbol{x}^\top (\boldsymbol{\theta}^\star - \widehat{\boldsymbol{\theta}}_0) \right \rvert &\leq \lVert \boldsymbol{x} \rVert_{(\boldsymbol{H}_0^\star)^{-1}} \lVert \boldsymbol{\theta}^\star - \widehat{\boldsymbol{\theta}}_0 \rVert_{\boldsymbol{H}^\star_0} \\ &\leq \gamma \sqrt\kappa \lVert \boldsymbol{x} \rVert_{\boldsymbol{V}^{-1}} \\ &\leq 2\gamma \sqrt\kappa \sum_{i=1}^N \lVert \boldsymbol{x}^i \rVert_{(\boldsymbol{V}^i)^{-1}} \\ &\leq 2\gamma \sqrt\kappa \sum_{i=1}^N \frac{\lVert \boldsymbol{x}^i \rVert}{\sqrt{\lambda_{\min}(\boldsymbol{V}^i)}} \end{align}\] where the first inequality uses the Cauchy-Schwarz inequality, the second inequality follows from Lemma 18 and Lemma 3, the third inequality follows from Lemma 27, and the final inequality follows from Rayleigh’s quotient.

Now, from Lemma 27, we have that \[\lambda_{\min} (\boldsymbol{V}^i) \geq \lambda + \frac{\rho |\mathcal{T}_0|}{2}.\] Thus, using the fact that \(\lVert \boldsymbol{x}^i \rVert \leq \sqrt{N^{-1}}\), we have \[\left \lvert \boldsymbol{x}^\top (\boldsymbol{\theta}^\star - \widehat{\boldsymbol{\theta}}_0) \right \rvert \leq 2\gamma\sqrt{\frac{ \kappa N}{\lambda + 0.5 \rho |\mathcal{T}_0|}}.\] Finally, using the fact that \(|\mathcal{T}_0| \geq 8 \gamma^2 R^2 \rho^{-1} \kappa N\), we get that \[\left \lvert \boldsymbol{x}^\top (\boldsymbol{\theta}^\star - \widehat{\boldsymbol{\theta}}_0) \right \rvert \leq \frac{1}{R}.\] ◻

Proof. Using the self-concordance property of GLMs, we have that \[\exp \left(-R\left\lvert \boldsymbol{x}^\top (\boldsymbol{\theta}^\star - \widehat{\boldsymbol{\theta}}_0) \right\rvert \right) \cdot \dot{\mu}(\boldsymbol{x}^\top \widehat{\boldsymbol{\theta}}_0) \preceq \dot{\mu}(\boldsymbol{x}^\top \boldsymbol{\theta}^\star) \preceq \exp \left(R\left\lvert \boldsymbol{x}^\top (\boldsymbol{\theta}^\star - \widehat{\boldsymbol{\theta}}_0) \right\rvert \right) \cdot \dot{\mu}(\boldsymbol{x}^\top \widehat{\boldsymbol{\theta}}_0).\] From Lemma 19, we get \[e^{-1} \cdot \dot{\mu}(\boldsymbol{x}^\top \widehat{\boldsymbol{\theta}}_0) \preceq \dot{\mu}(\boldsymbol{x}^\top \boldsymbol{\theta}^\star) \preceq e \cdot \dot{\mu}(\boldsymbol{x}^\top \widehat{\boldsymbol{\theta}}_0).\] Hence, we can write, \[\boldsymbol{H}_t^\star = \lambda \boldsymbol{I}_{Nd} + \sum_{s \in \mathcal{T}^{<t}_{\neg 0}} \dot{\mu}(\boldsymbol{x}_s^\top \boldsymbol{\theta}^\star) \boldsymbol{x}_s \boldsymbol{x}_s^\top \succeq \lambda \boldsymbol{I}_{Nd} + \sum_{s \in \mathcal{T}^{<t}_{\neg 0}} \dot{\mu}(\boldsymbol{x}_s^\top \widehat{\boldsymbol{\theta}}_0) e^{-1}\boldsymbol{x}_s \boldsymbol{x}_s^\top = \boldsymbol{H}_t.\] ◻

Proof. First, from the definition of \(s(t)\), we have that \(s(t) \leq t\). Thus, we have that \[|\mathcal{T}^{<s(t)}_{\neg 0}| \leq |\mathcal{T}_{\neg 0}^{<t}| \implies \boldsymbol{H}_{s(t)} \preceq \boldsymbol{H}_t \implies \boldsymbol{H}_{s(t)}^{-1} \succeq \boldsymbol{H}_t^{-1}.\] Hence, applying Lemma 29 with \(\boldsymbol{A} = \boldsymbol{H}_{s(t)}^{-1}\) and \(\boldsymbol{B} = \boldsymbol{H}_{t}^{-1}\), we get that \[\lVert \boldsymbol{x} \rVert^2_{\boldsymbol{H}^{-1}_{s(t)}} \leq \lVert \boldsymbol{x} \rVert^2_{\boldsymbol{H}^{-1}_{t}} \cdot \frac{\det \boldsymbol{H}_{s(t)}^{-1}}{\det \boldsymbol{H}_{t}^{-1}}.\] Using the fact that \(\det \boldsymbol{H}_{t} \leq 2 \det \boldsymbol{H}_{s(t)}\) (Section 9.1), we get that \[\lVert \boldsymbol{x} \rVert^2_{\boldsymbol{H}^{-1}_{s(t)}} \leq \lVert \boldsymbol{x} \rVert^2_{\boldsymbol{H}^{-1}_{t}} \cdot \frac{\det \boldsymbol{H}_{t}}{\det \boldsymbol{H}_{s(t)}} \leq 2 \lVert \boldsymbol{x} \rVert^2_{\boldsymbol{H}^{-1}_{t}}.\] ◻

Proof. First, it is easy to see that all the components of the optimal slate, i.e, \(\boldsymbol{x}^i_{t,\star}\) are also optimal w.r.t \({\boldsymbol{\theta}^\star}^i\). In other words, for all \(i \in [N]\), we have \[\boldsymbol{x}_{t,\star}^i = \mathop{\mathrm{arg\,max}}_{\boldsymbol{z} \in \mathcal{X}^i_t} \tilde{\boldsymbol{z}}^ \top \boldsymbol{\theta}^\star.\]

Fix \(i \in [N]\). Then, for some arbitrary \(\boldsymbol{z} \in \mathcal{X}^i_t\), we have that \[\begin{align} 0 &\leq \left( \tilde{\boldsymbol{x}}^i_{t,\star} - \tilde{\boldsymbol{z}}\right)^\top \boldsymbol{\theta}^ \star \\ &= \left( \tilde{\boldsymbol{x}}^i_{t,\star} - \tilde{\boldsymbol{z}} \right)^\top \left( \boldsymbol{\theta}^ \star - \widehat{\boldsymbol{\theta}}_0 \right) + \left( \tilde{\boldsymbol{x}}^i_{t,\star} - \tilde{\boldsymbol{z}} \right)^\top \widehat{\boldsymbol{\theta}}_0 \\ &\leq 2 \sqrt\kappa \gamma \lVert {\boldsymbol{x}}^i_{t,\star} \rVert_{(\boldsymbol{V}^i)^ {-1}} + 2 \sqrt\kappa \gamma \lVert \boldsymbol{z} \rVert_{(\boldsymbol{V}^i)^{-1}} + \left( \tilde{\boldsymbol{x}}^i_{t,\star} - \tilde{\boldsymbol{z}} \right)^\top \widehat{\boldsymbol{\theta}}_0 \\ &= \textrm{UCB}^{i,0}(\boldsymbol{x}^i_{t,\star}) - \textrm{LCB}^{i,0}(\boldsymbol{z}) \end{align}\] where the second inequality follows from Lemma 3. Since this is true \(\forall \boldsymbol{z} \in \mathcal{X}^i_t\), we get \[\textrm{UCB}^{i,0}(\boldsymbol{x}^i_{t,\star}) \geq \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \textrm{LCB}^{i,0}(\boldsymbol{z})\] or in other words, \[\textrm{UCB}^{i,0}(\boldsymbol{x}^i_{t,\star}) - \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \textrm{LCB}^{i,0}(\boldsymbol{z}) \geq 0.\]

Since this holds for a fixed but arbitrary \(i \in [N]\), the above inequality holds for all \(i \in [N]\). Thus, the components of the optimal slate, and hence, the optimal slate never get eliminated. ◻

Proof. Using the triangle inequality, we can write \[\left\lvert (\boldsymbol{x} - \boldsymbol{y})^\top \widehat{\boldsymbol{\theta}}_0 \right\rvert \leq \sum_{i=1}^N \left\lvert (\boldsymbol{x}^i - \boldsymbol{y}^i)^\top \widehat{\boldsymbol{\theta}}^i_0 \right\rvert.\] Now, since both \(\boldsymbol{x}\) and \(\boldsymbol{y}\) survive the elimination, their respective components \(\boldsymbol{x}^i\) and \(\boldsymbol{y}^i\) for all \(i \in [N]\) also do not get eliminated. Thus, for a fixed \(i \in [N]\), we have \[\textrm{UCB}^{i,0}(\boldsymbol{x}^i) \geq \max_{\boldsymbol{z} \in \mathcal{X}^i_t} \textrm{LCB}^{i,0}(\boldsymbol{z}^i) \geq \textrm{LCB}^{i,0}(\boldsymbol{y}^i).\] Using the definitions of \(\textrm{UCB}^{i,0}(\boldsymbol{z})\) and \(\textrm{LCB}^{i,0}(\boldsymbol{z})\) (Section 9.1), we get \[(\boldsymbol{y}^i - \boldsymbol{x}^i)^\top \widehat{\boldsymbol{\theta}}^i_0 \leq 2 \sqrt\kappa\gamma \lVert \boldsymbol{x}^i \rVert_{(\boldsymbol{V}^i_0)^ {-1}} + 2 \sqrt\kappa\gamma \lVert \boldsymbol{y}^i \rVert_{(\boldsymbol{V}^i_0)^ {-1}}.\] A symmetric argument gives us \[(\boldsymbol{x}^i - \boldsymbol{y}^i)^\top \widehat{\boldsymbol{\theta}}^i_0 \leq 2\sqrt\kappa\gamma \lVert \boldsymbol{x}^i \rVert_{(\boldsymbol{V}^i_0)^ {-1}} + 2 \sqrt\kappa\gamma \lVert \boldsymbol{y}^i \rVert_{(\boldsymbol{V}^i_0)^ {-1}}.\] Thus, combining both the inequalities, we get \[\begin{align} \left\lvert (\boldsymbol{x}^i - \boldsymbol{y}^i)^\top \widehat{\boldsymbol{\theta}}^i_0 \right\rvert &\leq 4\sqrt\kappa \gamma \max_{z \in \mathcal{X}^i_t} \lVert \boldsymbol{z} \rVert_{(\boldsymbol{V}^i_0)^ {-1}} \\ &\leq 4\gamma \sqrt\kappa \sum_{i=1}^N \max_{z \in \mathcal{X}^i_t} \frac{\lVert \boldsymbol{z} \rVert}{\sqrt{\lambda_{\min}(\boldsymbol{V}^i)}} \end{align}\] where the final inequality follows from Rayleigh’s quotient. Now, from Lemma 27, we have that \[\lambda_{\min} (\boldsymbol{V}^i) \geq \lambda + \frac{\rho |\mathcal{T}_0|}{2}.\] Thus, using the fact that \(\lVert \boldsymbol{z} \rVert \leq \sqrt{N^{-1}}\), we have \[\left\lvert (\boldsymbol{x}^i - \boldsymbol{y}^i)^\top \widehat{\boldsymbol{\theta}}^i_0 \right\rvert \leq 4\gamma\sqrt{\frac{ \kappa N}{\lambda + 0.5 \rho |\mathcal{T}_0|}}.\] Finally, using the fact that \(|\mathcal{T}_0| \geq 8 \gamma^2 R^2 \rho^{-1} \kappa N\), we get that \[\left\lvert (\boldsymbol{x}^i - \boldsymbol{y}^i)^\top \widehat{\boldsymbol{\theta}}^i_0 \right\rvert \leq \frac{2}{R}.\] ◻

Proof. Using a first-order Taylor Series expansion, for some \(z_t \in [\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star , \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star]\), we get \[\begin{align} \mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) &\leq \dot{\mu}(z_t) \left( \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star \right) \\ &\leq \dot{\mu}(z_t) \left[ \left\lvert \boldsymbol{x}_{t,\star}^\top (\boldsymbol{\theta}^\star - \widehat{\boldsymbol{\theta}}_{s(t)}) \right\rvert + \left\lvert \boldsymbol{x}_{t}^\top (\boldsymbol{\theta}^\star - \widehat{\boldsymbol{\theta}}_{s(t)}) \right\rvert + (\boldsymbol{x}_{t,\star} - \boldsymbol{x}_t)^\top \widehat{\boldsymbol{\theta}}_{s(t)} \right] \\ &\leq \dot{\mu}(z_t) \left[ \beta \lVert \boldsymbol{x}_{t,\star} \rVert_{\boldsymbol{H}_{s(t)}^{-1}} + \beta \lVert \boldsymbol{x}_{t} \rVert_{\boldsymbol{H}_{s(t)}^{-1}} + (\boldsymbol{x}_{t,\star} - \boldsymbol{x}_t)^\top \widehat{\boldsymbol{\theta}}_{s(t)} \right] \\ &\leq \dot{\mu}(z_t) \left[ \sqrt{2} \beta \lVert \boldsymbol{x}_{t,\star} \rVert_{\boldsymbol{H}_{t}^{-1}} + \sqrt{2}\beta \lVert \boldsymbol{x}_{t} \rVert_{\boldsymbol{H}_{t}^{-1}} + (\boldsymbol{x}_{t,\star} - \boldsymbol{x}_t)^\top \widehat{\boldsymbol{\theta}}_{s(t)} \right] \\ &\leq \dot{\mu}(z_t) \sum_{i=1}^N \left[ 2\sqrt{2} \beta \lVert \boldsymbol{x}^i_{t,\star} \rVert_{(\boldsymbol{H}^i_{t})^{-1}} + 2\sqrt{2}\beta \lVert \boldsymbol{x}^i_{t} \rVert_{(\boldsymbol{H}_{t}^i)^{-1}} + (\boldsymbol{x}^i_{t,\star} - \boldsymbol{x}^i_t)^\top \widehat{\boldsymbol{\theta}}^i_{s(t)} \right] \end{align}\] where the third inequality follows by applying the Cauchy-Schwarz inequality and Lemma 18 in tandem, the second-to-last inequality follows from Lemma 21, and the final inequality follows from Lemma 26.

Now, since \(\boldsymbol{x}_t\) is chosen, for some fixed slot \(i \in [N]\), from Step 17 of Algorithm 2, we have \[(\boldsymbol{x}^i_{t})^\top \widehat{\boldsymbol{\theta}}^i_{s(t)} + 2 \sqrt{2}\beta \lVert \boldsymbol{x}^i_{t} \rVert_{(\boldsymbol{H}_{t}^i)^{-1}} \geq (\boldsymbol{x}^i_{t,\star})^\top \widehat{\boldsymbol{\theta}}^i_{s(t)} + 2 \sqrt{2}\beta \lVert \boldsymbol{x}^i_{t,\star} \rVert_{(\boldsymbol{H}_{t}^i)^{-1}}.\] Rearranging and summing over all \(i \in [N]\), we get \[\sum_{i=1}^N (\boldsymbol{x}^i_{t,\star} - \boldsymbol{x}^i_{t})^\top \widehat{\boldsymbol{\theta}}^i_{s(t)} \leq 2 \sqrt{2}\beta \sum_{i=1}^N \lVert \boldsymbol{x}^i_{t} \rVert_{(\boldsymbol{H}_{t}^i)^{-1}} - 2 \sqrt{2}\beta \sum_{i=1}^N \lVert \boldsymbol{x}^i_{t,\star} \rVert_{(\boldsymbol{H}_{t}^i)^{-1}}.\] Substituting this back, we get \[\mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) \leq 4 \sqrt{2} \beta \dot{\mu}(z_t) \sum_{i=1}^N \lVert \boldsymbol{x}^i_t \rVert_{(\boldsymbol{H}^i_t)^{-1}}.\] Now, using the self-concordance property of GLMs, we have that \[\dot{\mu}(z_t) \leq \dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0) \exp \left(R \left\lvert z_t - \boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0\right\rvert \right).\] We now bound \(\left\lvert z_t - \boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0\right\rvert\) as follows: \[\begin{align} \left\lvert z_t - \boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0\right\rvert &\leq \left\lvert \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0\right\rvert + \left\lvert \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star - z_t \right\rvert \\ &\leq \left\lvert \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0\right\rvert + \left\lvert \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star \right\rvert \\ &\leq \left\lvert \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0\right\rvert + \left\lvert \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0\right\rvert + \left\lvert \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_{t,\star}^\top \widehat{\boldsymbol{\theta}}_0\right\rvert + \left\lvert \boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0 - \boldsymbol{x}_{t,\star}^\top \widehat{\boldsymbol{\theta}}_0 \right\rvert \\ &\leq \frac{5}{R} \end{align}\] where the second inequality follows from the fact that \(z_t \in [\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star , \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star]\) and the final inequality follows from Lemma 19, Lemma 22, and Lemma 23.

Similarly, we have \[\begin{align} \left\lvert z_t - \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star\right\rvert &\leq \left\lvert \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star \right\rvert \\ &\leq \left\lvert \boldsymbol{x}_t^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0\right\rvert + \left\lvert \boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star - \boldsymbol{x}_{t,\star}^\top \widehat{\boldsymbol{\theta}}_0\right\rvert + \left\lvert \boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0 - \boldsymbol{x}_{t,\star}^\top \widehat{\boldsymbol{\theta}}_0 \right\rvert \\ &\leq \frac{4}{R}. \end{align}\]

Thus, we get \[\dot{\mu}(z_t) \leq \sqrt{e^5 \dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)}\sqrt{ e^4\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \theta^\star)} = \sqrt{e^9 \dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \theta^\star)}\] and hence, \[\mu(\boldsymbol{x}_{t,\star}^\top \boldsymbol{\theta}^\star) - \mu(\boldsymbol{x}_t^\top \boldsymbol{\theta}^\star) \leq 4 \sqrt{2} e^5 \beta \sqrt{\dot{\mu}(\boldsymbol{x}_{t,\star}^\top \theta^\star)\cdot e^{-1} \dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)}\sum_{i=1}^N \lVert \boldsymbol{x}^i_t \rVert_{(\boldsymbol{H}^i_t)^{-1}}.\] ◻

Proof. The proof follows on the same lines as Lemma B.17 from [13]. However, all the matrices \(\boldsymbol{H}\) are now \(Nd\)-dimensional, resulting in a dependence on \(N\). ◻

Proof. Define \(\overline{\boldsymbol{x}}_t := \sqrt{\dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)e^{-1}} \boldsymbol{x}_t\) and \(\overline{\boldsymbol{x}}^i_t := \sqrt{\dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)e^{-1}} \boldsymbol{x}^i_t\). Then, note that \(\lVert \overline{\boldsymbol{x}}^i_t \rVert \leq \sqrt{L_\mu N^{-1}}\).

Also, for the sake of the proof, define \(\boldsymbol{U}_t := \textrm{diag}(\boldsymbol{H}^1_t , \ldots , \boldsymbol{H}^N_t)\). Thus, we can write \[\boldsymbol{H}_t = \lambda \boldsymbol{I}_{Nd} + \sum_{s \in \mathcal{T}^{<t}_{\neg 0}} \overline{\boldsymbol{x}}_s \overline{\boldsymbol{x}}_s^\top \quad \text{and} \quad \boldsymbol{H}^i_t = \lambda \boldsymbol{I} + \sum_{s \in \mathcal{T}^{<t}_{\neg 0}} \overline{\boldsymbol{x}}^i_s {\overline{\boldsymbol{x}}^i_s}^\top.\] and using Lemma B.1 from [6], we have that \[\boldsymbol{U}_t^{-1/2}\boldsymbol{H}_t \boldsymbol{U}_t^{-1/2}= \boldsymbol{I}_{Nd} + \boldsymbol{G}_t.\] where \((\boldsymbol{G}_t)_{ij} = \mathbb{1}\{i \neq j\} (\boldsymbol{H}^i_t)^{-1/2} \boldsymbol{H}_t^{(i,j)} (\boldsymbol{H}^j_t)^{-1/2}\) and \(\boldsymbol{H}^{(i,j)}_t = \sum_{t \in \mathcal{T}^{<t}_{\neg 0}} \overline{\boldsymbol{x}}^i_t {\overline{\boldsymbol{x}}^j_t}^\top\). A straightforward application of Lemma D.2 from [6] with the quantities \(m_1 = m_2 = \sqrt{L_\mu N^{-1}}\), \(d_1 = d_2 = d\) and \(\delta = \frac{2 \delta}{N(N-1)}\), followed by a union bound over all \(i \in [N]\) and \(j \in [i+1 , N]\) like in Lemma 13, gives us, with high probability, for all pairs of \((i,j)\) where \(i < j\), \[\lVert \boldsymbol{H}^{(i,j)}_t \rVert \leq \sqrt{\frac{8 L_\mu^2}{N^2} \left\lvert \mathcal{T}^{<t}_{\neg 0} \right\rvert \log \left( \frac{d N (N-1)}{\delta} \right)}.\]

Now, using the diversity conditions and the definition of \(\kappa\), we have that

\[\mathop{\mathrm{\mathbb{E}}}[\overline{\boldsymbol{x}}^i_t {\overline{\boldsymbol{x}}^i_t}^\top\mid \mathcal{F}_{t-1}] = \mathop{\mathrm{\mathbb{E}}}[\dot{\mu}(\boldsymbol{x}_t^\top \widehat{\boldsymbol{\theta}}_0)e^{-1} \boldsymbol{x}^i_t {\boldsymbol{x}^i_t}^\top \mid \mathcal{F}_{t-1}] \succeq \rho \kappa^{-1}e^{-1} \boldsymbol{I} .\] Similar to Lemma 13, applying Lemma 30 using the quantities \(\alpha = \kappa^{-1}e^{-1} \leq 1\), \(m = \sqrt{L_\mu N^{-1}}\), \(\gamma = \lambda\), \(\delta = \frac{\delta}{N}\) and \(c = 0.5\), alongside the fact that \((N-1)^2 \geq N^{-2}\), and followed by a union bound over all \(i \in [N]\) gives us with high probability, \[\lambda_{\min} \left(\boldsymbol{H}^i_t \right) \geq \lambda + \frac{\rho |\mathcal{T}^{<t}_{\neg 0}|}{2} \; \forall t \text{ such that } |\mathcal{T}^{<t}_{\neg 0}| \geq T(\neg 0) := \frac{48 L_\mu^2 + 8 L_\mu N \rho}{3\rho^2}(N-1)^2 \log \left(\frac{2dN T}{\delta} \right).\] Now, once again, for \(i \in [N-1]\), define \(\boldsymbol{Z}_t^i \in \mathbb{R}^{d \times id}\) as the following matrix: for \(j \in [i]\), the \(j^{th}\) \(d \times d\) block of \(\boldsymbol{Z}_t^i\) is given by \((\boldsymbol{H}^{N-i}_t)^{-1/2} \boldsymbol{H}^{(N-i,N-i+j)}_t (\boldsymbol{H}^{N-i+j}_t)^{-1/2}\).

Then, using Lemma B.7 from [6] and following a similar approach to that shown in Lemma 13, we have that,

\[\lVert \boldsymbol{Z}_t^i \rVert \leq \sum_{j \in [i]} \sqrt{\frac{96 \log \left( \frac{d N(N-1)}{\delta} \right)}{N^2 (48 L_\mu^2 + 8 L_\mu N \rho) (N-1)^2 \log \left(\frac{2dN T}{\delta} \right) } } \leq \frac{3 i}{2 N(N-1)}.\]

Writing \(\boldsymbol{G}_t\) as a matrix recurrence relation as in Lemma 13 and using Lemma B.2 from [6] gives: \[\lambda_{\max}(\boldsymbol{G}_t) \leq \frac{3}{4} \quad \text{ and } \quad \lambda_{\min}(\boldsymbol{G}_t) \geq -\frac{3}{4}.\] Substituting \(\boldsymbol{G}_t = \boldsymbol{U}_t^{-1/2}\boldsymbol{H}_t \boldsymbol{U}_t^{-1/2} - \boldsymbol{I}_{Nd}\), we get that \[\frac{1}{4} \boldsymbol{U}_t \preceq \boldsymbol{H}_t \preceq \frac{7}{4} \boldsymbol{U}_t.\] This finishes the proof for the first part. The second part is exactly the same as in Lemma 13. ◻

Proof. The proof is the same as that of Lemma 14. ◻

Proof. Define \(\Sigma_C := \mathop{\mathrm{\mathbb{E}}}[\boldsymbol{x}_s\boldsymbol{x}_s^\top \mid \mathcal{F}_{s-1}] \succeq \alpha \rho \boldsymbol{I}\). Also, define the matrix martingale \(\boldsymbol{Z}_t = \sum_{s \in [t]} \boldsymbol{x}_s\boldsymbol{x}_s^\top - t\Sigma_C\) and \(\boldsymbol{Z}_0 = 0\). Finally, define the martingale difference sequence \(\boldsymbol{X}_s = \boldsymbol{Z}_s - \boldsymbol{Z}_{s-1}\) for all \(s \geq 1\).

Then, we have that \(\lVert \Sigma_C \rVert \leq m^2\), and \(\lVert \boldsymbol{X}_s \rVert = \lVert \boldsymbol{x}_s\boldsymbol{x}_s^\top + \Sigma_C \rVert \leq 2m^2\). A calculation similar to Lemma D.1 from [6] shows that \[\sum\limits_{s \in [t]}\lVert \mathop{\mathrm{\mathbb{E}}}[\boldsymbol{X}_s^\top \boldsymbol{X}_s \mid \mathcal{F}_{s-1}] \rVert = \sum\limits_{s \in [t]}\lVert \mathop{\mathrm{\mathbb{E}}}[\boldsymbol{X}_s \boldsymbol{X}_s^\top \mid \mathcal{F}_{s-1}] \rVert \leq 2m^4 t.\] Thus, an application of Lemma 31 with the quantities \(d_1 = d_2 = d\), \(R = 2m^2\) , \(w = m^2 \sqrt{2t}\), and \(u = (1-c)\rho t\) for some \(c \in (0,1)\) results in \[\mathbb{P}\left\{\left\lVert \sum_{s \in [t]} \boldsymbol{x}_s\boldsymbol{x}_s^\top - t \Sigma_C\right\rVert \geq (1-c) \rho t\right\} \leq 2d \exp\left(-\frac{3(1-c)^2\rho^2 t^2}{12m^4 t + 4(1-c) m^2 \rho t} \right)\] Thus, for all \(t \geq T_0 := \frac{12m^4 + 4(1-c)m^2 \rho}{3(1-c)^2\rho^2} \log \left(\frac{2dT}{\delta}\right)\), we have that with probability at least \(1 - \frac{\delta}{T}\), \[\left\lVert \sum_{s \in [t]} \boldsymbol{x}_s\boldsymbol{x}_s^\top - t \Sigma_C\right\rVert \leq (1-c) \rho t.\] Now, using the fact that \(\lVert \boldsymbol{A} \rVert = \lambda_{\max}(\boldsymbol{A})\) and \(\lambda_{\max}(-\boldsymbol{A}) = -\lambda_{\min} (\boldsymbol{A})\), we have that \[\lVert \boldsymbol{A} - \boldsymbol{B} \rVert = \lVert (-\boldsymbol{A}) - (-\boldsymbol{B}) \rVert \geq \lvert \lambda_{\max}(-\boldsymbol{A}) - \lambda_{\max}(-\boldsymbol{B}) \rvert = \lvert \lambda_{\min}(\boldsymbol{A}) - \lambda_{\min}(\boldsymbol{B}) \rvert\] and thus, we can write that with probability \(1 - \frac{\delta}{T}\), \[(1-c) \rho t \geq t \lambda_{\min}(\Sigma_C) - \lambda_{\min}\left(\sum_{s \in [t]} \boldsymbol{x}_s\boldsymbol{x}_s^\top \right) .\] Rearranging results in \[\lambda_{\min}\left(\sum_{s \in [t]} \boldsymbol{x}_s\boldsymbol{x}_s^\top \right) \geq t \lambda_{\min} (\Sigma_C) - (1-c) \rho t \geq \alpha \rho t - (1-c) \rho t \geq c \rho t\] where the last inequality uses the fact that \(\alpha \in (0,1]\). A union bound over all \(t \in [T_0 , T]\) finishes the proof. ◻