Variance-Dependent Regret Lower Bounds for Contextual Bandits

Thank you for your thoughtful and constructive feedback. We respond to your concerns and questions point by point below.

Q1. Learner–Adversary Relationship
“The explanation of whether the learner and the adversary are in competition or collaboration is somewhat unclear. It would be very helpful if the authors could illustrate this relationship using real-world applications to provide greater intuition.”

A1. In linear contextual bandits, two common settings are considered:
(i) the oblivious setting, where the sequence of decision sets is fixed in advance, and
(ii) the adaptive setting, where the decision set may depend on the learner’s behavior.

When incorporating variance, a similar distinction applies. The variance sequence can be either predefined or chosen adaptively. Our lower bound focuses on the more challenging adaptive case, where an adversary selects the round-dependent variance $\sigma_t$, with each action’s variance upper bounded by $\sigma_t$ at that round. This flexible setup captures both adversarial and cooperative behaviors, depending on how variance is selected to influence learning. We will update the manuscript to clarify this relationship and provide practical examples to aid intuition.

Q2. Specificity of the Lower Bound Construction
“This paper focuses exclusively on establishing a lower bound... it would be greatly beneficial if the paper could also discuss the types of settings or conditions under which this hard instance is likely to occur.”

A2. Our lower bound characterizes the worst-case regret, which typically arises when the reward gap is $\Delta = \Theta(1/\sqrt{K})$. In such settings, distinguishing between instances requires $\Omega(K)$ samples, leading to total regret of $\Omega(\sqrt{K})$.

One important condition is whether the decision set is fixed. As we highlight in Corollary 5.7, when the decision set is fixed, early low-variance observations can significantly reduce regret, even if the cumulative variance is large. In contrast, our lower bound construction crucially relies on the adaptive decision set setting, which allows a lower bound for general variance sequence.

We acknowledge that this worst-case construction may not arise in many real-world applications. Nonetheless, it serves as a fundamental limit that any algorithm must overcome in the general setting with adaptive variance sequences and decision sets. We will emphasize these distinctions more clearly in the revised manuscript.

Q3. Generalization to Function Approximation
“Is it possible to generalize the results into contextual bandit with general function approximation?”

A3. Yes. The lower bound construction naturally extends to contextual bandits with general function classes by leveraging the notion of eluder dimension (Russo & Van Roy, 2013). Our current hard instance, defined over a linear function class of dimension $d$, also applies to function classes with eluder dimension $d$.

Q4. Lower Bound for the Stochastic Setting
“Can you provide a lower bound for the stochastic linear bandit setting, e.g., when the first $d$ rounds have zero variance?”

A4. The key distinction between the stochastic linear bandit and the contextual linear bandit lies in the fixed decision set. As shown in Corollary 5.7, in the stochastic setting, an algorithm may incur only $O(d)$ regret, even with large cumulative variance, provided early rounds allow accurate estimation of the latent vector $\mu$. This $O(d)$ lower bound is tight, as it still requires $d$ informative rounds to learn $\mu$ under zero noise. We will clarify this contrast in the revised version.

Q5. High-Probability Bound Form
“The 'high probability bound' in Theorem 5.2 appears to be in the form 'with probability at least $1 - 1/K$', which seems a bit odd. Can you prove a high probability bound in the form 'with probability at least $1 - \delta$'?”

A5. Thank you for pointing this out. Extending the result to a general high-probability statement (i.e., "with probability at least $1 - \delta$") is indeed possible and follows standard concentration techniques.

In our current formulation, we set $\delta = 1/K$ to simplify the presentation and ensure that the expected regret is lower bounded by $\Omega(d \sqrt{\sum \sigma_k^2})$. Since most prior lower bounds in contextual bandits focus on expected regret, we adopted this fixed-probability form for clarity.

In the revision, we will update the theorem to explicitly state the bound holds with probability at least $1 - \delta$. Additionally, we will include a remark noting that by setting $\delta = 1/K$, the expected regret is lower bounded by $\Omega(d \sqrt{\sum \sigma_k^2})$, which matches the focus of prior work on expected regret in contextual bandits.

Thank you for your thoughtful feedback. Below we address your concerns point-by-point.

Q1. Lack of Application Context
“The paper does not adequately motivate the problem with practical applications...”

A1. Our work focuses on the theoretical characterization of the fundamental difficulty in stochastic contextual linear bandits. While our lower bound construction may not always correspond directly to real-world applications, it is essential to understand worst-case regret behavior, which forms the foundation for evaluating algorithmic performance in general settings. We will update the introduction to better clarify this theoretical motivation.

