acceptodds
Under review as a conference paper at ICLR 2027

Stochastic Bandit Convex Optimization with Blocking Constraints

Abstract

We study stochastic bandit convex optimization under blocking constraints. After an action is selected, all actions within distance become unavailable for the next rounds, where is the blocking period. Since repeatedly selecting a minimizer is, in general, infeasible, we measure regret against an offline benchmark defined by the infimum average loss over feasible cycles of actions. We show that the convexity of the loss function and the action set allows the search for this benchmark to be restricted to a ball of radius around a global minimizer. This motivates the design and analysis of an algorithm that first learns a point with low loss and then uses lower confidence bound (LCBs) to explore feasible cycles in its neighborhood. By grouping repeated queries and controlling transitions between cycles, our algorithm respects the blocking constraints and accounts for all exploration and transition costs. Under a geometric condition ensuring local feasibility, we establish a regret upper bound of and a minimax lower bound of , for fixed action space dimension and blocking period . The lower bound holds on the unit Euclidean ball with Gaussian noise. Both bounds recover the classical regret when is small. For , a sharper decomposition based on the direction between the two actions improves the upper bound to match the lower bound, establishing minimax optimal dependence on and up to logarithmic factors.

Primary area:
learning theory
Keywords:
Bandit Convex Optimization, Blocking Bandits, Regret Minimization, Stochastic Optimization

Reviews

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

This paper studies stochastic bandit convex optimization under a temporary blocking constraint: after selecting an action (xt)(x_t), every point within distance (ε\varepsilon) is unavailable for the following (p-1) rounds. Because repeatedly playing a global minimizer is generally infeasible, the paper compares the learner against the minimum average loss of a feasible (p)-point (ε\varepsilon)-packing. The authors show that this benchmark coincides with the optimal long-run average loss achievable with full knowledge of the stationary loss function. The main structural result is a localization argument: if (z) is a low-loss point, then it is sufficient to search for a near-optimal packing inside (X∩B(z,2pε)X\cap B(z,2p\varepsilon)), with an additive loss controlled by (f(z)−f⋆f(z)-f^\star). This motivates an anchor-and-refine algorithm. The first phase uses a stochastic convex-bandit routine to obtain a low-loss anchor while embedding each query into a feasible cycle. The second phase searches for a low-loss packing in the localized region using lower-confidence estimates, while explicitly accounting for the physical rounds needed to move between feasible packings. Under an inball condition, the paper obtains, for fixed (p,d,L,σ)(p,d,L,\sigma), an upper bound of order O~!(T[1+(εT)d/(d+2)]).\widetilde O!\left(\sqrt{T}\left[1+(\varepsilon\sqrt{T})^{d/(d+2)}\right]\right). It also proves a lower bound on the Euclidean unit ball of order Ω!(T[1+(εT)(d−1)/(d+3)]),\Omega!\left(\sqrt{T}\left[1+(\varepsilon\sqrt{T})^{(d-1)/(d+3)}\right]\right), up to factors depending on (p) and (d). These rates do not match for general (p). For (p=2), the authors introduce a directional decomposition of feasible pairs and obtain a matching upper bound, establishing minimax-optimal dependence on (T) and (ε\varepsilon) up to logarithmic factors. Overall, I find the problem formulation novel and the technical development substantial. The strongest part of the paper is the combination of geometric blocking arguments with stochastic BCO, particularly the localization result and the matching characterization for (p=2). My main reservations concern the unresolved minimax gap for general blocking periods and the computational status of the proposed algorithms.

Critical strengths
  1. A well-motivated benchmark and a strong localization principle The choice of the feasible (p)-cycle benchmark is convincing. It corresponds to the optimal long-run average loss under full knowledge of the loss function, while avoiding the unavoidable linear penalty that would arise from comparison with the unconstrained global minimizer. More importantly, Proposition 2.1 substantially simplifies the structure of the problem. It shows that once a low-loss anchor is available, an optimal or near-optimal packing can be searched for in a radius-(2pε2p\varepsilon) neighborhood of that anchor. This is not an obvious consequence of convexity because the packing constraint itself is nonconvex. The compression argument is elegant and appears broadly useful beyond the specific algorithm developed here. The paper also handles the physical feasibility of the resulting learning process rather than treating the packing problem as an abstract combinatorial optimization problem. The transition lemmas quantify how quickly one feasible configuration can be changed into another and these costs are included in the regret analysis.

  2. The lower bound and the matching (p=2) result provide genuine structural insight The lower bound is more informative than a generic reduction from ordinary BCO. It constructs many possible favorable packing directions whose informative regions are smaller than the blocking radius, so the blocking rule directly limits the number of statistically informative observations. For (p=2), the paper then exploits the separation direction of a feasible pair and reduces the remaining optimization to a finite family of convex branches. This leads to upper and lower bounds with matching dependence on (T) and (ε\varepsilon), up to logarithmic factors. In my view, this is the cleanest evidence that the proposed model contains a new and nontrivial statistical phenomenon rather than merely adding a transition overhead to existing stochastic BCO.

