acceptodds
Under review as a conference paper at ICLR 2027

GWidExplore: Computationally-Efficient Exploration in Contextual Linear Bandits

Abstract

Achieving nearly optimal regret with efficient optimization over large action sets has remained an open problem in contextual linear bandits. Dani, Hayes, and Kakade (2008) gave an efficient algorithm, but with regret. The problem was posed by Agrawal and Goyal in 2014 and revisited by Kim and Tewari (2020). The oracle-efficient linear Thompson-sampling and spanner-based methods of have guarantees that incur the additional factor. We close this gap for compact convex action sets. Under standard boundedness and sub-Gaussian noise assumptions, our algorithm achieves regret with high probability using polylogarithmically many linear optimizations over convex sets per round. The algorithm progressively removes actions that are suboptimal by adding linear constraints to the current action set. It measures the remaining uncertainty using the Gaussian width of a rescaled feasible set, where the rescaling reflects information from previously sampled actions. When the width is small, the algorithm shrinks the set while preserving an optimal action with high probability. When the width is large, it samples a random direction and chooses uniformly between the two feasible actions that are farthest apart in that direction.

Primary area:
reinforcement learning
Keywords:
GWidExplore: Computationally-Efficient Exploration in Contextual Linear Bandits

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_TRR9OpenReview ↗
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 O~(dT)\widetilde{O}( d \sqrt{T}), matching the minimax dependence on dimension dd and horizon TT up to logarithmic factors. Unlike prior computationally efficient methods that typically incur an additional d\sqrt{d} 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 O~(dT)\widetilde{O} ( d \sqrt{T}) regret with only polylogarithmically many linear-optimization oracle calls per round, improving on prior computationally efficient approaches that incur an additional factor of d\sqrt{d}. 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 O~(dT)\widetilde{O}( d \sqrt{T}) 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

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).

  • Large, changing action sets. A new set is randomly generated every round: ellipsoids, and polytopes with exponentially many vertices.
  • Cumulative regret. At d=16d=16, T=2×105T=2\times10^5, the proposed algorithm has regret lower than (the better of) LinTS and ConfidenceBall1 by a factor 5.3 (unit ball), 2.5 (ellipsoids) and 1.9 (polytopes).
  • Dimension. GWidExplore regret is linear in dd (fitted exponents 0.93 and 1.19, dd from 4 to 64), against 1.4 to 1.8 for the baselines.

