acceptodds
Under review as a conference paper at ICLR 2027

Minimax-Optimal Regret with Near-Minimal Policy Updates in Linear Contextual Bandits

19 views

Abstract

Can linear contextual bandits attain minimax-optimal regret up to constant factors uniformly across the small- and large-action regimes? How many policy updates are necessary to attain this statistical optimum? We introduce GATE for -dimensional linear contextual bandits with at most actions per round and oblivious adversarial contexts. GATE achieves regret, with policy updates on every sample path. To the best of our knowledge, this is the first constant-factor minimax guarantee (i.e., the sharpest regret bound) uniformly across the small- and large-action regimes, without additional logarithmic or iterated-logarithmic multipliers. At the same regret level, a feedback lower bound establishes policy-update minimality up to an iterated-logarithmic factor in . The central technical result is a sharp Gaussian information inequality with additive, rather than multiplicative, dependence on action-set complexity and design growth. Independent Gaussian testing and exploration, direct prediction-error control, and joint threshold calibration yield the stated regret and policy-update bounds without computing Gaussian width.

Primary area:
learning theory
Keywords:
linear contextual bandits, minimax optimality, limited adaptivity, batched feedback, information-theoretic lower bounds

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_rvQBOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The author proposes a new algorithm for the contextual bandit problem with linear function approximation. The proposed algorithm is based on the idea of using a layered approach to approximate the confidence set of the reward function and to update the policy efficiently. The proposed algorithm achieves a regret bound of O~(dTmin⁡{d,log⁡K})\tilde{O}(\sqrt{dT \min\{d, \log K\}}) that is optimal in both small and large action spaces. The author also demonstrates the performance of the proposed algorithm through extensive experiments on synthetic and real-world datasets, showing that it outperforms existing methods in terms of both regret and computational efficiency.

Critical strengths

The proposed algorithm achieves a regret bound of O~(dTmin⁡{d,log⁡K})\tilde{O}(\sqrt{dT \min\{d, \log K\}}), which is better than the previous best regret bound of O~(dT)\tilde{O}(d \sqrt{T}) in SquareCB.lin~(Foster et al., 2021). Also, the proposed algorithm needs fewer policy updates than SquareCB.lin, which is a significant improvement in terms of computational efficiency. The authors also provide extensive experiments on synthetic and real-world datasets, showing that the proposed algorithm outperforms existing methods in terms of both regret and computational efficiency.

Critical weaknesses
  1. This paper is not well written. The author does not provide enough motivation for the algorithm design before presenting the algorithm. Without a clear motivation, it is hard to understand the design choice since the presented algorithm is quite complicated and notation heavy. Also, the notations are not well presented. Algorithm 1 should not be that complicated and notation heavy since using layer-based confidence bound is a common technique in the literature (For example, the cited paper Ruan et al., 2021). The author should provide a clear motivation for the algorithm design and simplify the notations in Algorithm 1.

  2. For the theoretical analysis, the author claims the efficient policy updating is one of the main contributions of this paper. However, we find that in the literature, Falcon (Simchi, 2021) and OE2D (Qin, 2026) also provide efficient policy updating for the contextual bandit problem. Although the former one does not work in the linear reward function approximation setting, the latter one does. The author should provide a more detailed comparison with these two methods in terms of both theoretical guarantees and the number of policy updates.

  3. In the experiments, the author only uses 22-layer confidence sets. It is unclear how the performance of the proposed algorithm changes with different numbers of layers. The author should provide more experiments to show how the performance changes with different numbers of layers.

Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design, Yufei Ruan, Jiaqi Yang, Yuan Zhou, 2021.

Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability, David Simchi-Levi, Yunzong Xu, 2021.

Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits, Hao Qin, Chicheng Zhang, 2026.

Questions for authors

I have some questions about the paper and would like to ask the authors for clarification:

  1. In lines 200-201, what is the definition of the ``admissible instance ν\nu''? Is it an instance that satisfies Assumption 1?

  2. Since the authors mention efficient policy updating in this paper, it is quite related to a line of work that reduces the contextual bandit problem to offline regression (Falcon (Simchi, 2021), OE2D (Qin, 2026)). I would like to see how the proposed algorithm compares to these methods in terms of both theoretical guarantees and the number of policy updates. Can the authors provide some insights on this? Especially, in OE2D, it covers the case where the reward function is linear. How does the proposed algorithm compare to OE2D in this case? Is it possible to achieve a better regret bound than OE2D when the reward function is linear?

Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability, David Simchi-Levi, Yunzong Xu, 2021.

Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits, Hao Qin, Chicheng Zhang, 2026.

9 comments

We thank the reviewer for recognizing the regret improvement and identifying the presentation, related-work comparison, and depth study that would strengthen the paper. The submitted paper already establishes immediate-feedback sequential minimax regret up to constants together with near-minimal policy updates for arbitrary oblivious context sequences, under the noise and norm conditions in Assumption 1 and the comparison ranges of Proposition 1 and Theorem 2. The revision clarifies these results without changing the original algorithms, assumptions, or main theorem statements. The red explanatory edits make the motivation, definitions, and proof mechanisms explicit. The added literature calculations, larger-depth justification from the existing analysis, and requested L=2,3,4L=2,3,4 experiments supplement the original results; the originally reported experiments and their results are retained.



Algorithm motivation and presentation

GATE is designed to postpone policy updates without losing the sharp sequential regret bound. A fixed policy must keep choosing actions while new observations accumulate. Its exploration must remain inexpensive and informative even though its estimates are not refreshed every round. Revised Sections 4.1 and 5.1–5.3 explain the design choices in this order.

Why elimination and layers? An informative action can still have high regret. Earlier eliminations first restrict the actions available to a later layer, bounding its exploration loss before the action is chosen. Layering also separates reward information: a later layer tests and selects exploration candidates before reading its own reward statistics, using earlier-layer estimates for ranking.