Critical weaknesses
  1. The central minimax characterization remains incomplete for general (p) The paper is formulated for arbitrary blocking period (p), but the general-period upper and lower bounds leave a substantial gap. For fixed (p) and (d), the blocking-dependent exponent in the upper bound is (d/(d+2)), whereas the lower bound contains ((d-1)/(d+3)). The dependence on (p) also does not match. The paper is transparent about this gap, and the exact (p=2) result is valuable. Nevertheless, for a top-tier theory paper, this is the main limitation of the contribution: the sharp statistical complexity of the general model introduced by the paper is still unresolved. It is currently unclear whether the gap comes from the cellwise refinement algorithm, from the lower-bound construction, or from genuinely different behavior when (p>2). This does not invalidate the results, but it prevents me from viewing the paper as a complete minimax treatment of the proposed model.

  2. The upper bounds are primarily information-theoretic rather than computationally implementable Algorithm 1 assumes an optimization oracle that finds a (T−2T^{-2})-accurate minimizer of the current LCB objective over the nonconvex feasible packing space. The paper explicitly notes that this geometric optimization can be computationally difficult and proves NP-hardness of approximating the offline benchmark when the dimension varies. This is an important limitation because the proposed method is presented as a learning algorithm, but the main general-period guarantee does not translate into a polynomial-time procedure in the natural input model. Even the (p=2) construction requires a directional net whose size scales as (θ−(d−1)\theta^{-(d-1)}), so the computational dependence on dimension can be severe. For an information-theoretic paper this is acceptable, but the distinction should be made more explicit in the statement of the contribution. A sharper characterization of the computational regime—for example, fixed dimension, specific domains such as Euclidean balls, or access to particular geometric oracles—would make the result considerably easier to interpret.

Questions for authors
  1. What do the authors believe is the correct minimax rate for general (p>2)? In particular, is there evidence that the (d/(d+2)) exponent in the upper bound is an artifact of discretizing the full localized packing space, analogous to what Section 5 improves for (p=2), or is there a reason to expect a genuine qualitative difference for (p>2)? A concrete conjecture would help clarify how complete the current theory is.

  2. Can the authors state the computational complexity of Algorithms 1 and 2 under a standard oracle model for (X)? For Algorithm 1, what oracle access is required to construct feasible completions and solve the LCB packing problem to accuracy (T−2T^{-2})? For (p=2), is Algorithm 2 polynomial-time when (d) is fixed, and what is its dependence on (T), (d), and the geometry of (X)?

  3. Could the authors clarify the precise implementation assumptions behind Lemma F.1? The polylogarithmic query-segment bound is essential because transitions are charged per segment. Since this property is derived by adapting Agarwal et al. rather than quoted directly, it would be useful to state explicitly which membership/separation/rounding oracles are needed for a general compact convex set and whether the resulting procedure is fully constructive under those assumptions.

  4. How essential is the known-inball assumption in the main upper-bound statement? The appendix gives a diameter-based implementation, but its regret dependence can deteriorate near the feasibility threshold (D\approx p\varepsilon). It would be useful to explain more explicitly which geometric assumption the authors consider intrinsic to the statistical problem and which is only a device for obtaining uniformly short transitions.

2 comments

Thank you for your detailed and constructive review. We acknowledge the general-period minimax gap and computational limitations, and have clarified the packing-oracle assumption and its required accuracy.

Question 1

We conjecture that, for fixed dd and p≥2p\geq 2, the minimax regret should be RT∗=Θ~d,p(T[1+(ϵT)d−1d+3])R_T^*=\widetilde{\Theta}_{d,p}\left(\sqrt{T}\left[1+(\epsilon\sqrt{T})^{\frac{d-1}{d+3}}\right]\right). We believe the general-period upper bound can be improved. Because our current algorithm for p>2p>2 didn't fully utilize the convexity of the expected objective function during the "refine" period. And for the case of p=2p=2, the upper bound and lower bound match for the ε\varepsilon and TT, which means the lower bound is tight in this case. While both algorithm 1 is designed for p>2, its results also holds for p=2p=2. However, both our theoretical results and complementary experiment(Section 6) show that under the instace with p=2p=2, algorithm 2 performs better than algorithm 1. So we guess new approach are needed for the case of p>2p>2,

