Contextual Combinatorial Bandits with Probabilistically Triggered Arms

The stochastic multi-armed bandit (MAB) problem is a classical sequential decision-making problem that has been widely studied (Robbins, 1952; Auer et al., 2002; Bubeck et al., 2012). As an extension of MAB, combinatorial multi-armed bandits (CMAB) have drawn attention due to fruitful applications in online advertising, network optimization, and healthcare systems (Gai et al., 2012; Kveton et al., 2015a; Chen et al., 2013, 2016a; Wang & Chen, 2017; Merlis & Mannor, 2019). CMAB is a sequential decision-making game between a learning agent and an environment. In each round, the agent chooses a combinatorial action that triggers a set of base arms (i.e., a super-arm) to be pulled simultaneously, and the outcomes of these pulled base arms are observed as feedback (typically known as semi-bandit feedback). The goal of the agent is to minimize the expected regret, which is the difference in expectation for the overall rewards between always playing the best action (i.e., the action with the highest expected reward) and playing according to the agent’s own policy.

Motivated by large-scale applications with a huge number of items (base arms), there exists a prominent line of work that advances the CMAB model: the combinatorial contextual bandits (or C²MAB for short)  (Qin et al., 2014; Li et al., 2016; Takemura et al., 2021). Specifically, C²MAB incorporates contextual information and adds the simple yet effective linear structure assumption to allow scalability, which provides regret bounds that are independent of the number of base arms $m$. Despite C²MAB’s success in leveraging contextual information for better scalability, existing works fail to formulate the general arm triggering process, which is essential to model a wider range of applications, e.g., cascading bandits (CB) and influence maximization (IM), and more importantly, they do not provide satisfying results for settings with probabilistically triggered arms. For example, Qin et al. (2014); Takemura et al. (2021) only consider the deterministic semi-bandit feedback for C²MAB. Li et al. (2016); Wen et al. (2017) implicitly consider the arm triggering process for specific CB or IM applications but only gives sub-optimal results with unsatisfying factors (e.g., $1/p_{\min},K$ that could be as large as the number of base arms), owing to loose analysis, weak conditions, or inefficient algorithms that explore the unknown parameters too conservatively.

To handle the above issues, we enhance the C²MAB framework by considering an arm triggering process. Specifically, we propose the general framework of contextual combinatorial bandits with probabilistically triggered arms (or C²MAB-T for short). At the base arm level, C²MAB-T uses a time-varying feature map $\bm{\phi}_{t}$ to model the contextual information at each round $t$, and the mean outcome of each arm $i\in[m]$ is a linear product of the feature vector $\bm{\phi}_{t}(i)\in\mathbb{R}^{d}$ and an unknown vector $\theta^{*}\in\mathbb{R}^{d}$ (where $d\ll m$ to handle large-scale applications). At the (combinatorial) action level, inspired by the non-contextual CMAB with probabilistically triggered arms (or CMAB-T) works (Chen et al., 2016b; Wang & Chen, 2017; Liu et al., 2022), we formally define an arm-triggering process to cover more general feedback models such as semi-bandit, cascading, and probabilistic feedback. We also inherit smoothness conditions for the non-linear reward function to cover different application scenarios, such as CB, IM, and online probabilistic maximum coverage (PMC) problems (Chen et al., 2016a; Wang & Chen, 2017). With this formulation, C²MAB-T retains C²MAB’s scalability while also enjoying CMAB-T’s rich reward functions and general feedback models.

Contributions. Our main results are shown in Table 1.

