- 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 , every point within distance () 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 ()-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 (), with an additive loss controlled by (). 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 , an upper bound of order It also proves a lower bound on the Euclidean unit ball of order 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 () 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
-
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-() 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.
-
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 (), 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
-
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.
-
The upper bounds are primarily information-theoretic rather than computationally implementable Algorithm 1 assumes an optimization oracle that finds a ()-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 (), 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
-
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.
-
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 ()? 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)?
-
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.
-
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
Question 2.
We require that the action space should have a polynomial-time separation oracle, a known inball , and a known diameter bound . Under the inball condition,
For Algorithm 1, the feasible packing containing a given query 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 points requires samples in expectation. Lemma G.5 then moves the packing into using line-segment operations. Similarly, the buffer in Lemma F.1 can be constructed by rejection sampling from a known ball inside . These operations can be done within polynomial time. The main computational difficulty is the LCB packing oracle. The "refine" phase need at most oracle calls, where . 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 and the blocking period 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 partition cells, we can enumerate at most cell assignments. For each assignment, feasibility can be checked through polynomial constraints in variables, including for . 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 in paper was chosen for simplicity and can be looser for our regret bound. Denote the oracle error as . As shown in the revised proof of Lemma G.4, the oracle error adds at most regret per complete packing cycle. Since there are at most such cycles, the total additional regret is at most . 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 is already sufficient to preserve the stated regret rate.
Algorithm 2 avoids the nonconvex packing oracle by introducing convex branches . Each branch has a separation oracle that requires at most two separation-oracle calls for and one linear-constraint check. Moreover, since and , each branch contains the explicit inball . Each branch is also contained in a ball of radius . Thus, its geometric condition ratio is at most .
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 . The transfers can also be constructed efficiently. Since , the known inball provides three -separated parking points. Lemma B.1 then guarantees that each transfer requires at most 10 physical rounds. The number of convex branches satisfies , where . With , we obtain .
Algorithm 2 processes at most virtual observations and starts at most convex-bandit runs. Let and denote the separation-oracle costs per observation and per initialization of a convex-bandit run. With standard oracle-based implementations, both are polynomial in , , and . Thus, the total number of separation-oracle calls is bounded by . Consequently, a conservative bound on the total computational complexity is , where is the time for one separation-oracle call at the required precision .
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 . In contrast, Algorithm 2 only have a polynomial-time implementation for fixed using only standard convex-oracle.
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 d and p≥2, the minimax regret should be RT∗=Θd,p(T[1+(ϵT)d+3d−1]). We believe the general-period upper bound can be improved. Because our current algorithm for p>2 didn't fully utilize the convexity of the expected objective function during the "refine" period. And for the case of p=2, the upper bound and lower bound match for the ε and T, 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=2. However, both our theoretical results and complementary experiment(Section 6) show that under the instace with p=2, algorithm 2 performs better than algorithm 1. So we guess new approach are needed for the case of p>2,
However, extending direction covering approach to p>2 is potentially difficult. For p=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 ε. 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=2. However, when p>2, (2p) pairwise separation constraints must hold simultaneously. This raises the difficulty of extend the direction-covering approach. For example, an equilateral triangle with side length ϵ is a possible geometry of the constraint, while three points lie in one line with edge length ϵ is also available and can be the optimal solution under some objective functions. To extend this approach to p>2, one possible way is to assign a separate direction uij to each pair (i,j) and define convex branches using the linear constraints ⟨uij,xi−xj⟩≥ϵ(1+θ2), for i<j, where θ is the computation accuracy to discretise. However, covering all directions uij would require up to O(θ−q) branches, where q=(d−1)(2p). Moreover, these directions are mutually coupled, so the argument used by p=2 does not directly apply. Therefore, achieving the desired rate for p>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=2, ε=1, and X=[0,1]. The packing {0,1} is feasible. However, if the algorithm first selects x=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=3, ε=1, and the two-dimensional disk X=B(0,1/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)=32(1±3x1)3. 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) 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.