acceptodds
Under review as a conference paper at ICLR 2027

Stronger, Tractable Notions of Regret for Online Submodular Maximization

Abstract

Online Submodular Maximization (OSM) is typically evaluated via static regret, which only guarantees competitiveness with the best fixed action in hindsight. While fundamental, this notion fails to capture more refined notions of rational behavior that arise naturally in combinatorial decision spaces. We revisit OSM through the lens of -regret, a family of stronger regret notions defined with respect to sets of action transformations. We identify rich yet tractable classes of transformations that encode natural operations on sets, including permutations and conditional trades, and show how to achieve sublinear -regret in polynomial time. Our algorithms combine classical machinery from online convex optimization with rounding schemes from combinatorial optimization.

Primary area:
optimization
Keywords:
online submodular optimization, online learning, regret minimization

Reviews

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

This paper investigates stronger notions of regret for online submodular maximization. The authors introduce affine and quadratic transformation classes and develop polynomial-time algorithms by combining online gradient ascent, approximate fixed-point computation, and contention resolution schemes. The proposed algorithms achieve sublinear approximate Φ\Phi-regret under the stated assumptions.

Critical strengths
  • The problem formulation is meaningful and theoretically interesting.

  • The paper provides detailed theoretical analysis.

Critical weaknesses
  • Insufficient experimental evaluation. The main focus of this paper is online submodular maximization. However, the objective functions used in the experiments are modular. Although modular functions are a special case of submodular functions, they do not capture the nontrivial diminishing-returns structure of general submodular objectives. Moreover, the experiments evaluate ordinary regret with α=1\alpha=1, whereas the theoretical guarantees are established for a smaller approximation factor. Achieving sublinear regret with α=1\alpha=1 is generally computationally intractable for submodular maximization under standard complexity assumptions. Therefore, the current experiments do not adequately validate the main theoretical guarantees.

  • Unclear relationship between the approximation factor, transformation classes, and regret guarantees. The theoretical guarantees in Theorem 6.3 involve several parameters, making the concrete regret bounds and their dependence on problem characteristics insufficiently clear. More importantly, the improvement over existing regret guarantees is not well established. For example, when k=2k=2, the approximation factor α=βk(1−1/e)\alpha=\beta_k(1-1/e) is strictly smaller than the classical 1−1/e1-1/e factor. Although the proposed framework considers stronger transformation-based regret notions, this comes with a weaker approximation factor, making direct comparisons with existing static-regret guarantees difficult. More fundamentally, the relationship between the achievable approximation factor α\alpha, the expressiveness of the transformation class Φ\Phi, and the resulting regret bounds remains unclear. It is also unclear under what conditions different (α,Φ)(\alpha,\Phi)-regret guarantees are achievable and whether the approximation losses are inherent or arise from the particular algorithmic framework.

Questions for authors
  • Please include experiments on genuinely submodular functions to better validate the theoretical guarantees, particularly the approximate Φ\Phi-regret bounds.

  • Please clarify the parameter dependence in Theorem 6.3 and discuss whether the approximation factor can match the classical offline approximation guarantee of 1−1/e1-1/e, and under what additional conditions this might be possible.

  • Please explicitly characterize the relationship and trade-offs among the approximation factor α\alpha, the transformation class Φ\Phi, and the achievable regret bounds. In particular, which conditions are sufficient or necessary for obtaining sublinear (α,Φ)(\alpha,\Phi)-regret?

4 comments

We thank the reviewer for their careful reading and constructive feedback. We address the concerns below.

Approximation factor (W2, Q2).

  • Affine mappings. We have improved Theorem 6.3's affine factor to 1−1/e1-1/e using randomized pipage rounding (Calinescu et al., 2011). For XtX_t rounded from yty_t, EXt=yt\mathbb E X_t=y_t implies E[ϕ(Xt)]=ϕ(yt)\mathbb E[\phi(X_t)]=\phi(y_t) for affine ϕ\phi. Moreover,

    \qquad \mathbb E f_t(X_t^{\rm CRS})\ge\beta F_t(y_t).$$ Applying Appendix C.2's inequality to $\phi(X_t)$ and taking expectations gives the regret bound for constants and permutations.
  • Quadratic mappings. We retain Theorem 6.3's CRS factor β(1−1/e)\beta(1-1/e), where β=1−e−kkk/k!\beta=1-e^{-k}k^k/k!. Pipage need not preserve E[ϕ(Xt)]=ϕ(yt)\mathbb E[\phi(X_t)]=\phi(y_t) for quadratic ϕ\phi, since this expectation depends on the probabilities of selecting pairs together. Whether the additional β\beta loss is necessary remains open.