First, we study C²MAB-T under the triggering probability modulated (TPM) smoothness condition, a condition introduced by Wang & Chen (2017) to remove a factor of $1/p_{\min}$ in the pioneer CMAB-T work (Chen et al., 2016a). This result follows a similar vein by devising C²-UCB-T algorithm and proving a $\tilde{O}(d\sqrt{KT})$ regret, which removes a $1/p_{\min}$ factor for prior contextual CB applications (Li et al., 2016) (Main Result 1 in Table 1). The key technical challenge is that the triggering group (TG) analysis (Wang & Chen, 2017) for CMAB-T cannot handle the triggering probability determined by time-varying contexts. To tackle this issue, we devise a new technique, called the triggering probability equivalence (TPE), which links the triggering probabilities with the random triggering event under expectation. In this way, we no longer need to bound the regret caused by possibly triggered arms, but only need to bound the regret caused by actually triggered arms. As a result, we can then directly apply the simple non-triggering C²MAB analysis to obtain the regret bound for C²MAB-T. In addition, our TPE can reproduce the results for CMAB-T in a similar way.

Second, we study the C²MAB-T under the variance modulated (VM) smoothness condition (Liu et al., 2022), in light of the recent variance-adaptive algorithms to remove the batch size dependence $O(\sqrt{K})$ for CMAB-T (Merlis & Mannor, 2019; Liu et al., 2022; Vial et al., 2022). We propose a new variance-adaptive algorithm VAC²-UCB and prove a batch-size independent regret $\tilde{O}(d\sqrt{T/p_{\min}})$ under VM condition (Main Result 2 in Table 1). The main technical difficulty is to deal with the unknown variance. Inspired by Lattimore et al. (2015), we use the UCB/LCB value to construct an optimistic variance and on top of that, we prove a new concentration bound to incorporate the triggered arms and optimistic variance to get the desirable results.

Third, we investigate the stronger triggering probability and variance modulated (TPVM) condition (Liu et al., 2022) in order to remove the additional $1/\sqrt{p_{\min}}$ factor. The key challenge is that we cannot directly use TPE to link the true triggering probability with the random trigger event as before, since the TPVM condition only yields a mismatched triggering probability associated with the optimistic variance used in the algorithm. Our solution is to bound this additional mismatch by lower-order terms based on mild conditions on the triggering probability, which achieves the $\tilde{O}(d\sqrt{T})$ regret bounds (Main Result 3 in Table 1).

As a valuable by-product, our TPE analysis and VAC²-UCB algorithm can be applied to non-contextual CMAB-T and C²MAB, improving the existing results by a factor $\sqrt{\log T}$ (Additional Result 1 in Table 1) and $\sqrt{K}$ (Additional Result 2 in Table 1), respectively. Our empirical results on both synthetic and real data demonstrate that the VAC²-UCB algorithm outperforms the state-of-art variance-agnostic and variance-aware bandit algorithms in the linear cascading bandit application that satisfies the TPVM condition.

Related Work. The stochastic CMAB model has received significant attention. The literature was initiated by (Gai et al., 2012). Since, its regret has been improved by Kveton et al. (2015b), Combes et al. (2015), Chen et al. (2016a). There exist two prominent lines of work in the literature related to our study: contextual CMAB and CMAB with probabilistically triggered arms (C²MAB and CMAB-T).

For C²MAB works, Qin et al. (2014) is the first study, which proposes C²UCB algorithm that considers reward functions under 2-norm $B_{2}$ smoothness condition. Then Takemura et al. (2021) replaces the 2-norm smoothness condition with a new 1-norm $B_{1}$ smoothness condition, and proves a $O(B_{1}d\sqrt{KT}\log T)$ regret bound. In this work, we extend the C²MAB with triggering arms to cover more application scenarios (e.g., contextual CB and contextual IM). Moreover, we further consider the stronger VM condition and propose a new variance-adaptive algorithm that can achieve a $\sqrt{K}$ factor improvement in the regret upper bound for applications like PMC.

