Sparsity-Agnostic Linear Bandits with Adaptive Adversaries

We appreciate your valuable time and effort in offering detailed feedback on our work. In the following, we address your questions one by one.

Q1: Can authors provide another distribution selection case which can recover $dS/\Delta$ instance-dependent bound in known sparsity and adaptive adversary setup?

A1: Yes, this can be achieved by setting $q_o = 1$. Then, Theorem 4 of [2] directly implies a problem-dependent bound of order $\tilde{O}\left(\frac{dS}{\Delta}\right)$ for $q_o = 1$. We will note this result in the revision.

Q2: For known sparsity and adaptive adversary setup, the instance-dependent regret bound in Corollary 3.5 is worse than that of [2], which is dS/Delta.

A2: See A1. For a known sparsity setup, our regret bound can be of the same order as that of [2].

Q3: Why the instance dependent regret bound shows no improvement compared with standard OFUL algorithm.

A3: We have provided some intuitions on why it is difficult to provide a problem-dependent bound that benefits from sparsity in Lines 214-220. Essentially, as long as you set $q_{n}$ as a constant (even as small as $1/\sqrt{T}$), the regret will scale as $\tilde O(d^2 / \Delta)$.

Q4: For the action chosen (step 5 in Algorithm 1), it could be difficult to compute $A_t$ since this optimization problem contains non-linear term and the action set is arbitrary.

A4: The computation of $A_t$ in Step 5 of Algorithm 1 is as hard as computing the prediction in the OFUL algorithm, which can be done efficiently when the action set is finite. In the case of arbitrary actions sets, not much can be said about the computational efficiency of solving this problem, see [17, Section 19.3.1].

We appreciate your valuable time and effort in offering detailed feedback on our work. In the following, we address your questions one by one.

Q1: The SparseLinUCB algorithm does not make stochastic assumptions about the action set (context vectors), thus providing theoretical guarantees even in the case of an adaptive adversary. However, AdaLinUCB is described as an algorithm for stochastic linear bandits. It seems that the stochastic assumptions required for AdaLinUCB's regret bound are not explained.

A1: AdaLinUCB is indeed designed to handle adaptive adversarial action sets (see, for example, the initial lines 414-419 of the proof where the adversarial nature of the action set appears in the analysis). We will clarify this in the revision. There may have been some confusion regarding the title of Section 4: "Adaptive Model Selection for Stochastic Linear Bandits." In the literature, such as Chapter 19 of the bandit book [17] and reference [2], the term "stochastic linear bandits" typically refers to the presence of stochasticity in the subgaussian noise term $\epsilon_t$, as outlined in Equation (2.1).

Q2: The explanation about $n$ in the confidence radius distribution $\\{q_s\\}_{s\in [n]}$ appears insufficient. Additionally, there seems to be no term for $n$ in the regret bound. I am curious whether the regret bound is independent of $n$.

A2: As stated in Line 182, we choose $n = \Theta(\log d)$, which is large enough to ensure $\alpha_n \geq \gamma(1/T)$. We will clarify this fact in the revision.

Q3: (Related to the 2nd bullet in weaknesses) It seems that how $\\{q_s\\}_{s\in [n]}$ is determined would impact the regret bound. You introduced a specific distribution in Eq. (3.3). How does the regret bound change if $n$ is significantly increased or decreased.

A3: Increasing $n$ beyond $\Theta(\log d)$ significantly affects the regret bound of Theorem 3.2 through the choice of $q_s$. If we increase $n$, the regret upper bound approximately becomes $O(n\sqrt{dT})$. Indeed, following our choice $q_i \approx 2^{−i}$ (Eq. (3.3)), the first term in Lines 190-191 has order $O(n\sqrt{dT})$, while the second term has order $O(S \sqrt{dT})$ since $Q\approx \sum_{i>o} 2^{-i} \approx 2^{-o}\approx O(1/S)$, regardless of the size of $n$. Therefore, the final regret bound becomes of order $O(n\sqrt{dT})$. Intuitively, this makes sense, as increasing the number of models increases the exploration, which eventually has a negative impact on the regret.

If $n$ is decreased such that $\alpha_n < \gamma(1/T)$, then $\theta^*$ may not belong to any confidence set in our hierarchy, and the regret could thus become linear in $T$. As such, we must ensure $\alpha_{n}\geq \gamma(1/T)$ and highlight it in Line 181.

Q4: The motivation for updating the confidence radius distribution at each time step in AdaLinUCB is interesting. However, the current result shows a looser regret bound compared to SparseLinUCB. Despite the computational cost of updating the distribution, there seems to be no statistical gain. In what instances would it be better to use AdaLinUCB over SparseLinUCB? Also, can you briefly explain why AdaLinUCB performs better empirically?

A4: AdaLinUCB works better empirically since it automatically adjusts the radius of the confidence bound. Theoretical confidence bounds are typically set very conservatively to ensure error probability guarantees for hard environments (e.g., when the action set is chosen by the adaptive adversary), which often results in over-exploration. For example, in Chapter 36 of the Szepesvari and Lattimore book "Bandits," the sixth note in Section 36.5 mentions that values of the Linear Thompson Sampling parameter (i.e., the variance of the posterior distribution playing a similar role to the radius of the confidence bound in UCB) which show good empirical performance do not have any theoretical guarantee. Conversely, the values of the parameter ensuring a solid theoretical guarantee consistently perform poorly in practice.