Submodular experiments and reward gains (W1, Q1). We extended the experiments in Section 7 and Appendix H.3 to nonmodular weighted coverage with overlapping features (T=500T=500, three instance seeds per size). All learners use the CRS rounding, repeated 64 times on each fractional decision sequence. Mean rewards per round are:

nnkkStatic OGAAffine OGAQuadratic OGAQuadratic gain over affine
3250.40220.50370.5483+8.9%
64100.41200.50180.5351+6.6%
128210.44090.51810.5418+4.6%

We have added the protocol and results to the revision.

Approximate-regret results (W1, Q1). On additional nonmodular coverage instances designed to separate static and affine regret, we used the same protocol with CRS and a fixed subset of affine maps shared by all learners. At (n,k)=(128,21)(n,k)=(128,21):

LearnerRegret measureApproximation factorMean regret per round
Static OGAStatic1−1/e1-1/e-0.0094
Static OGAAffineβ(1−1/e)\beta(1-1/e)+0.0375
Affine OGAAffineβ(1−1/e)\beta(1-1/e)-0.0514
Quadratic OGAAffineβ(1−1/e)\beta(1-1/e)-0.0421

At (128,21)(128,21), Static OGA has negative (1−1/e)(1-1/e)-static regret, yet a fixed permutation of its selected items earns more reward even after scaling by β(1−1/e)\beta(1-1/e). Across all nine instances, mean regret over the evaluated affine maps is positive for Static OGA and negative for Affine and Quadratic OGA.

Concrete guarantees and tradeoffs (W2, Q2). We have added an explicit regret theorem for Algorithm 2 (Theorem 6.4). Under the paper's assumptions (0≤ft(S)≤M0\le f_t(S)\le M for every SS), using pipage rounding for affine mappings and CRS for quadratic mappings gives, with probability at least 1−δ1-\delta:

\qquad R_{\beta(1-1/e)}^{\Phi_2}(T)\le\widetilde O(Mnk\sqrt T).$$ Here $\widetilde O$ hides logarithms in $n,1/\delta$. These bounds use Algorithm 2's $\ell_1$ fixed-point tolerance $\epsilon=T^{-1/2}$, one unbiased gradient sample per coordinate per round ($2nT$ value-oracle calls), and feasible projections within $O(D/T)$ of the exact projection in Frobenius norm, where $D$ is the coefficient set's diameter. We have added the proof and error analysis to Appendix D.5. **What quadratic regret adds (W2, Q3).** We extend the separation in Appendix F.2 with a coverage example in Appendix F.3 ($n=12,k=3$) where the same decisions can have negative $(1-1/e)$-affine regret while $\beta(1-1/e)$-quadratic regret grows linearly with $T$. Thus the affine guarantee does not imply the quadratic guarantee. We have added the proof to the appendix. **Expressiveness and tractability (W2, Q3).** Sections 5–6 and Appendix D.3 give sufficient conditions: polynomial-size convex programs, efficient approximate fixed points, and rounding that converts fractional surrogate regret into integral $\alpha$-regret. Necessity of these structural conditions remains open. Because our classes contain every constant map, $1-1/e$ is the worst-case limit for polynomial-query algorithms (Calinescu et al., 2011); the revised affine guarantee attains it.

With the discussion period ending soon, we would appreciate your thoughts on whether our response and revisions address your main concerns. Please let us know if any points need further clarification.

Thank you for the detailed response. I acknowledge the authors' efforts. These revisions have addressed some of my previous concerns. However, the practical advantages and theoretical trade-offs of the proposed quadratic mappings are not yet fully established.

Overall, I appreciate the additional theoretical and experimental efforts. I want to say is that these contributions are not a difficult task for current AI tools. Therefore, I prefer to maintain my original score. If the author can fully explain the practical advantages, perhaps I will improve my score