However, extending direction covering approach to p>2p>2 is potentially difficult. For p=2p=2, the optimal solution is exactly a pair of points with one separation constraint. This separation constraint can be interpreted as that the vector connect the two points in the optimal solution, where the vector has the exactly length equal to ε\varepsilon. The direction of this vector is considered in the direction-covering approach of Algorithm 2. So to be simple, the constraints determines that only one direction need to be considered in the case of p=2p=2. However, when p>2p>2, (p2)\binom{p}{2} pairwise separation constraints must hold simultaneously. This raises the difficulty of extend the direction-covering approach. For example, an equilateral triangle with side length ϵ\epsilon is a possible geometry of the constraint, while three points lie in one line with edge length ϵ\epsilon is also available and can be the optimal solution under some objective functions. To extend this approach to p>2p>2, one possible way is to assign a separate direction uiju_{ij} to each pair (i,j)(i,j) and define convex branches using the linear constraints ⟨uij,xi−xj⟩≥ϵ(1+θ2)\langle u_{ij},x_i-x_j\rangle \geq \epsilon(1+\theta^2), for i<ji<j, where θ\theta is the computation accuracy to discretise. However, covering all directions uiju_{ij} would require up to O(θ−q)O(\theta^{-q}) branches, where q=(d−1)(p2)q=(d-1)\binom{p}{2}. Moreover, these directions are mutually coupled, so the argument used by p=2p=2 does not directly apply. Therefore, achieving the desired rate for p>2p>2 would require a more efficient way to cover these constraints.

Question 3.

We clarify that Lemma F.1 requires the same geometric-oracle assumptions as Agarwal et al. (2013). We didn't require additional geometric oracle. As discussed in Sections 1 and 5 of Agarwal et al. (2013), their algorithm requires a separation oracle for the feasible set. Our construction directly follows their Algorithms 1 and 2 and is constructive under the same oracle model.

Question 4.

Our blocking bandit problem involves two coupled aspects: geometric feasibility and learning. Known-inball assumption or diameter-based assumption are sufiicient but not necessarily condition for geometric fesiblility. Their main role is to make sure both geometric feasibility and learning can work well, and guarantee feasible exploration and uniformly short transitions. Without such conditions, only the existence of a feasible packing cannot guarantee that the algorithm can always select a feasible action at each iteration. For example, consider p=2p=2, ε=1\varepsilon=1, and X=[0,1]\mathcal X=[0,1]. The packing {0,1}\{0,1\} is feasible. However, if the algorithm first selects x=1/2x=1/2, there is no feasible action in the next round. Even we assume there exists a feasible action available at every round, sublinear regret may still be impossible. Consider p=3p=3, ε=1\varepsilon=1, and the two-dimensional disk X=B(0,1/3)\mathcal X=B(0,1/\sqrt{3}). Every feasible packing consists of three vertices of an equilateral triangle on the boundary. Once the first point is selected, any feasible sequence have to repeating the same three vertices. Thus, the algorithm can always continue playing feasible actions, but it cannot switch to another packing. This can lead to linear regret. For example, consider the two convex Lipschitz loss functions f±(x)=(1±3x1)332f_\pm(x)=\frac{(1\pm\sqrt{3}x_1)^3}{32}. Their optimal packings have different positions. However, the algorithm must choose its initial orientation before observing any feedback and cannot change it. Therefore, at least one of these two instances leads to Ω(T)\Omega(T) expected regret for any algorithm.

Therefore, some additional geometric structure beyond feisiblity is needed to allow the algorithm to explore and move between different packings. Finding weaker geometric conditions that guarantee sublinear regret remains an interesting direction for future work.

Question 2.

We require that the action space X\mathcal X should have a polynomial-time separation oracle, a known inball B(c,r0)⊆XB(c,r_0)\subseteq\mathcal X, and a known diameter bound DD. Under the inball condition,

For Algorithm 1, the feasible packing containing a given query qq can be obtained sampling points from the known inball. Under the volume condition, each sample has an acceptance probability bounded below by a constant. Thus, constructing a packing of pp points requires O(p)O(p) samples in expectation. Lemma G.5 then moves the packing into B(q,2pε)B(q,2p\varepsilon) using line-segment operations. Similarly, the buffer in Lemma F.1 can be constructed by rejection sampling from a known ball inside X\mathcal X. These operations can be done within polynomial time. The main computational difficulty is the LCB packing oracle. The "refine" phase need at most O(Mlog⁡(eT))O(M\log(eT)) oracle calls, where M≤(6R/r)dM\leq(6R/r)^d. Each call minimizes a piecewise-constant LCB objective over the nonconvex packing-feasibility region. Polynomial-time cannot be expected for non convex optimization in general. However, when both dd and the blocking period pp are fixed, the optimization oracle can be implemented in polynomial time. Here, we assume that the domain has an explicit polynomial-size semialgebraic description (e.g., rational polytopes or Euclidean balls). Since the LCB objective is piecewise constant over MM partition cells, we can enumerate at most MpM^p cell assignments. For each assignment, feasibility can be checked through polynomial constraints in dpdp variables, including ∣ui−uj∣2≥ε2|u_i-u_j|^2\geq\varepsilon^2 for i<ji<j. These checks can be done in polynomial time using real-algebraic methods (Renegar, 1992). We then select t the smallest LCB value among all feasible packing.

