acceptodds
Under review as a conference paper at ICLR 2027

Adversarial Nonlinear Semi-Bandits: Hidden Interactions and Amplitude-Sensitive Regret

Abstract

Semi-bandit feedback reveals every selected base-arm outcome, yet nonlinear rewards can hide information in interactions that are observed only jointly. For every order , we construct an -way dependence whose proper marginals are unchanged and prove regret . The finite-difference certificate measures how strongly the known link values the hidden interaction. Selected coordinates also make every interaction supported inside the chosen action observable. A M\"obius decomposition turns this fact into an amplitude-sensitive upper bound , where is the range of an order- observable coefficient. For every fixed action size , the two bounds characterize minimax regret up to logarithmic factors, uniformly over normalized nonnegative polynomial mixtures and a reflected family of monotone concave links. The characterization includes links with a weak high-order component: their rate has a linear baseline and an amplitude-weighted high-order term. Finally, at fixed reward range, we prove that semi-bandit minimax regret is asymptotically smaller than under Bernoulli scalar feedback over a continuous parameter regime. Exact aggregate feedback additionally yields a complementary polynomial-approximation envelope.

Primary area:
learning theory
Keywords:
adversarial bandits, combinatorial semi-bandits, higher-order interactions, minimax regret, nonlinear rewards

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_iiuCOpenReview ↗
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 KK, 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 s≤Ks\le K 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
AuthorsOpenReview ↗

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 NN or TT. 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)jg(z)=\beta_0+\sum_{j=1}^d\beta_j(z/K)^j with real coefficients and g([0,K])⊆[0,1]g([0,K])\subseteq[0,1]: for N≥2KN\ge2K and 1≤d≤K1\le d\le 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)dg_\epsilon(z)=(1-\epsilon)z/K+\epsilon(z/K)^d has degree dd for every ϵ>0\epsilon>0, but its matched rate weights the high-order cost by ϵ\epsilon. 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 (Ks)\binom Ks 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 hh. For each order ss, define Hs(h)=2−sEJ∼Bin(K−s,1/2)[Δhsg(hJ)]H_s(h)=2^{-s}\mathbb E_{J\sim\mathrm{Bin}(K-s,1/2)}[\Delta_h^s g(hJ)]. It is a polynomial in hh whose hsh^s coefficient equals βss!/(2sKs)\beta_s s!/(2^sK^s).

Polynomial interpolation bounds this coefficient by Adsup⁡h∈[0,1]∣Hs(h)∣A_d\sup_{h\in[0,1]}|H_s(h)|, where Ad=(4d)d/d!A_d=(4d)^d/d!, and the supremum is at most Γs(g;K)\Gamma_s(g;K). Thus a signed coefficient cannot cancel at every step size. For example, K=2K=2 and g(z)=2z−z2g(z)=2z-z^2 give H1(h)=h−h2H_1(h)=h-h^2: the unit-step separation vanishes, but H1(1/2)=1/4H_1(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)b_s(g)\le2^sA_d\Gamma_s(g;K) for s≤ds\le 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-KK 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.

AuthorsOpenReview ↗

Response to iiuC Part 2: Exact aggregate feedback suffices for coefficient-uniform matching

Yes: exact aggregate feedback suffices for the fixed-KK, 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 g(z)=β0+∑j=1dβj(z/K)jg(z)=\beta_0+\sum_{j=1}^d\beta_j(z/K)^j, with real coefficients, g([0,K])⊆[0,1]g([0,K])\subseteq[0,1], 1≤d≤K1\le d\le K, and M=(NK)M=\binom NK. 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 zt=∑i∈Stvt,iz_t=\sum_{i\in S_t}v_{t,i}.

Write qj=(Kj)/(Nj)q_j=\binom Kj/\binom Nj and F∣β∣=∑j∣βj∣min⁡T,T/qjF_{|\beta|}=\sum_j|\beta_j|\min\\{T,\sqrt{T/q_j}\\}. Since (Nj)=(Kj)/qj\binom Nj=\binom Kj/q_j, the upper bound has the same fixed-K,dK,d rate as F∣β∣F_{|\beta|}. The semi-bandit lower bound also applies to the less informative aggregate model. Hence, for N≥2KN\ge2K, RAGG=Θ~K,d(F∣β∣)\mathfrak R_{\mathrm{AGG}}=\widetilde\Theta_{K,d}(F_{|\beta|}), uniformly over the coefficients.