We would appreciate clarification of which practical advantage or theoretical trade-off remains unresolved. Our response explains the additional expressive power of quadratic mappings and their approximation cost, while Section 6.3 and Theorem 6.4 quantify the computational and regret bounds. Appendix F.3 shows the added benefit of quadratic mappings. Experimentally, Appendix H.3 reports 4.6–8.9% higher mean rewards for Quadratic OGA than Affine OGA on the tested coverage instances.

In a nutshell, standard static regret formalizes one notion of rationality:

  1. Static: Compete with replacing all selected sets S1,…,STS_1,\ldots,S_T with a single fixed feasible set S⋆S^\star. Our framework asks for additional forms of rationality:
  2. Affine: Also compete with consistently swapping items: e.g., exchanging ii and jj in every selected set.
  3. Quadratic: Additionally compete with conditional replacements: e.g., replacing ii with jj whenever ii is selected and jj is absent.

Our contribution is primarily theoretical: to our knowledge, no prior work provides polynomial-time sublinear approximate Φ\Phi-regret guarantees for permutations and conditional trades in OSM. We identify these natural learning requirements and establish that they can be achieved efficiently.

We respectfully ask you to reconsider the statement about AI. We would welcome a concrete assessment of the novelty and significance of the guarantees established here.

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

This paper studies Φ\Phi-regret in full-information online monotone submodular maximization under cardinality constraints, extending the conventional static-regret framework to richer transformation-based comparators. It introduces tractable affine and quadratic transformation classes that capture permutations and conditional item trades, and establishes polynomial-time algorithms with sublinear approximate Φ\Phi-regret. The approach combines online convex optimization, approximate fixed-point computation, and randomized rounding. The theoretical results are complemented by separation examples and small-scale synthetic experiments illustrating the distinction between static and transformation regret.

Critical strengths
  1. The paper introduces transformation-based regret notions for online submodular maximization, capturing systematic decision errors that static regret may overlook. The separation examples demonstrate that affine and quadratic regret provide genuinely richer comparator classes, motivating the study of these stronger regret notions.

  2. The paper establishes polynomial-time tractability for the proposed transformation classes through polyhedral formulations and efficient approximate fixed-point computation. In particular, the comparator transfer lemma provides a nontrivial connection between transformed integral actions and fractional submodular objectives, enabling the sublinear approximate Φ\Phi-regret guarantee.

Critical weaknesses
  1. The proposed transformation classes rely on restrictive structural conditions, which limit their generality and applicability. Moreover, the main theorem achieves sublinear Φ\Phi-regret only with an approximation factor of β(1−1/e)\beta (1-1/e), weaker than the standard 1−1/e1-1/e factor for static regret. Although the comparator class is richer, the practical and theoretical benefits of this trade-off remain unclear.

  2. The experiments consider only a small synthetic instance with modular rewards and evaluate ordinary regret (α=1\alpha=1), rather than the approximate regret guaranteed by the theory. They also do not demonstrate a clear advantage of quadratic over affine transformations. Consequently, the experiments provide limited evidence of the benefits of the proposed framework for general submodular maximization.

Questions for authors
  1. Given the reduced approximation factor β(1−1/e)\beta(1-1/e), could the authors clarify in what sense the resulting guarantee offers a meaningful advantage over existing 1−1/e1-1/e static-regret guarantees? In particular, are there examples where this approximate Φ\Phi-regret criterion captures systematic decision errors that existing guarantees do not?

  2. Could the authors justify the practical relevance of the structural restrictions imposed on the affine and quadratic transformation classes? What important classes of decision transformations are excluded by these restrictions?

3 comments

We thank the reviewer for their careful reading and constructive feedback. We address the concerns below.

Practical meaning and structural limits (W1, Q2). Sections 4.1–4.3 allow constant maps, permutations, and disjoint conditional trades. A trade replaces ii by jj when only ii is selected and keeps both when both are selected. Excluded rules include arbitrary overlapping trades, substitutions conditioned on a third item, and dropping one item while leaving others unchanged. The restrictions yield nonexpansive maps and efficient approximate fixed points (Lemmas 6.1–6.2), plus polynomial-size convex programs (Appendices D.1–D.2).

