- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies contextual combinatorial bandits with post-serving contexts, where multiple arms must be selected before observing additional features that influence their rewards. The authors propose jointly optimistic OFUC$^2$-PC and oracle-efficient C$^2$UCB-PC, using a new noisy batched truncated elliptical potential lemma to analyze uncertainty from reward estimation and post-serving context prediction. The analysis establishes matching regret upper and lower rates, up to logarithmic factors, for additive rewards with context learnability rate under the stated parameter conditions, and variance-aware variants sharpen the reward-learning term under variance-modulated smoothness. Experiments on synthetic and MovieLens-based semi-synthetic environments show lower regret than the tested baselines, with oracle-efficient variants running approximately 18–36 times faster than their joint-optimization counterparts.
Critical strengths
-
Well-motivated problem formulation: Addresses combinatorial decisions where reward-relevant contexts become available only after serving, explicitly accounting for uncertainty that conventional contextual bandits overlook.
-
Substantive theoretical contribution: Develops a noisy batched truncated elliptical potential lemma that handles noisy contexts and batched feedback without a non-degenerate noise covariance assumption, supporting near-minimax regret guarantees for additive rewards with under the stated conditions.
-
Effective algorithmic alternatives: Provides oracle-efficient and variance-aware variants with strong regret guarantees; synthetic and semi-synthetic experiments demonstrate lower regret than the tested baselines and approximately 18–36× faster execution for oracle-efficient methods than their joint-optimization counterparts.
Critical weaknesses
-
Restrictive modeling assumptions: The guarantees rely on a shared linear reward model, uniformly controlled post-serving prediction errors, and conditionally independent arm noises. Robustness to model misspecification, correlated feedback, and interactions between selected arms remains unclear.
-
Limited experimental realism and scale: Evaluation uses synthetic and MovieLens-based semi-synthetic feedback, primarily with only 10 arms and a single reward structure. Runtime experiments extend to just 14 arms, providing limited evidence for large-scale applications or genuine post-serving behavior.
-
Gap between optimization guarantees and implementation: The joint algorithms assume exact optimistic optimization, while experiments use approximate multi-start SLSQP without quantifying optimization error. The oracle-efficient variants are tested with simple top- selection, leaving performance under harder combinatorial constraints unverified.
Questions for authors
See weakness.
2 comments
3. Optimization Guarantees and Implementation
We thank the reviewer for raising these concerns. Our additional experiments show that the SLSQP implementation is empirically stable. Moreover, our theoretical guarantees extend beyond Top-K selection under the stated optimization assumptions, and new experiments provide supporting evidence under partition constraints. We explain these results below.
Theoretical generalization beyond Top-K selection: Our algorithms and regret analysis are not restricted to Top-K selection. They apply to general feasible action families in which at most arms are selected per round. To illustrate this generality, we consider partition constraints.
Let the arms be partitioned into disjoint groups . Consider the partition-constrained family
where every feasible action contains exactly arms.
For OFUC$^2$-PC, under the joint confidence event, the true reward parameter and mean post-serving contexts belong to their respective confidence sets. Hence,
where maximizes the joint optimistic objective over . This argument requires only optimization over the feasible family and does not rely on the Top-K structure.
The regret analysis remains unchanged. The post-serving context-learning bound depends on the total number of selected-arm observations, which satisfies
Moreover, NBT-EPL (Lemma 1) applies to any selection policy choosing at most arms per round, independently of the feasible family's structure. Therefore, both the context-learning and reward-learning bounds remain valid, recovering the regret guarantee in Theorem 1.
For C$^2$UCB-PC, the monotonicity assumption and an exact combinatorial optimization oracle over preserve the optimism argument in Appendix F. Thus, Theorem 3 continues to hold. The variance-aware guarantees in Theorem 4 extend similarly under their additional assumptions.
Consequently, our existing regret upper bounds apply to partition constraints without changing their rates. We further evaluate this theoretical generality through the partition-constrained experiments below.
SLSQP restart sensitivity.
We compare restart caps of 6, 12, and 24 under , , , and five seeds.
Restart sensitivity: final cumulative pseudo-regret (mean SE).
| Method | Mapping | Cap 6 | Cap 12 | Cap 24 |
|---|---|---|---|---|
| OFUC$^2$-PC | Linear | |||
| Sine | ||||
| VA-OFUC$^2$-PC | Linear | |||
| Sine |
The final pseudo-regret shows no consistent improvement with additional SLSQP restarts. Increasing the cap from 6 to 24 raised runtime by --, while the paired 95% confidence intervals for cumulative regret differences included zero.
These results support empirical stability, although they do not certify global optimality.
Beyond Top- selection.
We additionally evaluate all seven algorithms under partition constraints with arms divided into five groups of ten, selecting exactly one arm per group.
The feasible family is
\mathcal S_{\mathrm{part}} = \left\\{ S\subseteq[m]: |S\cap G_j|=1,\\; j=1,\ldots,5 \right\\}.
Partition-constrained results (, ). Final cumulative pseudo-regret (mean SE).
| Method | Linear | Sine |
|---|---|---|
| X-only LinUCB | ||
| OFUC$^2$-PC | ||
| C$^2$UCB-PC | ||
| VA-OFUC$^2$-PC | ||
| VA-C$^2$UCB-PC |
Across both environments, all four proposed methods achieve lower mean cumulative pseudo-regret than the tested baselines. All 24 paired 95$\%$ confidence intervals exclude zero, supporting the observed improvements. The oracle-efficient methods are 25.7–32.2 times faster than their joint counterparts. These results show that our methods also work beyond Top- selection. Testing more general combinatorial constraints remains future work.
We have included the additional results in Appendix I (Figures 5–6) and Appendix K (Figures 13–15) of the revised manuscript for the reviewer's reference.
We would be happy to provide further clarification or address any additional questions you may have.
Response to Reviewer CbJd
1. Restrictive Modeling Assumptions
We thank the reviewer for highlighting these important modeling considerations.
Our assumptions follow established contextual and combinatorial bandit frameworks and serve specific purposes in our analysis. The shared linear reward model is a standard formulation in linear contextual bandits, enabling pooled parameter estimation and UCB confidence construction. The learnability conditions, following Wang et al. (2023) and Oh (2026), characterize prediction accuracy without restricting post-serving mappings to a particular parametric form. Conditional independence and zero-mean noise assumptions are commonly adopted in semi-bandit analysis to establish concentration guarantees, particularly for controlling cumulative uncertainty through NBT-EPL.
Our framework accommodates a broad range of settings beyond simple linear and additive models. Specifically, post-serving mappings can be nonlinear as long as the stated learnability conditions hold, while combinatorial reward functions can be nonlinear and non-additive under standard monotonicity and bounded-smoothness conditions. Furthermore, NBT-EPL does not require non-degenerate post-serving noise covariance. The shared linear reward model is used for our current parameter estimation and regret analysis, but parameter sharing is not required by NBT-EPL itself. An extension to arm-specific linear reward parameters is possible in principle.
The primary focus of our work is to address the challenges arising from noisy post-serving contexts and simultaneous combinatorial selection. Our main contributions include the NBT-EPL, which enables new regret guarantees, a matching minimax lower bound under the specified conditions, and the oracle-efficient C$^2$UCB-PC algorithm.
We agree that extending our framework to more general settings, such as misspecified reward models, correlated feedback, and unknown interactions among selected arms, is an interesting direction. These settings introduce additional challenges in parameter estimation and uncertainty analysis that go beyond the scope of the present work. We believe that exploring these more general settings would be a valuable direction for future research.
2. Limited Experimental Realism and Scale
We thank the reviewer for highlighting these concerns. Our additional experiments show that the proposed algorithms maintain their regret and computational advantages with substantially larger candidate-arm pools.
Larger synthetic experiments.
We evaluate all seven methods with m∈10,30,50,100, K=5, and T=20,000, under linear and sine mappings with five seeds.
Across all configurations, our four proposed methods achieve lower mean final pseudo-regret than any of the tested baselines.
Large-scale results at m=100, K=5. Final cumulative pseudo-regret (mean ± SE).
At m=100, the oracle-efficient variants achieve 29.9--38.8× runtime speedups over their joint-optimization counterparts.
Expanded MovieLens-1M experiment.
We increase the candidate pool from 10 to all 61 movies satisfying the original eligibility threshold of at least 500 construction-user ratings, without relaxing that criterion. With m=61, K=3, T=20,000, and five seeds, all four proposed methods achieve lower mean final pseudo-regret than any of the tested baselines. The oracle-efficient variants achieve approximately 10--13× runtime speedups. We acknowledge that our experiments remain semi-synthetic and use a single reward structure. Evaluations with real post-serving feedback and other reward functions remain future work.
We have included the additional results in Appendix I (Figures 7–9) and Appendix J (Figures 11–12) of the revised manuscript for the reviewer's reference.