As a future research direction, we can further explore the gap between the practical superior performance and theoretical limitations of AdaLinUCB, and even consider what the lower bound for sparsity-agnostic linear bandits might be.

We appreciate your valuable time and effort in offering detailed feedback on our work. In the following, we address your questions one by one.

Q1: The used techniques are based on the existing literature (e.g. seqsew, exp3 master algorithm). It will be better to show the theory novelty of this work in a separate paragraph.

A1: We do have a 40-line paragraph “Technical challenges” (Lines 61-100) explaining the theoretical novelty. One of our main technical contributions is demonstrating that our exploration, measured by $\det V_{t-1}$, grows very rapidly, as highlighted in Lines 81-86 (the proof details are shown in Lemmas D.4 and D.5). As an example to show the power of our new techniques, we achieve a $\sqrt{T}$ regret bound for AdaLinUCB, whereas previous works [11,24] using the Exp3 to learn the probability over a hierarchy of confidence sets have a regret bound of only $T^{2/3}$.

Please refer to the Technical challenges paragraph for a full list of our original contributions.

Q2: Why is the boundness of the random noise necessary in your theoretical proof?

A2: Note that our results in Section 3 do not require boundedness of the noise, but only 1-subgaussianity, see (2.1) in Lines 138-139. We only require $\epsilon_t \in [-1,1]$ in Section 4 because the Exp3 algorithm, which is used in the proof of Theorem 4.1, requires bounded rewards, which in turn requires the noise to be deterministically bounded.

Q3: Is it possible to bound the regret with high probability instead of the expected value? If some existing literature proposed the regret bound with high probability, then it may not be fair to do the direct order comparison in Table 1.

A3: Thanks for pointing out this interesting question. We believe our in-expectation regret bound for SparseLinUCB could be extended to a bound in high probability after some changes in the analysis. As these changes do not appear to be trivial as they require a somewhat intricate martingale concentration analysis, we will leave this extension to future work.

In the revised version, we will also add notes to the table highlighting the algorithms that are high probability.

Q4: Can you report the running time of your method in the experiments?

A4: Although there were slight differences depending on the sparsity level or initial probability distribution, on average, a run of OFUL took 0.7 seconds, a run of SparseLinUCB took 1.4 seconds, and finally, a run of AdaLinUCB took 1.9 seconds. The longer runtime of SparseLinUCB and AdaLinUCB is motivated by the need of managing an ensemble of models. However, as we did not optimize the code, we expect these runtimes to be improvable.

Thank you for your valuable time and effort in providing detailed feedback on our work. We now address your questions one by one.

Q1: The paper misses many very related works, especially those on K-armed bandits and linear bandits.

A1: It would be useful to have some concrete pointers to the missing works, but we will definitely browse more carefully through the relevant literature.

Q2: For the main algorithm design, I cannot see the necessity to use an online learning oracle to predict the reward.

A2: The use of an online linear regression oracle for sparse linear bandits is an established technique whose advantages in the analysis have been shown in [2] and also in bandit book [17], see our comment in Line 149. In particular, using a sparse online learning algorithm provides a dependence on the sparsity parameter $S$ in the confidence bound. We therefore use Lemmas 2.1 and 2.2 from [2] to set $\gamma(1/T) = O(S\log T)$. Thus, there exists some constant $C$ such that

$\mathcal C_t=\\{ \theta \in \mathbb R^d: \|\theta\|_2^2+ \sum_s(\hat X_s - \langle A_s, \theta \rangle)^2 \leq CS\log T \\}$.

It is unclear how such a dependence could be obtained using the standard least square estimator, which would only provide a dependence on $d$.

Q3: Line 249: “the parameter $q$ does not provide a similar flexibility”, so I do not see the use of this probable selection, what is the benefit of the new algorithm design in Section 4?

A3: The main advantage of AdaLinUCB is its empirical performance, as we explain in Lines 243-244 and demonstrate in our experiments where it outperforms both OFUL and SparseLinUCB. This improved empirical performance is due to AdaLinUCB’s ability of tuning its distribution based on observed rewards.

From a theoretical viewpoint, AdaLinUCB achieves a regret bound of $\tilde{O}(\sqrt{T})$, using novel techniques descibed in Lines 61-100. Previous analyses of Exp3-based algorithms in [11] and [24] only achieved $\tilde{O}(T^{2/3})$ regret bounds, even under i.i.d. assumptions on the generation of the action sets, see Lines 122-131 for a description of these related works.

Q4: In Line 176, “the distribution $\\{q_i\\}_{i\in[n]}$” is not well defined, over what?

A4: In Lines 174-176 we say that the algorithm uses a hierarchy of confidence sets of increasing radius and draws the index $I_t$ of the confidence set by sampling from the probability distribution $\\{q_i\\}_{i \in [n]}$. We will clarify that the distribution is over the indices of the confidence sets, and make it explicit that $n$ is an input parameter to SparseLinUCB.

Q5: The notation of the confidence set in 177.

A5: This is a typo. It should be $V_{t-1}$ norm. Thank you for your careful reading!

Q6: In equation 3.1, $\gamma$ is a problem-dependent term so you cannot set the exact value of $o$, as is done in Corollary 3.3.

A6: In Corollary 3.3, we explicitly state that it is assumed the sparsity level $S$ is known, as detailed in Lines 194-195. With $S$ known, the upper bound of $\gamma(\delta)$ can be easily calculated from its definition.

Q7: Line 240: in terms of?

A7: This is a typo. We will remove the words “in terms of”.