For CMAB-T works, Chen et al. (2016a) is the first work that considers the arm triggering process to cover CB and IM applications. The authors propose the CUCB algorithm, and give an $O(B_{1}\sqrt{mKT\log T}/p_{\min})$ regret bound under 1-norm $B_{1}$ smoothness condition. Then Wang & Chen (2017) proposes the stronger 1-norm triggering probability modulated (TPM) $B_{1}$ smoothness condition, and use the triggering group (TG) analysis to remove a $1/p_{\min}$ factor in the previous regret. Recently, Liu et al. (2022) incorporates the variance information, and proposes the variance-adaptive algorithm BCUCB-T, which also uses the TG analysis and further reduces the regret’s dependency on batch-size from $O(K)$ to $O(\log K)$ under the new variance and triggering probability modulated (TPVM) condition. The smoothness conditions considered in this work are mostly inspired by the above works, but directly following their algorithm and TG analysis fail to obtain any meaningful result for our C²MAB-T setting. Conversely, our new TPE analysis can be applied to CMAB-T, reproducing CMAB-T’s result under the 1-norm TPM condition, and improving a factor of $(\sqrt{\log T})$ under the TPVM condition.

There are also many studies considering specific applications under the C²MAB-T framework (by unifying C²MAB and CMAB-T), including contextual CB (Li et al., 2016; Vial et al., 2022), contextual IM (Wen et al., 2017), etc. One can see that these applications fit into our framework by verifying that they satisfy the TPM, VM, or TPVM conditions; thus achieving improved results regarding $K,p_{\min}$ factors. We defer a detailed theoretical and empirical comparison to Sections 3, 4 and 5. Zuo et al. (2022) study the online competitive IM and also uses C²MAB-T to denote their contextual setting. However, their meaning of “contexts” is the action of the competitor, which acts at the action level and only affects the reward function (or regret) but not the base arms’ estimation. This is very different from our setting, where contexts act at the base arm level and hence one cannot directly apply their results.

We study contextual combinatorial bandits with probabilistically triggered arms (C²MAB-T). We use $[n]$ to represent set $\{1,...,n\}$. We use boldface lowercase letters and boldface CAPITALIZED letters for column vectors and matrices, respectively. $\left\lVert\bm{x}\right\rVert_{p}$ denotes the $\ell_{p}$ norm of vector $\bm{x}$. For any symmetric positive semi-definite (PSD) matrix $\bm{M}$ (i.e., $\bm{x}^{\top}\bm{M}\bm{x}\geq 0,\forall\bm{x}$), $\left\lVert\bm{x}\right\rVert_{\bm{M}}=\sqrt{\bm{x}^{\top}\bm{M}\bm{x}}$ denotes the matrix norm of $\bm{x}$ regarding matrix $\bm{M}$.

We specify a C²MAB-T problem instance using a tuple $([m],\mathcal{S},\Phi,\Theta,D_{\text{trig}},R)$, where $[m]=\{1,2,...,m\}$ is the set of base arms (or arms); $\mathcal{S}$ is the set of eligible actions where $S\in\mathcal{S}$ is an action;^***$\mathcal{S}$ is a general action space. When $\mathcal{S}$ is a collection of subsets of $[m]$, we often refer to $S\in\mathcal{S}$ as a super arm. $\Phi$ is the set of possible feature maps where any feature map $\bm{\phi}\in\Phi$ is a function $[m]\rightarrow\mathbb{R}^{d}$ that maps an arm to a $d$-dimensional feature vector (and w.l.o.g. we normalize $\left\lVert\bm{\phi}(i)\right\rVert_{2}\leq 1$); $\Theta\subseteq R^{d}$ is the parameter space; $D_{\text{trig}}$ is the probabilistic triggering function to characterize the arm triggering process (and feedback), and $R$ is the reward function.

