Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation

NeurIPS 2026 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Oracle-efficient contextual bandits · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes SquareCB.Comb, a log-barrier regularized, oracle-efficient algorithm for contextual combinatorial semi-bandits with general function approximation, achieving sqrt(mAT log|F|) regret, claimed minimax optimal via a matching lower bound.

Problem

Contextual combinatorial semi-bandits with general (non-linear) reward function approximation, where the learner selects a subset of arms of cardinality at most m per round and observes semi-bandit feedback; prior regret bounds either are linear-only, suboptimal in m, or policy-based and computation

Approach

Solve an A-dimensional log-barrier regularized convex program over participation vectors each round (instead of over the exponentially large action set), then sample a combinatorial action with matching marginals; analysis via a new combinatorial square-loss decision-estimation coefficient (CS-DEC) yields sqrt(mAT log|F|) regret.

Key results

• On MSLR-WEB30k with gb5 oracle, SquareCB.Comb achieves 2.404 ± 0.001 average reward vs 2.398 for SquareCB.Lin and 2.366 for VCEE (skyline 2.536).
• On Yahoo LTR Set 1 with gb5 oracle, SquareCB.Comb achieves 3.217 ± 0.001 vs 3.211 for SquareCB.Lin, while LinUCB gets 3.168 with linear features.
• Lower bound of order sqrt(mAT log|F|) for finite classes, claimed to match the upper bound up to logs.

Surprising findings

• With the linear oracle on MSLR-WEB30k, LinUCB (2.330) outperforms SquareCB.Comb (2.024), and on Yahoo LTR the linear LinUCB also beats SquareCB.Comb with lin oracle.

Limitations

• Empirical gains over SquareCB.Lin are small (differences around 0.01 reward) and the experiments use a single pass over two LTR corpora.
• Realizability is required for the sqrt(mAT log|F|) guarantee; misspecification adds an epsilon m sqrt(A) T term.
• Sampling oracle must be designed per combinatorial structure; general efficient sampling is not provided.

Experimental setup

Datasets: MSLR-WEB30k Yahoo! Learning-to-Rank Challenge Set 1

Benchmarks: MSLR-WEB30k Yahoo! LTR Set 1

Metrics: average per-round reward at final round cumulative reward curves

Baselines: SquareCB.Lin VCEE LinUCB epsilon-greedy Uniform-random Skyline

Builds on: SquareCB E2D Decision-Estimation Coefficient FALCON C2UCB

Closest papers by meaning

• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions (AAAI 2021 · similarity 0.93)
• Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · similarity 0.91)
• From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards (NeurIPS 2025 · similarity 0.91)
• Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.90)
• Combinatorial Stochastic-Greedy Bandit (AAAI 2024 · similarity 0.90)
• Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits (NeurIPS 2024 · similarity 0.90)