For the positive mixtures and reflected concave family in Theorem 3, this gives Θ~K(Fβ)\widetilde\Theta_K(F_\beta) with the original mixture weights. The statement matches the fixed-KK rates, rather than asserting identical dependence on every parameter: the aggregate upper bound carries an additional (Kj)\sqrt{\binom Kj} 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: ztz_t reveals every normalized monomial (zt/K)j(z_t/K)^j. Each monomial has a linear representation of dimension Dj≤(Nj)D_j\le\binom Nj 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 A⋆A^{\star} be the best fixed action in hindsight for the full link gg, not a separate optimizer for each monomial. Sample the current action from the posterior distribution of this same A⋆A^{\star}.

  • Let δt,j\delta_{t,j} be the conditional expected regret of component jj against A⋆A^{\star}, and let ItI_t be the conditional information gain about A⋆A^{\star} from the common feedback. The rank bound and Pinsker's inequality give, simultaneously for all jj, $ |\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 min⁡T,DjTlog⁡M/2\min\\{T,\sqrt{D_jT\log M/2}\\}. Multiplying by ∣βj∣|\beta_j| 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-KK 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 K=2K=2, ϵ=N−1/4\epsilon=N^{-1/4}, and T=⌈N5/2⌉T=\lceil N^{5/2}\rceil, the same range-one quadratic link has aggregate-feedback regret Θ~(N2)\widetilde\Theta(N^2) and Bernoulli-feedback regret Θ(N9/4)\Theta(N^{9/4}). 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.

AuthorsOpenReview ↗

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.

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

The paper studies adversarial combinatorial bandits with a known nonlinear reward function and semi-bandit feedback revealing every selected coordinate. It constructs hidden high-order interactions that preserve all proper marginals and derives regret lower bounds through finite-difference certificates. A complementary Möbius decomposition yields amplitude-sensitive upper bounds. For fixed action size, these bounds match up to logarithmic factors and action-size-dependent constants for specified positive polynomial mixtures and reflected concave families. The paper also compares different feedback models and provides numerical illustrations of the theoretical bounds.

Critical strengths
  1. The amplitude-sensitive characterization is a meaningful contribution. Classifying difficulty solely by polynomial degree can obscure the behavior of links whose nonlinear coefficients vanish with problem size. The paper retains these coefficients explicitly and characterizes the transition between a linear baseline and costly higher-order interactions. This substantially improves the interpretation of nonlinear-bandit complexity.

  2. The lower and upper bounds provide complementary explanations of the information structure. Marginal-preserving perturbations demonstrate what selected-coordinate feedback cannot reveal, while observable Möbius coefficients identify the interactions it can exploit. The resulting connection between hidden dependence, interaction strength, and regret is technically substantive and informative.

Critical weaknesses
  1. The matching characterization has important scope restrictions. It holds for fixed action size KK, with matching constants that can grow exponentially in KK, and for structured link families whose positivity properties prevent cancellation. Consequently, the results do not provide a satisfactory characterization when KK grows, or for general signed polynomial and nonlinear links. Although these qualifications are acknowledged, they substantially limit the breadth of the minimax conclusion.

  2. The upper-bound algorithms are primarily information-theoretic. Maintaining a distribution over (NK)\binom{N}{K} actions can be computationally prohibitive, and the manuscript does not establish an efficient implementation for the general problem. The numerical illustrations evaluate theoretical expressions rather than the regret of an implemented learning algorithm. The statistical characterization is therefore stronger than the demonstrated algorithmic contribution.

Questions for authors
  1. Could you summarize the explicit dependence on KK in the matching constants and identify the parameter regimes in which the upper and lower bounds remain quantitatively comparable? Please distinguish uniformity in the link amplitudes from dependence hidden in fixed-KK constants.

  2. Which operations in the upper-bound algorithm require enumerating actions or subsets? Do the existing results provide a computationally efficient implementation for any nontrivial subclass beyond linear rewards?

  3. Outside the positive polynomial and reflected families, what prevents the lower certificates Γs\Gamma_s and upper coefficient ranges bsb_s from yielding matching bounds? Please clarify whether the limitation arises from cancellation in the current proof or from an identified separation between these quantities.

4 comments
AuthorsOpenReview ↗

Response to Tp5p Part 1: Explicit constants and matching beyond positive mixtures