Approximation factor (W1).

  • Affine mappings. We have improved Theorem 6.3's affine factor to 1−1/e1-1/e using randomized pipage rounding (Calinescu et al., 2011). For XtX_t rounded from yty_t, EXt=yt\mathbb E X_t=y_t implies E[ϕ(Xt)]=ϕ(yt)\mathbb E[\phi(X_t)]=\phi(y_t) for affine ϕ\phi. Moreover,

    \qquad \mathbb E f_t(X_t^{\rm CRS})\ge\beta F_t(y_t).$$ Applying Appendix C.2's inequality to $\phi(X_t)$ and taking expectations gives the regret bound for constants and permutations.
  • Quadratic mappings. We retain Theorem 6.3's CRS factor β(1−1/e)\beta(1-1/e), where β=1−e−kkk/k!\beta=1-e^{-k}k^k/k!. Pipage need not preserve E[ϕ(Xt)]=ϕ(yt)\mathbb E[\phi(X_t)]=\phi(y_t) for quadratic ϕ\phi, since this expectation depends on the probabilities of selecting pairs together. Whether the additional β\beta loss is necessary remains open.

Experiments on nonmodular objectives (W2). We extended the experiments in Section 7 and Appendix H.3 to nonmodular weighted coverage with overlapping features (T=500T=500, three instance seeds per size). All learners use the CRS rounding, repeated 64 times on each fractional decision sequence. Mean rewards per round are:

nnkkStatic OGAAffine OGAQuadratic OGAQuadratic gain over affine
3250.40220.50370.5483+8.9%
64100.41200.50180.5351+6.6%
128210.44090.51810.5418+4.6%

We have added the protocol and results to the revision.

On additional nonmodular coverage instances designed to separate static and affine regret, we used the same protocol with CRS and a fixed subset of affine maps shared by all learners. At (n,k)=(128,21)(n,k)=(128,21):

LearnerRegret measureApproximation factorMean regret per round
Static OGAStatic1−1/e1-1/e-0.0094
Static OGAAffineβ(1−1/e)\beta(1-1/e)+0.0375
Affine OGAAffineβ(1−1/e)\beta(1-1/e)-0.0514
Quadratic OGAAffineβ(1−1/e)\beta(1-1/e)-0.0421

At (128,21)(128,21), Static OGA has negative (1−1/e)(1-1/e)-static regret, yet a fixed permutation of its selected items earns more reward even after scaling by β(1−1/e)\beta(1-1/e). Across all nine instances, mean regret over the evaluated affine maps is positive for Static OGA and negative for Affine and Quadratic OGA.

What the stronger criteria detect (Q1). Appendix G separates ordinary static and affine regret. Our new coverage example in Appendix G.1 (n=32,k=2n=32,k=2) shows that standard Hedge has O(T)O(\sqrt T) expected ordinary static regret but Ω(T)\Omega(T) expected β(1−1/e)\beta(1-1/e)-regret against one fixed permutation. Thus the ordinary static guarantee does not imply the approximate affine guarantee. We have added this proof.

We extend the separation in Appendix F.2 with a coverage example in Appendix F.3 (n=12,k=3n=12,k=3) where the same decisions can have negative (1−1/e)(1-1/e)-affine regret while β(1−1/e)\beta(1-1/e)-quadratic regret grows linearly with TT. Thus the affine guarantee does not imply the quadratic guarantee. We have added the proof to the appendix.

With the discussion period ending soon, we would appreciate your thoughts on whether our response and revisions address your main concerns. Please let us know if any points need further clarification.

Thank you for the detailed response and additional results. The improved approximation factor and additional experiments address several of my concerns. However, I remain concerned about the restrictive transformation classes and the limited empirical validation. Overall, my concerns are partially addressed, and I am maintaining my original score.

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

The paper gives the first polynomial-time sublinear (α,Φ)(\alpha,\Phi)-regret guarantees for online submodular maximization over rich affine and quadratic transformation classes, including permutations and conditional trades. It combines relax-and-round, auxiliary-function OCO, anchored fixed points, and CRS rounding. Synthetic weighted-coverage experiments show that static OGA can incur affine regret, while transformation learners avoid it.