In C²MAB-T, a learning game is played between a learning agent (or player) and the unknown environment in a sequential manner. Before the game starts, the environment chooses a parameter $\bm{\theta}^{*}\in\Theta$ unknown to the agent (and w.l.o.g. we also assume $\left\lVert\theta^{*}\right\rVert_{2}\leq 1$). At the beginning of round $t$, the environment reveals feature vectors $(\bm{\phi}_{t}(1),...,\bm{\phi}_{t}(m))$ for each arm, where $\bm{\phi}_{t}\in\Phi$ is the feature map known to the agent. Given $\bm{\phi}_{t}$, the agent selects an action $S_{t}\in\mathcal{S}$, and the environment draws Bernoulli outcomes $\bm{X}_{t}=(X_{t,1},...X_{t,m})\in\{0,1\}^{m}$ for base arms^††† We assume $X_{t,i}$ are Bernoulli for the ease of exposition, yet our setting can handle any distribution with bounded $X_{t,i}\in[0,1]$., with mean $\mathbb{E}[X_{t,i}|\mathcal{H}_{t}]=\langle\bm{\theta}^{*},\bm{\phi}_{t}(i)\rangle$ for each base arm $i$. Here $\mathcal{H}_{t}$ denotes the history before the agent chooses $S_{t}$ and will be specified shortly after. Note that the outcome $\bm{X}_{t}$ is assumed to be conditional independent across arms given history $\mathcal{H}_{t}$, similar to previous works (Qin et al., 2014; Li et al., 2016; Vial et al., 2022). For convenience, we use $\bm{\mu}_{t}\triangleq(\langle\bm{\theta}^{*},\bm{\phi}_{t}(i)\rangle)_{i\in[m]}$ to denote the mean vector and $\mathcal{M}\triangleq\{\langle\bm{\theta},\bm{\phi}(i)\rangle_{i\in[m]}:\bm{\phi}\in\Phi,\bm{\theta}\in\Theta\}$ to denote all possible mean vectors generated by $\Phi$ and $\Theta$.

After the action $S_{t}$ is played on the outcome $\bm{X}_{t}$, base arms in a random set $\tau_{t}\sim D_{\text{trig}}(S_{t},\bm{X}_{t})$ are triggered, meaning that the outcomes of arms in $\tau_{t}$, i.e. $(X_{t,i})_{i\in\tau_{t}}$ are revealed as the feedback to the agent, and are involved in determining the reward of action $S_{t}$. At the end of round $t$, the agent will receive a non-negative reward $R(S_{t},\bm{X}_{t},\tau_{t})$, determined by $S_{t},\bm{X}_{t}$ and $\tau_{t}$, and similar to (Wang & Chen, 2017), the expected reward is assumed to be $r(S_{t};\bm{\mu}_{t})\triangleq\mathbb{E}[R(S_{t},\bm{X}_{t},\tau_{t})]$, a function of the unknown mean vector $\bm{\mu}_{t}$, where the expectation is taken over the randomness of $\bm{X}_{t}$ and $\tau_{t}\sim D_{\text{trig}}(S_{t},\bm{X}_{t})$. To allow the algorithm to estimate the underlying parameter $\bm{\theta}^{*}$ directly from samples, we assume the outcome does not depend on whether the arm $i$ is triggered, i.e., $\mathbb{E}_{\bm{X}\sim D,\tau\sim D_{\text{trig}}(S,\bm{X})}[X_{i}|i\in\tau]=\mathbb{E}_{\bm{X}\sim D}[X_{i}]$. To this end, we can give the formal definition of the history $\mathcal{H}_{t}=(\bm{\phi}_{s},S_{s},\tau_{s},(X_{s,i})_{i\in\tau_{s}})_{s<t}\bigcup\bm{\phi}_{t}$, which contains all information before round $t$, as well as the contextual information $\bm{\phi}_{t}$ at round $t$.

The goal of CMAB-T is to accumulate as much reward as possible over $T$ rounds by learning the underlying parameter $\theta^{*}$. The performance of an online learning algorithm $A$ is measured by its regret, defined as the difference of the expected cumulative reward between always playing the best action $S^{*}_{t}\triangleq\operatorname*{argmax}_{S\in\mathcal{S}}r(S;\bm{\mu}_{t})$ in each round $t$ and playing actions chosen by algorithm $A$. For many reward functions, it is NP-hard to compute the exact $S^{*}_{t}$ even when $\bm{\mu}_{t}$ is known, so similar to (Wang & Chen, 2017), we assume that the algorithm $A$ has access to an offline $(\alpha,\beta)$-approximation oracle, which for mean vector $\bm{\mu}$ outputs an action $S$ such that $\Pr\left[r(S;\bm{\mu})\geq\alpha\cdot r(S^{*};\bm{\mu})\right]\geq\beta$. The $T$-round $(\alpha,\beta)$-approximate regret is defined as