Thank you very much for recognizing the value of coefficient-uniform guarantees and the complementary roles of the lower and upper bounds. Your perceptive comments helped us make the dependence on KK explicit and extend matching beyond positive mixtures. In particular, the revision resolves the cancellation issue for signed polynomial links of degree at most KK.

1. Coefficient uniformity and dependence on KK are separate [W1; Q1: explicit constants and comparable regimes].

Assume N≥2KN\ge2K. Write qj=(Kj)/(Nj)q_j=\binom Kj/\binom Nj, ψj(T)=min⁡T,T/qj\psi_j(T)=\min\\{T,\sqrt{T/q_j}\\}, and Fβ=∑j=1dβjψj(T)F_\beta=\sum_{j=1}^d\beta_j\psi_j(T). For positive mixtures with βj≥0\beta_j\ge0, ∑jβj=1\sum_j\beta_j=1, supported on degrees at most d≤Kd\le K, and their reflected concave family, the revised comparison constant is $ c_{K,d}=\left(16\sum_{s=1}^d\frac{2^sK^s}{s!}\right)^{-1},\ \frac{d!}{32,2^dK^d}\le c_{K,d}\le\frac{d!}{16,2^dK^d}. $

With M=(NK)M=\binom NK, the bounds are cK,dFβ≤RSB≤2max⁡1,log⁡MFβc_{K,d}F_\beta\le\mathfrak R_{\mathrm{SB}}\le2\max\\{1,\sqrt{\log M}\\}F_\beta. Neither comparison factor depends on β\beta, even if its entries depend on N,TN,T or approach zero.

These formulas distinguish three regimes:

  • Fixed KK: the bounds match up to logarithmic factors, uniformly over the coefficient simplex.
  • Fixed degree dd with growing KK: cK,d=Θd(K−d)c_{K,d}=\Theta_d(K^{-d}). The ratio of the displayed upper and lower certificates is at most 2max⁡1,log⁡M/cK,d2\max\\{1,\sqrt{\log M}\\}/c_{K,d}, so the loss is polynomial in KK, in addition to the displayed logarithmic factor.
  • Full degree d=Kd=K: cK,K=Θ(K(2e)−K)c_{K,K}=\Theta(\sqrt K(2e)^{-K}). Thus the theorem does not give a constant-factor characterization uniformly in growing KK.

For a particular coefficient vector, the stronger certificate Lβ=116max⁡1≤s≤dβss!ψs(T)/(2sKs)L_\beta=\frac1{16}\max_{1\le s\le d}\\{\beta_s s!\psi_s(T)/(2^sK^s)\\} should be used before replacing it by cK,dFβc_{K,d}F_\beta. For example, for K=d=2K=d=2 and gϵ(z)=(1−ϵ)z/2+ϵ(z/2)2g_\epsilon(z)=(1-\epsilon)z/2+\epsilon(z/2)^2, it gives RSB≥max⁡(1−ϵ)ψ1(T)/64,ϵψ2(T)/128\mathfrak R_{\mathrm{SB}}\ge\max\\{(1-\epsilon)\psi_1(T)/64,\epsilon\psi_2(T)/128\\}. This retains the individual scales even when ϵ\epsilon vanishes.

Revision: Theorem 3 retains LβL_\beta in the main inequality. Section 4.2 and Appendix B.5 give cK,dc_{K,d} and its degree-dependent bounds; the scope statement distinguishes fixed-KK matching from growing-KK tightness.

2. Cancellation can be controlled for signed polynomials [W1; Q3: beyond the positive and reflected families].

The original positivity restriction was a limitation of the single-scale comparison, not an established separation. The revision removes that restriction for all bounded polynomial links of degree at most KK.

Let g(z)=β0+∑j=1dβj(z/K)jg(z)=\beta_0+\sum_{j=1}^d\beta_j(z/K)^j, with real coefficients and g([0,K])⊆[0,1]g([0,K])\subseteq[0,1]. For a fixed order ss, vary the parity construction's step size and write Hs(h)=2−sEJ∼Bin(K−s,1/2)[Δhsg(hJ)]H_s(h)=2^{-s}\mathbb E_{J\sim\mathrm{Bin}(K-s,1/2)}[\Delta_h^s g(hJ)]. This is a polynomial in hh whose hsh^s coefficient is βss!/(2sKs)\beta_s s!/(2^sK^s). Polynomial interpolation controls this coefficient by the supremum over h∈[0,1]h\in[0,1], which is at most Γs(g;K)\Gamma_s(g;K). With Ad=(4d)d/d!A_d=(4d)^d/d!, this gives $ \Gamma_s(g;K)\ge\frac{|\beta_s|s!}{A_d2^sK^s},\ b_s(g)\le2^sA_d,\Gamma_s(g;K),\ 1\le s\le d. $