Why Gaussian selection and testing? An action chosen under the frozen design need not be as informative under the accumulated design. Lemma 1 links these two designs with an additive coefficient, permitting longer batches without multiplying the action-complexity cost by design growth. The test uses the Gaussian maximum governing the prediction-error analysis and can be sampled from features and the frozen design alone. GATE controls error beyond that sampled radius rather than computing Gaussian width or requiring every interval to be correct.

Why separate draws, selective refreshes, and joint thresholds? Reusing the test draw would condition the exploration draw on the test outcome; an independent selection draw preserves the required Gaussian law. A layer's own trigger prevents requests elsewhere from changing its snapshot training set in a way influenced by its rewards. Jointly chosen thresholds and error budgets then balance exploration and final-choice losses without an additional confidence or full-depth factor. These choices make the sharp regret and limited updates compatible.

Section 4.2 now places the definition of JiJ_i, the accumulated and frozen states, the parameter and estimate definitions, and the individual Lines 3–7 operation–purpose mapping before the complete Algorithm 1. In particular, VsV_s accumulates assigned features immediately, whereas bsb_s contains received feature–reward products. Action selection reads fixed snapshots (Vˉs,bˉs)(\bar V_s,\bar b_s), not the evolving accumulated states. The algorithm is read in the following order:

Algorithm 1Operation and purpose
Before At\mathcal A_t: Lines 3–7Check accumulated design growth; receive pending rewards; refresh only requesting layers and the pool. Concurrent requests count once; nonrequesting layers retain their snapshots.
First layer: Lines 8–16Form survivors BB; check early terminal selection before exploring with a wide proposal or its certified fallback. If every survivor is narrow, pass BB onward.
Later layers: Lines 17–22Test before reading bˉs\bar b_s. Exploration uses an independent draw and earlier-layer estimates, then assigns the observation and stops. Otherwise read bˉs\bar b_s, eliminate, and continue.
Final ranking and recording: Lines 12, 23–25The pool ranks only terminal candidates. Every selected observation enters the pool and at most one layer. Terminal feedback deploys no new policy.

Section D establishes the conditional laws described above, and Section 4.2 explains the pool-only-query case. These are changes to the explanation, not to the policy: the original algorithmic instructions, certificates, fallbacks, and algorithm-line numbers are unchanged.

The contribution is the resulting simultaneous guarantee, beyond layering itself. Ruan et al. [1] provide the earlier layered construction with native O(dlog⁡dlog⁡T)O(d\log d\log T) switches and additional logarithmic regret factors. GATE combines additive information control, direct prediction-error control, and joint calibration to obtain constant-factor sequential minimax regret and approach the feedback lower bound at that regret target (Table 1 and Section J). Corollary 2 establishes matching worst-case dependence for Lemma 1's Gaussian-max matrix inequality.



FALCON and OE2D: explicit regret and policy-update comparisons

The decisive distinction is the context class: GATE handles arbitrary oblivious sequences, whereas the cited FALCON+ and OE2D guarantees use i.i.d. contexts. Simchi-Levi and Xu [2] (Example 2, pp. 18–19) explicitly state O(KT(d+log⁡T))O(\sqrt{KT(d+\log T)}) regret for FALCON+ with a linear least-squares regression oracle. We use that published linear example as the benchmark, rather than introducing a separate regression model.

For OE2D (Qin and Zhang [3]), the table separately evaluates its oracle-dependent analysis at the same linear-regression accuracy scale: population squared-prediction error O((d+log⁡T)/n)O((d+\log T)/n) on nn samples, with predictions in its required function class. For T≥16T\ge16, per-call confidence levels allocate total failure probability T−2T^{-2}. The FALCON+ doubling entry is the published Example 2 rate; the remaining entries are schedule-specific upper-bound calculations under this oracle condition. Appendix O.1 retains the source reward assumptions and expands FALCON+'s Theorem 2 and OE2D's Lemmas 7 and 10, including all displayed epoch factors.

Method and epoch scheduleExpected-regret upper boundContextsRegression calls / policy updates
FALCON+ [2], doublingO(KT(d+log⁡T))O(\sqrt{KT(d+\log T)})i.i.d.O(log⁡T)O(\log T) regression calls
FALCON+ [2], known-horizon fewer-epoch scheduleO(KT(d+log⁡T)log⁡log⁡T)O(\sqrt{KT(d+\log T)}\log\log T)i.i.d.O(log⁡log⁡T)O(\log\log T) regression calls
OE2D [3], linear, doublingO(dT(d+log⁡T)log⁡T)O(\sqrt{dT(d+\log T)}\log T)i.i.d.O(log⁡T)O(\log T) regression calls
OE2D [3], linear, known-horizon fewer-epoch scheduleO(dT(d+log⁡T)(log⁡log⁡T)2)O(\sqrt{dT(d+\log T)}(\log\log T)^2)i.i.d.O(log⁡log⁡T)O(\log\log T) regression calls
OE2D [3], finite-action, doublingO(KT(d+log⁡T)log⁡T)O(\sqrt{KT(d+\log T)}\log T)i.i.d.O(log⁡T)O(\log T) regression calls
OE2D [3], finite-action, known-horizon fewer-epoch scheduleO(KT(d+log⁡T)(log⁡log⁡T)2)O(\sqrt{KT(d+\log T)}(\log\log T)^2)i.i.d.O(log⁡log⁡T)O(\log\log T) regression calls
GATEO(dTlog⁡(1+T/d)min⁡d,log⁡K)O(\sqrt{dT\log(1+T/d)\min\\{d,\log K\\}})Arbitrary context sequence fixed before interaction, independently of learner randomness and noisePathwise policy updates (2), with QT=STQ_T=S_T

