Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit

[Q1] No, your first sentence (premise) in the question is incorrect: The LAC condition does not "imply a mode of the context distribution in zero.""

It seems there might be a misunderstanding of the LAC condition's properties. If you need any clarification, please feel free to let us know.

Regardless, if you are still interested in a shifted mean, it turns out that this is not an issue at all. Our regret bound still holds. For example, for the Gaussian with a shifted mean, please see Appendix C.1.

Here is a imple explanation. Let the mean zero contexts $\mathbf{X}(t)$'s density as $f(x)$ with LAC fuction ${L}(\cdot)$. Then, the shifted contexts with mean $\mu$ has density $g(x) = f(x + \mathbf{\mu})$ and see that

$

\lVert \nabla \log g(x) \rVert_{\infty} &= \lVert \nabla \log f(x + \mu) \rVert_{\infty} \ &\leq L( \lVert x + \mu\rVert_{\infty}) \ &\leq L( \lVert x \rVert_{\infty} +\lVert \mu\rVert_{\infty})

$

Hence the density $g(x)$ has LAC with function $L'(x) = L (x + \lVert \mu \rVert_{\infty})$ and since $\lVert \mu\rVert_{\infty} = O(1)$, it has the same rate.

[Q2] We believe there is a misunderstanding in the comment here. We do NOT assume i.i.d. of arms at all. We only assume the independence of the entire arm set over time (note there is a clear difference between i.i.d.-ness vs. independence only; independent of each arm vs. independence of the arm set!), and hence we allow that arms can even be dependent on each other in a given arm set. A rich body of linear contextual bandit studies assumes stochastic contexts and independence of the contexts (often even stronger i.i.d. contexts) over time [5, 8, 15, 16, 25, 28].

In particular, all of the relevant greedy contextual bandit literature assumed even i.i.d.-ness (often i.i.d. for each arm), which is stronger than our problem setting that only requires independence of the arm set (not each arm or i.i.d.). We emphasize again that $X_i(t), X_j(t)$ can be correlated for $i, j \in [K]$. Hence, we strongly believe that justification is provided in order for our work to be fairly evaluated (note again our problem setting is even weaker than the previous problem setting in greedy contextual bandits).

[Q3] We are happy to address this question. The reason we present both bounded and unbounded contexts (particularly why we include analysis for unbounded context) is because previous works in greedy contextual bandits largely utilized unbounded noise (e.g., Gaussian) in feature setups. Hence, for fair comparisons with the existing results, we feel that it is fair to include unbounded cases [25, 28, 29].

There is also a technical reason to separately consider the two cases. Boundedness assumptions affect the regret bound differently. Hence, we would like to use appropriate soft boundedness of unbounded contexts. If we were to assume conventionally accepted $\ell_2$ boundedness for light-tail unbounded distributions, there could be a dimension dependency for the high-probability bound. Generally, it has a $\tilde{O}(\sqrt{d})$ bound which is often ignored but can be significant. However, since we assume $\psi_1$ or $\psi_2$ norm boundedness for unbounded contexts, it is dimension-free and we can get a tighter bound even in a more transparent manner.

[Q4-5] Please see the answer to W2 part; we think it will help understand your questions in the proof sketch. We would be happy to answer any further questions.

Thank the reviewer for taking the time to review our paper and for the comments. However, we believe there is a fundamental disagreement between the reviewer's comments and the focus of our study. We hope to remedy this through open-minded discussion. We strongly believe and remain very confident that our work presents significant values and very important results that advance the existing knowledge about greedy algorithms in contextual bandits.

[W1] With all due respect, we are very concerned that the reviewer does not even agree with the stochastic context setting and suggests a new setting (the reviewer thinks it "looks more natural") where features are fixed but the parameter is sampled. Then, this leads to the reviewer's conclusion that our contribution should be somehow discounted, which we believe is an unfair evaluation.

This is problematic because all of the existing greedy contextual bandit literature so far has been proposed under stochastic contexts, focusing on how such stochasticity in context allows for greedy algorithms to achieve sub-linear regret [8, 16, 25, 28]. In fact, the previous literature focused only on very few distributions (e.g., Gaussian and uniform), as we state in the paper, which our work significantly expand and even achieve much smaller regret.