Thus opposite signs may cancel at one step size, but cannot hide a nonzero coefficient at every step size. For example, at K=2K=2, g(z)=2z−z2g(z)=2z-z^2 has H1(h)=h−h2H_1(h)=h-h^2: the unit-step value is zero, whereas h=1/2h=1/2 gives 1/41/4.

Using absolute coefficients in the upper bound and the preceding lower estimate yields (cK,d/Ad)F∣β∣≤RSB≤max⁡1,2log⁡MF∣β∣(c_{K,d}/A_d)F_{|\beta|}\le\mathfrak R_{\mathrm{SB}}\le\max\\{1,\sqrt{2\log M}\\}F_{|\beta|}, where F∣β∣=∑j∣βj∣ψj(T)F_{|\beta|}=\sum_j|\beta_j|\psi_j(T). Hence fixed-K,dK,d coefficient-uniform matching extends to signed links, with the explicit additional factor AdA_d.

For general non-polynomial links, the degree-bounded coefficient-extraction argument is unavailable. A matching comparison remains unproved; the difference between the certificates alone is not evidence of a minimax separation.

Revision: Section 4.3 gives the signed extension and cancellation example. Appendix B.8 proves both the matching bounds and the direct comparison between bsb_s and Γs\Gamma_s.

AuthorsOpenReview ↗

Response to Tp5p Part 2: Computational implementation and the role of the illustrations

The coordinate-feedback upper bound comes with an explicit exponential-weights policy. Its computational bottleneck is maintaining and updating the distribution over actions, rather than access to the observed subset coefficients. Below we separate the actual operations, the tractable fixed-KK case, and what the numerical illustrations establish.

1. Which operations enumerate actions or subsets [W2; Q2: implementation of the upper bound]

Let M=(NK)M=\binom NK, and let ρt\rho_t be the distribution obtained by normalizing the MM action weights.

OperationDirect implementation
Select an actionNormalize the action weights and sample from their categorical distribution.
Compute observable coefficientsFor each nonempty U⊆StU\subseteq S_t, evaluate cf,U(vt,U)c_{f,U}(v_{t,U}) from the selected coordinates.
Compute inclusion probabilitiesFor each required UU, sum ρt(S)\rho_t(S) over actions S⊇US\supseteq U to obtain qt(U)q_t(U).
Update weightsFor every action SS, sum the estimated losses of observed subsets contained in SS, then update its weight.

For a general link, the selected action contains at most 2K−12^K-1 nonempty subsets. For a degree-dd polynomial, coefficients above order dd vanish, so only ∑s=1d(Ks)\sum_{s=1}^d\binom Ks observed coefficients are needed. A coefficient can be computed by its alternating sum over subsets of UU; the polynomial expansion also gives an explicit way to evaluate it.

The policy therefore needs neither unobserved outcomes nor a reward oracle for unselected actions. However, low degree alone does not eliminate the enumeration of the MM action weights. Theorem 3 uses this same policy on a surrogate whose retained degrees are selected before play.

Revision: Section 4.1 now gives the policy steps and explicitly identifies action enumeration, inclusion-probability computation, and the degree cutoff.

2. Fixed-KK nonlinear subclasses admit a polynomial-time implementation [Q2: computationally tractable cases]

For fixed KK, the direct implementation is polynomial in NN, including for nonlinear polynomial links. For example, with K=2K=2 and a quadratic link, it stores (N2)\binom N2 action weights and observes only three subset coefficients: two singleton terms and one pair term. Scanning the pairs computes the required inclusion probabilities and updates all weights in O(N2)O(N^2) arithmetic work per round, with O(N2)O(N^2) action-weight storage. This implements the quadratic class used in our fixed-range separation.

When KK grows, even degree two can induce pairwise contributions in the action weights; the product structure of a linear objective is no longer automatic. We have not established an implementation polynomial jointly in NN and KK for general nonlinear links.

Proposition 6 establishes aggregate-feedback sufficiency through a minimax existence argument; the explicit implementation described here is the coordinate policy of Section 4.