The i.i.d. results do not subsume GATE's guarantee for arbitrary oblivious contexts. Simchi-Levi and Xu [2] explicitly explain immediately after Example 2 (p. 19) that a stochastic-context upper bound can lie below an oblivious-adversarial-context lower bound because the context models differ. With reward assumptions aligned, GATE's sequence-wise upper bound also covers i.i.d. contexts by averaging over the sampled sequence; Proposition 1 and Theorem 2 characterize the larger oblivious class. OE2D's distribution-shift extension still requires uniformly bounded two-sided density ratios to a common distribution [3] (Appendix D.3), and thus does not cover arbitrary oblivious sequences.

The few-call guarantees rely on a context restriction that GATE does not require. The cited FALCON+ [2] and OE2D [3] guarantees assume independent draws from the same context distribution across epochs. Conditional on the history at an epoch's start, its fixed action-selection kernel yields i.i.d. selected-action samples under the cited stochastic model. The common context law supports the exploration analysis that converts offline prediction error into subsequent regret. FALCON+ [2] explicitly uses only the preceding epoch's data to satisfy this oracle requirement (Section 3.1 and Algorithm 2). These i.i.d. guarantees do not cover arbitrary precommitted changes in context geometry. GATE instead controls information under the realized accumulated designs and establishes its simultaneous regret and policy-update bounds for every oblivious context sequence satisfying Assumption 1, without assuming a common context distribution. Thus, few regression calls under i.i.d. sampling do not establish the same regret–update guarantee on GATE's context class.

Reviewer_kv9aOpenReview ↗
Rating
3(+2)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces GATE, a layered algorithm for linear contextual bandits with delayed or batched feedback. GATE combines ridge estimates, Gaussian testing and exploration, thresholded elimination, and determinant-based update triggers. Under oblivious contexts and independent 1-sub-Gaussian noise, it achieves regret that matches the sequential minimax rate up to constants in the stated horizon regime. It also uses only a small number of policy updates, and the paper gives a feedback lower bound showing that this is close to necessary.

Critical strengths

The main strength is the combination of sharp regret and limited policy updates across both small-action and large-action regimes. The central Gaussian information inequality has additive dependence on action-set complexity and design growth, avoiding the multiplicative losses that commonly arise when policies use stale estimates. The independent testing/exploration construction and direct prediction-error analysis are technically well motivated, and the horizon-free version retains data rather than restarting at doubling epochs. The regret lower bound is substantial and self-contained, while the update upper and lower bounds establish meaningful near-optimality rather than only an algorithmic improvement over existing methods.

The authors wrote "We used AI tools solely to polish author-written text. The authors reviewed all edits and take full responsibility for the paper.". This is a strength in this age. That said, please use a bit more AI, to avoid things such as misuse of the term "iterated logarithm"...

Critical weaknesses
  1. I didn't find any iterated-log bounds. It seems that the authors don't really know what a log-star (iterated log) is. It is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1. This is very different from double log (log log) or triple log (log log log), etc. This can lead to a desk reject if you submit it to a journal. This red flag must be cleared before the paper could move to any future stages.

  2. Another weakness is overstatement that scatters here and there. For example, "A sharp additive information inequality and direct prediction-error control" is a bit too broad and sounds like a ground-breaking information inequality that deserves a reputable award... I'd recommend the authors to be more specific here. I'd suggest the authors to refrain from stretching too much the claims.

Questions for authors

N/A.

5 comments

We thank the reviewer for recognizing the simultaneous regret and policy-update guarantees and the substantive lower bounds, and for the suggestions on terminology and precision.

GATE attains constant-factor sequential minimax regret with near-minimal policy updates at the same regret level, under Assumption 1 and the comparison ranges of Proposition 1 and Theorem 2.

The revisions addressing your terminology and precision concerns are expository: the original algorithm, assumptions, regret and policy-update bounds, and comparison ranges are unchanged. The changes make the existing statements and proof arguments easier to verify.


Explicit logarithmic factors

Eq. (2) specifies the fixed composition of logarithms already displayed in the original abstract. Theorem 1 gives

$ S_T= O\left( d\log(1+T/d)\cdot \frac{\log(2+\log(2+\min\{d,\log K\}))} {\log(2+\min\{d,\log K\})} \right) \qquad\text{pathwise}. $

Sections G.8 and H prove this bound.

Published usage includes fixed double- and triple-logarithmic quantities, not only a count of logarithm applications. In the same linear-bandit literature, Li et al. [1], IEEE Transactions on Information Theory, 70(1):372–388 (January 2024), use “iterated logarithmic factors” in the abstract on p. 372; Theorem 1 and Remark 3 on p. 373 specify a polynomial double-logarithmic multiplier, written in our notation as poly⁡(log⁡log⁡(KT))\operatorname{poly}(\log\log(KT)).

This usage extends beyond a single paper or research group. The following fifteen distinct studies explicitly use the terminology for fixed logarithmic compositions. The tables identify the quantity being named and its location; they document terminology rather than compare guarantees across different models. “Author manuscript” identifies the version used for a page reference; otherwise the reference is to the published paper.

Direct precedents in bandits and sequential decision-making

Published workWording and the quantity it denotesLocation
Li et al. [1], IEEE Transactions on Information Theory (2024)“iterated logarithmic factors”: a polynomial double-logarithmic regret multiplier.Abstract, p. 372; Theorem 1 and Remark 3, p. 373.
Li et al. [2], AISTATS (2021)“iterated logarithmic terms”: a polynomial double-logarithmic correction to the linear-bandit regret rate.Abstract and Theorem 1, PDF pp. 1–2.
Wang et al. [3], NeurIPS (2018)“iterated logarithmic terms”: the square root of a double logarithm in the regret comparison.Abstract, PDF p. 1.
Xu et al. [4], AISTATS (2023)“iterated logarithmic factors”: a double-logarithmic horizon correction in dynamic-pricing regret, with other problem and probability parameters fixed.Abstract; Section 5.1, Theorem 6 and Remark 7, PDF p. 8.
Wang et al. [5], NeurIPS (2008)“iterated logarithmic exploration sequence”: a double-logarithmic exploration sequence, rather than a regret multiplier.Section 2.2, Eq. (11), PDF p. 6.

