Sparsity-Agnostic Linear Bandits with Adaptive Adversaries

Summary

This paper studies the sparse linear bandit problem without the prior knowledge of sparsity. The studied problem also considers general setup in which the context is chosen by an adaptive adversary and action set is not imposed with additional assumptions. Then, A OFUL based algorithms are proposed and regret bounds are provided.

Strengths

- Lifting assumptions used in existing works while still maintaining comparable or even better regret bounds. - The proposed algorithm provides an instance-dependent regret bound and worst-case bound as well. - As the performance of SparseLinUCB highly depends on distribution q, different choices of q are shown. - Numerical experiments are provided to support the significance of AdaLinUCB algorithm.

Weaknesses

- The instance dependent regret bound shows no improvement compared with standard OFUL algorithm, and could be even worse than that of OFUL, e.g., S^2>d. - For known sparsity and adaptive adversary setup, the instance depedent regret bound in Corollary 3.5 is worse than that of [2], which is dS/Delta. - The regret bound of SparseLinUCB is sensitive to the choice of distribution q. Though authors provide a specific example on the choice of q, the regret bound now highly depends on the choice of constant C. For example, if one chooses C=1, the instance dependent bound is worse than that of OFUL when S^2>d. - 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.

Questions

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

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes

Summary

This paper proposes statistically efficient linear bandit algorithms capable of handling cases where prior knowledge of the sparsity level $S$ is not given. The first algorithm, SparseLinUCB, achieves a $\tilde{O}(S \sqrt{dT})$ regret bound without any stochastic assumptions on the context vector, covering adversarially given context vectors. The main idea involves sampling the radius of the confidence set for the true reward parameter $\theta_*$ from a specific distribution and then selecting the optimistic action. It matches the lower bound when sparsity information is provided. The second algorithm, AdaLinUCB, updates the sampling distribution of the confidence radius using an approach (Exp3) that increases the likelihood of selecting a radius providing higher rewards. AdaLinUCB also achieves a $\tilde{O}(\sqrt{T})$ regret bound. Various experiments support the theoretical results of the proposed algorithms.

Strengths

- The motivation for the problem addressed in the paper is well explained, and the related work is thoroughly described. Overall, the paper is well-written and easy to understand. - The first algorithm, SparseLinUCB, is, to my knowledge, the first sparsity-agnostic linear bandit algorithm for adversarial context vectors. Additionally, it matches the lower bound regret when sparsity information is provided. - The second algorithm, which updates the confidence radius distribution at each time step, is also very interesting. Previous works using similar methods achieved loose regret bounds ($\tilde{O}(T^{2/3})$), whereas the proposed algorithm achieves $\tilde{O}(\sqrt{T})$ regret (though I have not rigorously checked this proof). - Various numerical experiments support the theory behind the proposed algorithms.

Weaknesses

- 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. - The explanation about $n$ in the confidence radius distribution $\set{ 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$.

Questions

- (Related to the 1st bullet in Weaknesses) Can AdaLinUCB still achieve the currently presented regret bound if the action set (context vectors) is given by an adaptive adversary? If not, can you briefly explain the issue? - (Related to the 2nd bullet in Weaknesses) It seems that how $\set{ 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? - 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?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors have well-addressed the limitations and further research directions in Section 6. The content discussed in this paper appears to have little to no negative societal impact.

Summary

This paper studies the stochastic linear bandits when the action set can be arbitrarily chosen without some additional assumptions. And the authors propose a randomized sparsity-agnostic bandit algorithm using the model selection idea, and show that EXP3 can be used as the master algorithm to obtain a decent regret bound. Experimental results are included in the end to verify the high efficiency of the proposed algorithms.

Strengths

1. The paper is easy to read, and most parts are pretty clear. E.g. Table 1 helps reader catch up all the existing literature and their differences quickly. 2. This paper studies an interesting and important problem when the arm set is arbitrarily chosen under the sparse linear bandit problem. I didn't check the proof in appendix in detail but all arguments seem reasonable to me. 3. Empirical results are provided to illustrate the high efficiency of the proposed algorithms.

Weaknesses

1. 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. 2. Lower bounds are not provided, as the authors mention in the limitation parts. So it is a little bit hard for readers to justify how good are the proposed bounds.

Questions

1. Why is the boundness of the random noise necessary in your theoretical proof? 2. 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. 3. Can you report the running time of your method in the experiments?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

No negative societal impact.

Summary

This paper studies Linear bandits with adversaries when the underlying parameter $\theta$ is sparse. It combines a previous sparse linear regression algorithm named SeqSEW with LinUCB, proposing an algorithm named SparseLinUCB. It also proposes a variant of the EXP3 algorithm named AdaLinUCB. Regret bounds dependent on the sparsity dimension $S$ are proved. Experiments are conducted on synthetic data.

Strengths

1. The paper proposes algorithms for sparse linear bandits with adversarial action sets. It proved a regret upper bound better than previous when the sparsity dimension $S$ is quite small with no assumptions on the sparsity structure. If the sparsity level is known, the result is optimal. 2. It also provides an instance-dependent regret bound. 3. It conducts synthetic experiments to show its better performance.

Weaknesses

1. The paper misses many very related works, especially those on K-armed bandits and linear bandits. 2. For the main algorithm design, I cannot see the necessity to use an online learning oracle to predict the reward $\hat X_t$ and then calculate the least squares estimation when having access to the real reward $X_t$. Could you explain it further? 3. The writing is unclear. (1) In Line 176, "the distribution $\\{q_i\\} _ {i \in [n]}$" is not well defined, over what? (2) The notation of the confidence set in Line 177 is contradictory with the notation in Appendix A, as it uses 2-norm rather than the $V_{t-1}$ norm. (3) 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. (4) Line 240: in terms of what? 4. 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?

Questions

See Weaknesses

Rating

5

Confidence

4

Soundness

3

Presentation

1

Contribution

2

Limitations

The authors have addressed the limitations and societal impact.