Revision: Section 4.1 states that the direct implementation is polynomial in NN for fixed KK and identifies the action-weight bottleneck when KK grows. Section 6 distinguishes the aggregate existence result from the explicit coordinate policy.

3. What the numerical illustrations contribute [W2: theoretical expressions versus empirical regret]

The figures evaluate quantities derived from the proved bounds. In Figure 1, the left panel shows when the amplitude-weighted high-order term becomes comparable to the linear baseline; the right panel shows parameter regimes certified to separate exact observations from Bernoulli feedback. They make the finite-horizon implications of the theorems visible, rather than measure the realized regret of an implemented algorithm.

The caption states the normalization and suppressed constant, so these curves are not presented as exact numerical minimax values. The regret guarantees rest on the explicit policy analysis and the lower-bound proofs; the illustrations explain their parameter dependence.

Figure 1 and Appendix E identify the plotted expressions, parameter choices, and interpretation.

Thank you again for your feedback.

Thanks for your response. I will keep my score.

We thank you for considering our response and for your thoughtful feedback. Your questions helped us clarify the quantitative scope and computational aspects of the results. We appreciate the time you have devoted to the paper and would be happy to address any further questions during the discussion.

Reviewer_5Zz8OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

In summary, the paper studies semi-bandit feedback in adversarial nonlinear reward setting with interactions between the arms. Concisely, the paper contributes lower and upper-bounds for this setting, with comparison of the said bounds to the closest ones existing in the literature. The paper is potentially validated through the natural need of lower bounds (establishing the learning limit) and the upper bounds (the provably achievable performance) for this adversarial learning and the proofs for the findings.

Critical strengths

The submission seems technically correct, however it is really hard to follow when it matters most due to missing explanations and notational definitions.

The submission is potentially experimentally rigorous and reproducible but their goal, i.e., how they connect with the findings (theorems) is not apparent.

Critical weaknesses

The submission is not clear. Too much information is presented without proper contextualization.

The submission may present novel findings (theoretically and not algorithmically), however the validation is too much work without proper explanations and the motivation remains weak without a proper algorithm.

Questions for authors

I do not understand hidden interaction. Isn't the link function known? How does this interaction work and affect the rewards and learning exactly?

Line 19: also mention what g, N, T are.

Line 36: define g.

Line 51: is interaction order the degree d, and amplitude epsilon?

Line 55: explain what you mean by "proper marginals have exactly the null law".

Page 2: too much information condensed without proper context. At least explain the meaning of these findings for a broader audience.

Line 164: explain the use of finite difference of g here.

Line 208: is the finite-difference term here the same as the reward-gap in (1)?

Line 219: define the notations here, are they the probabilities to select the optimal arm-set etc.

Theorem 1: explanation can be improved here, what this means etc.

Line 285: also explain the use of B_K.

Theorem 3: how do you combine lower and upper bounds in a single expression. Upper bound requires an exact policy (only the existence shown), while lower bound shows no policy can do better in adversarial setting. Am I missing something?

Line 344: why is B_K here different from earlier?

Line 368: properly define different interactions, weak etc.

5 comments
AuthorsOpenReview ↗

Response to 5Zz8 Part 1: Known rewards, hidden dependence, and the lower bound

Thank you very much for your careful reading and for identifying the explanations that were difficult to follow. We revised our paper in detail to clarify the model and motivation, placed examples before general constructions, and brought the policy into the main text. This response explains the lower bound (covering Q1–Q5 and Q7–Q10); the next covers the policy and matching (covering Q6 and Q11–Q14). Questions are numbered in your review order.

1. The reward rule is known; the dependence is hidden [W1; Q1–Q5: model, interaction order, and marginals].

[Q2–Q3: notation] There are NN arms, the learner selects KK each round, and TT is the horizon. The known link g:[0,K]→[0,1]g:[0,K]\to[0,1] converts the sum of selected outcomes into reward. The outcomes are not known before selection.

[Q1, Q5: what is hidden] Take K=2K=2 and g(z)=(z/2)2g(z)=(z/2)^2. Under a reference environment, all arms produce independent fair bits. Under an alternative, an unknown pair A=i,jA=\\{i,j\\} has probabilities (1+η)/4(1+\eta)/4 for each of (0,0),(1,1)(0,0),(1,1) and (1−η)/4(1-\eta)/4 for each of (0,1),(1,0)(0,1),(1,0), where 0<η≤1/20<\eta\le1/2. All remaining bits are mutually independent and independent of this pair.