where the expectation is taken over the randomness of outcomes $\bm{X}_{1},...,\bm{X}_{T}$, the triggered sets $\tau_{1},...,\tau_{T}$, as well as the randomness of algorithm $A$ itself.

Our proposed algorithm C²-UCB-T (Algorithm 1) is a generalization of the C³-UCB algorithm originally designed for contextual combinatorial cascading bandits (Li et al., 2016). Our main contribution is to show an improved regret bound by a factor of $1/p_{\min}$ under the 1-norm TPM condition.

Recall that we define the data about the history as $\mathcal{H}_{t}=(\bm{\phi}_{s},S_{s},\tau_{s},(X_{s,i})_{i\in\tau_{s}})_{s<t}\bigcup\bm{\phi}_{t}$. Different from the CUCB algorithm (Wang & Chen, 2017) that directly estimates the mean $\bm{\mu}_{t,i}$ for each arm, Algorithm 1 estimates the underlying parameter $\bm{\theta}^{*}$ via a ridge regression problem over the history data $\mathcal{H}_{t}$. More specifically, we estimate $\bm{\theta}^{*}$ by solving the following $\ell_{2}$-regularized least-square problem with regularization parameter $\gamma>0$:

The closed form solution is precisely the $\hat{\theta}_{t}$ calculated in line 4, where the Gram matrix $\bm{G}_{t}=\sum_{s<t}\sum_{i\in\tau_{s}}\bm{\phi}_{s}(i)\bm{\phi}_{s}(i)^{\top}$ and the b-vector $\bm{b}_{t}=\sum_{s<t}\sum_{i\in\tau_{s}}\bm{\phi}_{s}(i)X_{s,i}$ are computed in line 10 and 11. We claim that $\hat{\theta}_{t}$ is a good estimator of $\theta^{*}$ by bounding their difference via the following lemma, which is also used in (Qin et al., 2014; Li et al., 2016).

Building on this, we construct an optimistic estimation of each arm’s mean $\bar{\mu}_{t,i}$ in line 6, where $\rho(\delta)$ is in Proposition 1, $\langle\bm{\phi}_{t}(i),\hat{\bm{\theta}}_{t}\rangle$ and $\rho(\delta)\left\lVert\bm{\phi}_{t}(i)\right\rVert_{\bm{G}_{t}^{-1}}$ are the empirical mean and confidence interval towards the direction $\bm{\phi}_{t}(i)$, respectively. As a convention, we clip $\bar{\mu}_{t,i}$ into $[0,1]$ if $\bar{\mu}_{t,i}>1$ or $\bar{\mu}_{t,i}<0$.

Thanks to Proposition 1, we have the following lemma for the desired amount of the base arm level optimism,

After computing the UCB values $\bar{\bm{\mu}}_{t}$, the agent selects action $S_{t}$ via the offline oracle with $\bar{\bm{\mu}}_{t}$ as input. Then base arms in $\tau_{t}$ are triggered, and the agent receives observation set $(X_{t,i})_{i\in\tau_{t}}$ as feedback to improve future decisions.

Discussion. Looking at Theorem 1, we achieve an $O(B_{1}d\sqrt{KT}\log T)$ regret bound when $d\ll K\leq m\ll T$, which is independent of the number of arms $m$ and the minimum triggering probability $p_{\min}$. Consider the combinatorial cascading bandits (Li et al., 2016) satisfying $B_{1}=1$ (see Section 5), our result improves the Li et al. (2016) by a factor of $1/p_{\min}$. Consider the linear reward function (Takemura et al., 2021) without triggering arms (i.e., $p_{i}^{\bm{\mu},S}=1$ for $i\in S$, and $0$ otherwise), one can easily verify $B_{1}=1$ and our regret matches the lower bound ${\Omega}(d\sqrt{KT})$ Takemura et al. (2021) up to logarithmic factors.