The oracle tolerance T−2T^{-2} in paper was chosen for simplicity and can be looser for our regret bound. Denote the oracle error as δT\delta_T. As shown in the revised proof of Lemma G.4, the oracle error adds at most pδTp\delta_T regret per complete packing cycle. Since there are at most T/pT/p such cycles, the total additional regret is at most TδTT\delta_T. Therefore, the regret bound becomes R_T^{\varepsilon}\leq\min\left\\{T,\\,\widetilde O_{d,\sigma}\left(\sqrt{pT}\left[1+(L\varepsilon\sqrt{pT})^{\frac{d}{d+2}}\right]\right)+T\delta_T\right\\}. In particular, choosing δT=O(T−1/2)\delta_T=O(T^{-1/2}) is already sufficient to preserve the stated regret rate.

Algorithm 2 avoids the nonconvex packing oracle by introducing NN convex branches Cu={(x,y)∈X2:⟨u,x−y⟩≥ε(1+θ2)}\mathcal C_u=\{(x,y)\in\mathcal X^2:\langle u,x-y\rangle\geq\varepsilon(1+\theta^2)\}. Each branch has a separation oracle that requires at most two separation-oracle calls for X\mathcal X and one linear-constraint check. Moreover, since ε<r0\varepsilon<r_0 and θ≤Question1/2\theta\le Question 1/2, each branch contains the explicit inball B2d((c+34r0u,c−34r0u),18r0)⊆CuB_{2d}\bigl((c+\frac34r_0u,c-\frac34r_0u),\frac18r_0\bigr)\subseteq \mathcal C_u. Each branch is also contained in a ball of radius 2D\sqrt2D. Thus, its geometric condition ratio is at most κ=82Dr0\kappa=\frac{8\sqrt2D}{r_0}.

These geometric bounds make the rounding and stochastic convex-bandit subroutines of Agarwal et al. (2013) to be implemented in polynomial times oracle call, which is polynomial in log⁡κ\log\kappa. The transfers can also be constructed efficiently. Since ε<r0\varepsilon<r_0, the known inball provides three ε\varepsilon-separated parking points. Lemma B.1 then guarantees that each transfer requires at most 10 physical rounds. The number of convex branches satisfies N≤Cdir(d)θ−(d−1)N\leq C_{\mathrm{dir}}(d)\theta^{-(d-1)}, where Cdir(d)=2d(1+4d)d−1C_{\mathrm{dir}}(d)=2d(1+4\sqrt d)^{d-1}. With θT=min⁡{12,((ε/r0)2T)−1/(d+3)}\theta_T=\min\{\frac12,((\varepsilon/r_0)^2T)^{-1/(d+3)}\}, we obtain N=Od(1+((ε/r0)2T)d−1d+3)N=O_d\left(1+((\varepsilon/r_0)^2T)^{\frac{d-1}{d+3}}\right).

Algorithm 2 processes at most O(T)O(T) virtual observations and starts at most O(Nlog⁡(T+1))O(N\log(T+1)) convex-bandit runs. Let QstepQ_{\mathrm{step}} and QinitQ_{\mathrm{init}} denote the separation-oracle costs per observation and per initialization of a convex-bandit run. With standard oracle-based implementations, both are polynomial in dd, log⁡(D/r0)\log(D/r_0), and log⁡T\log T. Thus, the total number of separation-oracle calls is bounded by O(TQstep+Nlog⁡(T+1)Qinit)O\left(TQ_{\mathrm{step}}+N\log(T+1)Q_{\mathrm{init}}\right). Consequently, a conservative bound on the total computational complexity is O~d(T1+d−1d+3poly⁡(log⁡Dr0,BT)(1+τX(BT)))\widetilde O_d\left(T^{1+\frac{d-1}{d+3}}\operatorname{poly}\left(\log\frac{D}{r_0},B_T\right)(1+\tau_{\mathcal X}(B_T))\right), where τX(BT)\tau_{\mathcal X}(B_T) is the time for one separation-oracle call at the required precision BTB_T.

In summary, Algorithm 1 need polynomially many calls to a nonconvex packing oracle. Under additional semialgebraic assumptions, this oracle can be implemented in polynomial time for fixed d,pd,p. In contrast, Algorithm 2 only have a polynomial-time implementation for fixed dd using only standard convex-oracle.

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

