- 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 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 , which is better than the previous best regret bound of 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
-
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.
-
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.
-
In the experiments, the author only uses -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:
-
In lines 200-201, what is the definition of the ``admissible instance ''? Is it an instance that satisfies Assumption 1?
-
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
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 , 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, accumulates assigned features immediately, whereas contains received feature–reward products. Action selection reads fixed snapshots , not the evolving accumulated states. The algorithm is read in the following order:
| Algorithm 1 | Operation and purpose |
|---|---|
| Before : Lines 3–7 | Check 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–16 | Form survivors ; check early terminal selection before exploring with a wide proposal or its certified fallback. If every survivor is narrow, pass onward. |
| Later layers: Lines 17–22 | Test before reading . Exploration uses an independent draw and earlier-layer estimates, then assigns the observation and stops. Otherwise read , eliminate, and continue. |
| Final ranking and recording: Lines 12, 23–25 | The 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 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 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 on samples, with predictions in its required function class. For , per-call confidence levels allocate total failure probability . 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 schedule | Expected-regret upper bound | Contexts | Regression calls / policy updates |
|---|---|---|---|
| FALCON+ [2], doubling | i.i.d. | regression calls | |
| FALCON+ [2], known-horizon fewer-epoch schedule | i.i.d. | regression calls | |
| OE2D [3], linear, doubling | i.i.d. | regression calls | |
| OE2D [3], linear, known-horizon fewer-epoch schedule | i.i.d. | regression calls | |
| OE2D [3], finite-action, doubling | i.i.d. | regression calls | |
| OE2D [3], finite-action, known-horizon fewer-epoch schedule | i.i.d. | regression calls | |
| GATE | Arbitrary context sequence fixed before interaction, independently of learner randomness and noise | Pathwise policy updates (2), with |
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.
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,4 experiments supplement the original results; the originally reported experiments and their results are retained.