The earlier COLT 2019 publication of Li et al. [6] also uses the terminology in its abstract (PMLR 99:2173–2174). It is the same study as the IEEE journal article [1], not an additional independent example.

Direct precedents in statistical learning, testing, and estimation

Published workWording and the quantity it denotesLocation
Chugg et al. [7], JMLR (2023)“iterated logarithm term”: explicitly identified as a double logarithm.Section 1.2, p. 5; see also Section 5.1, Eq. (29).
Liu et al. [8], The Annals of Statistics (2021)“triple iterated logarithmic rate”: a fixed triple logarithm in the stated sparsity range; Section 2.1 also discusses a double-logarithmic factor.Section 2.2, p. 1085; Section 2.1, Eq. (3).
Li and Yuan [9], JMLR (2024)“polynomial of iterated logarithmic factor”: a power of a double logarithm in the adaptive testing rate.Section 5.1, discussion following Theorem 9, p. 16.
Schrab et al. [10], JMLR (2023)“iterated logarithmic term”: a double-logarithmic adaptation cost in two-sample testing.Corollary 10 and the following discussion, p. 22.
Schrab et al. [11], NeurIPS (2022)“iterated logarithmic factor”: a double-logarithmic correction in the squared-separation bound for the stated Sobolev classes.Theorem 3.5(ii) and the following discussion, PDF p. 7.
Mun et al. [12], JMLR (2025)“iterated logarithmic factors”: powers of double logarithms in the adaptive testing comparison, in the low-privacy regime.Theorem 12, p. 19, and the discussion on p. 20.
Gao et al. [13], The Annals of Statistics (2020)“iterated logarithmic dependence”: a double logarithm in the risk for isotonic piecewise-constant estimation.Introduction, p. 630; corresponding author manuscript, p. 2.
Li et al. [14], IEEE Transactions on Information Theory (2026)“iterated logarithmic factor”: the square root of a double logarithm in the stated change-point upper/lower comparison.Author manuscript, p. 7, comparison following Theorem 3 and Eq. (13); journal publication 72(1):571–609.
Wang and Yuan [15], Journal of the American Statistical Association (2019)“iterated logarithmic factor”: a square-root double-logarithmic gap in the graph-testing bounds.Section 4, discussion following Eqs. (14)–(15); author manuscript, p. 14.
Vershynin [16], Journal of Theoretical Probability (2012)“iterated logarithmic factor”: a squared double-logarithmic multiplier in the covariance-estimation bound.Author manuscript, Theorem 1.2 and the preceding discussion, p. 5.

The direct precedents show that the terminology is not reserved for a logarithm-application count. Eq. (2) specifies exactly which fixed composition our paper claims.

Our claim is the explicit expression above. To avoid any possible ambiguity, we have nevertheless replaced the terminology with the corresponding explicit logarithmic expressions throughout the revised manuscript. The formula in Eq. (2), its assumptions, and its parameter dependence are unchanged.

GATE preserves the immediate-feedback minimax regret up to constants while approaching the feedback required to attain it. Under Theorem 2's conditions, every general batched-feedback learner meeting the same fixed regret target requires Ω(dlog⁡T/log⁡(2+min⁡d,log⁡K))\Omega(d\log T/\log(2+\min\\{d,\log K\\})) worst-case expected feedback queries (Eq. (4)). This necessity holds even when actions can depend on time and context/action history between queries, a class broader than GATE's fixed within-batch policies (Section 3.1).

GATE attains that target with a pathwise query bound within an O(log⁡(2+log⁡(2+min⁡d,log⁡K)))\mathcal{O}(\log(2+\log(2+\min\\{d,\log K\\}))) factor of this lower bound. Its queries and policy updates coincide, QT=STQ_T=S_T, so Eq. (2) also bounds its expected queries. Section J uses the same regret-target constant for both bounds, chosen large enough for Theorem 1. The remaining factor depends only on dd and KK, with no additional horizon-dependent multiplier.



Sharpness of the Gaussian-max information inequality

The original sharpness claim is a proved property: Lemma 1 and Corollary 2 establish matching worst-case dependence on action-set complexity and design growth up to universal constants. To make this scope explicit, the contribution is now titled “Gaussian-max information inequality and direct prediction-error control” and directly cites both results. To prevent any broader interpretation, we also removed the redundant “sharpest” wording from the abstract and replaced “sharpest possible” in the first contribution with “minimax-optimal worst-case expected regret up to constant factors.” These wording changes leave both the sharpness result in Lemma 1 and Corollary 2 and the minimax statement and comparison range in Proposition 1 unchanged.

For Lemma 1's Gaussian-max selector, V⪰Vˉ≻0V\succeq\bar V\succ0, and ∣A∣=k|A|=k, Eq. (8) relates uncertainty under the frozen design Vˉ\bar V to expected information under the accumulated design VV:

$ W(A,\bar V)^2 \le \left[ \min\{d,2\log(2k)\} +\frac{\det V}{\det\bar V}-1 \right] \mathbb E_g\|x_{a(g)}\|_{V^{-1}}^2. $

Here W(A,Vˉ)W(A,\bar V) is the analysis-only Gaussian width; squared leverage under VV determines log-determinant growth. Eq. (8) lower-bounds the expected squared leverage by the squared frozen width divided by the displayed additive coefficient.