This paper studies stochastic bandit convex optimization with a blocking constraint. After the learner plays a point, all points within distance ε of it cannot be played in the next p-1 rounds. Since the minimizer cannot be played repeatedly, the regret is defined against T times the smallest average loss over feasible p-point packings, which is the best long-run average loss with full knowledge of f. The main structural result is that by convexity the search for the best packing can be restricted to a small ball around any low-loss anchor point, with a cost at most the suboptimality of the anchor. The algorithm first learns an anchor by batched BCO embedded in feasible cycles, and then refines a packing near the anchor by cellwise lower confidence bounds, with the transfer cost counted in the regret. The paper gives an upper bound and a lower bound; both are of order sqrt(T) when ε sqrt(T) is small, and their blocking-dependent terms have different exponents in d for general p. For p=2, a covering of the separation directions gives an upper bound that matches the lower bound. The appendix also shows the offline packing problem is NP-hard and analyzes the transition time between packings.

Critical strengths

The problem is new and clearly defined, and the paper is complete as a theory paper: the benchmark is justified against two natural alternatives (Appendix B), there are upper and lower bounds, a minimax tight case for p=2, and a hardness result for the offline problem. The key idea is simple: convexity lets the search for the best packing be localized near a low-loss anchor.

Critical weaknesses

First, the motivation does not support the model. The two applications in the introduction (cartilage stiffness mapping and laser spot thermography) motivate the temporary exclusion of nearby probe points, but not the rest of the model. In these applications, the goal is to map the whole field or to find defects, so the user wants to cover the domain, not to converge to the minimizer, and cumulative loss against a packing benchmark is not what they want to minimize. The field is also not convex: a defect is exactly a local bump, which convexity rules out. And the interference is a bias that decays with time and distance, not a hard exclusion. The paper should either give an application where the objective really is cumulative convex loss under exclusion, or present the model as an abstract problem in the spirit of blocking bandits (Basu et al. 2019).

Second, there is no experiment at all, not even a toy example. For a theory paper this is acceptable, but a one-dimensional illustration (for example f(x)=x^2 on [0,1] with p=2) would take little effort and would show whether the transition at ε √T of order one in the bounds is visible in practice, and how large the constants are compared with the bounds.

Third, the gap for p>2 is not explained. The paper attributes the matching rate at p=2 to discretizing only the (d-1)-dimensional space of separation directions instead of the full packing space cell by cell (Section 5 and the discussion after Theorem 5.2). But it does not discuss why the same approach does not extend to p>2, and it does not say on which side the gap for p>2 is more likely to be, the upper bound or the lower bound.

Questions for authors
  1. In the cartilage and thermography applications, what is the loss f, and why is the objective the cumulative loss instead of the estimation error over the field? Would a soft interference model (bias decaying in time and distance) be more realistic, and would it be easier or harder to analyze?

  2. For p>2, why does the direction-covering approach of Section 5 not extend? Is the gap between d/(d+2) and (d-1)/(d+3) more likely to come from the upper bound or from the lower bound?

  3. The algorithm needs an optimization oracle over feasible packings with additive error T^(-2), and Theorem C.1 shows this problem is NP-hard when d is part of the input. Is there a polynomial-time approximate oracle for fixed small d, and does the analysis still hold when the oracle error is larger than T^(-2)?

2 comments

Thank you for your careful reading and constructive review. In the revised manuscript, we have revised the motivation and added a numerical experiment to illustrate the theoretical results.

Question 1.

We agree that the original applications don't clearly explain the motivation for blocking constraints from the objective function. We have revised the Introduction and added more relevant applications, including online recommendation(Basu et al., 2019; Cao et al., 2020). In this new example, xx represents a continuous feature representation of recommended content, and f(x)f(x) models expected user dissatisfaction through a convex surrogate. Users may become tired of seeing similar content in consecutive rounds. Therefore, recently recommended content temporarily blocks sufficiently similar alternatives, which naturally be interpreted as neighborhood-based blocking. Moreover, since each recommendation directly affects the user experience, minimizing cumulative loss helps reduce the total expected user dissatisfaction over time.

We also agree that soft interference model with decaying in distance and time is generally more physically realistic in many setting. However, a general soft-interference model would typically be harder to analyze, since residual effects from previous actions could introduce history-dependent bias into observations, violating the stationary unbiased-feedback assumption used in the general regret analysis. And both learning and the optimal benchmark become history-dependent, requiring substantially different techniques.

Question 2.

Why the direction-covering approach does not directly extend to p>2p>2.

For p=2p=2, the optimal solution is exactly a pair of points with one separation constraint. This separation constraint can be interpreted as that the vector connect the two points in the optimal solution, where the vector has the exactly length equal to ε\varepsilon. The direction of this vector is considered in the direction-covering approach of Algorithm 2. So to be simple, the constraints determines that only one direction need to be considered in the case of p=2p=2. However, when p>2p>2, (p2)\binom{p}{2} pairwise separation constraints must hold simultaneously. This raises the difficulty of extend the direction-covering approach. For example, an equilateral triangle with side length ϵ\epsilon is a possible geometry of the constraint, while three points lie in one line with edge length ϵ\epsilon is also available and can be the optimal solution under some objective functions.