Critical strengths

S1: It proposes a sublinear (α,Φ)(\alpha,\Phi)-regret for OSM over affine/quadratic transformations in polynomial time. This extends OSM theory beyond static regret while avoiding known tractability barriers.

S2: It provides a concrete, modular algorithm with high-probability guarantees and supporting experiments. The relax-and-round, auxiliary-OCO, fixed-point, and projection framework is verifiable and practically instantiated.

Critical weaknesses

W1: The proposed regret notion is not meaningful enough as the target. Comparing against transformed versions of the learner’s own actions, with approximation factors α=β(1−1/e)\alpha=\beta(1-1/e), can be weak or hard to interpret; this undermines the main conceptual contribution.

W2: The experiments use a tiny synthetic n=6, k=2 weighted-coverage instance and mainly illustrate a distinction already argued theoretically; they do not validate practical relevance or scalability.

Questions for authors

See Critical Weaknesses.

2 comments

We thank the reviewer for their careful reading and constructive feedback. We address the concerns below.

Why the benchmark matters (W1). Static regret is Φ\Phi-regret for constant maps ϕ(S)=S⋆\phi(S)=S^\star to fixed feasible sets. Our affine class also includes permutations, while our quadratic class additionally includes trades replacing aa by bb when only aa is selected. The benchmark compares reward with α\alpha times that of the best fixed transformation in hindsight. Our revised affine guarantee retains 1−1/e1-1/e, which is worst-case optimal for polynomial-query algorithms even for static regret. Beyond competing with a fixed set, it is natural to avoid systematic mistakes that consistent swaps or trades could correct.

  • Affine mappings. We have improved Theorem 6.3's affine factor to 1−1/e1-1/e using randomized pipage rounding (Calinescu et al., 2011). For XtX_t rounded from yty_t, EXt=yt\mathbb E X_t=y_t implies E[ϕ(Xt)]=ϕ(yt)\mathbb E[\phi(X_t)]=\phi(y_t) for affine ϕ\phi. Moreover,

    \qquad \mathbb E f_t(X_t^{\rm CRS})\ge\beta F_t(y_t).$$ Applying Appendix C.2's inequality to $\phi(X_t)$ and taking expectations gives the regret bound for constants and permutations.
  • Quadratic mappings. We retain Theorem 6.3's CRS factor β(1−1/e)\beta(1-1/e), where β=1−e−kkk/k!\beta=1-e^{-k}k^k/k!. Pipage need not preserve E[ϕ(Xt)]=ϕ(yt)\mathbb E[\phi(X_t)]=\phi(y_t) for quadratic ϕ\phi, since this expectation depends on the probabilities of selecting pairs together. Whether the additional β\beta loss is necessary remains open.

To our knowledge, these are the first polynomial-time regret guarantees for permutations and conditional trades in OSM. We hope these guarantees and the additional results below address your concerns about the meaning and usefulness of the benchmark.

Experiments and practical relevance (W2). We extended the experiments in Section 7 and Appendix H.3 to nonmodular weighted coverage with overlapping features (T=500T=500, three instance seeds per size). All learners use the CRS rounding, repeated 64 times on each fractional decision sequence. Mean rewards per round are:

nnkkStatic OGAAffine OGAQuadratic OGAQuadratic gain over affine
3250.40220.50370.5483+8.9%
64100.41200.50180.5351+6.6%
128210.44090.51810.5418+4.6%

We have added the protocol and results to the revision.

On additional nonmodular coverage instances designed to separate static and affine regret, we used the same protocol with CRS and a fixed subset of affine maps shared by all learners. At (n,k)=(128,21)(n,k)=(128,21):

LearnerRegret measureApproximation factorMean regret per round
Static OGAStatic1−1/e1-1/e-0.0094
Static OGAAffineβ(1−1/e)\beta(1-1/e)+0.0375
Affine OGAAffineβ(1−1/e)\beta(1-1/e)-0.0514
Quadratic OGAAffineβ(1−1/e)\beta(1-1/e)-0.0421

At (128,21)(128,21), Static OGA has negative (1−1/e)(1-1/e)-static regret, yet a fixed permutation of its selected items earns more reward even after scaling by β(1−1/e)\beta(1-1/e). Across all nine instances, mean regret over the evaluated affine maps is positive for Static OGA and negative for Affine and Quadratic OGA.