Such a comment not only rejects the entire literature on greedy contextual bandits but also raises concerns about whether our work can be adequately evaluated compared to the existing results if the problem setting itself is disregarded. Our work significantly expand the set of context distributions admissible for greedy bandit algorithms, which has been an open question among many researchers.

There is a rich history of contextual bandits with stochastic contexts even beyond the greedy bandit literature [5, 8, 15, 16, 25, 28]. We hope for a fair re-evaluation based on the established and widely accepted problem setting compared to the relevant literature within the field. Please do not take this personally; we ask that the reviewer put themselves in the authors' shoes and consider whether there is any meaningful feedback to be gained from a comment that discredits the problem itself and disregards the entire history of research on greedy contextual bandits (and somehow hope that the authors' hard work can evaluated fairly). This is the main problem setting that all relevant literature has been working on. We respectfully but strongly dispute this point.

[W2] Firstly, we strongly disagree with the reviewer's statement that "the main paper is not very technical." We are unsure how our results and analysis could be perceived as "not very technical" to begin with. While we appreciate the feedback on improving the presentation in the appendix and will incorporate appropriate edits, we feel that the assertion that our paper is "not very technical" is unfounded. Throughout our paper, we present rigorous analysis and stronger results than what has previously been known in the literature.

Despite the disagreement, we are more than happy to provide a proof sketch—some details are already presented in Appendix D, but here, we will present more thorough arguments. We first demonstrate how our two challenges can lead to logarithmic regret.

Challenge 1: $\sqrt{t}$-rate $\ell_2$ concentration

First Challenge can lead the $\ell_2$ statistical resolution of the estimator. Under the Challenge 1, we can get

$

|X_{a(t)}^\top (\hat{\theta}{t-1} -\theta^\star)| \leq cx{\max}\frac{\sqrt{d}}{\sqrt{ \lambda_\star t}}, \quad |X_{a^\star(t)}^\top (\hat{\theta}{t-1} -\theta^\star)| \leq cx{\max}\frac{\sqrt{d}}{\sqrt{ \lambda_\star t}}

$

holds with high probability. Here, $c = \tilde{O}(1)$ constant.

However, this resolution in insufficient for the logarithmic regret, it can only get $O(\sqrt{T})$ regret bound.

Challenge 2: Logarithmic regret

But with the help of the Challenge 2 (margin condition), we can get logarithmic expected regret upper bound. When the greedy policy select $a(t)$, it means that

$

X_{a(t)}(t)^\top \hat{\theta}{t-1} \geq X{a^\star(t)}^\top \hat{\theta}_{t-1}

$

and by the definition of the optimal arm,

$

X_{a(t)}(t)^\top \theta^\star \leq X_{a^\star(t)}^\top \theta^\star

$

holds. Under the Challenge 1, we get

$

\operatorname{reg}'(t):= X_{a^\star(t)}(t)^\top \theta^\star- X_{a(t)}(t)^\top \theta^\star \leq 2cx_{\max}\frac{\sqrt{d}}{\sqrt{ \lambda_\star t}}.

$

Next, we define the event $E$ as the event of $\mathbf{X}(t)$ with regret occurring as $\operatorname{reg}'(t) > 0$. Under the event $E$, the suboptimality gap of $\mathbf{X}(t)$ satisfies

$

\Delta(\mathbf{X}(t)) \leq \operatorname{reg}'(t) \leq 2cx_{\max}\frac{\sqrt{d}}{\sqrt{ \lambda_\star t}}

$

and by the Challenge 2, we get

$

