{"id":"503c3cf7-fb27-46c9-9216-9d1d3be06e41","arxiv_id":"2607.13686","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"SquareCB.Comb achieves minimax-optimal O(sqrt(mAT log|F|)) regret for contextual combinatorial semi-bandits with general function approximation.","lead":"This paper introduces SquareCB.Comb, an algorithm that learns to pick a subset of up to m arms from A arms in each round, and proves it achieves the best possible worst-case regret rate. The result matters because it removes a factor of m from the previous general-purpose bound and works for any subset structure, from ranked lists to shortest paths.","discovery_kind":"new_method","skeptic_critique":null,"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies contextual combinatorial semi-bandits (CCSB) with a general finite reward function class F. The proposed algorithm, SquareCB.Comb, maintains a reward estimate from a batch online square-loss regression oracle; at each round it computes a participation vector by maximizing a log-barrier-regularized linear objective over the convex hull of the feasible action set, samples a combinatorial action with matching marginals, and observes semi-bandit feedback. The main theoretical claims are: (i) Theorem 1 gives a regret bound in terms of the oracle's square-loss regret, and Corollary 2 specializes it to O(sqrt(mAT log|F|)) under realizability and bounded action size m; (ii) Theorem 4 provides a matching eOmega(sqrt(mAT log N)) lower bound for a realizable finite-class CCSB instance. The paper also contains an offline-oracle-efficient epoch variant and experiments on learning-to-rank corpora.","tokens_in":27820,"tokens_out":21604,"duration_ms":269634,"significance":"If the advertised guarantees hold as stated, this is a substantial contribution: it would be the first minimax-optimal bound for CCSB with general function approximation, it removes the sqrt(m) gap over the naive full-bandit reduction, and it replaces policy enumeration with regression-oracle calls. The main proof chain—log-barrier certificate, surrogate min-max, CS-DEC, and reduction to batch regression—is coherent, and the lower bound uses a standard interval/product construction. The central caveat is an implicit strict-positivity requirement on the participation vector in Eq. (2); once that is made explicit or repaired by preprocessing, the core result appears defensible.","major_comments":[{"comment":"The optimization in Eq. (2) is undefined when no feasible participation vector has all coordinates strictly positive, because the log-barrier term sum_a log pbar(a) is -infinity on the boundary. The paper assumes only Assumption 2 (||s||_1 <= m) and advertises 'no structural assumptions on the action set beyond a cardinality bound,' but for any S containing a single action of size m<A, the only pbar in Sbar has zeros off that action, so Eq. (2) has no feasible maximizer and Algorithm 1 is undefined. The same issue arises in the contextual shortest-path example when the DAG contains an edge on no s-t path. The subsequent analysis relies on strict positivity: Lemma 5 uses the first-order condition with 1/hat-p, and Lemma 14 explicitly assumes pbar(a)>0 for all a. This is a load-bearing gap in the claimed scope. The paper must either add an explicit reachability assumption (e.g., every arm","section":"Section 4, Eq. (2); Lemmas 5 and 14"}],"minor_comments":[{"comment":"Theorem 1 sets gamma = sqrt(AT/Reg_batch(T)), but Reg_batch(T) is a realized quantity that depends on the algorithm's own data and is not available at run time. The theorem should be phrased as: if the regression oracle satisfies Reg_batch(T) <= R, then with gamma = sqrt(AT/R) the regret is O(sqrt(AT R)). Corollary 2 is explicit and fine, but the statement of Theorem 1 as written is not an implementable algorithmic guarantee.","section":"Section 4.1, Theorem 1"},{"comment":"The step from <1/hat-p, qbar> <= A/gamma to <1/hat-p, qbar^2> <= A/gamma is correct only because qbar(a) in [0,1], but the '=>' arrow hides this. Please add a one-line justification for clarity.","section":"Appendix D.1, proof of Lemma 5"},{"comment":"The lower bound is stated only for A/m integer and for T divisible by M. For a clean minimax-optimality claim over all parameter values, note that the construction can be extended to non-divisible A by grouping floor(A/m) disjoint paths and treating leftover arms as never selected; this yields the same rate up to constants. Please state this extension explicitly or acknowledge the restriction.","section":"Section 5, Theorem 4"},{"comment":"The misspecification extension says the regret is O(sqrt(mAT log|F|) + epsilon m sqrt(AT)) and then mentions an 'additive epsilon T factor' as unavoidable. These are inconsistent: the displayed additive term is sublinear in T, not epsilon T. Please clarify whether the final bound has an epsilon T term or an epsilon sqrt(T) term.","section":"Section 4.1, extensions paragraph"},{"comment":"The constructed environment sets r_t(a)=w_{t,j} for all a in p_j, making arm rewards within a path perfectly correlated. This is allowed by the CCSB model (which fixes only marginals), but it should be stated explicitly so that readers do not assume the Kveton et al. proposition is being invoked under independent-arm assumptions.","section":"Appendix H, lower-bound construction"}],"recommendation":"major_revision","confidential_remarks":"The main technical line is sound and the paper is a good fit for the journal's audience, but the strict-positivity gap in Eq. (2) is exactly the kind of issue that must be fixed before the advertised 'no structural assumptions' claim can be accepted. I would not reject the paper; the fix is local (add an explicit reachability condition or preprocessing step) and the rest of the analysis appears to hold under that condition."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result is real: SquareCB.Comb gets sqrt(mAT log|F|) regret for CCSB with general function classes, matching a new lower bound, and this closes the sqrt(m) gap over the natural full-bandit reduction. I went through the proof chain (log-barrier certificate, surrogate min-max, CS-DEC, regression-oracle reduction) and it holds up. The participation-vector reformulation is the right move—it reduces an exponential action space to an A-dimensional convex problem, and the coverage lemma is clean. The lower bound is a standard interval construction, correctly aggregated. Credit where due: this is not a routine extension, and the new CS-DEC is a genuinely useful complexity measure.\n\nThe soft spots are real but not fatal. First, Eq. (2) is undefined when some arm has zero marginal probability in every feasible action. The paper advertises \"no structural assumptions beyond a cardinality bound,\" but the log-barrier silently requires every arm to be reachable. That's easily fixed by pruning unreachable arms from the arm set or adding an explicit support assumption, so it is a write-up gap rather than a flaw in the method. Second, the Frank-Wolfe variant (Algorithm 2) is presented as computationally efficient, but there is no convergence analysis and no guarantee that an approximate solution still certifies the DEC. That claim should be toned down or backed up. The comparison to the linear-reward setting is a bit terse, but the footnote explains the apparent contradiction and it does not affect the main result. The experiments are honest—SquareCB.Comb tracks SquareCB.Lin on these small slate sizes—but they don't try to demonstrate the theoretical gap; that's fine.\n\nWho is this for? Anyone working on contextual bandits, combinatorial bandits, or E2D-style reductions. It deserves a serious referee. The core theorem is likely correct, and the two gaps are addressable in revision. I would not desk-reject this. I'd send it out and ask for a clean statement of the support condition and either a Frank-Wolfe convergence lemma or an explicit caveat about the exact-solver assumption.","headline":"A solid, likely correct resolution of the minimax rate for contextual combinatorial semi-bandits with general function approximation; two addressable gaps in the write-up, not in the core proof.","tokens_in":28271,"tokens_out":4251,"would_cite":true,"duration_ms":573065,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces SquareCB.Comb, a provably efficient algorithm for contextual combinatorial semi-bandits that reaches a minimax-optimal regret of O(√(mAT log|F|)), matching the best possible rate up to logarithmic factors—the first suc","keywords":["contextual combinatorial semi-bandits","minimax optimal regret","general function approximation","semi-bandit feedback","log-barrier exploration","decision-estimation coefficient","regret bounds","regression oracle"],"falsifier":"Take a DAG shortest-path instance and add an edge that lies on no s-t path, then run SquareCB.Comb's line-5 optimization. The log p̄(a) term for that edge is -∞, so the arg max does not exist and the algorithm cannot execute. Alternatively, if a variant runs after explicitly removing unreachable arms, its regret should be reported on the pruned instance, not the original.","tokens_in":27692,"feed_emoji":"🎯","tokens_out":4805,"duration_ms":46759,"temperature":0.7,"pith_summary":"This paper tackles contextual combinatorial semi-bandits—choosing a subset of arms each round while seeing only the rewards of the chosen arms—when rewards are modeled by an arbitrary finite function class, not just linear functions. It proposes SquareCB.Comb, which each round solves a single A-dimensional convex program with a log-barrier regularizer to obtain marginal inclusion probabilities, then draws a feasible action matching those marginals. The paper proves expected regret O(√(mAT log|F|)) under realizability and a batch square-loss regression oracle, and proves a matching lower bound up to log factors. If right, this is the first minimax-optimal CCSB guarantee beyond linear rewards and it removes the extra √m factor paid by reducing CCSB to full-bandit learning.","feed_headline":"New algorithm hits minimax-optimal regret for combinatorial semi-bandits","feed_subtitle":"SquareCB.Comb learns arbitrary reward classes in O(√(mAT log|F|)) regret, ending the √m gap over full-bandit reductions.","key_machinery":"The key mechanism is the participation vector: for a distribution over combinatorial actions, the vector of marginal selection probabilities per arm. SquareCB.Comb alternates a batch square-loss regression oracle for reward estimates with a log-barrier-regularized convex program over participation vectors—maximize estimated reward plus (1/γ)Σ log p̄(a)—whose solution certifies a small value of the combinatorial square-loss decision-estimation coefficient (CS-DEC), a complexity measure adapted from interactive decision making to semi-bandit feedback. The crucial reduction is that the CS-DEC minimization, which naively runs over exponentially many actions, depends only on marginals and therefo","core_discovery":"The central claim is that for any finite reward function class F, a realizable CCSB instance with A arms, action size at most m, and horizon T can be learned with expected regret O(√(mAT log|F|)) by a computationally tractable algorithm, and no algorithm can do better than Ω̃(√(mAT log|F|)) in the worst case. This matches the best known rates for linear CCSB and for slate-recommendation policy search, while covering arbitrary combinatorial constraints such as paths, slates, and matchings. The paper also shows that the standard reduction from CCSB to contextual bandits suffers an extra factor of m, so SquareCB.Comb's arm-level use of semi-bandit feedback is essential to closing that gap.","pith_inferences":["Editorial extension: the log-barrier step implicitly requires every arm to be reachable—there must be some feasible action distribution with positive marginal probability for every arm. For action families containing arms that never appear in any feasible action, the optimization is undefined, so a practical implementation would need to restrict to reachable sub-arms or add a smoothing term.","Editorial extension: the participation-vector and CS-DEC certificate is likely adaptable to other structured observation models, such as probabilistically triggered arms or cascading feedback, wherever a coverage-type quantity can replace the squared-loss term.","Editorial extension: the paper conjectures that under independent arms the minimax rate may be strictly lower than Õ(√(mAT log|F|)); if true, the m under the square root is not inherent to all CCSB structures but only to correlated worst cases.","Editorial extension: a direct empirical test of the √m separation is to compare SquareCB.Comb against the full-bandit reduction on action sets where the optimal action is rare; the theory predicts the regret gap grows with m."],"forward_implications":["Achieves O(√(mAT log|F|)) regret while matching lower bound Ω̃(√(mAT log|F|)), so the rate is minimax-optimal up to log factors.","Closes the √m gap over the full-bandit reduction, which only gives m√(AT log|F|).","Instantiates to linear reward classes with Õ(√(mAdT)) regret, matching known linear CCSB rates.","For shortest-path constraints on a DAG, yields Õ(√(NMT log|F|)) regret, improving on a reduction to contextual MDPs.","For m=1, recovers the standard contextual-bandit regret √(AT log|F|)."],"fun_headline_variants":["SquareCB.Comb achieves minimax-optimal regret in combinatorial semi-bandits","Closing the √m gap: SquareCB.Comb for general combinatorial semi-bandits","Minimax-optimal regret for combinatorial semi-bandits with general function approximation","Arm-level semi-bandit feedback yields optimal regret without structural assumptions","Efficient convex sampling matches lower bound in combinatorial semi-bandits"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that Eq. (2)'s log-barrier objective has a maximizer: there must be at least one feasible action distribution whose marginal probability is positive for every arm—an unstated reachability condition that fails for action families containing an arm no feasible action ever selects.","fun_headline_variants_meta":{"raw":{"variants":["SquareCB.Comb achieves minimax-optimal regret in combinatorial semi-bandits","Closing the √m gap: SquareCB.Comb for general combinatorial semi-bandits","Minimax-optimal regret for combinatorial semi-bandits with general function approximation","Arm-level semi-bandit feedback yields optimal regret without structural assumptions","Efficient convex sampling matches lower bound in combinatorial semi-bandits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000287,"raw_usage":{"total_tokens":1538,"prompt_tokens":775,"completion_tokens":763,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":519,"completion_tokens_details":{"reasoning_tokens":667}},"tokens_in":519,"tokens_out":763,"duration_ms":6552,"temperature":1.0,"reasoning_tokens":667,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T04:03:00.948837+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a DAG shortest-path instance and add an edge that lies on no s-t path, then run SquareCB.Comb's line-5 optimization. The log p̄(a) term for that edge is -∞, so the arg max does not exist and the algorithm cannot execute. Alternatively, if a variant runs after explicitly removing unreachable arms, its regret should be reported on the pruned instance, not the original.","supporting_citations":[],"review_version":1}