Analysis. Here we explain how to prove a regret bound that removes the $1/p_{\min}$ factor under the 1-norm TPM condition. The main challenge is that the mean vector $\bm{\mu}_{t}$ and the triggering probability $p_{i}^{\bm{\mu}_{t},S}$ are dependent on time-varying contexts $\bm{\phi}_{t}(i)$, so it is impossible to derive any meaningful concentration inequality or regret bound based on $T_{t,i}$, which is the number of times that arm $i$ is triggered, and has been used by the triggering group (TG) technique (Wang & Chen, 2017) to remove $1/p_{\min}$. To deal with this problem, we bypass the quantity $T_{t,i}$ and use the triggering-probability equivalence (TPE) technique that equalizes $p_{i}^{\bm{\mu}_{t},S}$ with $\mathbb{E}_{t}[\mathbb{I}\{i\in\tau_{t}\}]$, which in turn replaces the expected regret produced by all possible arms with the expected regret produced by $i\in\tau_{t}$ to avoid $p_{\min}$. To sketch our proof idea, we assume the oracle is deterministic with $\beta=1$ (the randomness of the oracle and $\beta<1$ are handled in Appendix A), and let filtration $\mathcal{F}_{t-1}$ be the history data $\mathcal{H}_{t}$ (defined in Section 2). Denote $\mathbb{E}_{t}[\cdot]=\mathbb{E}[\cdot\mid\mathcal{F}_{t-1}]$, the $t$-round regret $\mathbb{E}_{t}[\alpha\cdot r(S^{*}_{t};\bm{\mu}_{t})-r(S_{t};\bm{\mu}_{t})]{\leq}\mathbb{E}_{t}[r(S_{t};\bar{\bm{\mu}}_{t})-r(S_{t};\bm{\mu}_{t})]$, based on Condition 1, Lemma 1 and definition of $S_{t}$. Then

where (a) is by Condition 2, (b) is because $\bar{\mu}_{t,i},\mu_{t,i},S_{t}$ are $\mathcal{F}_{t-1}$ measurable so that the only randomness is from triggering set $\tau_{t}$ and we can substitute $p_{i}^{\bm{\mu}_{t},S_{t}}$ with event $\mathbb{I}\{i\in\tau_{t}\}$ under expectation, $(c)$ is by absorbing the expectation over $\tau_{t}$ to $\mathbb{E}_{t}$, and $(d)$ is a change of notation. After applying the TPE, we only need to bound the regret produced by $i\in\tau_{t}$. Hence

where (a) follows from Lemma 1, (b) is by Cauchy Schwarz inequality over both $i$ and $t$, and (c) is by the ellipsoidal potential lemma (Lemma 5) in the Appendix.

In this section, we propose a new variance-adaptive algorithm VAC²-UCB (Algorithm 2) to further remove the $O(\sqrt{K})$ factor and achieve $\tilde{O}(B_{v}d\sqrt{T})$ regret bound for applications satisfying stronger VM/TPVM conditions.

Different from Algorithm 1, VAC²-UCB leverages the second-order statistics (i.e., variance) to speed up the learning process. To get some intuition, we first assume the variance $V_{s,i}=\text{Var}[X_{s,i}]$ for each base arm $i$ at round $s$ is known in advance. In this case, VAC²-UCB adopts the weighted ridge-regression to learn the parameter $\bm{\theta}^{*}$:

where the first term is “weighted” by the true variance $V_{s,i}$. The closed-form solution of the above estimator is $\hat{\bm{\theta}}_{t}=\bm{G}_{t}^{-1}\bm{b}_{t}$ where the Gram matrix $\bm{G}_{t}=\sum_{s<t}\sum_{i\in\tau_{s}}V_{s,i}^{-1}\bm{\phi}_{s}(i)\bm{\phi}_{s}(i)^{\top}$ and the b-vector $\bm{b}_{t}=\sum_{s<t}\sum_{i\in\tau_{s}}V_{s,i}^{-1}\bm{\phi}_{s}(i)X_{s,i}$, which enjoys the similar form (but uses different weights $\bar{V}_{s,i}$) of line 12 and line 13.

The intuition of using the inverse of $V_{s,i}$ to re-weight the observation is that: the smaller the variance, the more accurate the observation $(\bm{\phi}_{t}(i),X_{t,i})$ is, and thus more important for the agent to learn unknown $\bm{\theta}^{*}$. In fact, the above estimator $\hat{\bm{\theta}}_{t}$ is closely related to the best linear unbiased estimator (BLUE) (Henderson, 1975). Concretely, in the literature of linear regression, Equation (5) is the lowest variance estimator of $\bm{\theta}^{*}$ among all unbiased linear estimators, when the regularization term $\gamma=0$, $V_{s,i}$ are the true variance proxy of outcomes $(X_{s,i})_{s<t,i\in\tau_{s}}$ and the context sequence $(\bm{\phi}_{s}(i))_{s<t,i\in\tau_{s}}$ follows the fixed design in Equation (5).

For our C²MAB-T setting, one new challenge arises since the variance $V_{s,i}=\mu_{s,i}(1-\mu_{s,i})$ is not known a priori. Inspired by (Lattimore et al., 2015; Zhou et al., 2021), we construct an optimistic estimation $\bar{V}_{s,i}$ to replace the true variance $V_{s,i}$ in Equation 5. Indeed, we construct $\bar{V}_{t,i}$ by solving the optimal value for the problem $\max_{\mu\in[\underaccent{\bar}{\mu}_{t,i},\bar{\mu}_{t,i}]}\mu(1-\mu)$, whose closed form solution immediately follows from the equation below,

where $\bar{\mu}_{t,i}$ and $\underaccent{\bar}{\mu}_{t,i}$ are UCB and LCB values to be introduced later. Notice that with high probability the true $\mu_{t,i}$ lies within LCB and UCB values and as they are getting more accurate, the optimistic variance $V_{t,i}$ is also approaching the true variance $V_{t,i}$.

To guarantee $\hat{\bm{\theta}}_{t}$ is a good estimator, we prove a new lemma (similar to Proposition 1) to guarantee the concentration bound of $\bm{\theta}_{t}$ but in face of the unknown variance. Note that the sentinel work Lattimore et al. (2015) proves a similar concentration bound, the difference is that we have multiple arms triggered in each round instead of a single arm. To address this, we replaced the original concentration bound with the new one below that has an extra $K^{4}$ factor in $N$, which finally results in $\log K$ factor in the confidence radius $\rho(\delta)$.

Building on this lemma, we construct $\bar{\mu}_{t,i}$ as an upper bound of $\bm{\mu}_{t,i}$ in line 6, and $\underaccent{\bar}{\mu}_{t,i}$ as a lower bound of $\bm{\mu}_{t,i}$ in line 7, based on our variance-adaptive $\hat{\bm{\theta}}_{t}$, $\bm{G}_{t}$. Note that the doubling of the radius $2\rho(\delta)$ instead of using $\rho(\delta)$ in Lemma 2 is purely for the correctness of our technical analysis. As a convention, we clip $\bar{\mu}_{t,i},\underaccent{\bar}{\mu}_{t,i}$ into $[0,1]$ if they are above 1 or below 0.

After the agent plays $S_{t}$, the base arms in $\tau_{t}$ are triggered, and the agent receives observation set $(X_{t,i})_{i\in\tau_{t}}$ as feedback. These observations (reweighted by optimistic variance $\bar{V}_{t,i}$) are then used to update $\bm{G}_{t}$ and $\bm{b}_{t}$ for future rounds.