Every arm is still a fair bit. Selecting any pair other than AA gives exactly the reference distribution of the entire observed vector. Selecting AA yields a higher expected reward. The learner knows how rewards are computed but must discover which pair has the reward advantage.

“Proper marginals have exactly the null law” means that observations omitting any member of the hidden set have the same full distribution—not just the same mean—as under the reference. Sampling the entire i.i.d. outcome sequence before play gives valid random instances of the oblivious-adversary model.

[Q4: order versus amplitude] The order ss counts coordinates in the hidden dependence; it need not equal the polynomial degree dd. The lower bound treats every 1≤s≤K1\le s\le K. In the weak-component example, ϵ\epsilon weights the known nonlinear term, whereas η\eta perturbs the outcome distribution. The certificate Γs\Gamma_s measures the link's reward response to that perturbation.

Revision: The Abstract now first describes the action, feedback, and known link. Section 2 defines the model; Section 3 puts this pair example before the general construction, making the distinction between a known reward rule and unknown dependence concrete.

2. Finite differences calculate the reward gap [Q7–Q8: why finite differences appear].

In the example, probability mass moves from unequal-bit outcomes to equal-bit outcomes. Therefore, $\mathbb E_A[g(v_i+v_j)]-\mathbb E_0[g(v_i+v_j)] =\frac{\eta}{4}[g(2)-2g(1)+g(0)]=\frac{\eta}{8}.$

The bracket is the second finite difference, arising directly from these probability changes.

For order ss, coordinates take values aa or a+ha+h. The signed coefficient is Gs(a,h)=2−sEJ[Δhsg(Ka+hJ)]G_s(a,h)=2^{-s}\mathbb E_J[\Delta_h^s g(Ka+hJ)], where J∼Bin(K−s,1/2)J\sim\mathrm{Bin}(K-s,1/2) counts high-valued selected coordinates outside the hidden set. After choosing the perturbation's sign, actions containing the hidden set have an expected-reward advantage of η∣Gs(a,h)∣\eta|G_s(a,h)| over those omitting it: the coefficient must be multiplied by η\eta. The certificate Γs\Gamma_s is the supremum of ∣Gs(a,h)∣|G_s(a,h)| over a,h≥0a,h\ge0 with a+h≤1a+h\le1.

Revision: Section 3.2 derives the reward-gap identity, equation (6), before defining Γs\Gamma_s in equation (7), so the certificate follows its reward interpretation.

3. Joint coverage controls discovery [Q9–Q10: notation and Theorem 1].

The coverage fraction qs=(Ks)/(Ns)q_s=\binom Ks/\binom Ns is combinatorial, not the learner's probability of choosing an optimal action. Each action contains (Ks)\binom Ks of the (Ns)\binom Ns candidate hidden sets. Under the reference, expected coverage averaged over candidates is therefore qsTq_sT for every policy.

Here NA(T)N_A(T) counts rounds with A⊆StA\subseteq S_t; P0T,PAT\mathbb P_0^T,\mathbb P_A^T are the history laws under the reference and alternative, and E0,EA\mathbb E_0,\mathbb E_A are their expectations. Observations omitting part of AA provide zero information for distinguishing these environments. The KL bound quantifies information gained on covering rounds.

For N≥2KN\ge2K, Theorem 1 gives $\mathfrak R_{\mathrm{SB}}(g,N,K,T) \ge\frac{\Gamma_s(g;K)}{16}\min\{T,\sqrt{T/q_s}\}.$

Here RSB\mathfrak R_{\mathrm{SB}} is the smallest worst-case expected regret against the best fixed KK-subset in hindsight. The bound separates the reward effect Γs\Gamma_s from the coverage difficulty qs−1q_s^{-1}. For s<Ks<K, many actions contain the same hidden set, and each action covers multiple candidates; the proof accounts for both overlaps.

Revision: Sections 2.3 and 3.3 define the coverage and history notation and explain the two factors in the lower bound.

AuthorsOpenReview ↗

Response to 5Zz8 Part 2: A concrete learning policy and coefficient-uniform matching

For the selected-coordinate model in Theorems 2–3, the upper bound is achieved by an explicit policy. The revised Section 4 now gives its steps before presenting the matching result, so the achievable guarantee can be checked directly in the main text.

1. A concrete policy reuses observable contributions [W2; Q11, Q13: algorithm and BK\mathcal B_K].