[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(log⁡6(T/δ))O(\log^6(T/\delta)) oracle calls per round. The interior ball assumption and poly(dd) calls; both are removed. The reason is that: a constrained query has m≤⌈log⁡2T⌉m\le\lceil\log_2T\rceil extra halfspaces, so its Lagrangian dual is a convex problem in mm variables whose value costs one ordinary call. The ellipsoid method in dimension mm solves it with polylogarithmically many calls, independently of dd. 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 AtA_t is a polytope given by inequalities (the same LP with at most ⌈log⁡2T⌉\lceil\log_2T\rceil 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(log⁡4(T/δ))O(\log^4(T/\delta)) ordinary calls (Theorem 3.6).

[approximate optimization] Optimization errors up to order 1/T1/\sqrt 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)\min(\tau_L,\epsilon_L)/64\ge 1/(4096 C_\star\sqrt T), the regret bound holds with a larger constant and the same number of calls. An error ee changes each width sample by at most 2e2e and each filter comparison by at most ee; both are absorbed by the gap between the threshold τℓ\tau_\ell and the filter margin 2ϵℓ2\epsilon_\ell. So O(log⁡T)O(\log T) bits of accuracy suffice.

Experiment. We ran experiments to validate this (Figure 3a) which show that when every oracle answer exactly ee-suboptimal, the regret is unchanged up to e=10−3e=10^{-3}, 10% higher at e=10−2e=10^{-2}, and clearly worse only at e=0.1e=0.1.

[role of each component] (New Appendix B.10.) The d\sqrt 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.

  • Gaussian width. Let KK be the surviving set, VV the design matrix, ww the width. (a) With independent noise the comparison error over KK is O~(w)\tilde O(w). (b) The exploration step has E∥X∥V−12≥w2/(4d)E\lVert X\rVert^2_{V^{-1}}\ge w^2/(4d). So one quantity certifies elimination and guarantees exploration progress, using only linear optimization. Existing algorithms use r=max⁡x,y∈K∥x−y∥V−1r=\max_{x,y\in K}\lVert x-y\rVert_{V^{-1}} instead. Maximizing it is non-convex optimization problem, and the known replacements (ℓ1\ell_1 confidence sets, spanners, inflated posterior sampling) each lose a factor d\sqrt d.
  • Halfspace filters. They confine the exploration of layer ℓ\ell to 6ϵℓ6\epsilon_\ell-optimal actions and keep the surviving set convex.
  • Layering (from SupLinRel/SupLinUCB). The bound (a) needs the reward noise to be independent of the actions at which the rewards were collected. A single estimator that uses all the data violates this, because its actions are chosen from past rewards. The bound that still holds in that case (Abbasi-Yadkori et al.) is weaker by a factor d\sqrt d and gives O~(d3/2T)\tilde O(d^{3/2}\sqrt T) regret. With layers, the actions in a layer's regression are chosen without looking at that layer's rewards, so (a) applies.
  • Why not drop the layers? we do not know how to prove fact (a) with a single estimator and no layers. The bound we are aware of that applies for this is the self-normalized bound resulting in regret guarantee O~(d3/2T)\tilde O(d^{3/2}\sqrt T). Obtaining a width-based confidence bound for adaptively collected data without layering is an interesting open question.
  • Quantization. is needed only because the noise may depend on past rewards. With independent noise it can be dropped (we added Proposition B.24 proving this).

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.

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

The paper studies the long-standing statistical-computational gap in contextual linear bandits with large convex action sets. Existing oracle-efficient methods achieve approximately regret, while statistically optimal methods achieve regret but require computationally intractable optimization. The paper proposes GWidExplore, a layered elimination algorithm based on Gaussian width.

Critical strengths

• Addresses open problem. The paper directly targets the oracle-efficient regret in contextual linear bandits highlighted by prior work. The problem is important and long-standing.

• Elegant use of Gaussian Width. Gaussian width acts as the common factor between confidence and information gain, allowing the authors to tie elimination and exploration together tightly enough to achieve the optimal regret rate.

Critical weaknesses

• Lack of empirical evaluation. The paper provides strong theoretical guarantees, but no empirical validation of the proposed algorithm. This omission is particularly noticeable given that empirical evaluation is standard in the contextual bandit and oracle-efficient learning literature, even for primarily theoretical contributions, as it helps assess both the practical relevance and computational implications of new methods [1, 2, 3]. Since GWidExplore relies on Gaussian-width estimation, multiple elimination layers, quantization procedures, and repeated optimization-oracle interactions, it is difficult to gauge its actual computational overhead, scalability, and finite-sample behavior from the theory alone. While experiments are not necessary to establish the regret guarantees, empirical evidence would significantly strengthen the paper by demonstrating whether the theoretical improvements translate into meaningful practical advantages over existing oracle-efficient baselines.

References: 1.Kim, B., & Tewari, A. (2020, August). Randomized exploration for non-stationary stochastic linear bandits. In Conference on Uncertainty in Artificial Intelligence (pp. 71-80). PMLR. 2.Wagenmaker, A., Katz-Samuels, J., & Jamieson, K. (2021, March). Experimental design for regret minimization in linear bandits. In International Conference on Artificial Intelligence and Statistics (pp. 3088-3096). PMLR. 3.Kitamura, T., Liu, S., & Szepesvári, C. (2026). Randomized Exploration for Linear Bandits via Absolute Perturbations. arXiv preprint arXiv:2606.28616.

Questions for authors

• Have the authors implemented GWidExplore or conducted any preliminary experiments comparing it with existing oracle-efficient contextual bandit algorithms? Even small-scale results would help clarify whether the theoretical improvement from to translates into meaningful finite-sample or computational advantages in realistic regimes.

• Can the authors provide a more detailed runtime analysis, including the costs of Gaussian-width estimation, maintaining multiple elimination layers, and the required linear-algebra operations (e.g., covariance updates and matrix decompositions)? How do these costs scale with and in practice?

2 comments

We thank the reviewer for their review and time.

[empirical evaluation] We implemented GWidExplore and added an experimental section (Appendix H; the setup and the tables are in our response to all reviewers). The main findings:

  • Regret. At d=16d=16 and T=2×105T=2\times10^5, the regret of GWidExplore is lower than that of the better oracle-efficient baseline (LinTS, ConfidenceBall1) by a factor 5.3 on the unit ball, 2.5 on changing ellipsoids and 1.9 on changing polytopes.
  • The d\sqrt d improvement is validated. The regret of GWidExplore grows linearly in dd (fitted exponent 0.93 on the ball and 1.19 on ellipsoids, for dd from 4 to 64). The baselines grow with exponent 1.4 to 1.8 until their regret is nearly linear in TT.
  • Computation. We used 9 to 21 oracle calls and 0.4 to 1.6 ms time per round; please see details below.

[running time] Analysis (new Appendix B.8, Table 1). Let nw=O(log⁡(T/δ))n_w=O(\log(T/\delta)) be the number of Gaussian probes in one width estimate. A round visits at most L+1≤12log⁡2TL+1\le\frac12\log_2T layers, and at each visited layer it does the following:

StepOracle callsArithmeticWhen
Width estimate2nw2n_wO(nwd2)O(n_w d^2)every visited layer
Filter (one halfspace)1O(d)O(d)if the width is small
Exploration2O(d2)O(d^2)at most once per round
Regression update0O(d2)O(d^2)at most once per round

In total, a round uses at most (L+1)(2nw+2)(L+1)(2n_w+2) oracle calls and O(d2nwlog⁡T)O(d^2 n_w\log T) arithmetic operations, and the algorithm stores L+1L+1 matrices of size d×dd\times d.

  • No matrix decomposition needed: The algorithm uses V−1/2GV^{-1/2}G only through its distribution N(0,V−1)N(0,V^{-1}), so V−1/2V^{-1/2} can be replaced by a triangular factor RR with RR⊤=V−1RR^\top=V^{-1}, which is maintained under rank-one updates in O(d2)O(d^2) time. Only one layer is updated per round, so maintaining L+1L+1 layers costs memory but no extra time.
  • Fewer probes than in the submission. Your question led us to a simpler width estimate (new Lemma B.15). The range is rr-Lipschitz in GG with r≤π/2wr\le\sqrt{\pi/2} w, where ww is the width. By Gaussian concentration, the plain average of ⌈4πlog⁡(2/α)⌉\lceil 4\pi\log(2/\alpha)\rceil ranges lies in [w/2,3w/2][w/2,3w/2] with probability at least 1−α1-\alpha. It can replace the median of means and needs about 30 times fewer oracle calls. We updated our algorithm to use this estimator.
  • Dependence on TT. The per-round cost depends on TT only through L+1L+1 and nwn_w; it does not grow with tt.
  • Dependence on the action set. Its size or number of vertices enters only through the cost of one oracle call.

Numerics (Appendix H, Table 4; T=2×105T=2\times10^5 rounds; changing random ellipsoid action sets).

dd48163264
Layers L+1L+176543
Calls per round, ConfidenceBall18163264128
Calls per round, GWidExplore211815129
ms per round, GWidExplore1.621.080.820.640.43
  • Dependence on dd: At fixed TT the number of layers decreases with dd, so the number of calls decreases, while ConfidenceBall1 needs 2d2d calls.
  • With an LP oracle (changing polytopes, d=16d=16). A round takes 0.7 ms for GWidExplore, 1.2 ms for ConfidenceBall1 and 0.08 ms for LinTS; one LP takes 46-50 μ\mus. LinTS is the cheapest algorithm per round; GWidExplore trades a logarithmic number of additional oracle calls for the lower regret.

Thank you for the detailed rebuttal and the revisions. The new Appendix H answers my main concern about the lack of empirical evaluation, and Appendix B.8 answers my runtime question clearly. The experiments are useful, but some caution is needed in reading them. GWidExplore uses parameters tuned on pilot runs and a single Gaussian probe per width estimate, while the baselines use the theoretical confidence radii, which are known to over-explore. The reported oracle counts also come from this practical variant rather than the configuration the theorems cover. I’d encourage the authors to state these caveats in the final version and, if possible, to include baselines with tuned radii. Overall, I remain supportive of acceptance and maintain my rating of 3 (weak acceptance). I have no further questions.

Reviewer_an8hOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the problem of achieving nearly optimal regret while maintaining computational efficiency in contextual linear bandits with large action sets. The proposed algorithm, GWidExplore, combines a layered elimination structure with Gaussian-width-based uncertainty estimates to determine when to explore and when to eliminate actions. For compact convex action sets whose sequence is fixed before the interaction, the paper establishes a high-probability O~(dT)\widetilde{O}(d\sqrt{T}) regret bound for a fixed noise scale. The algorithm uses only polylogarithmically many linear-optimization oracle calls per round, where each query optimizes over the current action set intersected with additional linear constraints.

Critical strengths

The main strength is the combination of nearly optimal O~(dT)\widetilde{O}(d\sqrt{T}) regret and computational efficiency under the stated oracle model. Achieving this regret bound without enumerating the action set is a contribution for large-action-space contextual bandits. The Gaussian-width-based exploration mechanism provides an approach to balancing statistical efficiency with tractable action selection.

Critical weaknesses
  1. The oracle model complicates comparisons with prior work. The main efficiency guarantee relies on an oracle that optimizes over the action set intersected with additional halfspaces, rather than only over the original action set. Consequently, the stated oracle-call complexity is not immediately comparable to that of methods using an ordinary linear-optimization oracle. Although Appendix D discusses implementations under additional assumptions, the distinction between the main constrained-oracle guarantee and these implementations should be more prominent in the presentation of the computational contribution.

  2. The scope of the contextual assumption needs clearer positioning. The paper assumes an oblivious sequence of action sets. This restriction appears important to the analysis and should be explicitly distinguished from settings in which contexts can be selected adaptively based on past interactions. In particular, the relationship between the result proved here and the open question attributed to Agrawal and Goyal should be stated more precisely. This distinction affects how broadly the claimed resolution of the statistical–computational gap can be interpreted.

Questions for authors

1. Clarification of the oracle model.

How does Assumption 3.4 compare with the linear-optimization oracles used in the relevant prior work? My understanding is that the polylogarithmic query bound in Theorem 3.5 applies to the constrained oracle, whereas implementations using an ordinary oracle require additional assumptions and may incur polynomial overhead, as discussed in Appendix D. Is this interpretation correct? Please clarify which computational guarantees permit a direct comparison with prior methods.

2. Clarification of the contextual setting and the open problem.

The open question attributed to Agrawal and Goyal appears to concern a setting that permits adaptively chosen contexts, whereas this paper assumes that the action-set sequence is fixed before the interaction. Is this distinction correct? If so, please specify precisely which version of the open problem the paper resolves and how the obliviousness assumption limits the scope of the result.

3. Suggestion for empirical validation.

Could the authors provide numerical experiments comparing regret, runtime, and oracle-call counts with relevant oracle-efficient baselines? Such results would help assess whether the theoretical efficiency translates into practical computational advantages, particularly given the overhead of layered width estimation.

2 comments

Thank you for the review and time.

[oracle model and comparison with prior work] Your reading of the submission is correct: Theorem 3.5(ii) counts calls to the constrained oracle, and the ordinary-oracle implementation of the submitted Appendix D needed a supplied interior ball and a number of calls polynomial in dd. The revision removes both.

Updated Theorem 3.6. Under Assumptions 3.1-3.3, with only an ordinary linear-optimization oracle on each AtA_t, there is an algorithm with regret (1+σ)dTpolylog(T/δ)(1+\sigma) d\sqrt T \mathrm{polylog}(T/\delta) with probability at least 1−δ1-\delta, using O(log⁡6(T/δ))O(\log^6(T/\delta)) oracle calls per round and arithmetic polynomial in dd and log⁡(T/δ)\log(T/\delta). Nothing is assumed on AtA_t beyond compactness and convexity.

Comparing this with prior work, which uses the same oracle as ConfidenceBall1 and LinTS (new Table 2; LO = linear optimization):

AlgorithmRegretAccess to AtA_tCalls per round
OFUL / LinUCBO~(dT)\tilde O(d\sqrt T)non-convex program-
ConfidenceBall1O~(d3/2T)\tilde O(d^{3/2}\sqrt T)ordinary LO2d2d
LinTSO~(d3/2T)\tilde O(d^{3/2}\sqrt T)ordinary LO1
SpannerIGWO~(d3/2T)\tilde O(d^{3/2}\sqrt T)ordinary LOpoly(dd)
Theorem 3.5O~(dT)\tilde O(d\sqrt T)LO with at most ⌈log⁡2T⌉\lceil\log_2 T\rceil halfspacesO(log⁡Tlog⁡(T/δ))O(\log T\log(T/\delta))
Theorem 3.6 (new)O~(dT)\tilde O(d\sqrt T)ordinary LOO(log⁡6(T/δ))O(\log^6(T/\delta))

Why polylogarithmically many ordinary calls suffice (Appendix D.2). A constrained query adds m≤⌈log⁡2T⌉m\le\lceil\log_2T\rceil halfspaces to AtA_t. Its Lagrangian dual is a convex problem in only mm variables, and evaluating the dual function at a given multiplier is one ordinary oracle call. The ellipsoid method in dimension mm solves it with a number of calls polynomial in mm (for any dd), and a convex combination of the returned points is a feasible near-optimal answer. This requires a strictly feasible point which is obtained from the filters themselves. Feasible approximate answers also preserve the regret bound (Proposition D.1).

[oblivious action sets and the open problem] Yes, the distinction is correct. Agrawal and Goyal allow contexts chosen by an adaptive adversary. We resolve their question for an oblivious adversary: the sequence A1,…,ATA_1,\dots,A_T is arbitrary, with no stochastic assumption, but it is fixed before the interaction. The adaptive case remains open, and the abstract, introduction and related work now state this clearly.

What the oblivious model covers (new Remark 3.8). Fixed action sets, and random action sets drawn independently of the learner and of the noise, such as i.i.d. or Markovian contexts. Even for i.i.d. changing action sets, no efficient algorithm with O~(dT)\tilde O(d\sqrt T) regret was known.

Obliviousness is the usual model for layered elimination (SupLinRel, SupLinUCB and their refinements), for the same reason as here. The confidence bound of a layer conditions on the actions sampled by that layer and needs its reward errors to remain independent. If AtA_t depended on past rewards, the later actions of a layer would carry information about its own earlier rewards (Remark B.8).

Solving the problem for an adaptive adversary remains as an interesting open problem.

[experiments] Please see our response to all reviewers and Appendix H. At d=16d=16 and T=2×105T=2\times10^5, the regret of GWidExplore is lower than that of the better of LinTS and ConfidenceBall1 by a factor 5.3 on the unit ball, 2.5 on changing ellipsoids and 1.9 on changing polytopes. It makes 9 to 21 oracle calls per round (LinTS: 1; ConfidenceBall1: 2d2d) and takes 0.4 to 1.6 ms per round.

Thank you for the detailed response and revisions. The ordinary-oracle result in Theorem 3.6 and the clarification of the oblivious setting substantially address my original concerns. The additional experiments are helpful, although the practical comparisons warrant some caution: they evaluate direct constrained optimization rather than the ordinary-oracle reduction, and GWidExplore uses tuned parameters while the baselines use theoretical confidence radii. Overall, I remain supportive of acceptance and maintain my rating of 3: Weak acceptance. I have no further questions.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to all reviewers

[Summary of the revision and new experiments] We thank the reviewers for their thorough review. We uploaded a revised PDF addressing the reviewers comments. The three main changes are:

1. Ordinary oracle (an8h, TRR9). To address the reviewers concern on using an expensive oracle, we updated Theorem 3.6: we show that the O~(dT)\tilde O(d\sqrt T) regret bound also holds with an ordinary linear-optimization oracle on AtA_t, for arbitrary compact convex action sets, with O(log⁡6(T/δ))O(\log^6(T/\delta)) oracle calls per round. No interior ball or other condition on AtA_t is needed, and the number of calls does not depend on dd.

2. Experiments (all reviewers). In response to the reviewers suggestion, we have added Appendix H, summarized below, which provides a numerical evaluation illustrating the benefits of our proposed approach. While we believe that the main contribution of our work lies in its theoretical results, we agree that the numerical evaluation offers a useful complementary perspective and highlights the practical relevance of our work.

3. Scope (an8h). The abstract, introduction and related work now state that the action sets are chosen by an oblivious adversary, and that the adaptive case of the question of Agrawal and Goyal remains open (new Remark 3.8 and Appendix G).

Experiments: setup. θ\theta uniform on the unit sphere, N(0,1)N(0,1) noise, T=2×105T=2\times 10^5. Three families of action sets: the unit ball (the lower-bound instance); a new random ellipsoid every round; a new random polytope every round, given by random linear inequalities and accessed through an LP solver. Baselines: the two oracle-efficient algorithms with regret guarantees for changing action sets, linear Thompson sampling (LinTS; Agrawal and Goyal, Abeille and Lazaric) and ConfidenceBall1 (Dani et al.), both with the confidence radius of Abbasi-Yadkori et al. The constants of GWidExplore (threshold constant, number of layers, number of Gaussian probes per width estimate) were chosen once on short pilot runs and are the same in all experiments. The entries below are means over 10 runs for d=16d=16 and 5 runs otherwise.

Regret at d=16d=16 (Figure 1, Table 3):

Action setsGWidExploreLinTSConfidenceBall1best baseline / ours
Unit ball9,831 ±\pm 24454,17652,1045.3x
Ellipsoids, changing7,977 ±\pm 59027,93920,2702.5x
Polytopes, changing7,368 ±\pm 79830,81014,3091.9x

Regret as a function of dd, unit ball (Figure 2, Table 3):

dd48163264
GWidExplore2,7035,8939,83119,44737,739
LinTS7,41121,18154,176111,257161,103
ConfidenceBall15,75619,74952,104105,115152,045
  • Dimension. The regret of GWidExplore grows linearly in dd: the fitted exponent over dd from 4 to 64 is 0.93 on the ball and 1.19 on ellipsoids. The baselines grow with exponent 1.4 to 1.8 for d≤16d\le 16; for larger dd their regret is already nearly linear in TT at this horizon.
  • Oracle calls and running time (Table 4). GWidExplore makes 3(L+1)3(L+1) calls per round (which is between 9 (d=64d=64) and 21 (d=4d=4)), where L=⌊log⁡2(T/d)⌋L=\lfloor\log_2(\sqrt T/d)\rfloor; LinTS makes 1 and ConfidenceBall1 makes 2d2d. With closed-form oracles, a round of GWidExplore takes 0.4 to 1.6 ms for dd from 64 to 4 (LinTS and ConfidenceBall1: 0.04 to 0.1 ms); with an LP oracle at d=16d=16 it takes 0.7 ms (ConfidenceBall1: 1.2 ms; LinTS: 0.08 ms; one LP takes ~46 μ\mus). LinTS is the cheapest algorithm per round. Compared with ConfidenceBall1, GWidExplore makes fewer oracle calls for d≥16d\ge 16 and is faster with the LP oracle.
  • Approximate oracle (Figure 3a). Making every oracle answer ee-suboptimal leaves the regret unchanged up to e=10−3e=10^{-3}, which is the tolerance of Proposition D.1 here. The regret is 10% higher at e=10−2e=10^{-2} and degrades clearly only at e=0.1e=0.1.
  • Number of probes (Figure 3b). The regret is the same within the standard error with 1, 6 or 80 Gaussian probes per width estimate.

Theorem, appendix, figure and table numbers in our responses refer to the revised PDF.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.