To extend this approach to p>2p>2, one possible way is to assign a separate direction uiju_{ij} to each pair (i,j)(i,j) and define convex branches using the linear constraints ⟨uij,xi−xj⟩≥ϵ(1+θ2)\langle u_{ij},x_i-x_j\rangle \geq \epsilon(1+\theta^2), for i<ji<j, where θ\theta is the computation accuracy to discretise. However, covering all directions uiju_{ij} would require up to O(θ−q)O(\theta^{-q}) branches, where q=(d−1)(p2)q=(d-1)\binom{p}{2}. Moreover, these directions are mutually coupled, so the argument used by p=2p=2 does not directly apply. Therefore, achieving the desired rate for p>2p>2 would require a more efficient way to cover these constraints.

Which bound is more likely to be loose?

We believe the general-period upper bound can be improved. Because our current algorithm for p>2p>2 didn't fully utilize the convexity of the expected objective function during the "refine" period. And for the case of p=2p=2, the upper bound and lower bound match for the ε\varepsilon and TT, which means the lower bound is tight in this case. While both algorithm 1 is designed for p>2, its results also holds for p=2p=2. However, both our theoretical results and complementary experiment(Section 6) show that under the instace with p=2p=2, algorithm 2 performs better than algorithm 1. So we guess new approach are needed for the case of p>2p>2,

Question 3.

When both dd and the blocking period pp are fixed, the optimization oracle can be implemented in polynomial time. Here, we assume that the domain has an explicit polynomial-size semialgebraic description (e.g., rational polytopes or Euclidean balls). Since the LCB objective is piecewise constant over MM partition cells, we can enumerate at most MpM^p cell assignments. For each assignment, feasibility can be checked through polynomial constraints in dpdp variables, including ∣ui−uj∣2≥ε2|u_i-u_j|^2\geq\varepsilon^2 for i<ji<j. These checks can be done in polynomial time using real-algebraic methods (Renegar, 1992). We then select t the smallest LCB value among all feasible packing.

The oracle tolerance T−2T^{-2} in paper was chosen for simplicity and can be looser for our regret bound. Denote the oracle error as δT\delta_T. As shown in the revised proof of Lemma G.4, the oracle error adds at most pδTp\delta_T regret per complete packing cycle. Since there are at most T/pT/p such cycles, the total additional regret is at most TδTT\delta_T. Therefore, the regret bound becomes R_T^{\varepsilon}\leq\min\left\\{T,\\,\widetilde O_{d,\sigma}\left(\sqrt{pT}\left[1+(L\varepsilon\sqrt{pT})^{\frac{d}{d+2}}\right]\right)+T\delta_T\right\\}. In particular, choosing δT=O(T−1/2)\delta_T=O(T^{-1/2}) is already sufficient to preserve the stated regret rate.

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

This paper is on stochastic bandit convex optimisation with "blocking constraints": for a known natural pp and real ε\varepsilon, the bandit learner is restricted so that its actions in any round tt must be at least ε\varepsilon-far from every action played in the last p−1p-1 rounds. Such constraints have natural motivations arising from local relaxation times of physical systems in response to point perturbations (in particular, the authors mention laser spot thermography, and measurements of the properties of cartilage). Further, the associated problem in multi-armed bandits has seen interest in the recent literature. In the BCO setting, this blocking constraint raises new challenges which occupy the study in this paper. As pointed out in the appendix, the continuous domain throws new challenges (e.g., simple greedy comparators cannot be defined).

The authors first identify a natural comparator for this problem, namely a minimal cost ε\varepsilon-packing of size pp. It is further argued that it suffices to restrict oneself to finding a good packing with a ball of radius 2pε2p\varepsilon near a point of low cost---the optimal such packing near a point zz has suboptimality bounded by f(z)−f∗f(z) - f_{*}.

