Lasso Bandit with Compatibility Condition on Optimal Arm

Authors: Harin Lee, Taehyun Hwang, Min-hwan Oh
Primary area: learning theory
Keywords: Sparse linear bandits, Lasso, Regret analysis

Abstract:
We consider a stochastic sparse linear bandit problem where only a sparse subset of context features affects the expected reward function, i.e., the unknown reward parameter has a sparse structure.
In the existing Lasso bandit literature, the compatibility conditions, together with additional diversity conditions on the context features are imposed to achieve regret bounds that only depend logarithmically on the ambient dimension $d$.
In this paper, we demonstrate that even without the additional diversity assumptions, the \textit{compatibility condition on the optimal arm} is sufficient to derive a regret bound that depends logarithmically on $d$, and our assumption is strictly weaker than those used in the lasso bandit literature under the single-parameter setting.
We propose an algorithm that adapts the forced-sampling technique and prove that the proposed algorithm achieves $\mathcal{O}(\text{poly}\log dT)$ regret under the margin condition.
To our knowledge, the proposed algorithm requires the weakest assumptions among Lasso bandit algorithms under the single-parameter setting that achieve $\mathcal{O}(\text{poly}\log dT)$ regret.
Through numerical experiments, we confirm the superior performance of our proposed algorithm.

Decision: accept (poster)
Reviewer scores: 8, 6, 5

Reviews and discussion:
<thread>
creation date:
1730518385546

thread_type:
official_review

<thread_object>
creator: reviewer_ynf4

<content>
summary:
This paper proposes a weaker sufficient condition for high dimensional bandit algorithm. Under such weaker condition, the paper also proves regret bounds for bandit algorithms.

strengths:
1. The authors provide a lot of intuitions for the algorithm design.
2. I think in general the weaker condition, and the algorithm induced, would be a good addition to the literature.

weaknesses:
1. The paper needs to be restructured. If the key idea of this paper is the weaker condition proposed, then the main section and main results should be about this condition. Therefore, Appendix B should be the main part of the paper instead of just in the appendix. 
Besides, the novelty claimed, such as the cyclic induction (Lemma 6?), should be moved to the main text as well. It's hard to read and understand the novelty for the current version.
2. Assumption 3 is claimed to be "strictly weaker" than the existing conditions. Then, some counterexamples should be provided to show that Assumption 3 holds but not any of the existing conditions. 

I'd be willing to update my rating if the paper can be structured and easy to understand.

questions:
N/A
</content>
</thread_object>

</thread>
<thread>
creation date:
1730690511295

thread_type:
official_review

<thread_object>
creator: reviewer_wnkd

<content>
summary:
The author devised an algorithm called FS-WLasso, which is based on a greedy algorithm with the addition of forced exploration. According to the authors, this algorithm demonstrates polylogarithmic regret even under the weakest assumptions in the context of sparse linear bandits in a stochastic environment. They also demonstrated the algorithm’s practical effectiveness through simulations.

strengths:
- Soundness: In theoretical research, relaxing assumptions is undoubtedly meaningful. This work is particularly valuable in the sense that the authors united all various assumptions in sparse contextual linear bandits, and allows researchers to focus on a single general condition.

- Clarity: The authors clearly illustrated the relationship between their results and previous work using diagrams, and, through an extensive literature review, they included comparisons in multi-parameter setups to highlight the versatility of their setting (Remark 1). Additionally, their meticulous preparation is evident in the various remarks and supplementary materials to address anticipated questions (even the fixed arm set case) and to emphasize their significance/novelty.

- They also introduced a novel proof technique using induction - like a domino, they've constructed an interesting proof scheme to maintain their compatibility condition.

weaknesses:
- Their algorithm works on a more general 'environment', but to guarantee their performance the learning agent requires additional knowledge, such as the sparsity level $s_0$ or the gap $\Delta_0$. As they have mentioned, their result is not sparsity-agnostic. Even though they've mentioned in Appendix D, it is still true that they rely on the sparsity parameter $s_0$ and many other parameters, and I personally think this parameter is somewhat less general info than the noise level $\sigma$ or the norm bound of the context vector $x_{max}$.

questions:
- Why the exploration in Algorithm 1, line 5 should be a uniform one? I think the most intuitive exploration to guarantee the minimum eigenvalue is $a = argmax_{x\in x_t} \|\|x\|\|_{V_t^{-1}}$. 

- I don't understand why the fact that $M_0$ depends on multiple variables implies that it is a tunable parameter. Isn't it a worse situation, that a core parameter depends on multiple parameters (even $\Delta_*$ and $\phi_*$)? To compare it with Oh et al., 2021, it feels like 'an algorithm which is easy to run but should satisfy some strong assumptions on the environment' vs 'an algorithm which works on a weaker assumption but requires more information about the environment'. Some readers might think of this as an incremental improvement.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730717801075

thread_type:
official_review

<thread_object>
creator: reviewer_ltvm

<content>
summary:
The paper contributes to the high-dimensional bandits literature by relaxing the compatibility conditions required for analysis. Specifically, it reduces the need for compatibility conditions on all arms to only the optimal arm, thereby enhancing the generality of the results.

strengths:
By weakening the compatibility condition from all arms to only the optimal arm and relaxing all other diversification requirement in other high-dimensional bandits papers, this paper makes a solid contribution that broadens the applicability of high-dimensional bandit algorithms. Figure 1 and Table 1 clearly sketched the comparison against existing literature.

weaknesses:
- While the paper criticizes other studies for unverifiable conditions, it does not clearly explain how the compatibility condition on the optimal arm (Assumption 3) is more verifiable in practice. This lack of clarity weakens the argument against existing methods. 