Q2. Clarity of Presentation
“Section 1.1 (‘Our Contributions’) is difficult to follow... and proof of Theorem 4.1 needs revision...”

A2. Thank you for this suggestion. We will revise Section 1.1 to enhance its readability and restructure the proof of Theorem 4.1 (especially lines 206–226). The hard instance construction, elaborated in Section 4.2, partitions the variance spectrum into logarithmic bins $[2^{i-1}/K, 2^i/K]$, with a modified lower-bound instance constructed for each bin. Details are provided in Appendix C.3. We will reorganize the section for clarity and highlight the intuition behind this construction.

Q3. Problematic Assumption on $\sum \sigma_k^2 \geq 1 + 384d^2$
“This requires the number of arms to exceed 1000...”

A3. This appears to be a misunderstanding. In our paper, $K$ denotes the number of rounds, not arms, since we are working in the linear bandit setting. Unlike the multi-armed bandit case, the complexity depends on the dimension $d$, not the number of actions. A condition like $\sum \sigma_k^2 \geq 1 + 384d^2$ (or equivalently $K \geq O(d^2)$ when $\sigma = 1$) is standard in linear bandits to overcome the trivial $O(K)$ regret upper bound. We will clarify this in the paper.

Q4. Concern Regarding $\Delta = 1/\sqrt{96K}$ Dependency
“This dependency weakens the claimed lower bounds...”

A4. We respectfully disagree. The construction of lower bounds in contextual linear bandits is inherently dependent on the number of rounds $K$. In particular, a regret of $\sqrt{K}$ typically arises from a sample complexity of $\Omega(K)$ required to distinguish between instances with a gap of $1/\sqrt{K}$, which results in total regret on the order of $K \times 1/\sqrt{K} = \sqrt{K}$. It is impossible to construct a single fixed instance that incurs $\Omega(\sqrt{K})$ regret uniformly for all $K$. Conversely, for a fixed instance with a fixed gap, the regret is often upper bounded by $\log K$ as $K$ becomes large. Therefore, allowing $\Delta$ to scale with $K$ is necessary to reflect the true minimax hardness of the learning problem. We will clarify this relationship between gap size, sample complexity, and regret in the revised paper.

Q5. Equivalence Between Fixed and Adaptive Variance Sequences
“If the lower bound depends only on the sum of variances, how different are the adaptive and fixed cases?”

A5. This is a very insightful question. Our work aims to characterize the worst-case regret under general variance sequences, and in doing so, we demonstrate that the upper bound from [1] remains nearly optimal even in the adaptive setting. While fixed variance budgets (e.g., $\Lambda = \sum \sigma_k^2$) provide a coarse characterization, they fail to capture structural differences.

For example, a variance sequence with $\sigma_k = 1$ for the first $\Lambda$ rounds and $\sigma_k = 0$ afterward yields the same budget as a sequence where the variance is spread uniformly. Yet, the difficulty faced by the algorithm is quite different. In the former case, a standard variance-independent lower bound of $\Omega(d\sqrt{\Lambda})$ applies, but the actual regret may be significantly lower if variance is concentrated later. Our framework accounts for these subtleties.

Q6. Temporal Ordering of Variance
“Why treat all variances equally? Should early-stage variance be weighted more?”

A6. Excellent point. Indeed, temporal ordering does affect learning in contextual linear bandits. However, contextual linear bandit problem involves adaptive decision sets at each round, which makes transferring knowledge from early stages (even with low variance) difficult. Nevertheless, we highlight in Corollary 5.7 that if the decision set is fixed, early low-variance observations can significantly reduce regret, even if the cumulative variance is large. We will make this distinction clearer in the revised manuscript.

Reference
[1] Zhou, D., Simchowitz, M., Gu, Q., & Dubey, A. (2023). Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency. COLT 2023.

Thank you for your follow-up. We appreciate your careful reading and the opportunity to clarify.

Firstly, if there exists a strictly positive gap $\Delta > 0$ independent of $K$, then the OFUL algorithm (Theorem 5 in [1]) already achieves a regret bound of $O(d^2 \log K / \Delta)$ for the linear contextual bandit problem, which grows only logarithmically with $K$. This implies that for any fixed $\Delta$, the regret becomes slog-\{K} once $K$ is large enough.

While it may be possible to construct a lower bound instance with constant $\Delta$ when the total variance satisfies $\sum \sigma_k^2 = O(\log K)$, this no longer holds for general variance sequences. In particular, when $\sigma_k^2 = 1$ for all $k$, prior variance-independent lower bounds show that obtaining a $\sqrt{K}$ regret lower bound requires setting the gap $\Delta = O(1/\sqrt{K})$.