This observations also naturally sets up a two phase scheme: the authors first run a vanilla BCO routine to find a near-optimal point, and then refine the space near it to find a good packing.

  • The main challenge in running the BCO routine is that such a routine would likely pick actions that don't respect the blocking constraint. This is handled by introducing a generic "transfer" widget, whereby in ≤H\le H steps, one can feasibly transfer from playing points in any one packing to another. This worst case transition time HH is characterised, via a volume argument, as ≤2p−1\le 2p-1 for any domain that contains a ball of radius at least 2ε(2p)1/d2\varepsilon (2p)^{1/d}, where dd is the ambient dimension, and (via construction) as ≤4p2+3p\le 4p^2 + 3p for any domain that contains a line of length at least pεp\varepsilon (with further refinements). This phase of the proposed algorithm amounts to allocating a certain number of rounds of the underlying BCO procedure, with the added restriction that the number of trajectory transfers utilised is limited, since each such trajectory transfer can lead to Θ(H)\Theta(H) cost. This is enabled by using a method of Agrawal et al., and carefully accounting for the number of query switches within (which is shown to be of the form Cdlog⁡(T)C_d \log(T)).
  • In the second phase, the authors adopt an LCB strategy: an appropriately sized ball around the output of the vanilla BCO procedure is discretised, and a LCB is constructed for the value in each cell (by pooling all visits to the cells). Then, in a batchwise way, this LCB is optimised over choices of packings (within this restricted domain), and the batch size is set so that either a new cell is visited, or so that at least one cell that the packing visits has its visit count increased by a fixed constant factor. Note that this geometric increase means that the number of times a new packing is picked is limited, and so the potential transfer costs are limited too. These transfer costs are further controlled by combining the ball and diameter constructions above to generate a new transfer trajectory that stays close to the near-optimal point, and so does not incur too much cost.
  • Optimising the vanilla BCO budget and the radii and length of the second phase leads to, under the assumption of the domain containing a large enough ball, a regret bound of the form O~d,σ(pT(1+(εpT)d/(d+2)),\tilde{O}_{d, \sigma}(\sqrt{pT} (1 + (\varepsilon \sqrt{pT})^{d/(d+2)} ), where it is worth noting that the hidden dd-dependent terms are polynomial. A nice sanity check is that if ε\varepsilon is ≲1/T\lesssim 1/\sqrt{T}, this bound reduces to the standard T\sqrt{T} (which makes sense since vanilla BCO is stable to such a small jitter), whereas for large ε,\varepsilon, the overhead due to blocking constraints is significant.

This upper bound is complemented by a minimax lower bound of Ω(Tpoly(p)(1+(εT)(d−1)/(d+3)).\Omega(\frac{\sqrt{T}}{\mathrm{poly}(p)} (1 + (\varepsilon \sqrt{T})^{(d-1)/(d+3)} ). While it doesn't exactly match the upper bound, it gets fairly close, and clearly illustrates 'nonparametric rates' in the regime of large ε\varepsilon. It should be noted that the lower bound is stated on a domain that satisfies the large ball condition above. The construction and argument underlying this are suprisingly simple: a quadratic-linear map, with a localised bump perturbation, and a relatively straightforward statistical accounting. The key difference from vanilla BCO lies in the structure of the solution when p>1p > 1 for a quadratic objective: due to blocking, optimal packings have points far away from zero, which gives an opportunity to introduce a large amount of highly localised perturbations.

Finally, in the specific case of p=2,p = 2, the authors improve the regret upper bound to match the lower bound. Recall that in the case of p=2,p = 2, we're looking for a pair (x,y)(x,y) that is ε\varepsilon-far. The authors discretize the set of \emph{directions of difference} between xx and yy, exploiting the fact that the separation condition can then be written as a condition that is affine in (x,y)(x,y) and the difference direction uu. Then, one can separately optimise over this difference, and for each difference, over the best pair satisfying the appropriate affine condition (which is convex, so BCO can be used). In particular, a LCB-style approach is used over the directions. The algorithm attaches a number of visits to each direction in a net, and in each phase, first, a direction with the lowest LCB is picked, and its visit budget is doubled. Then a BCO algorithm over joint choices of (x,y)(x,y) is run for the available budget (with the above constraint on (x,y)(x,y) ). This approaches the optimum in an interated way (min⁡umin⁡(x,y)∈Kuf(x)+f(y)\min_{u} \min_{(x,y) \in K_u} f(x) + f(y)). The main win comes from the fact that a sphere is discretised instead of a ball.

Critical strengths

I think this is a nice paper. The problem has natural motivations and is timely, and thus would be of interest to the online learning/bandits communities at ICLR. The paper does a good job contextualising both the problem and its results. The main text is well written, and the intuitions behind the approach and argument comes through well, especially in the achievability sections (3,5). The exposition makes the results appear almost simple, but the details are intricate, and well executed. I have read most of the proofs, and to my reading these are correct.

Critical weaknesses

There's a couple of natural limitations: the setting is restricted to stochastic bandits, and the algorithms used tend to have large exponents in their dimension dependence, both of which are negatives. Computationally, the algorithms require access to an oracle which solves an NP-hard problem, but perhaps this is okay because the full-information problem is already NP-hard. However, even given this oracle, the LCB phase of the main algorithm requires maintaining Ω(Td/(d+2))\Omega(T^{d/(d+2)}) chunks, so makes the cost per round quite large with TT. Nevertheless, I think these limitations don't detract too much from the paper.

A couple of things that I think would improve the paper are thus:

  • In the lower bound section, it would be helpful to describe where the argument uses p≥2p \ge 2. This is the main point of separation from the vanilla BCO case, and it doesn't come through in the main text. In fact, it doesn't come through in the appendix either. Like, it's almost confusing, because H.2-H.5 read just like typical bandit lower bound arguments, whereas the main point is (as far as I understand) (41), in that the fact that r∗>1/2r_* > 1/2 is the crucial resource that enables a large net of perturbations. I don't know if this is too technical to communicate, but it would be good to give some intuition for the basic separation from vanilla BCO here from the lower bound side.
  • It would help to remove symbol overload, which happens a lot. The biggest example is BB: B(P),Bˉ,Bd,B(n)B(P), \bar{B}, B_d, B(n) are all semantically very distinct objects (not to mention Sec.H.3 where you end up writing B(0,B)B(0,B)). Other clashes: KzK_z and KuK_u are quite distinct kinds of sets; vj,vε,vdv_j, v_{\varepsilon}, v_d are different types of objects. Also, in the proof of Lemma 3.1, DaD_a is confusing since DD meant diameter before (within the same proof). Incidentally, it should be noted that the DD in the buffer radius (line 889) is the diameter.

Some other writing notes:

  • Lemma 3.1. Presumably this should say "Assume that ∃c∈X,r0∈R\exists c \in \mathcal{X}, r_0 \in \mathbb{R} such that" instead of just "Assume"
  • Line 708: this is written a bit confusingly, since the second inequality is a combination of the first and the vertex count, so doesn't come directly from edge counting. Maybe just a "and thus" before the second inequality would be enough.
  • Line 1518: similarly to the above, the second inequality is due to the independence of the VVs, not "Pinsker applied to..". This might just be a style thing, but I saw this pattern recur a couple more times, and IMO it is clearer to explicitly declare which amongst a series of steps an argument is for.
Questions for authors

In the lower bound construction, all the action is in the quadratic region. Given that, I'm kind of confused as to why a linear region is needed at all. In other words, why can't I just set B=1B = 1? Everything important still goes on in a ball of radius 2rpε<12 r_p \varepsilon < 1. I guess the value gets decreased by a factor of 1/B,1/B, but I didn't see BB showing up explicitly in H.5, so it seems like this can just be absorbed there?

1 comment

Thank you for your helpful and constructive feedback. We have revised the manuscript to clarify the role of p≥2p\ge2 in the lower bound, reduce notation overload, and correct the presentation issues you identified.

We agree that the construction of lower bounds only uses perturbations inside the quadratic region. For the quadratic region, the reason we choose ρquad=2rpε\rho_{\rm quad}=2r_p\varepsilon rather than ρquad=1\rho_{\rm quad}=1 is to keep the baseline globally Lipschitz on the unit ball, while maintaining the curvature of the functions in the meantime. Since the original function ∇2f0(x)=12ρquadI\nabla^2 f_0(x)=\frac{1}{2\rho_{\rm quad}}I in the quadratic region, other functions are constructed based by adding perturbations of depth Δ\Delta, each supported on a ball of radius ss. Their Hessians satisfy

\left(\frac{1}{2\rho_{\rm quad}}-\frac{\Delta}{4s^2}\right)I.$$ With $s^2=\rho_{\rm quad}\Delta$ the perturbed functions preserves enough curvature. With our choice of $\rho_{\rm quad}=2r_p\varepsilon$, the support radius is $s=\Theta(\sqrt{\varepsilon\Delta})$; if $\rho_{\rm quad}=1$, it would instead be $\Theta(\sqrt{\Delta})$. When applying Lemma H.5, the choice of $\rho_{\rm quad}$ affects the packing bound through the support radius $s$. With $R=\varepsilon r_\star\geq\varepsilon/2$ and $s=\sqrt{\rho_{\rm quad}\Delta}$, we obtain $$M\geq\left(\frac{R}{2s}\right)^{d-1} \geq\left(\frac{\varepsilon^2}{16\rho_{\rm quad}\Delta}\right)^{(d-1)/2}.$$ Setting $\rho_{\rm quad}=\Theta(\varepsilon)$ gives $M\gtrsim_{d,p}(\varepsilon/\Delta)^{(d-1)/2}$, whereas $\rho_{\rm quad}=1$ gives only $M\gtrsim(\varepsilon^2/\Delta)^{(d-1)/2}$. Combining the two respective bounds with $\Delta^2T\lesssim M$, we have $$\begin{aligned} \rho_{\rm quad}=2r_p\varepsilon: &\quad \Delta\asymp_{d,p} \varepsilon^{\frac{d-1}{d+3}}T^{-\frac{2}{d+3}},\\ \rho_{\rm quad}=1: &\quad \Delta\asymp_{d,p} \varepsilon^{\frac{2(d-1)}{d+3}}T^{-\frac{2}{d+3}}. \end{aligned}$$ where the difference in the $\varepsilon$​ dependence will lead to the difference on the regret lower bounds. In short, the outer linear region allows higher curvature in the $O(\varepsilon)$ region while preserving global Lipschitzness, and thereby enabling smaller perturbation supports and the stronger lower bound.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.