With the discussion period ending soon, we would appreciate your thoughts on whether our response and revisions address your main concerns. Please let us know if any points need further clarification.

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

This paper studies stronger notions of regret for full-information online monotone submodular maximization under a cardinality constraint. Standard static regret compares the learner with one fixed feasible set. Here, the comparator is a fixed transformation ϕ\phi chosen in hindsight, and its reward on round tt is ft(ϕ(St))f_t(\phi(S_t)), where StS_t is the learner's own set. The affine transformation class contains constant maps and item permutations. The quadratic class also contains conditional trades, where an item is replaced only when another item is present.

The algorithm operates on the cardinality polytope. The paper gives polynomial-size coefficient descriptions for relaxed affine and quadratic transformations, proves that they are non-expansive in ℓ1\ell_1, and computes approximate fixed points using an anchored contraction. It then applies online gradient ascent to a non-oblivious surrogate of the multilinear extension and rounds the fractional point with a contention-resolution scheme. Theorem 6.3 converts surrogate transformation regret into high-probability integral (α,Φℓ)(\alpha,\Phi_\ell)-regret, where α=β(1−1/e)\alpha=\beta(1-1/e) and β=1−e−kkk/k!\beta=1-e^{-k}k^k/k!. Appendix E separates the three regret notions, and the weighted-coverage experiment shows that static OGA can have high affine regret.

Critical strengths
  1. The affine class contains constant maps and permutations, while the quadratic class also contains conditional trades. Both classes have polynomial-size coefficient descriptions and are non-expansive, which permits efficient approximate fixed-point computation. This makes the stronger action-dependent benchmark computationally usable.

  2. Theorem 6.3 converts a surrogate-regret bound on fractional actions into a high-probability regret bound for the rounded feasible sets. Lemmas C.2-C.3 justify the transformed-comparator step despite the dependencies created by randomized rounding. Appendix E separates the three regret notions, and Appendix F shows that static OGA can have linear affine regret.

Critical weaknesses
  1. The paper does not clearly separate its contribution from existing work on Φ\Phi-regret. (Gordon et al. 2008) already reduce Φ\Phi-regret to external regret and fixed-point computation, while (Zhang et al. 2025) and (Anagnostides et al. “Swap Regret Minimization Through Response-Based Approachability”, COLT 2026) give efficient methods for polynomial-dimension deviations on convex domains. The paper should explain whether these methods already imply its fractional surrogate-regret bound; otherwise, its novelty claim is too broad.

  2. Theorem 6.3 has the approximation factor β(1−1/e)\beta(1-1/e) rather than the standard static factor 1−1/e1-1/e; when k=1k=1, this is approximately 0.400.40 instead of 0.6320.632, and the paper does not show that the additional factor β\beta is necessary. The theorem also assumes a surrogate-regret bound, but the paper does not state how gradient estimation and approximate fixed points affect the regret and runtime of Algorithm 2.

Questions for authors
  1. Can the authors clarify how the fractional surrogate-regret guarantee used in Theorem 6.3 relates to (Zhang et al., 2025) or (Anagnostides et al. “Swap Regret Minimization Through Response-Based Approachability”, COLT 2026)? In particular, what are the similarities and differences in their assumptions, comparator classes, and guarantees?

  2. Is the additional factor β\beta necessary for integral transformation regret? Can a different rounding or coupling preserve the comparison with transformed sets while retaining the standard 1−1/e1-1/e static approximation factor?

  3. Can the authors give a regret and runtime theorem for Algorithm 2? How many value-oracle calls does it use, and how do gradient estimation and approximate fixed points affect the bound?

2 comments

We thank the reviewer for their careful reading and constructive feedback. We address the concerns below.

Relationship to prior work (W1, Q1).

  • Gordon et al. (2008). We use their standard external-regret/fixed-point reduction, which underpins much of the work on Φ\Phi-regret.
  • Anagnostides et al. (2026). Their affine method also gives a sublinear affine surrogate-regret bound in our setting. Their nonlinear extension uses distributions over fractional actions. They leave efficient solution of its saddle-point problem using only domain oracles open.
  • Zhang et al. (2025). Their method covers broader classes with polynomially many parameters, using distributions over fractional actions and nested ellipsoid computations. They leave improving the polynomial runtime and avoiding ellipsoid methods as open directions.