For f(z)=(z/K)2f(z)=(z/K)^2, reward separates into singleton terms vi2/K2v_i^2/K^2 and pair terms 2vivj/K22v_iv_j/K^2. Selecting an action reveals each term it contains; an observed pair term can inform every other action containing that pair.

For a general link, define cf,U(vU)=∑V⊆U(−1)∣U∣−∣V∣f(∑i∈Vvi)c_{f,U}(v_U)=\sum_{V\subseteq U}(-1)^{|U|-|V|}f(\sum_{i\in V}v_i). These coefficients reconstruct reward as f(0)+∑∅≠U⊆Scf,U(vU)f(0)+\sum_{\varnothing\ne U\subseteq S}c_{f,U}(v_U). Each coefficient for U⊆StU\subseteq S_t is computable from the selected coordinates.

Let usu_s be the supremum of an order-ss coefficient and set λt,U=u∣U∣−cf,U(vt,U)\lambda_{t,U}=u_{|U|}-c_{f,U}(v_{t,U}). These losses are nonnegative. Their sum over an action equals a constant independent of the action minus its reward, so loss regret equals the original reward regret.

Starting with uniform positive action weights, the policy repeats:

  • Sample StS_t from the normalized weights ρt\rho_t.
  • Compute observed subset losses and inclusion probabilities qt(U)=∑S⊇Uρt(S)q_t(U)=\sum_{S\supseteq U}\rho_t(S).
  • Set λ^t,U=λt,U/qt(U)\widehat\lambda_{t,U}=\lambda_{t,U}/q_t(U) for observed subsets and zero otherwise. Form L^t(S)=∑∅≠U⊆Sλ^t,U\widehat L_t(S)=\sum_{\varnothing\ne U\subseteq S}\widehat\lambda_{t,U} and update wt+1(S)=wt(S)exp⁡(−ηL^t(S))w_{t+1}(S)=w_t(S)\exp(-\eta\widehat L_t(S)).

[Q11: what BK\mathcal B_K controls] Write bs(f)b_s(f) for the range width of an order-ss coefficient. Then BK(f;N)=∑s=1Kbs(f)(Ks)(Ns)\mathcal B_K(f;N)=\sum_{s=1}^K b_s(f)\sqrt{\binom Ks\binom Ns} combines contribution size with subset-estimation cost. It controls the estimator's second moment. With M=(NK)M=\binom NK and learning rate η=2log⁡M/(TBK2)\eta=\sqrt{2\log M/(T\mathcal B_K^2)}, the policy achieves regret at most 2Tlog⁡MBK\sqrt{2T\log M}\mathcal B_K. If BK=0\mathcal B_K=0, all actions have equal rewards.

[Q13: the definition does not change] For gβ+(z)=∑jβj(z/K)jg_\beta^+(z)=\sum_j\beta_j(z/K)^j, with βj≥0\beta_j\ge0 and ∑jβj=1\sum_j\beta_j=1, substituting its coefficient widths into the same definition gives BK(gβ+;N)≤∑jβj/qj\mathcal B_K(g_\beta^+;N)\le\sum_j\beta_j/\sqrt{q_j}, where qj=(Kj)/(Nj)q_j=\binom Kj/\binom Nj. The later expression bounds the original quantity for this link class.

Revision: Section 4.1 now proceeds from the square-link example to loss–reward equivalence, the three policy steps, and the key second-moment argument. Section 4.2 derives the polynomial specialization of the same BK\mathcal B_K.

2. One achievable upper bound and an all-policy lower bound [Q12: how Theorem 3 combines the bounds].

Both bounds use the same fixed link and the same best-fixed-action comparator:

  • The upper bound supplies a policy with bounded expected regret for every oblivious outcome sequence.
  • The lower bound applies to every policy: its worst-case expected regret is at least the stated amount.

Taking the infimum over policies therefore sandwiches the same minimax value. Theorem 3 matches the rate Fβ=∑jβjψj(T)F_\beta=\sum_j\beta_j\psi_j(T), where ψj(T)=min⁡T,T/qj\psi_j(T)=\min\\{T,\sqrt{T/q_j}\\}, up to logarithms and fixed-KK constants independent of β\beta.

To achieve the termwise minima, the policy uses a polynomial surrogate chosen before play: it retains terms worth estimating at the given horizon and treats the others as a residual. The retained terms are learned together by one instance of the policy above.

Revision: Immediately after Theorem 3, the main text distinguishes the two quantifiers and explains how surrogate selection yields the matching upper bound.

