- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies adversarial nonlinear combinatorial bandits with semi-bandit feedback. The authors establish regret lower bounds for arbitrary interaction orders using parity perturbations and finite differences. They also derive upper bounds using a Möbius decomposition and exponential weights. For certain polynomial families, the upper and lower bounds match up to logarithmic factors for fixed , with constants independent of the polynomial coefficients. The paper further establishes a regret separation between semi-bandit and Bernoulli scalar feedback and derives additional upper bounds using polynomial approximation.
Critical strengths
- Theorem 1 establishes regret lower bounds under semi-bandit feedback by constructing hidden dependencies among any arms, with explicit dependence on the reward function.
- Theorem 3 establishes matching regret bounds for nonnegative polynomial mixtures, uniformly over the polynomial coefficients.
Critical weaknesses
- The presentation is difficult to follow. The paper introduces many unnecessary terms, such as "amplitude-sensitive regret", "matching amplitude law", "hidden–observable interaction bridge", and "polynomial-approximation envelope", which make the main ideas harder to understand.
- The Introduction could explain the problem background, motivation, and main contributions more clearly. It relies too heavily on abstract and unnecessarily complicated language rather than concrete explanations.
- The technical novelty of Theorem 1 is not sufficiently clear. Simchowitz et al. (2016) already used a similar parity construction to establish lower bounds under semi-bandit feedback. The authors could better explain what new technical difficulties arise when extending this construction to general nonlinear reward functions and arbitrary interaction orders.
Questions for authors
- Theorem 3 establishes matching regret bounds for polynomial mixtures under semi-bandit feedback. Since exact aggregate feedback also allows the learner to compute each polynomial term, could the same bounds, including their dependence on the polynomial coefficients, be achieved using only exact aggregate feedback?
- Could the authors explain more clearly the main technical advances relative to Simchowitz et al. (2016) and Han et al. (2021)?
5 comments
Response to iiuC Part 2: Exact aggregate feedback suffices for coefficient-uniform matching
Yes: exact aggregate feedback suffices for the fixed-, coefficient-uniform matching rates. We have added Proposition 6 and its proof in Appendix C.3. The result preserves all coefficient weights under one policy and also covers signed polynomial links.
1. An aggregate-only upper bound matches the polynomial rates [Q1: sufficiency of exact aggregates]
Let , with real coefficients, , , and . Proposition 6 gives $ \mathfrak R_{\mathrm{AGG}}(g,N,K,T) \le\sum_{j=1}^d|\beta_j| \min\left\{T,\sqrt{\frac12\binom Nj T\log M}\right\}. $
Here the learner observes only .
Write and . Since , the upper bound has the same fixed- rate as . The semi-bandit lower bound also applies to the less informative aggregate model. Hence, for , , uniformly over the coefficients.
For the positive mixtures and reflected concave family in Theorem 3, this gives with the original mixture weights. The statement matches the fixed- rates, rather than asserting identical dependence on every parameter: the aggregate upper bound carries an additional in each square-root term relative to the coverage scale.
Revision: Proposition 6 states the explicit bound as equation (22). Appendix C.3 proves it and its matching lower bound.
2. One policy exploits all observed monomials [Q1: why computing the terms is sufficient]
Your observation supplies the key feedback property: reveals every normalized monomial . Each monomial has a linear representation of dimension on the fixed-cardinality action set. The remaining step is to retain all coefficient weights while using one action sequence and one comparator.
We adapt the rank-based information argument of [1], followed by Bayesian minimax duality [2]:
-
Fix any prior over the entire oblivious outcome sequence. Let be the best fixed action in hindsight for the full link , not a separate optimizer for each monomial. Sample the current action from the posterior distribution of this same .
-
Let be the conditional expected regret of component against , and let be the conditional information gain about from the common feedback. The rank bound and Pinsker's inequality give, simultaneously for all , $ |\delta_{t,j}|\le\min\{1,\sqrt{D_jI_t/2}\},\ \sum_{t=1}^T\mathbb E I_t\le\log M. $
-
Summing over time bounds each component by . Multiplying by and summing proves the displayed upper bound for the same posterior policy. Its guarantee is uniform over priors; minimax duality yields an aggregate-only policy for all oblivious sequences.
The common comparator is essential: simply running a separate bandit algorithm for each polynomial term would not provide a single action sequence achieving their summed guarantees. Appendix C.3 gives the full common-policy argument and a finite-signal justification of the minimax step.
3. What this establishes about the feedback comparison [Q1: consequence for the paper's conclusions]
Recovering individual subset products is sufficient for the explicit coordinate estimator in Section 4, but is not necessary for the fixed- polynomial matching rates. Proposition 6 establishes that sufficiency using only exact aggregates.
Consequently, the fixed-range separation in Theorem 5 also holds between exact aggregate feedback and Bernoulli scalar feedback. For example, at , , and , the same range-one quadratic link has aggregate-feedback regret and Bernoulli-feedback regret . Since this link is strictly increasing, its exact scalar reward also determines the aggregate.
Revision: The Introduction now states aggregate sufficiency; Section 6 provides Proposition 6 and its proof idea; Theorem 5 explicitly extends the matched rates and separation to aggregate feedback.
Thank you again for your feedback.
[1] Russo and Van Roy. An Information-Theoretic Analysis of Thompson Sampling. JMLR, 17(68):1–30, 2016.
[2] Lattimore and Szepesvári. An Information-Theoretic Approach to Minimax Regret in Partial Monitoring. COLT, 2019.
Follow-up to iiuC on aggregate feedback and the technical contributions
Thank you again for your thoughtful questions. Your aggregate-feedback question led us to establish Proposition 6, showing that exact aggregates suffice for the fixed-action-size, coefficient-uniform matching rates. Our responses also explain the signed-polynomial extension and the technical distinctions from prior work. We would greatly appreciate your perspective on whether these results and explanations address your concerns, and would welcome the opportunity to discuss any remaining questions.
Response to iiuC Part 1: Coefficient-uniform matching and its technical advances
Thank you very much for recognizing the all-order lower bound and coefficient-uniform matching result. Your perceptive comments helped us sharpen the technical positioning and presentation. Your aggregate-feedback question also led to an affirmative result, now Proposition 6, explained in our second response.
1. The main advance is a coefficient-uniform regret characterization [W3; Q2: what is added beyond the existing lower bounds]
The central result characterizes how polynomial coefficients enter minimax regret, uniformly even when they vanish with N or T. Theorem 3 establishes this for positive mixtures and reflected concave links. The revision extends it to every g(z)=β0+∑j=1dβj(z/K)j with real coefficients and g([0,K])⊆[0,1]: for N≥2K and 1≤d≤K, $ \mathfrak R_{\mathrm{SB}}(g,N,K,T) =\widetilde\Theta_{K,d}\left( \sum_{j=1}^d|\beta_j| \min\left\{T,\sqrt{\frac{\binom Nj}{\binom Kj}T}\right\} \right). $
The comparison constants are independent of the coefficient vector. For example, gϵ(z)=(1−ϵ)z/K+ϵ(z/K)d has degree d for every ϵ>0, but its matched rate weights the high-order cost by ϵ. It quantifies changes in difficulty that fixed-link exponents leave in link-dependent constants.
Simchowitz et al. [1] established dependence hiding for a max objective, including semi-bandit lower bounds and adversarial-regret consequences. Han et al. [2] established degree-dependent adversarial rates under noisy scalar feedback. Our characterization connects an explicit general-link lower certificate to an achievable, coefficient-sensitive upper bound under exact observations.
Theorem 1 computes the reward response through an averaged finite difference and accounts for the (sK) candidate supports exposed per action. The construction preserves full coordinate-observation laws whenever the hidden support is not covered. The upper bound completes the comparison by charging estimation according to the ranges of observable subset contributions.
Revision: The Introduction foregrounds coefficient-uniform matching. Updated Table 1 compares [1,2]; Sections 3–4 explain the lower–upper connection.
2. Varying the step size resolves signed cancellation [W3; Q2: the technical extension beyond positive mixtures]
With signed coefficients, a nonzero component may disappear from the reward separation at a particular scale. We address this by varying the perturbation step h. For each order s, define Hs(h)=2−sEJ∼Bin(K−s,1/2)[Δhsg(hJ)]. It is a polynomial in h whose hs coefficient equals βss!/(2sKs).
Polynomial interpolation bounds this coefficient by Adsuph∈[0,1]∣Hs(h)∣, where Ad=(4d)d/d!, and the supremum is at most Γs(g;K). Thus a signed coefficient cannot cancel at every step size. For example, K=2 and g(z)=2z−z2 give H1(h)=h−h2: the unit-step separation vanishes, but H1(1/2)=1/4.
This produces a coefficient-wise lower bound that pairs with the absolute-coefficient upper bound. It also proves bs(g)≤2sAdΓs(g;K) for s≤d, directly relating observable estimation widths to hidden reward amplitudes.
Revision: Section 4.3 and Appendix B.8 establish signed-polynomial matching and the certificate comparison. The positive and reflected families retain sharper constants.
3. Exact aggregates suffice through one shared policy [Q1: a new matching theorem]
Your aggregate-feedback question has a positive answer. Proposition 6 proves the same fixed-K coefficient-uniform rates from the exact selected sum alone, including signed polynomial links.
The key step combines all observed monomials under one policy, one best-in-hindsight comparator for the full link, and one information budget. This retains the coefficient weights while respecting the requirement to choose a single action each round. Our second response gives the explicit bound and the common-policy proof.
Revision: Proposition 6 and Appendix C.3 establish this result. Theorem 5 also extends the fixed-range separation to exact aggregate versus Bernoulli feedback.
4. Concrete examples make the results easier to follow [W1–W2: presentation and motivation]
We reduced umbrella terminology and made the Abstract and Introduction result-led. Section 3 begins with a two-arm example of unchanged individual observations and improved joint reward. Section 4 explains the square-link singleton/pair decomposition before giving the explicit policy. The Introduction states the weak-component motivation, main rate, and a concrete feedback separation.
[1] Simchowitz, Jamieson, and Recht. Best-of-K Bandits. COLT, 2016.
[2] Han, Wang, and Chen. Adversarial Combinatorial Bandits with General Non-linear Reward Functions. ICML, 2021.