- The suggestion to treat the forced sampling iteration number  $M_0$  as a tuning parameter could also be applied to other methods where assumptions are stronger and cannot be easily verified as well. This weakens the significance of the advantage in assuming compatibility for only the optimal arm and does not effectively address the issue of unverifiable assumptions.

- The proof sketch in Section 3.3 lacks sufficient emphasis on the techniques used to overcome the challenges posed by the weakened compatibility assumption. Without a clear explanation of how the standard compatibility condition is avoided, readers may find it difficult to understand the paper’s methodological contributions.

questions:
See weakenesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732548133830

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Our Key Contributions

comment:
We sincerely thank you for taking the time to review our paper and for recognizing our work. We hope our responses have adequately addressed your questions/feedback. If you have any further questions or comments, we would be more than happy to address them. In the sparse linear bandit problem, various assumptions and methods have been introduced to achieve sharp regret, but many of these assumptions are needed solely for technical purposes. A rigorous discussion on the relative strength of one assumption over another has not been provided before. **This paper offers the first rigorous discussion on the relative strength of assumptions, introduces a strictly relaxed sufficient condition needed to achieve sharp regret, presents a practical algorithm, and analyzes the proposed algorithms using a novel mathematical induction-based technique.** We hold our work in high regard and are immensely proud of the contributions we've made through our research. The depth of our analysis, the rigor of our methodology, and the potential impact of our findings are aspects of our work that we believe stand on their own merits. We strongly believe that our submission well surpasses the threshold of sufficient contribution. In the meantime, we would like to highlight some of the principal points.

**Weakest known condition for achieving poly-logarithmic regret in Lasso bandits:** In this paper, we primarily focus on alleviating strong stochastic assumptions imposed on context distribution in the previous Lasso bandit literature. Existing Lasso bandit literature necessitate stronger assumptions on the context distribution (e.g., relaxed symmetry \& balanced covariance or anti-concentration), which importantly, are non-verifiable in practical scenarios. However, **we show that the compatibility condition on the optimal arm is sufficient to achieve poly-logarithmic regret under the margin condition**, and **demonstrate that our assumption is strictly weaker than those used in other Lasso bandit literature** (Please refer to Figure 1 \& Appendix B). We genuinely believe that this paper stands on its own merit by establishing the weakest known condition for achieving poly-logarithmic regret in Lasso bandits, paving the way for future advancements in this area of research!

**Practically Applicable Algorithm:** Previous forced-sampling-based algorithm (Bastani \& Bayati, 2020) maintains two estimators and operates in two steps when choosing actions, whereas our algorithm only needs to select actions greedily based on the Lasso estimator, making our algorithm simple to implement. In addition, compared to the ESTC algorithm (Hao et al., 2020b), which is restricted to using only the samples gathered during the exploration period, our algorithm is designed to leverage data from both the exploration period (forced-sampling stage) and the adaptive action selection period (greedy selection stage) for estimation purpose. **Therefore, our algorithm demonstrates superior statistical performance, achieving lower regret (and thus higher reward) by fully utilizing all accessible data.** Also, our algorithm does NOT require strong context diversity assumption, which, importantly, are non-verifiable in practical scenarios. Even in cases where the context features of all arms except for the optimal arm are fixed (thus, assumptions such as anti-concentration are not valid), our proposed algorithms outperform the existing algorithms.

**Novel Analysis Technique:** Our proof technique significantly differs from the regret analysis in previous Lasso bandits. We observe that under Assumption 3, if the optimal arm has been selected sufficiently many times up to time 
$t$, the estimation error at $t$ can be controlled, and a well-estimated estimator leads to the selection of the optimal arm at the next time step. This observation reveals the cyclic structure regarding the estimation error and the selection of the optimal arms. Previous Lasso bandit papers do not capture this cyclic structure but instead rely on more convenient assumptions or automatic exploration ensured by diverse context distributions. **We analyze the cyclic structure of such good events using a novel mathematical induction argument (Proposition 1 in Appendix.E.1). We assert with confidence that our technical contributions are more distinct and significant than the other Lasso bandit literature, and we believe that this new analytical techniques will significantly influence future research in this field!**

In conclusion, we remain confident in the substantial value our work brings to the table, not only through the **introduction of new, more relaxed conditions and enhanced regret analysis** but also by **presenting a practical, straightforward-to-implement algorithm which is made possible by our new theoretical results.** This work is indeed a complete package, offering theoretical depth, novel insights, and practical applicability.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper examines the stochastic sparse linear bandit problem and proposes an algorithm that achieves $O(\mathrm{polylog}(T))$ regret under relaxed assumptions compared to prior work. The algorithm is analyzed theoretically, and its effectiveness is validated through numerical experiments. This work can be highly valued for presenting solid improvements on a problem of significant interest within the bandit community.

However, the paper has some weaknesses. It lacks sufficient discussion of specific applications or realistic scenarios that become feasible due to the relaxed assumptions. Additionally, reviewers raised concerns about the requirement for prior knowledge of sparsity parameters and the inability to pre-verify conditions corresponding to the relaxed assumptions. Specifically, while the authors highlight that the conditions in prior work are unverifiable, they do not address the verifiability of their own conditions, which is unfair and warrants additional discussion. Furthermore, concerns about the clarity and impact of the technical contributions were also noted.

Despite these weaknesses, discussions with the authors, including their rebuttal addressing these points, led to an overall positive assessment from the reviewers. Based on the premise that the above weaknesses will be addressed in the final version, I support the acceptance of this paper.