Corollary 2 matches this dependence under the same constraints. For d≥1d\ge1, k≥2k\ge2, and D≥1D\ge1, the coefficient in Lemma 1 is at most 2[min⁡d,log⁡(2k)+D−1]2[\min\\{d,\log(2k)\\}+D-1] whenever ∣A∣≤k|A|\le k and det⁡V/det⁡Vˉ≤D\det V/\det\bar V\le D. Under these constraints, Corollary 2 constructs at most kk unit-norm features, at least one nonzero, and V⪰Vˉ≻0V\succeq\bar V\succ0 for which Eq. (28) holds:

$ \frac{W(A,\bar V)^2} {\mathbb E_g\|x_{a(g)}\|_{V^{-1}}^2} \ge \frac{\min\{d,\log(2k)\}+D-1}{4\pi}. $

Lemma 1 and Corollary 2, both in the original submission, establish worst-case sharpness up to universal constants for this matrix inequality (Section E.4). Corollary 1 carries its additive dependence to Algorithm 1's actual selector with a factor-two loss (Section E.3).

The additive dependence permits longer batches. Direct norm comparison multiplies action complexity by the determinant ratio. At a ratio of order min⁡d,log⁡K\min\\{d,\log K\\}, Lemma 1 keeps the coefficient of that same order, permitting the common log⁡(2+min⁡d,log⁡K)\log(2+\min\\{d,\log K\\}) part of the log-determinant update thresholds. Section 5.1 explains this calculation and how the same selector yields both action regimes.

Elimination controls regret per exploration; the inequality controls informative exploration counts. Layer-specific updates and independent testing and exploration preserve the required conditional laws. Direct prediction-error control and joint threshold calibration avoid additional confidence and full-depth factors (Sections 4.1 and 5.2–5.3).


Expository revisions addressing these two concerns (marked in red)

LocationExpository revisionOriginal result or argument retained
Abstract and introductionExplicit logarithmic expressions; concise abstract range references; redundant “sharpest” wording removed from the abstract.Theorem 1's bounds and the conditions of Proposition 1 and Theorem 2.
ContributionsGaussian-max heading with direct Lemma 1 and Corollary 2 references; “sharpest possible” replaced by the precise minimax statement in the first contribution.Proposition 1's minimax guarantee; Lemma 1 and Corollary 2's sharpness result.
Section 5.1Frozen uncertainty, accumulated information, additive decomposition, both action regimes, and longer batches.Lemma 1's inequality and Corollaries 1–2.
Sections 4.1 and 5.2–5.3Roles of elimination, independent tests, prediction-error control, and joint threshold calibration.Algorithm 1 and the existing prediction-error and threshold-calibration arguments.

The cited sequential guarantees leave a statistical gap before policy updates are restricted. Li et al. [1] retain the polynomial double-logarithmic regret multiplier. The same-noise-model SquareCB.Lin guarantee in Section K (Foster et al. [17]) matches the large-action rate, but its min⁡d,K−1\min\\{d,K-1\\} dependence does not recover the optimal log⁡K\log K dependence uniformly throughout the full small-action regime.

GATE matches the immediate-feedback minimax regret up to constants (Proposition 1), while Theorem 1's pathwise update bound approaches Theorem 2's feedback lower bound for a class broader than GATE's fixed within-batch policies—at the same regret target and in the stated comparison ranges.

We would appreciate pointers to any remaining sentence whose scope is unclear. We respectfully ask you to reconsider the recommendation in light of these direct answers and the clearer exposition of the original simultaneous guarantees and substantive lower bounds.


Reviewer_afUcOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the linear contextual bandit problem and claims to obtain the first minimax optimal regret up to constant factors for both the small- and large- action regime (the accepted boundary is usually K≍edK \asymp e^d.) while ensuring optimal number of policy updates. The algorithm is built on rarely-switching algorithms introduced in [1,2] and can achieve regret O~(dTmin⁡(d,log⁡K))\tilde{\mathcal O}(\sqrt{dT}\min(d,\log K)) regret with O(dlog⁡Tlog⁡log⁡min⁡(d,log⁡K))\mathcal O(d\log T \log\log \min(d,\log K)) policy updates. They also obtain a matching lower bound up to iterated log factors. At the heart of the new algorithm is a Gaussian information inequality which reduces the multiplicative dependence on complexity terms to an additive dependence.

Critical strengths

(i) The first-known bounds that have sharp regret characterizations in both the small- and large-action regimes without additional iterated log factors while maintaining the optimal number of switches.

(ii) A matching lower bound upto min⁡{log⁡log⁡d,log⁡log⁡log⁡K}\min\{\log\log d , \log\log\log K\} factors.

(iii) A new Gaussian information inequality that may be of independent interest.

(iv) They also present a horizon-free algorithm that achieves the same regret as the known-horizon algorithm.

Critical weaknesses

The biggest weakness for me is the technical presentation. While the content covers all technicalities, it also consists of incredible amounts of jargon, and in the process, it is difficult to understand what drives the optimality of the algorithm in both small- and large-action regimes that was missing from prior works. Particularly, the new Gaussian Information inequality may be of independent interest, however, the details around it seem to be incredibly difficult to parse. Also, it would help if the algorithmic description would mention why a particular step is being used while explaining the step. A few examples are below:

(i) Lines 3-7 in the GATE algorithm consists of several steps, and it would have helped if the algorithmic description mapped each step to a more layman explanation rather than stringing together a paragraph of sentences and leaving the mapping between the explanation and the steps in the algorithm to the reader.

(ii) In line 6 of the algorithm, the algorithm updates bs←bs+∑i∈Q:Ji=sxi,airib_s \leftarrow b_s + \sum_{i \in Q : J_i = s} x_{i,a_i}r_i, without having mentioned what JiJ_i refers to in any of the previous lines.

The questions revolve around the larger picture of the algorithm. More formally, GATE uses a familiar elimination technique seen previously in several algorithms such as [2,3], while, it also has a layered structure similar to SupLinUCB presented in [3]. Is it a combination of both ideas that helps or is it solely because of the new information inequality established.