3. Why a weak nonlinear term needs a uniform guarantee [W1; Q6, Q14: motivation, interpretation, and illustrations].

Consider gϵ(z)=(1−ϵ)z/K+ϵ(z/K)dg_\epsilon(z)=(1-\epsilon)z/K+\epsilon(z/K)^d, with 2≤d≤K2\le d\le K and 0≤ϵ≤1/20\le\epsilon\le1/2. Every ϵ>0\epsilon>0 gives degree dd, even as the nonlinear term vanishes. For N≥2KN\ge2K, Corollary 4 gives $ \mathfrak R_{\mathrm{SB}}(g_\epsilon,N,K,T) =\widetilde\Theta_{K,d}\bigl(\psi_1(T)+\epsilon\psi_d(T)\bigr). $

This separates the linear baseline from the high-order term, uniformly even when ϵ\epsilon varies with NN or TT. A linear surrogate pays an ϵT\epsilon T residual; estimating the weak term instead gives the statistical term O~K,d(ϵT/qd)\widetilde O_{K,d}(\epsilon\sqrt{T/q_d}) once T≥qd−1T\ge q_d^{-1}. Figure 1 visualizes the proved rate expression and feedback-separation certificate.

Revision: The Introduction now uses this family to explain why degree alone is insufficient before introducing the technical quantities. Section 4.2 interprets both rate terms and their crossover.

Thank you again for your feedback.

AuthorsOpenReview ↗

Follow-up to 5Zz8 on the clarifications and revised presentation

Thank you again for your careful reading and detailed questions. Our two responses explain the hidden-dependence construction through a concrete example and provide the explicit learning policy and the logic behind the matching bounds. These explanations are also incorporated into the revised manuscript. We would greatly appreciate the opportunity to discuss any points that remain unclear, particularly concerning the model, algorithm, or interpretation of the results, and would be happy to provide further clarification here.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions and discussion

We thank the Area Chair for considering our submission and all three reviewers for their careful reading and thoughtful discussion. The central contribution is a coefficient-uniform characterization of minimax regret for polynomial links, including when nonlinear coefficients vanish with problem size.

1. Substantive theoretical additions

  • Matching beyond positive coefficients (Section 4.3; Appendix B.8). In response to Tp5p's concern about the positivity restriction, we extended our matching regret bounds to all polynomial links g:[0,K]→[0,1]g:[0,K]\to[0,1] of degree at most KK, for fixed KK and N≥2KN\ge 2K. The key idea is to vary the finite-difference step size to handle cancellation between positive and negative coefficients. The resulting rates match up to logarithmic factors, with constants independent of the coefficients.

  • Exact aggregate feedback is sufficient (Proposition 6; Appendix C.3). iiuC raised the important question of whether observing individual arm outcomes was necessary to achieve our rates. We now show that observing only the exact sum of selected outcomes suffices for the same fixed-KK, coefficient-uniform rates, including for signed polynomial links. The proof establishes the existence of a single policy that uses all polynomial terms together, without needing to recover individual subset products.

This second result also extends our fixed-range feedback separation to exact aggregates. For K=2K=2, ε=N−1/4\varepsilon=N^{-1/4}, and T=⌈N5/2⌉T=\lceil N^{5/2}\rceil, the range-one quadratic link gε(z)=(1−ε)z/2+ε(z/2)2g_\varepsilon(z)=(1-\varepsilon)z/2+\varepsilon(z/2)^2 has minimax regret Θ~(N2)\widetilde\Theta(N^2) under exact aggregate feedback versus Θ(N9/4)\Theta(N^{9/4}) under Bernoulli feedback. This polynomial improvement holds even when the quadratic term dominates the matched aggregate-feedback rate.

2. Clearer explanations and scope

In response to 5Zz8's detailed questions, we added a concrete two-arm example in Sections 2–3 to explain how interactions can remain hidden even when the reward function is known. Section 4 now presents the explicit coordinate-feedback policy and explains how the upper and lower bounds fit together. We also clarified the dependence of the bounds on KK and the computational costs of the policy, including its polynomial-time implementation in NN for fixed KK. The Abstract and Introduction have been revised to explain the motivation more directly and distinguish our contributions from earlier work.

We thank all three reviewers for considering our responses and revisions and for their positive assessments following the discussion. Their feedback has helped us strengthen both the theory and its presentation.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.