Therefore, to reflect the worst-case difficulty under general variance sequences, we set $\Delta = 1/\sqrt{96K}$ in our construction. We will clarify this point in the revised version of the paper.

[1] Improved Algorithms for Linear Stochastic Bandits. NeurIPS 2011.

Thank you for your helpful suggestions. We address each of your questions below:

Q1. Use of K instead of T for denoting the number of rounds:
A1. We respectfully disagree with this point. While T is commonly used for the number of rounds in multi-armed bandits, our work focuses on the stochastic contextual linear bandit setting, which differs significantly. In linear bandit literature, K is frequently used to denote the number of rounds, and the problem complexity primarily depends on the dimension d, not the number of arms. We follow this convention to maintain consistency with related works in the linear bandit domain.

Q2. Clarification on Theorem 5.4:
A2. Theorem 5.4 demonstrates the necessity of the limitation imposed in Theorem 5.2—namely, that the adversary must select the variance sequence before observing the decision sets. If the adversary were allowed to observe the decision set beforehand (i.e., a stronger adversary), the lower bound construction could be circumvented. This highlights the tightness of our assumptions and clearly delineates the conditions under which the lower bound holds.

Q3. Clarification on Theorem 4.1 and the hard instance construction:
A3. The construction of hard instances is detailed in Section 4.2. Specifically, we partition the variance spectrum into logarithmic bins of the form $[2^{i-1}/K, 2^i/K]$. For each bin, we construct a hard-to-learn instance based on a modified version of the instance used in [1], adapting it to the corresponding variance level. This leads to a variance-dependent lower bound for each range. Detailed proofs and constructions can be found in Appendix C.3.

Q4. Line 224: role of $\sigma^2(i)$ and definition of $\sigma_k$:
A4. Thank you for pointing this out. The term $\sigma_k$ is defined in Equation (3.1) as the maximum variance for round $k$. In our lower bound construction, we identify the variance bin $[2^{i-1}/K, 2^i/K]$ that contains $\sigma_k$, and assign the corresponding contextual instance for that bin to round $k$. Thus, $\sigma^2(i)$ represents the variance used in the hard instance associated with bin $i$, and it provides a lower bound on the variance for all rounds falling within that bin. We will revise the manuscript to clarify this explanation.

Q5. Typo noted.
A5. Thank you for catching this. We will correct the typo in the final version.

Reference
[1] Zhou, D., Gu, Q., & Szepesvári, C. (2021). Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes. In Conference on Learning Theory (COLT).

Thank you for your positive feedback. We address your comments below:

Q1. Assumption of bounded errors in Equation (3.1):
A1. In our work, we aim to establish a theoretical lower bound to characterize the fundamental difficulty of the stochastic contextual linear bandit problem. To ensure consistency and avoid gaps in assumptions, we adopt the same bounded noise assumption as the upper bound analysis in [1] Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency (COLT 2023). Nevertheless, our results can be extended to sub-Gaussian noise distributions, including Gaussian noise, with appropriate modifications. We will clarify this point in the revised manuscript.

Q2. How variance is defined in our setting:
A2. In our setting, we study stochastic contextual linear bandits where the decision set can change adaptively across rounds. As such, assigning a fixed variance to each action (as is common in fixed-arm bandit settings) becomes challenging. Instead, we assume that in each round, the environment generates a variance level, and all actions in that round share the same variance. This round-wise variance captures the environment's uncertainty and simplifies analysis while preserving generality. We will revise the paper to better explain this assumption.

Q3. Relation to variance-dependent best-arm identification literature:
A3. Thank you for pointing out these related works. The BAI literature (e.g., Lu et al. 2021; Lalitha et al. 2023; Kato et al. 2024) typically assumes a fixed and known action set, where each arm has a constant variance across all rounds. This allows for variance-specific instance-dependent lower bounds. In contrast, our setting considers adaptive and potentially changing action sets, where variances can vary across rounds but are identical within a round. Thus, while the overall theme of variance-dependent analysis is shared, the assumptions and techniques differ. We will include a discussion of these connections and distinctions in the related work section.

Q4. Applicability of Ito et al. (2022):
A4. We carefully reviewed Ito et al. (2022), which focuses on variance-dependent regret bounds in adversarial multi-armed bandits. While they use a linear formulation via a probability distribution over fixed arms, their setting remains within the multi-armed bandit framework. In contrast, our setting involves contextual linear bandits, where each action corresponds to a context vector and reward is linear in that context. Therefore, while the techniques share high-level ideas, such as variance-aware exploration, they are not directly applicable to our contextual formulation. We will clarify this distinction and cite their work appropriately.