\mathbb{P}[\operatorname{reg}'(t) >0] \leq 2c x_{\max}C_{\Delta} \frac{\sqrt{d}}{\sqrt{ \lambda_\star t}} + \frac{1}{\sqrt{T}} \leq 3cx_{\max}C_{\Delta} \frac{\sqrt{d}}{\sqrt{ \lambda_\star t}}

$

By combining two things, we can bound the expected regret as

$

\operatorname{reg}(t) &= \mathbf{E}[\operatorname{reg}'(t)] \leq 3cx_{\max}C_{\Delta} \frac{\sqrt{d}}{\sqrt{ \lambda_\star t}} \times 2cx_{\max}\frac{\sqrt{d}}{\sqrt{ \lambda_\star t}}\ &= 6c^2x_{\max}^2 C_{\Delta} \frac{d}{\lambda_\star t}.

$

Using this argument, our only remainning goal is bounding two constants in Challenge 1 and 2.

[Bounded and unbounded contexts] Please see the [Q3] parts.

Thank you for your feedback and for the opportunity to discuss our work with you. Most of your feedback appears to be clarifications and suggestions for stylistic edits or minor typos, which we appreciate. However, none of your comments seem critical enough to warrant a rating of "Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility, and/or incompletely addressed ethical considerations."

Hence, we sincerely ask for a re-evaluation of our work. We strongly believe that the significance and impact of our results are very high, significantly expanding what had previously been known and doing so at a very timely moment. And, please let us know If you have any remaining questions.

[W1] The definition of the Gram matrix is $\Sigma(t):=\sum_{s=1}^t X_{a(s)}(s)X_{a(s)}(s)^\top$ and is stated in Algorithm 1. Readers of the linear bandit literature are familiar with this term, but we will provide the formal definition of the Gram matrix earlier in the text.

[W2] In healthcare, if a healthcare provider treats a patient with what appears to be sub-optimal (non-greedy) just for the purpose of exploration to learn the effect of a new treatment (not for the benefit of the particular patient being treated), it would be clearly unethical or often not feasible in actual healthcare practices (beyond clinical trials). This aspect has been discussed in various previous literature, including [8].

[W3] The exact definition of the margin condition is stated in Challenge 2 (line 266).

[W7] (LAC examples) First, we prove results in line 195. For exponential, Laplace, and Student's t, we prove results for 1-dimensional distribution. However, using Proposition 1, we can extend this to multi-dimensional contexts.

• Exponential: $\nabla \log f(x) = -\lambda$ and hence $| \nabla \log f(x) | \leq \lambda$.
• Uniform: $\nabla \log f(\mathbf{x}) = \mathbf{0}$ and hence $||\nabla \log f(\mathbf{x}) ||_\infty \leq 1$. (multi-dimensional)
• Laplace: $f(x) = \frac{1}{2 b} \exp \left(-\frac{|x-\mu|}{b}\right)$ and then $|\nabla \log f ({x})| = |\frac{1}{b}|$.
• Student's t: $f(x)= \Gamma\big(\frac{\nu+1}{2}\big) / \sqrt{\nu \pi} \Gamma\big(\frac{\nu}{2}\big) \cdot \big(1+\frac{x^{2}}{\nu}\big)^{-(\nu+1)/2}$ then $|\nabla \log f(x)|=|\nabla \frac{\nu +1}{2}\log(1 + \frac{x^2}{\nu})| = \frac{(\nu+1)x}{\nu + x^2}\leq C(\nu)$ for some constant $C(\nu)>0$.

[W10] Our experiment demonstrates that a greedy algorithm clearly outperforms other widely used algorithms (LinUCB and LinTS) that balance exploration and exploitation for common distributions. It appears that for those distributions, any type of exploration is unnecessary -- greedy algorithms suffice, which is the main assertion of this paper. Due to space constraints, the discussion is provided in Appendix N.

[W4-6, 8-9] Thank you for pointing out typos and stylistic suggestions. We will incorporate the appropriate edits suggested by the reviewer.

[Q1] LinUCB and LinTS are the most widely used linear contextual bandit algorithms. The LinUCB algorithm follows the paper by Abbasi-Yadkori et al. (2011), and the LinTS algorithm follows the paper by Agrawal and Goyal (2013) to conduct the experiments.

[Q2] We mean that if the two challenges regarding the context distribution are satisfied, i.e., if two key constants exist, logarithmic regret can be achieved. However, to get the exact upper bound, rather than proving existence of the constant bounding the two constant is essential, and we discuss this throughout the whole paper.

[Details for two challenges and regret] The following part breifly describe how to challenges can make logartihmic regret.

Challenge 1: $\sqrt{t}$-rate $\ell_2$ concentration

First Challenge can lead the $\ell_2$ statistical resolution of the estimator. Under the Challenge 1, we can get

holds with high probability. Here, $c = \tilde{O}(1)$ constant.

However, this resolution in insufficient for the logarithmic regret, it can only get $O(\sqrt{T})$ regret bound.

Challenge 2: Logarithmic regret

But with the help of the Challenge 2 (margin condition), we can get logarithmic expected regret upper bound.

When the greedy policy select $a(t)$, it means that

$

X_{a(t)}(t)^\top \hat{\theta}{t-1} \geq X{a^\star(t)}^\top \hat{\theta}_{t-1}

$

and by the definition of the optimal arm,

$

X_{a(t)}(t)^\top \theta^\star \leq X_{a^\star(t)}^\top \theta^\star

$

holds.

Under the Challenge 1, we get

$

\operatorname{reg}'(t):= X_{a^\star(t)}(t)^\top \theta^\star- X_{a(t)}(t)^\top \theta^\star \leq 2cx_{\max}\frac{\sqrt{d}}{\sqrt{ \lambda_\star t}}.

$

Next, we define the event $E$ as the event of $\mathbf{X}(t)$ with regret occurring as $\operatorname{reg}'(t) > 0$. Under the event $E$, the suboptimality gap of $\mathbf{X}(t)$ satisfies

$

\Delta(\mathbf{X}(t)) \leq \operatorname{reg}'(t) \leq 2cx_{\max}\frac{\sqrt{d}}{\sqrt{ \lambda_\star t}}

$

and by the Challenge 2, we get

$

\mathbb{P}[\operatorname{reg}'(t) >0] \leq 2c x_{\max}C_{\Delta} \frac{\sqrt{d}}{\sqrt{ \lambda_\star t}} + \frac{1}{\sqrt{T}} \leq 3cx_{\max}C_{\Delta} \frac{\sqrt{d}}{\sqrt{ \lambda_\star t}}

$

By combining two things, we can bound the expected regret as

$

\operatorname{reg}(t) &= \mathbf{E}[\operatorname{reg}'(t)] \leq 3cx_{\max}C_{\Delta} \frac{\sqrt{d}}{\sqrt{ \lambda_\star t}} \times 2cx_{\max}\frac{\sqrt{d}}{\sqrt{ \lambda_\star t}}\ &= 6c^2x_{\max}^2 C_{\Delta} \frac{d}{\lambda_\star t}.

$

Using this argument, our only remainning goal is bounding two constants in Challenge 1 and 2.

Thank you very much for recognizing the value of our results. We appreciate your feedback and are happy to provide our responses to your comments.

[W1] We are happy to address your comment and assure you that this should not be considered a weakness. Context distributions with discrete support, particularly fixed contexts, do not satisfy the LAC condition. However, for such distributions, the greedy algorithm fails (i.e., the greedy algorithms can incur linear regret) in the worst case. To the best of our knowledge, the LAC condition is the most inclusive condition for greedy algorithms to succeed. This is a crucial finding!

For further details, please read Appendix M, which contains a detailed discussion on this matter. We would be more than happy to elaborate on this. More details are also discussed in the answer to [Q1].

[W2] Our algorithm and regret bound are valid regardless of the choice of $\theta_0$ as long as it is bounded (and we have the freedom to choose a parameter with an adequate bound). Note that we can show that the minimum eigenvalue of the gram matrix selected by the greedy policy increases linearly with time for any $\theta_0$. Hence, we can derive the same regret bound. We will include this discussion in the revision.

[Q1] LAC is a sufficient condition, not a necessary condition. However, we do not know of any distributions (yet) that do not satisfy LAC but allow poly-logarithmic regret for greedy algorithms. There are good examples of distributions that are not LAC where greedy algorithms fail (or cannot achieve poly-logarithmic regret).

Firstly, it is well known that the greedy algorithm can fail in the worst case when contexts are fixed. Another example where LAC does not hold is a context distribution supported in a low-rank space. In this case as well, it is known that logarithmic regret is impossible [25], and we are not aware of the success of the greedy algorithm to the best of our knowledge. It is very important to note that our work significantly expands what has been known to be admissible for greedy algorithms. LAC is the most general condition currently known to allow greedy algorithms to achieve poly-logarithmic regret.

[Q2] Yes, our analysis extends to the GLM bandit as well for regular link functions as long as the link function has a bounded first derivative, which is commonly assumed in GLM bandit literature [14, 23]. As long as the concentration of the estimator is controlled by the gram matrix, most of the analysis is similar.

In the case of the kernelized bandit, it can be expressed in the form of a linear contextual bandit through the RKHS formulation. However, it usually assumes eigenvalue decay, so the minimum eigenvalue can become arbitrarily small. Hence, it might be difficult to apply the same analysis but would be an interesting future direction. So far, we have not even known what was possible for linear contextual bandits. Extension to other parametric bandits or kernelized bandits would be interesting.

[Q3] We appreciate your pointer to this related work. While the paper shares some common points of addressing the minimum eigenvalue of the gram matrix, our analysis significantly differs in that one of the key ingredients of our analysis is ensuring that the minimum eigenvalue of the gram matrix increases linearly (whereas in theirs it isn't). Furthermore, ensuring the margin condition from scratch is a key step that is not addressed in the reference you provided. However, analyzing the (though not logarithmic but some sublinear) performance of the greedy algorithm within the setup of the referred paper would be an interesting direction.

Thanks for the detailed response, which have addressed all my questions. I will retain my score.

But, please do make sure to take the other reviewers' concerns and suggestions on the paper's organization, including

• table of contents (a suggestion of mine that I forgot to mention)
• significantly reorganizing Appendix so that the readers can easily locate the main proof.
• typos
• etc

Thank you very much for recognizing the value of our results. We appreciate your feedback and are happy to provide our responses to your comments.

[W1] In order to validate optimality of contextual bandit algorithms under stochasticity, we need to derive proper lower bounds. However, existing studies ([7, 8, 5, 15]) that have examined poly-logarithmic regret under margin conditions (similar to our paper) have not discussed lower bounds or optimality either. One caveat is that since the greedy algorithm is not adaptive, the dimensionality and $K$ dependence can vary depending on context distributions. In such cases, deriving distribution-dependent lower bounds would be meaningful to determine optimality. However, we conjecture that such an analysis would be quite challenging. Nonetheless, it would be an interesting future direction to provide a lower bound under the margin condition, not just for greedy bandit algorithms but for linear contextual bandits in general.

[Q1] In short, to our best knowledge, the distributions that satisfy LAC are currently the only ones proven to be admissible for greedy algorithms! Typical cases where LAC is not satisfied include:

1. Fixed or discrete context distributions.
2. Low rank or nearly low rank contexts.

In case 1, it is known that the greedy algorithm fails for fixed contexts. In case 2, it is known that logarithmic regret is impossible [25]. Additionally, for distributions with double exponential density (e.g., Gumbel distribution), LAC is not satisfied. However, with slight modifications, it might be possible to show a sublinear regret bound, but we are unsure how tight the bound can be (we do not know whether poly-logarithmic regret would be possible). It is very important to note that our work significantly expands what has been known to be admissible for greedy algorithms.

[Q2] Previous literature assumes the existence of a constant satisfying the margin condition and regards it as a fixed constant. However, we derive the upper bound of the margin constant from the LAC density.

We emphasize again that we do not assume the existence of the margin constant. For example, many previous studies [7, 8, 5, 15] assume that there exists $C_\Delta$ satisfying: $\mathbb{P}[X_{a^\star}(t)^\top \theta^\star - \max_{i \neq a^\star} X_{i}(t)^\top \theta^\star \leq \varepsilon] \leq C_\Delta \varepsilon.$ With this margin assumption, one can achieve logarithmic regret. However, our paper calculates and estimates the margin constant $C_\Delta$ from scratch, only assuming the densities of contexts are LAC.

Also, note that if the above holds, then our equation of the margin condition (equation (3)) holds directly. Hence, our version of the margin condition is weaker. More importantly, we do not even impose such an assumption to start with! Instead, we prove that distributions in LAC automatically satisfy the margin condition which is a significant contribution.