Their nonlinear guarantees do not directly apply to our action-dependent auxiliary gradient. We use coefficient QPs and directly computed approximate fixed points, followed by rounding, to control transformation regret on the played sets. We have added this comparison to Section 2.

Approximation factor (W2, Q2).

  • Affine mappings. We have improved Theorem 6.3's affine factor to 1−1/e1-1/e using randomized pipage rounding (Calinescu et al., 2011). For XtX_t rounded from yty_t, EXt=yt\mathbb E X_t=y_t implies E[ϕ(Xt)]=ϕ(yt)\mathbb E[\phi(X_t)]=\phi(y_t) for affine ϕ\phi. Moreover,

    \qquad \mathbb E f_t(X_t^{\rm CRS})\ge\beta F_t(y_t).$$ Applying Appendix C.2's inequality to $\phi(X_t)$ and taking expectations gives the regret bound for constants and permutations.
  • Quadratic mappings. We retain Theorem 6.3's CRS factor β(1−1/e)\beta(1-1/e), where β=1−e−kkk/k!\beta=1-e^{-k}k^k/k!. Pipage need not preserve E[ϕ(Xt)]=ϕ(yt)\mathbb E[\phi(X_t)]=\phi(y_t) for quadratic ϕ\phi, since this expectation depends on the probabilities of selecting pairs together. Whether the additional β\beta loss is necessary remains open.

Explicit bounds (W2, Q3). We have added an explicit regret theorem for Algorithm 2 (Theorem 6.4). Under the paper's assumptions (0≤ft(S)≤M0\le f_t(S)\le M for every SS), using pipage rounding for affine mappings and CRS for quadratic mappings gives, with probability at least 1−δ1-\delta:

\qquad R_{\beta(1-1/e)}^{\Phi_2}(T)\le\widetilde O(Mnk\sqrt T).$$ Here $\widetilde O$ hides logarithms in $n,1/\delta$. These bounds use Algorithm 2's $\ell_1$ fixed-point tolerance $\epsilon=T^{-1/2}$, one unbiased gradient sample per coordinate per round ($2nT$ value-oracle calls), and feasible projections within $O(D/T)$ of the exact projection in Frobenius norm, where $D$ is the coefficient set's diameter. We have added the proof and error analysis to Appendix D.5. **Runtime (W2, Q3).** Combining Lemma 6.2 (Appendix E.2) with Section 5 gives $O(n^{\ell+1}k\sqrt T\log(2+k\sqrt T))$ arithmetic operations per fixed point, for $\ell\in\{1,2\}$. Each round also solves a convex QP with $O(n^{\ell+1})$ variables and constraints (Appendices D.1–D.2); for rational input, its cost is polynomial in $n$, input bit length, and $\log T$ at the accuracy above. Gradient sampling and rounding add $O(n^2)$ expected operations. Total cost is $T$ times these per-round costs plus the oracle calls above; querying played rewards adds at most $T$ calls. We have consolidated these costs in the revision.

With the discussion period ending soon, we would appreciate your thoughts on whether our response and revisions address your main concerns. Please let us know if any points need further clarification.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions

We thank the reviewers for their feedback. The revised manuscript includes the following changes:

  • Section 2: Clarified the relationship to prior Φ\Phi-regret methods and the additional steps needed for our setting.
  • Theorem 6.3; Appendices B and D.4: Improved the affine approximation factor to 1−1/e1-1/e using randomized pipage rounding.
  • Section 6.3, Theorem 6.4; Appendix D.5: Added explicit regret and oracle-complexity bounds, theoretical runtime analysis, and error analysis for gradient estimation, approximate fixed points, and projections.
  • Appendices G.1 and F.3: Added separations between ordinary static and approximate affine regret, and between affine and quadratic regret at the stated approximation factors, respectively.
  • Section 7; Appendix H.3: Added nonmodular weighted-coverage experiments up to n=128n=128, comparing learner rewards and approximate regret over a shared finite family of affine maps.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.