Moreover, I would also like to understand the motivation behind some of the new ideas. For example, a new Gaussian information inequality has been established. What encouraged the use of Gaussian tests in the algorithm? Does this only work in the linear setting because of the presence of sub-gaussian noise? What if the rewards follow an exponential family (such as in [3]), can such an information inequality and/or gaussian tests be used for that purpose as well?

Another paper that may be relevant to mention is [5], which also obtains optimal regret bounds in both small- and large-action regimes, under a static schedule.

This paper is novel and puts forth some interesting ideas, however, for the ideas to be of value to the community, the paper needs to significantly improve the exposition and detail the motivation and use of the novel ideas with a more precise and accessible terminology.

[1] Abbasi-Yadkori et al. Improved Algorithms for Linear Stochastic Bandits. NeurIPS 2011.

[2] Ruan et al. Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design. STOC 2021.

[3] Sawarni et al. Generalized Linear Bandits with Limited Adaptivity. NeurIPS 2024.

[4] Peter Auer. Using confidence bounds for exploitation- exploration trade-offs. JMLR 2002.

[5] Yu and Oh. Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates. ICML 2026.

Questions for authors

Please see weaknesses.

7 comments

We thank the reviewer for the careful reading and constructive suggestions. The revisions addressing your presentation concerns clarify the original algorithm and analysis; the algorithmic instructions, assumptions, and original theorem statements remain unchanged. We have revised Sections 2, 4.1–4.2, and 5.1–5.3 to make the motivation, key calculations, and purpose of each step explicit; these explanatory revisions are marked in red. Below, we answer the four conceptual questions and provide the requested algorithm-to-purpose mapping under “Lines 3–7 and the definition of JiJ_i”.

GATE attains the fully sequential minimax regret up to constants across both action regimes, and attains that same regret with near-minimal policy updates. The regret comparison holds for fixed δ>0\delta>0, d,K≥2d,K\ge2, and T≥d2+δT\ge d^{2+\delta} (Proposition 1). Under Assumption 1, both known-horizon and horizon-free GATE satisfy Theorem 1’s bounds:

$ \mathbb E R_T\le\|R_T\|_{L^2} =O\left(\sqrt{dT\log(1+T/d)\min\{d,\log K\}}\right), $

$ S_T=O\left( d\log(1+T/d)\cdot \frac{\log(2+\log(2+\min\{d,\log K\}))} {\log(2+\min\{d,\log K\})} \right) \qquad\text{pathwise}. $

Under Theorem 2’s conditions and for sufficiently large dd and KK, the policy-update bound is within an O(min⁡log⁡log⁡d,log⁡log⁡log⁡K)O\left(\min\\{\log\log d,\log\log\log K\\}\right) factor of the feedback lower bound, with no additional horizon-dependent multiplier.


What drives optimality in both regimes, beyond the prior guarantees?

Two different issues must be resolved: obtaining the sharp min⁡d,log⁡K\min\\{d,\log K\\} dependence, and retaining it without additional confidence or layer factors. GATE resolves both while allowing infrequent updates.

The prior guarantees compared in Sections 2 and K leave a specific gap. Li et al. [1] obtain O(dTlog⁡Tlog⁡K)O(\sqrt{dT\log T\log K}) regret with a residual poly⁡(log⁡log⁡(KT))\operatorname{poly}(\log\log(KT)) multiplier. SquareCB.Lin (Foster et al. [2]) already matches the large-action expected-regret order, but its min⁡d,K−1\min\\{d,K-1\\} bound does not recover the sharp log⁡K\log K dependence throughout the entire small-action regime. GATE closes the remaining gap by attaining uniform constant-factor minimax regret across both action regimes together with the near-minimal policy-update bound.

Both regimes follow from bounding the same quantity in two ways: by the number of actions and by the dimension. Revised Section 5.1 expands the presentation of the two bounds already established in the original Section E.1 proof. Use Section E.1's signed selection label JJ: the selected action together with its projection sign. For each outcome, E[g∣J]\mathbb E[g\mid J] averages the Gaussian vectors that produce it. Write Σ=Cov⁡(E[g∣J])\Sigma=\operatorname{Cov}(\mathbb E[g\mid J]), as in Section E.1. Here JJ is the signed selection outcome; the algorithm's layer-assignment labels are JiJ_i.

For g∼N(0,Id)g\sim\mathcal N(0,I_d) and k≤Kk\le K incoming actions, the Gaussian entropy bound and total covariance give, respectively,

$ \begin{aligned} \operatorname{tr}\Sigma =\mathbb E\|\mathbb E[g\mid J]\|_2^2 \le 2\log(2k),\qquad 0\preceq\Sigma&\preceq I_d \quad\Longrightarrow\quad \operatorname{tr}\Sigma\le d. \end{aligned} $

Thus tr⁡Σ≤min⁡d,2log⁡(2k)\operatorname{tr}\Sigma\le\min\\{d,2\log(2k)\\}. Both bounds control the same quantity for the same selector. When log⁡K≤d\log K\le d this is O(log⁡K)O(\log K); when log⁡K>d\log K>d it is O(d)O(d), yielding the uniform O(min⁡d,log⁡K)O(\min\\{d,\log K\\}) dependence.

Preserving that factor is the second, essential step. Direct prediction-excess control avoids requiring every later-layer confidence interval to be correct. Joint threshold calibration then bounds the first-layer confidence contribution by a constant and avoids multiplying the regret by the full depth. Section 5.3 obtains

$ \Phi^2=O\left(dH\log(1+H/d)\min\{d,\log K\}\right). $

Here H=TH=T in the known-horizon analysis and Φ\Phi is the minimum of Equation (10)’s deterministic objective. Sections F and G turn the displayed bound on Φ2\Phi^2 into the L2L^2 regret bound in Theorem 1, including prediction excess and Gaussian-triggered exploration. The two cases are:

RegimeResulting regret order
log⁡K≤d\log K\le dO(dTlog⁡(1+T/d)log⁡K)O\left(\sqrt{dT\log(1+T/d)\log K}\right)
log⁡K>d\log K>dO(dTlog⁡(1+T/d))O\left(d\sqrt{T\log(1+T/d)}\right)

The minimum explains the two regimes; the prediction-error analysis and joint calibration explain why no additional regret multiplier remains. The additive treatment of design growth, explained next, makes this sharp statistical rate compatible with longer batches.



What does the Gaussian information inequality actually say?

An action chosen using the frozen design must still provide enough expected information under the accumulated design. Lemma 1 quantifies this connection without multiplying the action-complexity cost by the design-growth cost.

The two matrices have different roles. Vˉ\bar V is the fixed design used for selection; V⪰VˉV\succeq\bar V also includes features accumulated since that snapshot. The width W(A,Vˉ)W(A,\bar V) measures the Gaussian uncertainty of the incoming actions under the frozen design. It is an analysis quantity; GATE does not compute it. In contrast, ∣x∣V−12\\|x\\|_{V^{-1}}^2 measures the information in adding xx to the accumulated design: it determines the log-determinant increment (Section A.3). Using the frozen design to choose an action does not automatically guarantee that this action remains informative under VV.

For V⪰Vˉ≻0V\succeq\bar V\succ0, ∣A∣=k|A|=k, and the Gaussian-max selector of Lemma 1, Equation (8) gives

$ W(A,\bar V)^2 \le \left[ \min\{d,2\log(2k)\} +\frac{\det V}{\det\bar V}-1 \right] \mathbb E_g\|x_{a(g)}\|_{V^{-1}}^2. $

Read this as a lower bound on expected information whenever the frozen width is large. If V=VˉV=\bar V, the growth term is zero. Delaying a refresh adds the determinant-ratio term; it does not multiply the original complexity term. A direct comparison of the two norms would multiply these costs. When the determinant ratio reaches the action-complexity scale, that comparison has a quadratic coefficient, whereas Lemma 1 has a linear one. Consequently, updates can wait for the common log⁡(2+min⁡d,log⁡K)\log(2+\min\\{d,\log K\\}) part of the log-determinant threshold rather than a constant amount. This directly connects Lemma 1 to the denominator of the policy-update bound.

Why is addition possible? The proof bounds the frozen-design contribution and the additional growth separately. Revised Section 5.1 now spells out the decomposition already present in the original Section E.1 proof. With Σ\Sigma as above, set M=Vˉ−1/2VVˉ−1/2⪰IdM=\bar V^{-1/2}V\bar V^{-1/2}\succeq I_d, as in Section E.1. Metric Cauchy–Schwarz and the two bounds on Σ\Sigma give

$ \begin{aligned} W(A,\bar V)^2 &\le \mathbb E_g\|x_{a(g)}\|_{V^{-1}}^2\operatorname{tr}(M\Sigma),\\ \operatorname{tr}(M\Sigma) &=\underset{\text{frozen design}}{ \underbrace{\operatorname{tr}\Sigma} } +\underset{\text{additional growth}}{ \underbrace{\operatorname{tr}((M-I_d)\Sigma)} } \\ &\le \min\{d,2\log(2k)\}+\operatorname{tr}(M-I_d)\\ &\le \min\{d,2\log(2k)\}+\frac{\det V}{\det\bar V}-1. \end{aligned} $

The trace bound controls the frozen term. The matrix bound Σ⪯Id\Sigma\preceq I_d controls the growth term because M−Id⪰0M-I_d\succeq0, so growth pays no second action-complexity factor. Finally, tr⁡(M−Id)≤det⁡M−1\operatorname{tr}(M-I_d)\le\det M-1 and det⁡M=det⁡V/det⁡Vˉ\det M=\det V/\det\bar V. Adding these separately bounded contributions gives exactly the additive coefficient in Lemma 1.

Corollary 2 establishes the correct worst-case order of the additive coefficient in both action-set complexity and design growth. Corollary 1 extends the inequality to Algorithm 1’s approximate selector with a factor-two loss. The exploration-count analysis then uses expected information over the selection draw (Lemma 11).



Is the result due to elimination and layering, or to the new inequality?

In GATE, elimination controls regret per exploration, the information inequality controls informative exploration counts, and layer-specific data and updates make the prediction-error bounds applicable. Joint threshold calibration combines these controls without additional confidence or full-depth factors. Revised Section 4.1 makes these existing roles explicit, and Section 5.3 displays the exploration-cost accounting from the original Section G analysis.

Consider a round that reaches a later layer ss. Every preceding layer has eliminated without exploring. Therefore, every incoming action already has regret at most 4εs−14\varepsilon_{s-1} plus the preceding prediction-excess terms (Equation (9)). Elimination makes exploration among these actions inexpensive before the Gaussian selector chooses one.

Let NsinfN_s^{\mathrm{inf}} count the informative assignments of Section G.5. The information inequality and total log-determinant bound give Equation (47); multiplying by the nominal per-exploration charge yields

$ \begin{aligned} \mathbb E N_s^{\mathrm{inf}} \le\frac{a_s}{4\varepsilon_s^2}, \qquad 4\varepsilon_{s-1}\mathbb E N_s^{\mathrm{inf}} \le a_s\frac{\varepsilon_{s-1}}{\varepsilon_s^2}. \end{aligned} $

Applying Lemma 11 in Section G.5 gives Equation (48), ∣Nsinf∣L2=O(as/εs2)\\|N_s^{\mathrm{inf}}\\|_{L^2}=O(a_s/\varepsilon_s^2). These are the later-layer terms in Equation (10)'s deterministic objective:

$ \Phi= \min_{\varepsilon_0,\ldots,\varepsilon_{L-1}>0} \left\{ \underset{\text{layer-0 exploration}}{ \underbrace{\frac{a_0}{\varepsilon_0}} } + \underset{\text{later-layer exploration}}{ \underbrace{\sum_{s=1}^{L-1}a_s\frac{\varepsilon_{s-1}}{\varepsilon_s^2}} } + \underset{\text{final choices}}{ \underbrace{4H\varepsilon_{L-1}} } \right\}. $

Here the minimum is over positive thresholds before the cap in Equation (41), and the asa_s are the deterministic coefficients of Section G.2. Thus εs\varepsilon_s controls exploration at layer ss and the next layer's nominal regret, so the thresholds are optimized jointly. Gaussian-triggered assignments outside the informative case and prediction excess are controlled separately.

Layering also has a statistical purpose: layer ss tests and selects exploration candidates before reading its own reward statistics, using earlier-layer estimates to rank candidates. It reads its own reward statistics only on the elimination branch. Together with layer-specific refreshes, this ordering preserves the conditional noise law needed for the fixed-design prediction bound (Lemma 7).

Finally, the exact optimizer in Lemma 9 makes the first-layer confidence coefficient enter Φ2\Phi^2 only through (β02)21−L(\beta_0^2)^{2^{1-L}}, which the prescribed depth bounds by a universal constant. For the known-horizon policy, Equation (13) charges each layer refresh to its own log-determinant threshold and includes pool-only queries; Equation (52) then gives

$ \begin{aligned} S_T &\le d\log(1+T/d) \left(\sum_{s<L}z_s^{-1}+z_0^{-1}\right)\\ &=O\left( d\log(1+T/d) \frac{\log(2+\log(2+\min\{d,\log K\}))} {\log(2+\min\{d,\log K\})} \right). \end{aligned} $

The count uses the sum of reciprocal thresholds rather than paying the full depth. Section H extends the counting argument to the horizon-free policy with retained statistics.


Comments on the paper

3 comments

Dear Reviewer kv9a,

Thank you for the follow-up. We appreciate this opportunity to interact with you. We hope that our response below can help establish common ground and provide a clear basis for evaluating our work. We would first like to emphasize that we have already incorporated the changes addressing your comments into the revised manuscript and described them in our earlier response. To make the outcome clear, we summarize those completed revisions first below.


1. Revisions to the manuscript

Terminology. We have addressed your terminology concern by removing “iterated logarithm” throughout the revised manuscript and stating the corresponding factors explicitly, including

$ \log(2+\log(2+\min\{d,\log K\})). $

The revised PDF contains no occurrence of “iterated.”

Contribution wording. To address your second concern, we have changed the contribution heading to “Gaussian-max information inequality and direct prediction-error control,” with direct references to Lemma 1 and Corollary 2, and removed “sharpest.”


2. Terminology and the purpose of our references

We would also like to clarify the purpose of the references in our earlier response. We recognize that “iterated logarithm” denotes log⁡∗n\log^* n in standard algorithms references in CS, such as CLRS [1]. At the same time, the phrase also has an established association with a double logarithm in the probability/statistics literature through the law of the iterated logarithm [2], as well as in many works in the learning theory literature, some of which are cited above. More directly relevant to our paper, Li, Wang, and Zhou [3] describe the poly⁡(log⁡log⁡(nT))\operatorname{poly}(\log\log(nT)) factor in their linear-bandit bound using “iterated logarithmic terms.” Yet, with your feedback, we agree that precedent alone does not necessarily establish that the wording is sufficiently clear, particularly when different fields use the same term differently.

Before we proceed further, we believe it is important to establish common ground, so that the evaluation does not involve unnecessary disputes over differences in convention. To be clear, we are not arguing that only our usage is right; we acknowledge and accept the convention you mentioned. We sincerely hope that we can all agree that different terminological conventions often coexist (particularly across subfields), and that this does not (and should not), by itself, make one field’s usage the only correct one and another field’s usage always false. We wholeheartedly trust this is an academic standard we share.

Our references were intended as evidence of these different, long-established uses in the probability, statistics, and learning theory literature. When terminology overlaps across research contexts and subdomains, differing conventions can create ambiguity without necessarily making one usage correct and the other incorrect. We recognize, however, that readers should not have to resolve such differences to understand our results. This is why we have adopted explicit expressions, thanks to your input: they make the mathematical quantities clear and provide a common basis for assessing the claims.

We hope this clarifies both the background of our original wording and our willingness to improve it. We take the accuracy of our claims and references seriously, and would appreciate the opportunity to resolve any remaining disagreement through specific statements in the revised manuscript.


3. Remaining concerns and reassessment

Could you please clarify:

  1. W1: Does replacing the terminology with explicit expressions in the revised manuscript resolve this concern?
  2. W2: Do the revised heading and more specific wording address the examples raised? If another passage still overstates a result, could you identify it so that we can address it directly?

We would welcome any other remaining concern about the results or their presentation. If these revisions resolve your concerns, we would be grateful if you would reconsider your recommendation in light of the revised manuscript.


References

[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 3rd ed. MIT Press, 2009. §3.2, pp. 58–59, “The iterated logarithm function.”

[2] A. Kolmogoroff. Über das Gesetz des iterierten Logarithmus. Mathematische Annalen, 101:126–135, 1929.

[3] Y. Li, Y. Wang, and Y. Zhou. Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits. Proceedings of COLT, PMLR 99:2173–2174, 2019. (Technical locators refer to the full version, arXiv:1904.00242: Theorem 1 and the comparison following Theorem 2 and Remark 3)

Sincerely,
Authors

Thanks for clearing my concerns.

Thank you for your follow-up and for your time in reviewing our paper. We appreciate your feedback, which has helped us improve the clarity and precision of the manuscript.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.