- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper introduces GWidExplore, an algorithm for contextual linear bandits that closes a longstanding gap between statistically optimal regret and computational efficiency when the available action sets are large and can change over time. Under standard boundedness and conditionally sub-Gaussian noise assumptions, the algorithm achieves high-probability regret of , matching the minimax dependence on dimension and horizon up to logarithmic factors. Unlike prior computationally efficient methods that typically incur an additional factor, GWidExplore requires only polylogarithmically many linear-optimization oracle calls per round.
The key contribution is an exploration and elimination strategy based on Gaussian width, which measures uncertainty across the surviving action set after accounting for information from previous observations. When the width is small, the algorithm eliminates actions with low estimated rewards by adding linear constraints while preserving an optimal action with high probability. When uncertainty is large, it samples one of the two actions that maximize and minimize a randomly generated, information-adjusted linear objective.
The validation is primarily theoretical. The paper proves the regret and oracle-complexity guarantees, establishes that the regret rate is minimax-optimal up to logarithmic factors, and shows that the width can be estimated efficiently using a logarithmic number of oracle calls. The paper does not present empirical experiments demonstrating practical performance. Thus, its main contribution is a statistical theory.
Critical strengths
The paper addresses an important gap in contextual linear bandits: achieving near-minimax-optimal regret while keeping computation efficient, even when action sets are large or change over time. Its main contribution is that GWidExplore achieves regret with only polylogarithmically many linear-optimization oracle calls per round, improving on prior computationally efficient approaches that incur an additional factor of . This combination of statistical theory and computational guarantees is consequential for making theoretically optimal exploration more practical in complex action spaces.
Another strength is the technical novelty. The Gaussian-width-based exploration and elimination strategy adapts to uncertainty over the surviving action set, while layered estimators, randomized reward quantization, and a coupling argument address the complications introduced by history-dependent noise. The paper provides theoretical guarantees for both regret and oracle complexity, including minimax optimality up to logarithmic factors. Although empirical validation is absent, the theoretical results are substantial and directly support the paper’s central claims.
Critical weaknesses
1. There is no empirical validation. The paper’s main contribution is a theoretically efficient exploration algorithm, but it does not demonstrate its practical performance on any simulated or real-world bandit problems. It is thus hard to evaluate whether the theoretical improvements translate into meaningful practical benefits.
2. The computational-efficiency claim depends on a nontrivial oracle model. The main result counts calls to an oracle that optimizes over the action set subject to additional linear constraints, which is stronger than access to an ordinary linear-optimization oracle. This seems to limit the generality of the paper’s computational claim.
Questions for authors
1. How essential is the stronger constrained-oracle assumption to the main result? Specifically, the algorithm queries an oracle that optimizes over the action set subject to additional linear constraints. Under what conditions can this oracle be implemented with comparable computational cost using only a standard linear-optimization oracle?
2. How sensitive is the regret guarantee to approximate optimization? Specifically, the paper discusses approximate oracle solutions, but how do optimization errors affect the final regret bound? How robust is the algorithm against optimization errors while retaining regret? This would help establish whether the theoretical result survives the numerical approximations.
3. How much of the improvement comes from the Gaussian-width exploration rule itself? SPecifically, how should I think of the roles of Gaussian-width-based elimination, layered estimators, and randomized reward quantization in obtaining the regret and computational guarantees? In particular, why a simpler width-based exploration strategy cannot achieve the same regret with comparable oracle complexity?
4. Some experimental results would greatly improve the paper. For example, one can evaluate GWidExplore against the most relevant computationally efficient baselines on synthetic contextual linear bandits with large, changing action sets. Report metrics such as cumulative regret, and sensitivity to dimension and action-set representation.
2 comments
I appreciate the rebuttal by the authors. In particular, the lack of experimental results is now fixed with new experimental results added to the new Appendix H of the draft. The experiment shows the benefit of the proposed algorithm for contextual linear bandit. Overall, I think the rebuttal is good and thus raised my score to 3. I have no additional questions for the paper.
Thank you for the review and time.
[experiments] We ran the experiments you described (Appendix H; setup and tables in our response to all reviewers).
[constrained oracle] Using constrained oracle calls is not essential. We added a wew Theorem 3.6 proving that: the same regret bound holds with an ordinary linear-optimization oracle, with O(log6(T/δ)) oracle calls per round. The interior ball assumption and poly(d) calls; both are removed. The reason is that: a constrained query has m≤⌈log2T⌉ extra halfspaces, so its Lagrangian dual is a convex problem in m variables whose value costs one ordinary call. The ellipsoid method in dimension m solves it with polylogarithmically many calls, independently of d. A convex combination of the returned points is a feasible near-optimal answer, and the strictly feasible point the method needs comes from the filters (Appendix D.2).
When is the cost comparable? The cost is always comparable up to log factors. A constrained query costs about the same as an ordinary one when when At is a polytope given by inequalities (the same LP with at most ⌈log2T⌉ more rows), is given by a separation or membership oracle, or is a ball or an ellipsoid. In general, for a black-box ordinary oracle, one constrained query costs O(log4(T/δ)) ordinary calls (Theorem 3.6).
[approximate optimization] Optimization errors up to order 1/T cost a constant factor. By Proposition D.1, if every answer is feasible and optimal up to an additive error min(τL,ϵL)/64≥1/(4096C⋆T), the regret bound holds with a larger constant and the same number of calls. An error e changes each width sample by at most 2e and each filter comparison by at most e; both are absorbed by the gap between the threshold τℓ and the filter margin 2ϵℓ. So O(logT) bits of accuracy suffice.
Experiment. We ran experiments to validate this (Figure 3a) which show that when every oracle answer exactly e-suboptimal, the regret is unchanged up to e=10−3, 10% higher at e=10−2, and clearly worse only at e=0.1.
[role of each component] (New Appendix B.10.) The d improvement and the oracle efficiency both come from the Gaussian-width exploration rule. Layering and quantization do not change the rate; they make the confidence bound valid for adaptively collected data and history-dependent noise.