Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation Hao Qin
Chicheng Zhang
The University of Arizona
arXiv:2607.13686v1 [cs.LG] 15 Jul 2026
{hqin,chichengz}@arizona.edu
Abstract We study the contextual combinatorial semi-bandit (CCSB) problem with general reward function approximation. At each round, the learner observes a context, selects a combinatorial action consisting of a subset of basic arms, and receives the reward of each selected arm; the goal is to maximize the cumulative reward over time. We propose SquareCB.Comb, a computationally efficient algorithm that, at each round, solves a convex optimization problem to sample a combinatorial action that balances exploration and exploitation. SquareCB.Comb scales to large arm sets and imposes no structural assumptions on the action set beyond a cardinality bound of m on each p combinatorial action. We prove that SquareCB.Comb achieves a minimax optimal regret bound of O mAT log |F| , where A is the number of arms, m is the maximum number of arms in a combinatorial action, T is the time horizon, and F is the reward function class. In the realizable setting, this bound matches the state-of-the-art regret guarantees achieved by policy search-based algorithms in the more restricted slate recommendation settings, while simultaneously generalizing to arbitrary combinatorial action structures and general reward function approximation.
1
Introduction
The contextual combinatorial semi-bandit (CCSB) problem is a framework for sequential decision making in which the learner repeatedly selects a subset of base arms (a combinatorial action) based on observed contextual information, with the goal of maximizing cumulative reward over time. For example, Hoseini et al. (2024) formulate bottleneck identification in road networks as a CCSB problem, where the learner repeatedly selects a source-to-destination path (a subset of road segments) and seeks to minimize the largest travel cost along the chosen path, using contextual side information such as time of day and traffic conditions. As another example, Panda et al. (2025) formulates online routing for multi-LLM serving as a CCSB problem with knapsack constraints, where for each incoming user query the learner selects a subset of LLMs (a combinatorial action) to invoke subject to a token-budget cap and seeks to maximize the resulting response quality. Other applications include energy-efficient path planning for vehicle navigation (Åkerblom, 2024), online personalized slate recommendation (Wang et al., 2017; Aramayo et al., 2023), and resource allocation in wireless networks, including channel assignment (Gai et al., 2012) and beam management (Li et al., 2025b). A CCSB environment is specified by a context space X and an arm set A of size A. The combinatorial A action space S ⊆ {0, 1} is a feasible family of subsets of A determined by the problem structure (e.g., the m-set setting Kale et al. (2010) or knapsack constraints Panda et al. (2025)). At each round t of interaction, the environment shows a context xt to the learner, together with a vector rt ∈ [0, 1]A representing the reward of each arm, hidden from the learner. The learner selects a combinatorial actionPst ∈ S based on xt , observes the semi-bandit feedback {rt (a) : st (a) = 1}, and receives reward ⟨rt , st ⟩ = a:st (a)=1 rt (a). The goal is to minimize the regret over T rounds, defined as the gap between the cumulative reward of the optimal context-dependent action in hindsight and the algorithm’s expected cumulative reward. Prior works on contextual combinatorial semi-bandits with function approximation focus on the linearreward setting, in which the expected reward of each arm is a linear function of the context (Qin et al., 2014; 1
Table 1: A comparison between our work and prior works on contextual combinatorial semi-bandits with e · hides logarithmic factors in T , A, and δ. d is the dimension of the general function approximation. O feature in the linear reward setting, and |Π| is the size of the policy class in the general reward setting. SquareCB.lin is a contextual bandit algorithm adapted to the semi-bandit setting by aggregating per-arm feedback into a slate-level reward. In the policy-class setting, regret is measured against the best policy in Π in hindsight; in the value-function-approximation setting, the learner is assumed to be realizable with respect to F and competes against the optimal context-dependent action in hindsight. Algorithm Kale et al. (2010) SquareCB.lin (Foster et al., 2020) SquareCB.comb (ours)
Problem Setting
Combinatorial Constraint
Approximation Type
Stochastic context, adversarial reward Adversarial context, stochastic reward
m-set m-ordered slate
Policy
Regret Guarantee p e mAT log(|Π|) O
General
Value
e m O
General
Value
e O
Adversarial context, stochastic reward
p AT log(|F |)
p
mAT log(|F |)
Li et al., 2025a; Takemura et al., 2021). In many real-world applications, however, the mapping from context and arm to reward is not strictly linear. For instance, user clicks in online recommendation systems often exhibit highly non-linear dependence on contextual features. In this work, we consider a general function approximation setting for CCSB, where the mapping from the context to the expected reward of the arms is assumed to lie in some known function class F. Our contributions. We propose an algorithm, SquareCB.Comb, for the CCSB problem with general reward function approximation. Our algorithm builds on the Estimation-to-Decisions principle for online decision making (Foster p et al., 2021), which lets the algorithm balance exploration and exploitation and yields e mAT log |F| , where m is the maximum number of arms in a combinatorial action, A a regret bound of O is the number of arms, T is the time horizon, and F is the reward function class. This bound matches the best known regret rate for the linear-reward setting and extends it to general reward function approximation.
2
Related Work
Contextual combinatorial semi-bandit (CCSB) with linear function approximation. Motivated by personalized recommendation, Qin et al. (2014) first introduced the contextual combinatorial semi-bandit (CCSB) problem under the assumption that the expected reward of each arm is linear in the context with a shared d-dimensional coefficient, while the reward of a combinatorial action may bepa general function of the per-arm rewards. They proposed C2 UCB, a UCB-based algorithm with an O (d + m)dmT regret guarantee. Li et al. (2016) studied a variant of the CCSB problem with a cascade feedback structure and √ proposed an algorithm with O dmT regret under a (strong) feedback coverage assumption. Takemura et al. √ (2021) gave a refined analysis of C2 UCB and obtained a minimax optimal regret guarantee of O d mT . In comparison, √ our algorithm, instantiated with a discretization of the linear reward function class, attains regret e mAdT in this setting.1 Zierahn et al. (2023) studied the adversarial linear rewards CCSB problem, O where each arm’s linear reward √ coefficient is chosen adversarially, and proposed a follow-the-regularized-leader (FTRL) algorithm with O T regret. Liu et al. (2023) generalizes the results of Li et al. (2016); Takemura et al. (2021) to linear contextual combinatorial bandits with probabilistically triggered arms; when instantiated in the setting of Li et al. (2016), their result replaces the minimum triggering probability assumption with a 1 It may appear that their lower bound contradicts ours when d is large; however, a close examination of their lower-bound instances shows that they take A = m2d .
2
natural assumption on the√ reward function. Li et al. (2025a) gave the first best-of-both-worlds algorithm for linear CCSB, attaining O T regret in the adversarial setting and O log T regret in the stochastic setting by combining FTRL with a negative Shannon entropy regularizer. Contextual combinatorial semi-bandit (CCSB) with general function approximation. Levy et al. (2023) studied the contextual MDP (CMDP) problem with adversarial losses, which can be used to solve the contextual shortest-path problem as a special case. On a graph with N nodes and M edges, the shortest-path instance can bepcast as an episodic CMDP with episode length Np ; under this reduction, e N 7 T log |F| , which is worse than our bound O e N M T log |F | in this their algorithm attains regret O setting (see Section 4.1 for details). Hwang et al. (2023) studied the general function approximation with a Lipschitz continuity assumption and proposed algorithms based on the Thompson sampling and UCB p ˜ e principles, achieving O mdT , where d˜ is the effective dimension of the neural tangent kernel associated with the reward function class. Another line of work approaches CCSB via policy search: the learner is given a policy class Π and seeks to minimize regret against the best policy in Π in hindsight. The early work of Kale p et al. (2010) e mAT log(|Π|) proposed algorithms based on exponential weighting over the policy class, achieving O regret in the unordered and ordered slate settings with n items (where A = n and mn respectively). Their algorithm is computationally inefficient as it requires enumerating all policies in the policy class. Subsequently, Krishnamurthy et al. (2016) studied CCSB with a linearly weighted reward structure and proposed the VCEE algorithm, which improves computational efficiency by extending the policy elimination technique of Agarwal et al. (2014) to call a cost-sensitive classification class rather than enumerating all policies. p oracle overthe policy p e mAT log |Π| and O e m AT log |Π| , depending on the reward Their regret guarantee ranges between O structure. Erez and Koren (2025) studied CCSB in both the PAC guarantee and the regret minimization settings, and adapted the technique of Agarwal to construct an importance-weighted sampler p et al. (2014) e over the policy class, achieving an O |Π| + msT log |Π| regret guarantee under the sparsity assumption ∥rt ∥1 ≤ s, where Π denotes the policy class. We compare our work with the most related prior works in Table 1. Applying contextual bandit algorithms to the CCSB problem. A natural approach to the CCSB problem is to reduce it to a contextual bandit problem with reward being linear in action per-context 2 A Specifically, we encode each combinatorial action s ∈ S ⊆ {0, 1} as a binary indicator vector and define A the reward as ⟨r(x), s⟩, where r(x) ∈ R is an unknown context-dependent per-arm reward vector. Under this canonical reduction, off-the-shelf regression-based contextual bandit algorithms apply directly, including SquareCB.Lin (Foster et al., 2020), the linear FALCON algorithm of Xu and Zeevi (2020), and the SpannerIGW algorithm of Zhu et al. (2022); all of these algorithms operate in the linear reward structure per-context setting and generalize the inverse-gap-weighting (IGW) algorithm of Abe and Long (1999), which learns an estimate of the reward p function and uses it to sample actions. Applying SquareCB.Lin under this reduction e m AT log |F| in the m-set setting, where F denotes the underlying reward function yields a regret of O class. The extra factor of m originates from the reward aggregation. Due to space limits, additional related works are discussed in Section B.
3
Preliminaries
P Basic notations. For any two vectors x, y ∈ RA , we write x, y := a∈A x(a)y(a) for their inner product. pP 2 2 For any set S ⊆ RA , we write Conv(S) for its convex hull, and ||f ||p = a∈A p(a)f (a) for the L (p) norm A of a vector f ∈ R . ∆(S) denotes the set of distributions over S. O · and Ω · denote upper and lower e · and Ω e · additionally hide polylogarithmic bounds that hide absolute constants; their tilde variants O factors in A, m, T, log |F |. We write ≲ for inequalities that hide absolute constants. 2 This is different from the aforementioned “reward linear in context”setting.
3
Contextual combinatorial semi-bandits. Let X be a context space and A a finite set of arms with size A A. The set of feasible combinatorial actions is S ⊆ {0, 1} , where for any combinatorial action s ∈ S, s(a) = 1 encodes that arm a is selected by s. The agent is given a class F of mean reward functions f : X × A → [0, 1], and we adopt two standard assumptions. Assumption 1 (Realizability). The ground-truth reward function f ⋆ lies in F . Assumption 2 (Bounded combinatorial-action size). There exists a known constant m ∈ N such that ∥s∥1 ≤ m for every s ∈ S. Realizability is a standard assumption in the contextual bandit literature and is necessary for sublinear regret with general function classes (Foster and Rakhlin, 2020; Foster et al., 2020). Lattimore et al. (2020) show that, without realizability, linear regret of order εT is unavoidable for linear contextual bandits with misspecification level ε. The bounded combinatorial-action-size assumption is also standard in the combinatorial bandit literature, as it covers many applications including unordered and ordered slate selection (Kale et al., 2010), maximum-weight matching (Gai et al., 2012), and weighted online recommendation (Kveton et al., 2015). Interaction protocol.
At each round t = 1, . . . , T :
1. the environment draws a context xt and a reward vector rt ∈ [0, 1]A , with xt revealed to the agent. We assume that E [rt (a) | xt = x] = f ⋆ (x, a). 2. the agent selects a combinatorial action st ∈ S; 3. the agent observes semi-bandit feedback ot = (rt (a))a:st (a)=1 The expected reward of combinatorial action s on context x takes a linear form s, f (x, ·) , where f (x, ·) ∈ RA stacks the per-action rewards. We denote the optimal combinatorial action at context x by s⋆ (x) := t arg maxs∈S s, f ⋆ (x, ·) . After t rounds, the agent has collected a dataset Dt = {(xi , si , oi )}i=1 . Running examples. As example applications, we will demonstrate the utility of our algorithm on the following examples throughout this paper: • Unordered m-set recommendations Kale et al. (2010). Here we have A = n available with n items n items for recommendation, S = s ∈ 0, 1 : ∥s∥1 = m contains all subsets of size m that can be recommended at each round. Each item is regarded equally, and we observe the user’s click-through rates on the items recommended. • Ordered m-slate recommendations with n items Kale et al. (2010). Here, the user’s click-through rate depends on both the item recommended and its position in the ranked list. Here, our combinatorial Pm m×n Pn action set is the set of permutations: S = M ∈ 0, 1 : j=1 Mi,j = 1, ∀i and i=1 Mi,j ≤ 1, ∀j , where Mi,j = 1 indicates that item j is recommended at position i. Therefore, A = m · n. • Contextual shortest path on a directed acyclic graph (DAG) Hoseini et al. (2024). Here, we have a DAG vertices V andPM edges E, together with a designated source s and terminal t; with N P S = (xe )e∈E : e∈N+ (v) xe − e∈N− (v) xe = I(v = t) − I(v = s), xe ∈ {0, 1} is the set of all s-t paths, where N+ (v) and N− (v) are the sets of edges entering and leaving v, respectively. Semi-bandit feedback means that the learner only sees the delays on the road segments it traverses. In this example, A = M and we may take m ≤ N . The agent’s goal is to minimize its cumulative (pseudo-)regret: Regret(T ) :=
PT
⋆ ⋆ t=1 ⟨s (xt ), f (xt , ·)⟩ −
4
PT
t=1 ⟨st , f
⋆
(xt , ·)⟩ .
(1)
Distributions, participation vectors, and policies. Given a distribution p ∈ ∆(S) over combinatorial actions, denote by its participation vector p̄ ∈ S̄ such that p̄(a) := Es∼p [s(a)] , a ∈ A. For each p̄ ∈ S̄, the p that corresponds to it may not be unique. A policy is a (measurable) map π : X → ∆(S). Given a context x, we write π̄(x) ∈ S̄ for the participation vector of distribution π(x) ∈ ∆(S). Note that π̄(x) is A-dimensional, and its a-th coordinate π̄(x)(a) is the marginal probability of selecting arm a under π(x). Batch-mode online regression oracle. Online regression oracles are commonly used in the design and analysis of contextual bandit algorithms (Foster and Rakhlin, 2020; Zhu and Mineiro, 2022). Since we observe reward feedback from multiple arms at each round, in this paper we adopt the following batchmode formulation of the online square-loss regression oracle Obatch . Let G be a finite function class. At each round t, the regression oracle first outputs a predictor ĝt based on past batches, and then receives a Bt batch {(zt,b , yt,b )}b=1 of Bt ≤ B labeled examples. The regression oracle’s performance is measured by the square-loss regret compared to the best predictor in G on the sequence of batches: PT PBt PT PBt 2 2 Regbatch (T ) = t=1 b=1 (ĝt (zt,b ) − yt,b ) − inf g∈G t=1 b=1 (g(zt,b ) − yt,b ) . We make the following assumption on the batch-mode online regression oracle Obatch : Assumption 3 (Batch-mode online regression oracle). Suppose the reward function g ⋆ belongs to a finite function class G. The batch-mode online regression oracle Obatch with batch size B guarantees that, for any T sequence of inputs and outputs {(zt,b , yt,b )}t=1 , where yt,b ∈ [0, 1] for all t, b, the predictors ĝt ’s output by Obatch satisfy Regbatch (T ) ≲ B log |G|. Indeed, Mesterharm (2005) gives a reduction from the batch/delayed-feedback setting to the standard online learning setting that incurs an additional multiplicative factor of B relative to the standard regret bound. Furthermore, when G is finite, the Exponentially Weighted Average (EWA) algorithm attains regret O log |G| in the standard online learning setting (Cesa-Bianchi and Lugosi, 2006; Rakhlin and Sridharan, 2014b), which translates into regret O B log |G| in the batch-mode setting.
4
Proposed Algorithm
We propose an algorithm for thepcontextual combinatorial semi-bandit setting, called SquareCB.Comb e mAT log |F| regret under the realizability assumption. The algorithm is (Algorithm 1), which achieves O inspired by the SquareCB algorithm for contextual bandits (Foster and Rakhlin, 2020), whose action-selection rule is the solution of a log-barrier regularized optimization problem (Foster et al., 2020) every round. At each round, the learner obtains an estimate of the reward function by calling a batch-mode online regression oracle Obatch trained on past observations of the form (context, arms, rewards) (line 3), and observes the context xt (line 4). The learner then computes a participation vector p̄t over arms by solving a log-barrier regularized optimization problem (line 5), and invokes a sampling oracle Osample to sample a combinatorial action st whose marginals match p̄t (line 6). Finally, the learner observes the semi-bandit feedback ot (line 7) and forwards the new observation to Obatch for use in the next round. Computing an exploratory participation vector. Our key algorithmic innovation lies in the computation of the participation vector p̄t : at that step, the learner solves the following A-dimensional convex optimization problem (Eq. (2)). The first term in the objective, p̄, fˆt (xt , ·) , measures the “greediness” of ˆ the participation vector p̄, i.e., how Poptimal p̄ is with respect to the current reward function estimate ft and context xt ; the second term γ1 a∈A log p̄(a) is a log-barrier regularizer that encourages p̄ to spread its support, thereby preventing concentration on a small set of arms and promoting exploration. By balancing these two terms, the learner obtains a participation vector that exploits the current reward estimate while ensuring sufficient exploration to control the estimation error.
5
Algorithm 1 SquareCB.Comb 1: Input: Semi-bandit tuple (X , S, A), online regression oracle Obatch , sampling oracle Osample , reward function
class F, exploration schedule γ. 2: for round t = 1, 2, . . . do 3: Receive an updated estimate fˆt from Obatch based on the history {(xτ , sτ , oτ )}τ <t . 4: Observe context xt . 5: Compute a participation vector p̄t ∈ S̄ by solving
D E 1 X log p̄(a). p̄t = arg max p̄, fˆt (xt , ·) + γ a∈A p̄∈S̄
(2)
6: Sample a combinatorial action st such that E [st ] = p̄t by calling Osample (p̄t , S). 7: Observe semi-bandit feedback ot = {rt (a) : st (a) = 1}. 8: end for
Sampling Oracle for Combinatorial Constraints. The learner needs to sample a combinatorial action st from a distribution pt ∈ ∆(S) whose marginal expectation matches the participation vector p̄t computed in Line 5. This step is nontrivial because the participation vector p̄t is defined in the convex hull of the combinatorial action space S̄, whose dimension is A, while the actual sampling must be performed in ∆(S), a space of dimension |S| that can be exponentially larger than A. For many structured combinatorial action sets, however, efficient sampling algorithms are readily available. For instance: • Unordered m-set recommendations with n items. Here, after computing p̄t , we can use dependent rounding (Gandhi et al., 2006) to sample st with running time O(n). • Ordered m-slate recommendations with n items. Kale et al. (2010) give an efficient sampler (which in turn uses the efficient algorithm of Helmbold and K Warmuth (2009)) that first decomposes any p̄ ∈ S̄ to a convex combination of n2 matrices, and samples from it. • Contextual shortest path on DAG. Any p̄ ∈ S̄ is a unit s-t flow, and can be represented as a convex combination of s-t paths via standard flow decomposition procedures (Ahuja et al., 1988). When S admits an efficient linear optimization oracle (i.e., arg mins∈S ⟨ℓ, s⟩ is tractable for any ℓ), as in shortest path and Pn maximum weight matching, lines 5 and 6 can be merged: Frank-Wolfe on Eq. (2) produces iterates p̄n = i=1 αi si with si ∈ S and α ∈ ∆n−1 , so sampling i ∼ Categorical(α) and returning si yields st with marginals p̄n . See Algorithm 2 in Appendix C.
4.1
Regret Analysis of SquareCB.Comb
We now present the main regret guarantee of SquareCB.Comb. In Theorem 1, we give a general regret bound in terms of the online regression oracle’s square-loss regret Regbatch (T ), which, combined with the guarantee of Assumption 3, yields the explicit bound in Corollary 2. Theorem 1 (Total regret bound). p Suppose Assumptions 1 and 2 hold and SquareCB.Comb uses the constant exploration parameter γ = AT /Regbatch (T ). Then the expected regret of SquareCB.Comb is bounded as p A T Regbatch (T ) . E [Regret(T )] ≤ O Combining Theorem 1 with the guarantee of the online regression oracle in the finite-class semi-bandit setting gives the following regret bound: q AT Corollary 2. Under Assumptions 1 to 3, and γ = m log|F | , the expected regret of SquareCB.Comb is upper bounded by p E [Regret(T )] ≤ O mAT log |F| . 6
√ The bound is sublinear in T and exhibits the same mAT dependence as the standard regret rate for the stochastic combinatorial semi-bandit problem under linear rewards (Kveton et al., 2015), while permitting the mean reward function to belong to a general class F. When m = 1, the contextual combinatorial semi-bandit p setting reduces to the standard contextual bandit setting, and Theorem 1 recovers the AT log |F| regret of the IGW algorithm for contextual bandits (Foster and Rakhlin, 2020) under realizability. Compared with reducing CCSB to a contextual bandit problem on the slate space and applying a contextual bandit algorithm p top the aggregated full-bandit reward, SquareCB.Comb’s regret bound scales as mAT log |F| rather than m AT log |F| (see Section F for a formal justification); this gap can be significant when m is large. Specializing Corollary 2 to the three running examples gives: with n items. Each arm corresponds to one so A = n, and Corollary 2 • Unordered m-set p p of the n items, e mnT log |F| . This matches the O e mnT log |Π| regret of Kale et al. (2010); yields regret O Krishnamurthy et al. (2016), which compete against the best policy in a class Π, while SquareCB.Comb is computationally more efficient since it relies on a better practicality of regression oracles relative to classification oracles. p e m nT log |F| , comparable • Ordered m-slate with n items. Since A = mn, Corollary 2 yields regret O to the bound of Kale et al. (2010) with better computational efficiency. p e N M T log |F| . • Contextual shortest path on a DAG. Since A = M and m ≤ N , Corollary 2 yields regret O In comparison, applying the contextual MDP algorithm of Levy et al. (2023) requires solving an N -state, p 7 e N -action MDP with episode length H = N , which yields regret at least O N T log |F| . Extensions: infinite classes, misspecified setting, and offline oracle-efficient algorithm. Theorem 1 treats the regression oracle abstractly through its cumulative square-loss regret Regbatch (T ), which readily yields regret-efficient CCSB algorithms beyond the basic realizable, finite-class setting by plugging in different online regression oracles. For an infinite class F, instantiating the oracle with online squareloss regression based on sequential covering or sequential Rademacher complexity (Rakhlin and Sridharan, 2014a,b) replaces m log |F | with the corresponding sequential complexity. For the ε-misspecified setting, where inf f ∈F supx,a |f (x, a) − f ⋆ (x, a)| ≤ ε, combining SquareCB.Comb with the misspecification-aware online p √ regression oracle of Foster et al. (2020) yields regret O mAT log |F| + εm AT ; the additive εT factor is √ unavoidable in light of the Ω(ε dT ) lower bound of Lattimore et al. (2020) for the misspecified d-dimensional linear bandit problem. In Section E, we present a variant of SquareCB.Comb that reduces CCSB to O(log T ) offline regression problems while enjoying similar regret guarantees when the contexts are i.i.d. Given the wider availability of offline regression guarantees, this variant can be preferable in practice (Foster et al., 2024).
4.2
Proof sketch of Theorem 1
In this section, we provide a proof sketch of Theorem 1. We aim to adopt an analysis similar to SquareCB Foster and Rakhlin (2020) that first bounds the instantaneous regret at round t in terms of the expected regression error at the same round, and then conclude the regret bound by summing over all t’s. However, SquareCB’s analysis is inherently tied to bandit feedback (the learner receives a single reward observation per round) and thus does not extend to our semi-bandit setting. Furthermore, the general E2D algorithm (Foster et al., 2021) (see Section A for a brief overview of the DMSO framework and the Decision-Estimation Coefficient) is not directly applicable here, since we do not have exact knowledge of the conditional distribution of {rt (a) : st (a) = 1} given the reward model f and (xt , st ). This inspires us to define a new notion of DEC customized to square loss and combinatorial semi-bandits: Definition 1. For a regressor ĝ : A → [0, 1], a function class G, and a combinatorial action set S, define
7
their combinatorial square-loss DEC (CS-DEC) as decγ (ĝ, G) = min
⋆
max
p∈∆(S) q∈∆(S),g ⋆ ∈G
⋆
Es∼q [⟨g , s⟩] − Es∼p [⟨g , s⟩] − γEs∼p
" A X
# ⋆
2
s(a)(ĝ(a) − g (a))
,
(3)
a=1
{z
|
}
=:F (p)
and define decγ (G) = maxĝ decγ (ĝ, G). The CS-DEC accounts for the semi-bandit feedback by offsetting the instantaneous regret with the expected square-loss regression error over the entire set of arms associated with the combinatorial action; unlike DEC, it does not rely on exact probabilistic modeling of the reward distribution. To use CS-DEC for algorithm design, we need to find a distribution p ∈ ∆(S) that approximately minimizes F (·). This is in general difficult, since the corresponding optimization problem is |S|-dimensional and |S| may be exponential in m. Our key observation is that the CS-DEC admits an equivalent representation in the space of participation vectors, which has the much lower dimension A, thereby admitting tractable solutions: Proposition 3. We have the following equivalent characterization: decγ (ĝ, G) = min
max
⟨g ⋆ , q̄⟩ − ⟨g ⋆ , p̄⟩ − γ
p̄∈S̄ q̄∈S̄,g ⋆ ∈G
A X
p̄(a)(ĝ(a) − g ⋆ (a))2 .
(4)
a=1
|
{z
=:F̄ (p̄)
}
In addition, any p such that Es∼p [s] = p̄ satisfies that F (p) = F̄ (p̄). This enables the optimization problem (3) to be approximately solved in two steps: first, compute a p̄ that approximately solves (4); second, convert p̄ into a distribution p ∈ ∆(S) satisfying Es∼p [s] = p̄. We show that the solution to the optimization problem in line 5 certifies that decγ (fˆt (xt , ·), Fxt ) ≤ A γ, where Fxt := {f (xt , ·) : f ∈ F }. To this end, we design a surrogate min-max objective that relaxes the DEC, and establish two intermediate results: (i) the participation vector computed by the log-barrier optimization certifies a small value of the surrogate min-max objective; and (ii) a small value of the surrogate objective certifies a small value of the DEC. Specifically, our surrogate objective is: D E D E 1 inf max fˆt (xt , ·), q̄ − fˆt (xt , ·), p̄ + Coverage(p̄, q̄). (5) γ p̄∈S̄ q̄∈S̄ 2 P where Coverage(p̄, q̄) = a∈A q̄(a) p̄(a) quantifies the estimation error under the data collected using action distributions with participation vector p̄ when trying to estimate the reward of action distribution with participation vector q̄. In Lemma 5, we show that the p̄t computed by the log-barrier optimization certifies a small value of the above surrogate objective. Subsequently, in Lemma 6, we show that any participation vector p̄t that certifies the surrogate min-max objective to be smaller than A/γ also certifies the DEC to be smaller than O(A/γ). Combining the above two lemmas yields the instantaneous regret decomposition:
max ⟨s, f ⋆ (xt , ·)⟩ − ⟨p̄t , f ⋆ (xt , ·)⟩ ≲ s∈S
A + γ||fˆt (xt , ·) − f ⋆ (xt , ·)||p̄2t . γ
By taking the instantaneous regret decomposition at each round and summing over t, we have T X t=1
max ⟨s, f ⋆ (xt , ·)⟩ − s∈S
T X
⟨p̄t , f ⋆ (xt , ·)⟩ ≲
t=1
≤
8
T X AT +γ ||fˆt (xt , ·) − f ⋆ (xt , ·)||2p̄t γ t=1
AT + γRegbatch (T ). γ
Here, the second inequality is due to the batch-mode online regression oracle’s guarantee as well as that E [yt (a) | xt ] = f ⋆ (xt , a) p for all a ∈ A. Finally, taking expectation over the randomness in the algorithm and history, choosing γ = AT /Regbatch (T ) yields the regret guarantee of Theorem 1: p E [Regret(T )] ≲ AT Regbatch (T ). Under Assumption 3, substituting Regbatch (T ) = m log |F| recovers the result in Corollary 2.
5
Lower Bound
We complement the upper bound of Corollary 2 with a matching lower bound, showing that SquareCB.Comb is minimax optimal in m, A, T , and log |F| up to logarithmic factors. The lower bound is parameterized by an upper bound N on the size of the reward function class F used in the construction. Theorem 4 (Lower bound for CCSB with finite function class). For any m, A, T, N ∈ N such that A/m ∈ N, N ≥ A/m, T /⌊logA/m N ⌋ ∈ N, and T /⌊logA/m N ⌋ ≥ 16A/m, there exists a CCSB problem with A arms and combinatorial-action size at most m, and a reward function class F with |F| ≤ N , such that for any algorithm √ Alg there isan environment realizable with respect to F on which the expected regret of Alg is at e m A T log N . least Ω The construction (deferred to Section H) partitions the horizon into M = ⌊logA/m N ⌋ equal-length intervals, assigns each interval a distinct context, and embeds an independentpnon-contextual m-path instance of Kveton et al. (2015) into each interval. Aggregating the per-interval Ω mAT /M regret across the M intervals yields the displayed bound. p e Minimax optimality. Setting N = |F| in Theorem 4 yields a lower bound of Ω m A T log |F | , which matches the upper bound of Corollary 2 up to polylogarithmic factors. Hence SquareCB.Comb attains the minimax-optimal regret rate for CCSB with general reward function approximation up to logarithmic factors. To our knowledge, this is the first minimax-optimal regret guarantee for CCSB beyond the linear-reward setting. We also remark that our lower bound crucially uses the dependence of (rt (a))a∈A . Under the additional assumption that (rt (a))a∈A are independent given xt (as studied in Combes et al. (2015)), we p e m A T log |F | ; we leave this as an conjecture that the minimax regret bound may be strictly lower than O interesting open question.
6
Experiments
We compare SquareCB.Comb against several semi-bandit and contextual-bandit baselines on two public learning-to-rank corpora, running each algorithm for a single pass over the entire corpus, so that the horizon T equals the corpus size. We first search an optimal hyperparameter for each algorithm by maximizing the mean realized cumulative reward over the tuning seeds, then choose the best hyperparameter for each algorithm and compare their performance on 10 disjoint runs. Datasets. We use MSLR-WEB30k (Qin and Liu, 2013) and the Yahoo! Learning-to-Rank Challenge Set 1 (Chapelle and Chang, 2011). Both corpora are recast as CCSB instances via the standard supervised-tobandit reduction (Krishnamurthy et al., 2016; Qin et al., 2014; Foster and Rakhlin, 2020), with per-document relevance labels in {0, 1, 2, 3, 4} used as semi-bandit feedback. Following the conventions of Krishnamurthy et al. (2016), we set the candidate pool size A = 10 and the slate size m = 3 on MSLR-WEB30k, and A = 6, m = 2 on Yahoo! LTR Set 1. After filtering out queries with fewer than A candidate documents, each run makes one pass over the remaining queries, giving horizons of T = 30,846 rounds on MSLR-WEB30k and T = 27,630 rounds on Yahoo! LTR Set 1 (see Section G for details).
9
Figure 1: Per-round average reward on MSLR-WEB30k (left) and Yahoo! LTR Set 1 (right), with each online learner instantiated on the depth-5 gradient-boosted regression-tree (gb5) oracle (LinUCB is linear-only). The X-axis is logarithmic. Curves are the means over 10 seeds with ±1 standard deviation. The supervised Skyline (gb5, the ceiling) and Uniform-random (the floor) references bracket the online algorithms. Algorithms. We instantiate SquareCB.Comb (Algorithm 1) with a linear regression (lin) and a gradientboosted regression tree ensemble (gb; see Appendix section G.3 for details) as its regression oracle. We compare against four other algorithms: SquareCB.Lin (Foster et al., 2020), which replaces the per-arm A IGW sampler with a log-determinant optimization problem over the m size-m super-arms, drawing the slate as one categorical sample from the resulting distribution and uses the summed semi-bandit reward feedback as bandit reward feedback; VCEE (Krishnamurthy et al., 2016), the policy-based contextual combinatorial bandit algorithm; LinUCB (Chu et al., 2011), the linear UCB algorithm adapted to the semi-bandit setting; and ε-greedy (Langford and Zhang, 2007), which maintains an online regression oracle of per-arm rewards and, at each round, plays a uniformly random size-m slate with probability ε or the predicted top-m slate under the oracle otherwise. We additionally report two non-learning algorithms for reference: a uniform-random slate (the floor), and a supervised skyline (the ceiling) that fits a regression oracle once on the entire labeled corpus and then greedily plays the in-sample top-m arms every round; the table (Table 2) reports one skyline per regression oracle (lin, gb2, gb5). Results. Figure 1 plots the per-round average reward (on a logarithmic round axis) and Table 2 reports its value at the final round t = T , both over the 10 disjoint Stage-2 seeds: the figure shades √ a ±1 standarddeviation band across the 10 seeds, while the table reports the mean ± standard error (std/ 10).
10
Table 2: Average per-round reward at the final round, broken out by regression oracle (lin, gb2, gb5). Mean ± standard error over 10 seeds. In each column, the highest average reward among the online learners (excluding the Skyline) is shown in bold. Skyline and Uniform-random are non-online learning references that upper and lower bound the performance of online algorithms; Skyline is reported separately for each regression oracle. LinUCB is linear-only. MSLR-WEB30k
Yahoo! LTR Set 1
Algorithm
lin
gb2
gb5
lin
gb2
gb5
Skyline
2.340 ± 0.001
2.402 ± 0.001
2.536 ± 0.001
3.209 ± 0.001
3.219 ± 0.001
3.335 ± 0.001
SquareCB.Comb (ours) 2.024 ± 0.002 2.373 ± 0.002 2.404 ± 0.001 3.141 ± 0.001 3.187 ± 0.001 3.217 ± 0.001 SquareCB.Lin 2.028 ± 0.002 2.366 ± 0.002 2.398 ± 0.002 3.138 ± 0.001 3.184 ± 0.001 3.211 ± 0.001 VCEE 2.252 ± 0.002 2.309 ± 0.003 2.366 ± 0.003 3.083 ± 0.009 3.132 ± 0.001 3.189 ± 0.002 ε-greedy 2.030 ± 0.002 2.373 ± 0.001 2.401 ± 0.002 3.140 ± 0.001 3.186 ± 0.001 3.214 ± 0.001 LinUCB 2.330 ± 0.002 — — 3.168 ± 0.001 — — Uniform-random
1.815 ± 0.002
2.591 ± 0.002
References N. Abe and P. M. Long. Associative reinforcement learning using linear probabilistic concepts. In ICML, pages 3–11, 1999. A. Agarwal, M. Dud\’\ik, S. Kale, J. Langford, and R. Schapire. Contextual bandit learning with predictable rewards. In Artificial Intelligence and Statistics, pages 19–26, 2012. A. Agarwal, D. Hsu, S. Kale, J. Langford, L. Li, and R. Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International conference on machine learning, pages 1638–1646. PMLR, 2014. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows. 1988. N. Åkerblom. Combinatorial semi-bandit methods for navigation of electric vehicles. Chalmers Tekniska Hogskola (Sweden), 2024. V. Anantharam and P. Varaiya. Asymptotically Efficient Allocation Rules for the Multiarmed Bandit Problem with Multiple Plays—Part I: I.I.D. Rewards. Automatic Control, IEEE Transactions on, 32:968 – 976, Dec. 1987. doi: 10.1109/TAC.1987.1104491. N. Aramayo, M. Schiappacasse, and M. Goic. A multiarmed bandit approach for house ads recommendations. Marketing Science, 42(2):271–292, 2023. J.-Y. Audibert, S. Bubeck, and G. Lugosi. Minimax policies for combinatorial prediction games. In Proceedings of the 24th Annual Conference on Learning Theory, pages 107–132. JMLR Workshop and Conference Proceedings, 2011. J.-Y. Audibert, S. Bubeck, and G. Lugosi. Regret in Online Combinatorial Optimization. Mathematics of Operations Research, 39(1):31–45, 2014. N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006. O. Chapelle and Y. Chang. Yahoo! learning to rank challenge overview. In Proceedings of the learning to rank challenge, pages 1–24. PMLR, 2011. W. Chen, Y. Wang, Y. Yuan, and Q. Wang. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. Journal of Machine Learning Research, 17(50):1–33, 2016. 11
W. Chu, L. Li, L. Reyzin, and R. E. Schapire. Contextual Bandits with Linear Payoff Functions. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 15, pages 208– 214, 2011. R. Combes, M. S. Talebi Mazraeh Shahi, A. Proutiere, et al. Combinatorial bandits revisited. Advances in neural information processing systems, 28, 2015. L. Erez and T. Koren. From contextual combinatorial semi-bandits to bandit list classification: Improved sample complexity with sparse rewards. arXiv preprint arXiv:2502.09257, 2025. D. Foster and A. Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199–3210. PMLR, 2020. D. Foster, A. Agarwal, M. Dudik, H. Luo, and R. Schapire. Practical Contextual Bandits with Regression Oracles. In Proceedings of the International Conference on Machine Learning (ICML), pages 1534–1543, 2018. D. J. Foster, C. Gentile, M. Mohri, and J. Zimmert. Adapting to misspecification in contextual bandits. Advances in Neural Information Processing Systems, 33:11478–11489, 2020. D. J. Foster, S. M. Kakade, J. Qian, and A. Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487, 2021. D. J. Foster, A. Rakhlin, A. Sekhari, and K. Sridharan. On the complexity of adversarial decision making. Advances in Neural Information Processing Systems, 35:35404–35417, 2022. D. J. Foster, Y. Han, J. Qian, and A. Rakhlin. Online estimation via offline estimation: An informationtheoretic framework. Advances in Neural Information Processing Systems, 37:42840–42898, 2024. Y. Gai, B. Krishnamachari, and R. Jain. Combinatorial network optimization with unknown variables: Multiarmed bandits with linear rewards and individual observations. IEEE/ACM Transactions on Networking, 20(5):1466–1478, 2012. R. Gandhi, S. Khuller, S. Parthasarathy, and A. Srinivasan. Dependent rounding and its applications to approximation algorithms. Journal of the ACM (JACM), 53(3):324–360, 2006. D. P. Helmbold and M. K Warmuth. Learning permutations with exponential weights. Journal of Machine Learning Research, 10(7), 2009. F. Hoseini, N. Åkerblom, and M. Haghir Chehreghani. A contextual combinatorial semi-bandit approach to network bottleneck identification. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pages 3782–3786, 2024. T. Hwang, K. Chai, and M.-h. Oh. Combinatorial neural bandits. In International Conference on Machine Learning, pages 14203–14236. PMLR, 2023. M. Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In International conference on machine learning, pages 427–435. PMLR, 2013. M. Jourdan, M. Mutnỳ, J. Kirschner, and A. Krause. Efficient pure exploration for combinatorial bandits with semi-bandit feedback. In Algorithmic Learning Theory, pages 805–849. PMLR, 2021. S. Kale, L. Reyzin, and R. E. Schapire. Non-stochastic bandit slate problems. Advances in Neural Information Processing Systems, 23, 2010. J. Kirschner, A. Bakhtiari, K. Chandak, V. Tkachuk, and C. Szepesvári. Regret minimization via saddle point optimization. Advances in Neural Information Processing Systems, 36:35246–35265, 2023. 12
A. Krishnamurthy, A. Agarwal, and M. Dudik. Contextual semibandits via supervised learning oracles. Advances In Neural Information Processing Systems, 29, 2016. B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvari. Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence and Statistics, pages 535–543. PMLR, 2015. J. Langford and T. Zhang. The epoch-greedy algorithm for contextual multi-armed bandits. Advances in neural information processing systems, 20(1):96–1, 2007. T. Lattimore, C. Szepesvari, and G. Weisz. Learning with good feature representations in bandits and in rl with a generative model. In International conference on machine learning, pages 5662–5670. PMLR, 2020. O. Levy, A. Cohen, A. Cassel, and Y. Mansour. Efficient rate optimal regret for adversarial contextual mdps using online function approximation. In International Conference on Machine Learning, pages 19287–19314. PMLR, 2023. M. Li, P. J. Schneider, J. Aleksić, and D. Kuhn. Efficient best-of-both-worlds algorithms for contextual combinatorial semi-bandits. arXiv preprint arXiv:2508.18768, 2025a. S. Li, B. Wang, S. Zhang, and W. Chen. Contextual combinatorial cascading bandits. In International conference on machine learning, pages 1245–1253. PMLR, 2016. Z. Li, X. Luo, M. Chen, C. Xu, S. Mao, and Y. Liu. Contextual combinatorial beam management via online probing for multiple access mmwave wireless networks. IEEE Journal on Selected Areas in Communications, 43(3):959–972, 2025b. X. Liu, J. Zuo, S. Wang, J. C. Lui, M. Hajiesmaili, A. Wierman, and W. Chen. Contextual combinatorial bandits with probabilistically triggered arms. In International Conference on Machine Learning, pages 22559–22593. PMLR, 2023. C. Mesterharm. On-line learning with delayed label feedback. In International Conference on Algorithmic Learning Theory, pages 399–413. Springer, 2005. G. Neu, M. Papini, and L. Schwartz. Optimistic information directed sampling. In The Thirty Seventh Annual Conference on Learning Theory, pages 3970–4006. PMLR, 2024. P. Panda, R. Magazine, C. Devaguptapu, S. Takemori, and V. Sharma. Adaptive llm routing under budget constraints. arXiv preprint arXiv:2508.21141, 2025. H. Qin and C. Zhang. Taming the monster every context: Complexity measure and unified framework for offline-oracle efficient contextual bandits. arXiv preprint arXiv:2602.09456, 2026. L. Qin, S. Chen, and X. Zhu. Contextual combinatorial bandit and its application on diversified online recommendation. In Proceedings of the 2014 SIAM international conference on data mining, pages 461–469. SIAM, 2014. T. Qin and T. Liu. Introducing LETOR 4.0 datasets. CoRR, abs/1306.2597, 2013. URL http://arxiv. org/abs/1306.2597. A. Rakhlin and K. Sridharan. Online non-parametric regression. In Conference on Learning Theory, pages 1232–1264. PMLR, 2014a. A. Rakhlin and K. Sridharan. Statistical learning and sequential prediction. Book Draft, 6, 2014b. D. Simchi-Levi and Y. Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 47(3):1904–1931, 2022.
13
K. Takemura, S. Ito, D. Hatano, H. Sumita, T. Fukunaga, N. Kakimura, and K.-i. Kawarabayashi. Nearoptimal regret bounds for contextual combinatorial semi-bandits with linear payoff functions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9791–9798, 2021. Y. Wang, H. Ouyang, C. Wang, J. Chen, T. Asamov, and Y. Chang. Efficient ordered combinatorial semibandits for whole-page recommendation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017. Y. Xu and A. Zeevi. Upper counterfactual confidence bounds: a new optimism principle for contextual bandits. arXiv preprint arXiv:2007.07876, 2020. Y. Zhu and P. Mineiro. Contextual bandits with smooth regret: Efficient learning in continuous action spaces. In International Conference on Machine Learning, pages 27574–27590. PMLR, 2022. Y. Zhu, D. J. Foster, J. Langford, and P. Mineiro. Contextual bandits with large action spaces: Made practical. In International Conference on Machine Learning, pages 27428–27453. PMLR, 2022. L. Zierahn, D. van der Hoeven, N. Cesa-Bianchi, and G. Neu. Nonstochastic contextual combinatorial bandits. In International conference on artificial intelligence and statistics, pages 8771–8813. PMLR, 2023. J. Zimmert, H. Luo, and C.-Y. Wei. Beating stochastic and adversarial semi-bandits optimally and simultaneously. In International Conference on Machine Learning, pages 7683–7692. PMLR, 2019.
14
Contents 1 Introduction
1
2 Related Work
2
3 Preliminaries
3
4 Proposed Algorithm 4.1 Regret Analysis of SquareCB.Comb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Proof sketch of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 6 7
5 Lower Bound
9
6 Experiments
9
A Decision Making with Structured Observations
15
B Additional Related Work
16
C Sampling from exploration distribution using linear optimization oracle
17
D Regret Guarantees of SquareCB.comb 17 D.1 Lemmas about the reduction from DEC to the log-barrier optimization . . . . . . . . . . . . . 17 D.2 Regret guarantee of SquareCB.Comb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 E An Offline Oracle-efficient Variant: OE2D.Comb
20
F The Suboptimality of Using Contextual Bandit Algorithms to Solve CCSB Problems 23 F.1 Applying SquareCB.Lin under full-bandit feedback . . . . . . . . . . . . . . . . . . . . . . . 23 F.2 Applying FALCON.Lin under full-bandit feedback . . . . . . . . . . . . . . . . . . . . . . . . 23 G Experiments Details 24 G.1 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 G.2 From a learning-to-rank corpus to a CCSB instance . . . . . . . . . . . . . . . . . . . . . . . 24 G.3 Algorithms compared . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 G.4 Experimental protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 G.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 H Lower Bound for the CCSB Problem I
A
26
Supporting Lemmas 29 I.1 Off-policy evaluation lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 I.2 Batch Mode Offline Regression Oracle Guarantees . . . . . . . . . . . . . . . . . . . . . . . . 30
Decision Making with Structured Observations
Foster et al. (2021) introduced a general framework for interactive decision making with structured observations (DMSO), which captures a wide range of problems including contextual bandits and reinforcement learning, and which subsumes the contextual combinatorial semi-bandit setting. The interactive protocol of DMSO is as follows. At the beginning, the learner has access to a model class M that contains the true model M ⋆ ; each model M is associated with a reward function f M : Π → R. At every time step t: 15
1. The learner selects a decision πt from a decision set Π; 2. The environment draws an observation ot ∼ M ⋆ (πt ) and sends it to the learner; the learner incurs ⋆ reward f M (πt ). The exploration-exploitation trade-off is a fundamental challenge in DMSO, and a key step in our analysis is to characterize its statistical complexity. The Decision-Estimation Coefficient (DEC) of Foster et al. (2021) captures this complexity: h ⋆ i h ⋆ i h i 2 decγ (M, M̂ ) := inf sup Eπ∼q f M (π) − Eπ∼p f M (π) − γEπ∼p DH (M̂ (π), M ⋆ (π)) , p∈∆(Π) q∈∆(Π), M ⋆ ∈M
2 where DH is the squared Hellinger distance between the distributions over observations induced by π under M and M̂ .
B
Additional Related Work
Noncontextual combinatorial semi-bandit: stochastic and adversarial settings. The non-contextual combinatorial semi-bandit, also known as the combinatorial multi-armed bandit (CMAB), is a special case of the CCSB problem in which no contextual information is available. The CMAB problem admits a variety of formulations in the literature (Audibert et al., 2011). Anantharam and Varaiya (1987) first studied a special case of the CMAB problem under the fixed-cardinality constraint, in which the learner chooses m arms per round, and proposed an algorithm with an asymptotically optimal regret guarantee. Gai et al. (2012) studied the CMAB problem with arbitrary combinatorial constraints on the action space and proposed a UCB-based e m3 A/∆2 instance-dependent bound, where ∆ is the minimum gap between the optimal algorithm with an O and a suboptimal combinatorial action; Kveton et al. (2015) analyzed a similar UCB-based algorithm and e mA/∆ to achieve optimality when the arm set has dependency improved the instance-dependent bound to O √ and obtained a O mAT minimax regret bound. Combes et al. (2015) gives an optimal instance-dependent √ e mA/∆ when arms are independent. Chen et al. (2016) extended the analysis to a general rate as O reward structure of a combinatorial action and gave both gap-dependent and gap-independent regret bounds. Jourdan et al. (2021) studied the pure-exploration / best-arm identification problem with fixed confidence in the CMAB setting, where the learner aims to identify the optimal combinatorial action with high confidence. Another line of work studies the CMAB problem in the adversarial setting with semi-bandit feedback, where each arm’s reward is chosen by an adversary. Kale et al. (2010) first studied the CMAB problem under the fixed-cardinality constraint and proposed √ an algorithm based on relative-entropy projections over the set of distributions on slates, achieving O mAT regret. Audibert et al. (2014) adapted the Online Stochastic Mirror Descent (OSMD) √ algorithm to solve the adversarial CMAB problem and obtained optimal minimax regret bounds O mAT ; Zimmert et al. (2019) proposed an FTRL-based algorithm that achieves √ the first best-of-both-worlds guarantee, with O T regret in the adversarial setting and O log T regret in the stochastic setting; Complexity measures of online decision-making problems. Our method follows the Estimation-toDecisions (E2D) paradigm of Foster et al. (2021), which reduces an online decision-making problem to a statistical estimation problem. Foster et al. (2021) introduced the Decision-Estimation Coefficient (DEC) as a complexity measure for the interactive decision-making problems and developed the Decision Making with Structured Observations (DMSO) framework around it. This framework has inspired a line of work that follows the same reduction idea. For example, Foster et al. (2022) extended the DEC to adversarial decision-making with structured observations; Neu et al. (2024) bridged the Bayesian theory of information-directed sampling and the frequentist theory of E2D via the DEC; and Kirschner et al. (2023) relaxed E2D to an anytime variant and applied it to linear bandits with side observations.
16
C
Sampling from exploration distribution using linear optimization oracle
Recall that a key step of Algorithm 1 is to sample s ∈ S at random such that E[s] is the solution of the following optimization problem: A 1X max ⟨g, s̄⟩ + log(s̄(a)) (6) γ a=1 s̄∈S̄ We show in this section that as long as S admits an efficient linear optimization oracle, this can be done efficiently. Indeed, Algorithm 2 first solves the optimization above approximately using the Frank-Wolfe algorithm Jaggi (2013), which crucially maintains a sparse convex combination representation of the iterates Pi s̄i ’s – specifically, at any point, s̄i = j=1 αj sj , where α ∈ ∆i−1 and all sj ’s are elements in S. Specifically, the last iterate, s̄n , is also a convex combination of si , i = 1, . . . , n. Thus, sampling I = i with probability αi and returning sI that has expectation equal to s̄n , an approximate solution to (6). Algorithm 2 Find a combinatorial action whose expectation approximately solves (6) Let s̄0 be an arbitrary element in S. Let α = (). for i = 0, 1, . . . , n − 1 do D E Find si+1 ← arg maxs∈S s, ĝ + γ1s̄i 2 2 i+1 s̄i+1 ← (1 − i+2 )s̄i + i+2 s 2 i α ← ( i+2 α).append( i+2 ) end for Sample I ∼ Categorical(α1 , . . . , αn ), and return sI .
D
Regret Guarantees of SquareCB.comb
In this section, we present and prove the regret guarantee of SquareCB.Comb, and provide all necessary lemmas with their proofs in the following subsection.
D.1
Lemmas about the reduction from DEC to the log-barrier optimization
The analysis in this subsection is conducted conditional on the observed context xt and the estimated reward function fˆt at round t, and we omit the dependence on xt and fˆt for brevity. We write g(a), ĝ(a), and G to denote f ⋆ (xt , a), fˆt (xt , a), and Fxt := {f (xt , ·) : f ∈ F }, respectively. In the proof sketch of Theorem 1, we noted that the solution of the log-barrier optimization problem in Eq. (2) certifies that the CS-DEC is upper bounded by A γ up to a constant factor. 1 X p̄t = arg max ⟨ĝ, q̄⟩ + log(q̄(a)) γ q̄∈S̄ a∈A
Specifically, we aim to show that the solution p̄t satisfies the following inequality: max ⟨g ⋆ , q̄⟩ − ⟨g ⋆ , p̄t ⟩ − γ · ||g ⋆ − ĝ||p̄2t ≲
q̄∈S̄,g ⋆
A , γ
(7)
To this end, we introduce a surrogate min-max optimization problem that connects the log-barrier optimization problem with Eq. (7). Specifically, the surrogate min-max optimization problem is defined as follows: min max ⟨ĝ, q̄⟩ − ⟨ĝ, p̄⟩ + p̄∈S̄ q̄∈S̄
17
1 Coverage(p̄, q̄) γ
(8)
2 P where the coverage term is defined as Coverage(p̄, q̄) = a∈A q̄(a) p̄(a) . We show in Lemma 5 that the solution p̄t of the log-barrier optimization problem approximately solves Eq. (8). Taking Eq. (8) as an intermediate result, we then show in Lemma 6 that p̄t certifies a small CS-DEC value (Eq. (7)).
Lemma 5 (Solving log-barrier regularized problem approximately solves Eq. (8)). For any ĝ , define L(s̄; ĝ) := ⟨ĝ, s̄⟩ +
1 X log(s̄(a)) γ a∈A
for any s̄ ∈ S̄. Let p̂ be the optimal solution of maxs̄∈S̄ L(s̄; ĝ), then we have max ⟨ĝ, q̄⟩ − ⟨ĝ, p̂⟩ + q̄∈S̄
1 A Coverage(p̂, q̄) ≤ . γ γ
Proof of Lemma 5. Throughout this proof, for any vector u ∈ RA with strictly positive entries, we write 1 A 2 A u ∈ R for its entrywise reciprocal, and u ∈ R for its entrywise square. Since L(q̄; g) is a strictly concave function of q̄ and S̄ is a convex set, we know that the optimal solution p̂ is achieved when it meets the first-order optimality condition, that is, for any q̄ ∈ S̄, we have ⟨∇q̄ − L(q̄) |q̄=p̂ , q̄ − p̂⟩ ≥ 0 1 , q̄ − p̂ ≥ 0 ⇔ −ĝ − γ p̂ 1 ⇔ ĝ + , q̄ − p̂ ≤ 0 γ p̂ A 1 1 , q̄ ≤ ⇔ ⟨ĝ, q̄ − p̂⟩ + γ p̂ γ
(Gradient of −L at p̂)
Since p̂ satisfies the above first-order optimality condition, we know that for any q̄ ∈ S̄, 1 1 A ⟨ĝ, q̄ − p̂⟩ + , q̄ ≤ γ p̂ γ A 1 1 2 , q̄ ≤ ⇒ ⟨ĝ, q̄⟩ − ⟨ĝ, p̂⟩ + γ p̂ γ 1 A ⇔ ⟨ĝ, q̄⟩ − ⟨ĝ, p̂⟩ + Coverage(p̂, q̄) ≤ γ γ
(9)
Lemma 6 (Certifying Eq. (7) by Eq. (8)). Let ĝ be any reward estimate and p̂ ∈ S̄ a participation vector. If p̂ satisfies the inequality 1 A max ⟨ĝ, q̄⟩ − ⟨ĝ, p̂⟩ + Coverage(p̂, q̄) ≤ , γ γ q̄∈S̄ then p̂ also satisfies the inequality max ⟨g ⋆ , q̄⟩ − ⟨g ⋆ , p̂⟩ − γ · ||g ⋆ − ĝ||2p̂ ≲
q̄∈S̄, g ⋆
A , γ
where we recall that the squared weighted norm is defined as ||g ⋆ − ĝ||p̂2 =
P
a∈A p̂(a)
2 g ⋆ (a) − ĝ(a) .
Proof of Lemma 6. Fix the ground-truth reward function g ⋆ and two participation vectors s̄, p̂ ∈ S̄. Decompose the excess reward among s̄ and p̂ as follows: ⟨g ⋆ , s̄⟩ − ⟨g ⋆ , p̂⟩ = ⟨ĝ, s̄⟩ − ⟨ĝ, p̂⟩ + ⟨g ⋆ − ĝ, s̄⟩ + ⟨ĝ − g ⋆ , p̂⟩ 18
We bound the second difference by using the Off-policy evaluation (OPE) lemma (Lemma 14) followed by AM-GM: q ⟨g ⋆ − ĝ, s̄⟩ ≤ Coverage(p̂, s̄) · ||g ⋆ − ĝ||2p̂ 1 Coverage(p̂, s̄) + γ · ||g ⋆ − ĝ||p̂2 . γ P For the third term, Cauchy-Schwarz combined with a∈A s̄(a) ≤ m, ∀s̄ ∈ S̄ from Assumption 2 and AM-GM yields s X ⟨ĝ − g ⋆ , p̂⟩ ≤ p̂(a) · ||ĝ − g ⋆ ||p̂2 ≲
a∈A
m γ ≤ + · ||ĝ − g ⋆ ||p̂2 . γ 4 Plugging the two bounds back into the decomposition, ⟨g ⋆ , s̄⟩ − ⟨g ⋆ , p̂⟩ ≲ ⟨ĝ, s̄⟩ − ⟨ĝ, p̂⟩ +
m 1 Coverage(p̂, s̄) + + γ · ||g ⋆ − ĝ||2p̂ . γ γ
Since the above inequality holds for any s̄ ∈ S̄, we can take the maximum over s̄ on the left-hand side and use the fact that p̂ approximately solves Eq. (8) to upper bound the sum of first three terms on the right-hand side by A γ , which gives A m + + γ · ||g ⋆ − ĝ||2p̂ γ γ A ⇒ ⟨g ⋆ , s̄⟩ − ⟨g ⋆ , p̂⟩ − γ · ||g ⋆ − ĝ||p̂2 ≲ γ ⟨g ⋆ , s̄⟩ − ⟨g ⋆ , p̂⟩ ≲
The last inequality holds for any s̄ ∈ S̄ and g ⋆ ∈ G, which completes the proof. Lemma 7 (Solution of log-barrier optimization certifies small DEC). Under Assumptions 1 and 2, the solution p̄t of the log-barrier optimization problem in Eq. (2) satisfies that for any q̄ ∈ S̄ and any g ⋆ ∈ G, we have ⟨g ⋆ , q̄⟩ − ⟨g ⋆ , p̄t ⟩ − γ · ||g ⋆ − ĝ||2p̄t ≲
A . γ
Proof of Lemma 7. From Lemma 5, we have that the solution p̄t of the log-barrier optimization problem in Eq. (2) certifies Eq. (8). Then, applying Lemma 6 by letting p̂ = p̄t , we get that p̄t certifies Eq. (7).
D.2
Regret guarantee of SquareCB.Comb
We are now ready to bound the regret of SquareCB.Comb at each round by leveraging the fact that the solution of the log-barrier optimization problem certifies a small DEC value. We define the regret of SquareCB.Comb at round t as regrett (p̄t ) = maxq̄∈S̄ ⟨f ⋆ (xt , ·), q̄⟩ − ⟨f ⋆ (xt , ·), p̄t ⟩, which represents the difference between the expected reward of the best combinatorial action and that of the combinatorial action selected by SquareCB.Comb at round t. Lemma 8 (Instantaneous regret upper bound of SquareCB.Comb). Under Assumptions 1 and 2, for each round of the regret of SquareCB.Comb is bounded by regrett (p̄t ) ≲
A + γ||f ⋆ (xt , ·) − fˆt (xt , ·)||p̄2t . γ 19
(10)
Proof of Lemma 8. By Lemma 7, the solution p̄t of the log-barrier optimization problem in Eq. (2) certifies that, for any q̄ ∈ S̄ and any f ⋆ ∈ F, A ⟨f ⋆ (xt , ·), q̄⟩ − ⟨f ⋆ (xt , ·), p̄t ⟩ − γ · ||f ⋆ (xt , ·) − fˆt (xt , ·)||p̄2t ≲ . γ Then, for the regret of SquareCB.Comb at round t, we have regrett (p̄t ) = max ⟨f ⋆ (xt , ·), q̄⟩ − ⟨f ⋆ (xt , ·), p̄t ⟩ q̄∈S̄
= max ⟨f ⋆ (xt , ·), q̄⟩ − ⟨f ⋆ (xt , ·), p̄t ⟩ − γ · ||f ⋆ (xt , ·) − fˆt (xt , ·)||2p̄t + γ · ||f ⋆ (xt , ·) − fˆt (xt , ·)||p̄2t q̄∈S̄
≤
A + γ · ||f ⋆ (xt , ·) − fˆt (xt , ·)||2p̄t , γ
where the first inequality is due to Eq. (7). We are now ready to prove the main regret guarantee of SquareCB.Comb. Proof of Theorem 1. By Lemma 8, we bound the instantaneous regret of SquareCB.Comb at every round t. Summing over t = 1, . . . , T and then taking expectation over all the randomness we have E[Regret(T )] =
T X
E[regrett (p̄t )]
t=1
≤
T X A
γ t=1
+ γ · E[||f ⋆ (xt , ·) − fˆt (xt , ·)||p̄2t ]
T X TA = + γ · E Est ∼pt γ t=1
X
(Apply Lemma 8)
2 f ⋆ (xt , a) − fˆt (xt , a)
a:st (a)=1
TA ≤ + γ Regbatch (T ) γ In the second-to-the-last equation, we use the definition of expectation. The last inequality uses the online regression guarantee in Assumption 3, where for any sequence of (st , at , ot )Tt=1 , we have T X X E (fˆ(xt , a) − f ⋆ (xt , a))2 t=1 a:st (a)=1
T X =E
X
(fˆ(xt , a) − rt (a))2 − (f ⋆ (xt , a) − rt (a))2
t=1 a:st (a)=1
≤Regbatch (T ), ⋆ where the equality p is due to that E [rt (a) | xt ] = f (xt , a). Setting γ = AT /Regbatch (T ) balances the dominant exploitation term T A/γ against the exploration p penalty γRegbatch (T ), yielding Regret(T ) ≤ O AT Regbatch (T ) , which completes the proof.
E
An Offline Oracle-efficient Variant: OE2D.Comb
In this section, we present OE2D.Comb, an epoch-based variant of SquareCB.Comb that replaces the batch-mode online regression oracle Obatch with an offline regression oracle Obatch.off , in the spirit of the 20
offline oracle-efficient contextual bandit algorithms FALCON (Simchi-Levi and Xu, 2022) and the OE2D framework of Qin and Zhang (2026). The algorithm partitions the horizon T into M epochs with endpoints 0 = τ0 < τ1 < · · · < τM = T ; within each epoch m, the reward estimate fˆm ∈ F is held fixed, and at every round the same log-barrier optimization problem (the analogue of Eq. (2) with γ replaced by γm ) is solved to obtain a participation vector p̄t ∈ S̄. We assume access to an offline regression oracle Obatch.off that, given a batch of i.i.d. semi-bandit observations, returns the empirical risk minimizer fˆm ∈ F of the squared loss summed over the observed coordinates; its on-policy estimation error is controlled by Lemma 16. Algorithm 3 OE2D-comb: epoch-based offline-regression variant of SquareCB.Comb. Input: Semi-bandit tuple (X , S, A), horizon T , offline regression oracle Obatch.off , sampling oracle Osample , M M epoch schedule {τm }m=1 , exploration schedule {γm }m=1 , reward function class F . for epoch m = 1, 2, . . . , M do τ Let fˆm = 0 for m = 1. Otherwise, Call Obatch.off to obtain fˆm from the dataset {(xτ , sτ , oτ )}τm−1 =τm−2 +1 collected in epoch m − 1; for round t = τm−1 + 1, . . . , τm do Observe context xt . Compute the participation vector D E 1 X p̄t = arg max fˆm (xt , ·), p̄ + log (p̄(a)) . γm p̄∈S̄ a∈A
Sample a combinatorial action st such that E [st ] = p̄t by calling Osample (p̄t , S). Observe semi-bandit feedback ot = {rt (a) : st (a) = 1}. end for end for The optimization problem solved at every round of OE2D.Comb is precisely the A-dimensional log-barrier optimization problem in SquareCB.Comb (Eq. (2)), instantiated with the per-epoch estimate fˆm and exploration parameter γm . As in SquareCB.Comb, the convex hull constraint p̄t ∈ S̄ ensures that p̄t is realizable by some distribution over S, and the sampling oracle Osample converts p̄t into a combinatorial action st with matching marginals (cf. Section 4). By Lemma 5, the resulting p̄t certifies the surrogate min-max objective of Eq. (5) at value at most A/γm , which we use below to prove OE2D.Comb’s regret bound: T
Theorem 9. Suppose that the contexts {xt }t=1 are drawn i.i.d. from DX . Under p Assumptions 1 and 2, OE2D.Comb with the doubling schedule τm = 2m and exploration parameter γm = A/RegObatch.off (F, τm−1 /2) satisfies p e m A T log |F | . E [Regret(T )] ≤ O Proof sketch of Theorem 9. Our proof utilizes Theorem 10 (deferred after the proof), a regret theorem for an epoch-based decision making algorithm abstracted from Qin and Zhang (2026). First, we will adopt a policy-viewpoint of OE2D.Comb: at epoch m, we view the algorithm as executing the policy π(x) with participation vector: D E 1 X π̄m (x) = arg max fˆm (x, ·), p̄ + log (p̄(a)) ; γm p̄∈S̄ a∈A
Therefore, the regret of the algorithm can be represented as E [Regret(T )] =
M X
(τm − τm−1 )Ex∼DX max ⟨f ⋆ (x, ·), λ⟩ − ⟨f ⋆ (x, ·), πm (x)⟩ . λ∈Λ
m=1
21
We now apply Theorem 10 by taking Λ = S̄, pm = π̄m , C = Coverage (recall that Coverage(p̄, q̄) = PA q̄(a)2 A ⋆ 2 ˆ a=1 p̄(a) ), Dm = γm and Em = ||fm − f ||p̄m−1 . The two conditions of Theorem 10 are satisfied: • Condition 1 follows from Lemma 5; • Condition 2 follows from Lemma 14; Thus, applying the theorem, E [Regret(T )] τn 2 ˆ ⋆ 2 ≤E τ1 + max A + max γn ||fm − f ||p̄m−1 n∈[2,M ] γn n∈[2,M ] τn 2 ≲τ1 + max · A + max γn RegObatch.off (F, τn−1 /2) n∈[2,M ] γn n∈[2,M ] r RegObatch.off (F, τn−1 /2) ≲1 + max τn ·A A n∈[2,M ] r mA ln |F | p ≲ mAT ln |F|. ≲1 + max 2n · 2n n∈[2,M ] where the first inequality is by Theorem 10; the second inequality uses that E ||fˆm −f ⋆ ||2p̄m−1 ≤ RegObatch.off (F, τm−1 /2) p by Lemma 16; the third inequality uses γm = A/RegObatch.off (F, τm−1 /2); and the forth inequality uses q ln |F | that RegObatch.off (F, τm−1 /2) = mτm−1 and the definition of τn = 2n ; the last inequality is by algebra. Theorem 10 (Abstract version of Qin and Zhang (2026), Theorem 1). Suppose Λ ⊂ RA + , and we have a M A M b sequence of reward predictors (Gm )m=1 ⊂ R and distributions (pm )m=1 ⊂ Λ, a mapping C : Λ × Λ 7→ R+ , M M and sequence of positive numbers {(Dm , Em )}m=1 and a sequence of nonnegative increasing numbers {γm }m=1 , that satisfies: 1. For every m ≥ 1, pm is such that D E D E bm , λ − G b m , pm + 1 C(pm , λ) ≤ Dm max G λ∈Λ γm 2. For every m ≥ 2, and for any λ ∈ Λ, D E p b m , λ − ⟨G⋆ , λ⟩ ≤ C(pm−1 , λ)Em−1 G
Then, the following holds: M X
(τm − τm−1 ) max ⟨G⋆ , λ⟩ − ⟨G⋆ , pm ⟩ λ∈Λ
m=1
τn ≲τ1 + max · max γn Dn + max γn2 En n∈[1,M ] n∈[2,M ] n∈[2,M ] γn
22
F
The Suboptimality of Using Contextual Bandit Algorithms to Solve CCSB Problems
In this section, we present the regret guarantee obtained by applying SquareCB.Lin (Foster et al., 2020) and FALCON.Lin (Xu and Zeevi, 2020), originally designed for contextual bandits with linear reward structure per-context, to the CCSB problem under full-bandit feedback. Following the canonical reduction described in Section 2, from the contextual bandit learner’s perspective, the expected aggregate reward of combinatorial action s is linear in s (for every fixed context x): E [⟨rt , st ⟩ | xt = x, st = s] = ⟨f ⋆ (x, ·), s⟩. Under this reduction, the contextual bandit problem’s decision space is S, the action feature dimension is A, the reward range is [0, m], and the reward function class H = {h(x, s) = ⟨f (x, ·), s⟩ : f ∈ F}.
F.1
Applying SquareCB.Lin under full-bandit feedback
Applying SquareCB.Lin’s regret theorem (Foster et al., 2020, Theorem 1) under the above reduction requires a single change relative to the standard linear contextual bandit setting: the batch-mode online regression oracle Obatch now operates on aggregated bandit feedback (xt , st , ⟨rt , st ⟩), whose label range is [0, m] rather than [0, 1]. As a result, the square-loss regret bound provided by Obatch scales as Regbatch (T ) ≲ m2 log |F|, i.e., a factor of m2 worse than the unit-reward case, reflecting the fact that the slate reward range is [0, m]. The IGW-style exploration distribution and the linear-DEC certificate A/γ used in the proof of SquareCB.Lin is unaffected by the reduction; only the regression regret rate changes. Theorem 11. Under Assumptions 1 and 2, SquareCB.Lin applied to the CCSB problem with full-bandit q feedback, with constant exploration parameter γ = m2 AT , log |F | satisfies p E [Regret(T )] ≤ O m A T log |F | . Proof sketch of Theorem 11. Identical to the proof of Foster et al. (2020, Theorem 1), except that we plug the inflated regression rate Regbatch (T ) ≲ m2 log |F| into the general SquareCB.Lin bound p p A T Regbatch (T ) ≲ m A T log |F |. E [Regret(T )] ≲
F.2
Applying FALCON.Lin under full-bandit feedback
Applying FALCON.Lin’s regret theorem (Xu and Zeevi, 2020, Section 4) under the above reduction requires a single change: the offline regression oracle now operates on aggregated bandit feedback (xt , st , ⟨rt , st ⟩), and its on-policy guarantee is given by Lemma 15 rather than the standard offline regression guarantee for [0, 1]-valued rewards, with rate m2 log |F | RegObatch.off (F, n) ≲ , n i.e., a factor of m worse than the unit-reward case, reflecting the fact that the slate reward range is [0, m]. The per-context DOEC certificate Dm = A/γm and the off-policy evaluation lemma used to verify Conditions 1 and 2 of Theorem 10 carry over unchanged from the standard linear contextual bandit analysis. T
Theorem 12. Suppose contexts {xt }t=1 are drawn i.i.d. from DX . Under Assumptions 1 and 2, FALCON.Lin m applied to the CCSB p problem with full-bandit feedback, with the doubling schedule τm = 2 and exploration parameter γm = A/RegObatch.off (F, τm−1 /2), satisfies p e m A T log |F | . E [Regret(T )] ≤ O 23
Proof sketch of Theorem 12. Identical to the proof of Xu and Zeevi (2020), except that we plug RegObatch.off (F, n) ≲ m2 log |F|/n from Lemma 15 into the abstract bound of Theorem 10: 2 τn · max γn Dn + max γn RegObatch.off (F, τn−1 /2) E [Regret(T )] ≲ τ1 + max n∈[1,M ] n∈[2,M ] n∈[2,M ] γn q p 2 ≲ 1 + max 2n m A2nln |F | ≲ m A T ln |F |. n∈[2,M ]
G
Experiments Details
We compare our algorithm against representative existing methods for contextual combinatorial semi-bandits on two public learning-to-rank benchmarks, MSLR-WEB30k (Qin and Liu, 2013) and the Yahoo! Learningto-Rank Challenge Set 1 (Chapelle and Chang, 2011). Specifically, we treat them as CCSB problems with the combinatorial action space S being all m-sets (the unordered slate setting). Both corpora are recast as CCSB instances via the supervised-to-bandit reduction commonly used in the contextual-bandit literature (Krishnamurthy et al., 2016; Qin et al., 2014; Foster and Rakhlin, 2020), as we give more details PT PT P next; we use the average cumulative pseudo-reward T1 t=1 rt = T1 t=1 a:st (a)=1 f ∗ (xt , a), where f ∗ (x, a) is the recorded relevance label for the (query, document) pair (x, a) and T is the horizon, as the performance metric. This is the same reduction and metric used by Krishnamurthy et al. (2016) and Foster et al. (2018), so our numbers are directly comparable to theirs.
G.1
Datasets
We use two public learning-to-rank corpora. MSLR-WEB30k. Released by Microsoft Research (Qin and Liu, 2013), the whole dataset contains 31,531 queries sampled from Bing’s search logs, each associated with a candidate set of documents and a relevance label per (query, document) pair, with an integer relevance scale in {0, 1, 2, 3, 4}. Each (query, document) pair is summarized by 136 features. After filtering out queries with fewer than 10 candidate documents, we are left with 30,846 queries and 1,489,911 query-document records. Yahoo! LTR Set 1. The Yahoo! Learning-to-Rank Challenge corpus (Chapelle and Chang, 2011) provides 29,921 queries sampled from Yahoo! search logs, each associated with a candidate set of documents and a relevance label per (query, document) pair, with an integer relevance scale in {0, 1, 2, 3, 4}. Each (query, document) pair is summarized by 519 features. After filtering out queries with fewer than 6 candidate documents, we are left with 27,630 queries and 669,295 query-document records. Query-order seeds. Each run reshuffles the pool with its own random seed and reads queries off the shuffled order one round at a time. We use 20 seeds in all: seeds 0-9 for the hyperparameter tuning and seeds 10-19 for the performance evaluation with the selected hyperparameters, so the two stages do not share a query order.
G.2
From a learning-to-rank corpus to a CCSB instance
We turn each corpus into an online CCSB simulator. Round t proceeds in three steps: 1. Context. The next query is pulled from the seed-shuffled pool, and its feature vector xt is revealed to the algorithm as the round’s context.
24
2. Action. The simulator exposes a candidate set of A documents associated with xt (sampled uniformly without replacement when the underlying pool exceeds A; as mentioned above, we have already removed queries with fewer than A candidates). The algorithm draws a slate st of m documents. 3. Feedback. The simulator reveals the relevance label of each document in st (semi-bandit feedback). Default configuration. We follow the conventions established by Krishnamurthy et al. (2016) for these two datasets. On MSLR-WEB30k we set the candidate pool size A = 10 and the slate size m = 3; on Yahoo! LTR Set 1 we set A = 6 and m = 2. Each run makes a single pass over the entire filtered corpus, and the horizon equals the number of retained queries: T = 30,846 on MSLR-WEB30k and T = 27,630 on Yahoo! LTR Set 1.
G.3
Algorithms compared
Regression oracles. All algorithms that need a per-arm reward predictor share the same two regression oracles, chosen at run time by learning_alg: • lin: a linear regressor on the raw d-dimensional features. • gb2, gb5: sklearn’s GradientBoostingRegressor with 100 trees of depth d ∈ {2, 5}, refit from scratch on the cumulative interaction buffer at a doubling schedule of rounds. Our method. SquareCB.Comb is our Algorithm 1. At each round it solves a per-arm IGW program over participation vectors p̄t ∈ S̄ and then draws a size-m slate whose per-arm marginals match p̄t exactly p via dependent rounding (Gandhi et al., 2006). The exploration parameter follows the schedule γt = γ0 At/m, with γ0 being a hyperparameter. We instantiate the regression oracle with the linear and gradient-boosted backbones (lin, gb2, gb5). Baselines.
We list the following baselines to compare against our method:
• SquareCB.Lin (Foster et al., 2020) is a contextual bandit algorithm that each round it selects one arm. To apply it to the semi-bandit feedback setting, we treats each combinatorial action/slate s ∈ S A as a single arm, and draws a slate from the m size-m combinatorial action set. The algorithm draws a slate from a distribution that minimizes a log-determinant barrier objective over the combinatorial action set. • VCEE (Krishnamurthy et al., 2016) is the policy-elimination CCSB algorithm and is, to our knowledge, the strongest published semi-bandit baseline on these corpora. • LinUCB (Chu p et al., 2011) maintains a ridge estimator of the linear reward and a UCB-style confidence ⊤ radius θ ϕ + α ϕ⊤ Σ−1 ϕ, with Σ refreshed every 100 rounds; it represents the linear-bandit baseline. • ε-greedy (Langford and Zhang, 2007) is a baseline that maintains an online regression oracle (the same regression backbone as SquareCB.Comb) and plays a uniformly random size-m slate with probability ε, otherwise the hindsight top-m slate under the regression oracle (tuned ε per dataset) • Uniform-random draws a uniformly random size-m subset every round and never learns. • Skyline is an in-sample supervised learning comparator: a regression oracle (one per backbone family) is fit once on the entire labeled training corpus and then, every round, greedily plays the top-m arms under its own predictions. We report one skyline per regression oracle (lin, gb2, gb5) in Table 2; the learning-curve figures show the skyline matching each panel’s oracle (gb5 in Figure 1). All oracle-based methods (SquareCB.Comb, SquareCB.Lin, VCEE, ε-greedy, and the supervised Skyline ceiling) are reported with the lin, gb2, and gb5 oracles. 25
Table 3: Per-algorithm scalar tuning knob and search grid (same on both datasets). Algorithm SquareCB.Comb SquareCB.Lin VCEE ε-greedy LinUCB
G.4
Hyperparameter
Grid
γ0 γ0 µ ε α
{1, 2, 5} · 10k ,
# pts k = −1, 0, 1, plus 102
same as SquareCB.Comb {1, 3} · 10k , k = −4, . . . , 0 {1, 2, 5} · 10k , k = −3, −2, −1, plus 1 {1, 3} · 10k , k = −3, . . . , 1
10 10 10 10 10
Experimental protocol
We adopt a two-stage protocol: Stage 1 uses seeds I ∈ {0, . . . , 9} to pick, for each (algorithm, oracle, sampler, dataset) tuple, the hyperparameter value that yields the highest mean realized cumulative reward, and Stage 2 re-runs the Stage-1 winners on the disjoint seeds I ∈ {10, . . . , 19}. Both stages run for the full horizon, i.e., a single pass over the entire filtered dataset. The realized cumulative reward of a single run is cum_reward(v, I) =
T X X
rt (a),
t=1 a∈st
where st is the size-m slate played at round t and rt (a) ∈ {0, 1, 2, 3, 4} is the relevance label of item a observed under semi-bandit feedback. Selecting by realized reward keeps the tuning objective on the same scale as the reported benchmark and avoids the instability of a prediction-based criterion. The full searching table of hyperparameter grids is deferred to Table 3.
G.5
Results
Figure 1 in the main body fixes the depth-5 GBRT (gb5) oracle. Figure 2 complements it by breaking out the same online learners across the three regression oracles reported in Table 2 (lin, gb2, gb5); LinUCB exclusively uses linear regression and therefore appears only in the lin column. The curves confirm the table’s two trends: (i) for a fixed learner, richer oracles (gb5 > gb2 > lin) lift the per-round reward, and (ii) on the gradient-boosted oracles (gb2, gb5), SquareCB.Comb, SquareCB.Lin, and ε-greedy track each other closely and lead VCEE, whereas on the weaker lin oracle the spread narrows and VCEE (together with LinUCB) becomes competitive; in all cases the online learners sit well above the Uniform-random floor and below the supervised Skyline ceiling.
H
Lower Bound for the CCSB Problem
In this section, we establish a lower bound on the CCSB regret in terms of |F|, T , m, and A. Our lower bound construction uses a contextual m-path problem with A arms and a function class F of size at most N , building on the non-contextual m-path lower bound of Kveton et al. (2015) and the realizable contextual bandit lower bound of Agarwal et al. (2012). In the contextual m-path problem, the learner chooses an m-edge path at each round, and each f ∈ F maps from the space of (context, arm) pairs to [0, 1]. We partition the time horizon T into M non-overlapping intervals of equal length T /M . The main result of this section is the following lower bound for CCSB with general function approximation. Theorem 4 (Lower bound for CCSB with finite function class). For any m, A, T, N ∈ N such that A/m ∈ N, N ≥ A/m, T /⌊logA/m N ⌋ ∈ N, and T /⌊logA/m N ⌋ ≥ 16A/m, there exists a CCSB problem with A arms and combinatorial-action size at most m, and a reward function class F with |F| ≤ N , such that for any algorithm √ Alg there isan environment realizable with respect to F on which the expected regret of Alg is at e m A T log N . least Ω Proof of Theorem 4. We will first give the construction of a family of contextual shortest path instances and argue that Alg must suffer a large regret in one of the instances. 26
Figure 2: Per-round average reward by regression oracle: rows are the two corpora (MSLR-WEB30k, top; Yahoo! LTR Set 1, bottom) and columns are the lin, gb2, and gb5 oracles. LinUCB is linear-only and appears only in the lin column; the Skyline reference uses the column’s oracle. The round axis is logarithmic. Curves are the means over 10 seeds; shaded bands show ±1 standard deviation across those seeds. The gb5 column reproduces Figure 1. The construction. Let M = ⌊logA/m N ⌋ and τ = T /M ; both are positive integers under our assumptions that N ≥ A/m and T /M ∈ N. Define the context space X = {1, . . . , M } and the combinatorial action space S = sj = 1pj : j ∈ [A/m] , pj = {m(j − 1) + 1, . . . , mj} , We use sj to represent the j-th path from the start to the goal; see Figure 3 for an illustration Each combinatorial action has cardinality exactly m, so the size constraint of the CCSB problem holds. For each j ∈ [A/m], define gj : A → [0, 1] by ( r 1 , a ∈ pj , A 2 gj (a) = 1 where ∆ = ∈ (0, 14 ]. m τ − ∆, a ∈ / p , j 2 Our assumption τ ≥ 16A/m ensures that ∆ ≤ 1/4. Set G = {gj : j ∈ [A/m]} and F = {f : f (i, ·) ∈ G for every i ∈ [M ]} . By construction, |F| = (A/m)M ≤ N . 27
Figure 3: Contextual m-path construction. Each m × (A/m) grid depicts the shared arm set [A], with cell (j, k) being the k-th node of the j-th path. The optimal path is shaded pink and yields expected reward 1/2; the remaining A/m − 1 paths are shaded beige and yield reward 1/2 − ∆. Different contexts induce different optimal paths, so the reward distributions across contexts are independent. For each f ∈ F, define the environment Ef as follows: for t in the i-th interval [(i − 1)τ + 1, iτ ], the environment shows context xt = i, and the reward vector rt is drawn by first sampling path rewards wt,1 , . . . , wt,A/m independently with wt,j ∼ Bernoulli f (i, m(j − 1) + 1) and then setting rt (a) = wt,j for all a ∈ pj . In other words, the realized rewards of the arms within each path are identical; see Figure 3. By construction E [rt (a) | xt ] = f (xt , a), so Ef is realizable with respect to F . Lower bound from the non-contextual m-path problem. For any fixed g ∈ G, define Eg to be the environment with horizon τ in which rt is drawn by sampling wt,1 , . . . , wt,A/m independently with wt,j ∼ Bernoulli g(m(j − 1) + 1) and setting rt (a) = wt,j for all a ∈ pj . We will use the following non-contextual lower bound. Lemma 13 (Kveton et al., 2015, Proposition 2). For any m, A, τ ∈ N with A/m ∈ N and τ ≥ 16A/m, and any algorithm Alg, " τ # X √ ⋆ ⋆ Eg⋆ ∼Unif(G) EAlg,Eg⋆ max ⟨g , s⟩ − ⟨g , st ⟩ ≥ Ω Amτ . t=1
s∈S
Aggregating across intervals. Let Alg be any CCSB algorithm and let pt ∈ ∆(S) denote its action distribution at round t. The expected regret of Alg on environment Ef ⋆ is Regretf ⋆ (Alg) =
T X t=1
max ⟨f ⋆ (xt , ·), s⟩ − Es∼pt ⟨f ⋆ (xt , ·), s⟩ . s∈S
Sampling f ⋆ uniformly at random from F gives a Bayesian lower bound on the worst case: sup Regretf ⋆ (Alg) ≥ Ef ⋆ ∼Unif(F ) Regretf ⋆ (Alg).
f ⋆ ∈F
Splitting the sum across the M intervals, Ef ⋆ ∼Unif(F ) Regretf ⋆ (Alg) =
M X i=1
Ef ⋆ ∼Unif(F )
iτ X
max ⟨f ⋆ (i, ·), s⟩ − Es∼pt ⟨f ⋆ (i, ·), s⟩ .
t=(i−1)τ +1
s∈S
Since F = G M as a Cartesian product, drawing f ⋆ ∼ Unif(F) is equivalent to drawing f ⋆ (i, ·) ∼ Unif(G) independently for each i ∈ [M ]. The history available to Alg during interval i depends only on {f ⋆ (j, ·)}j<i , 28
which are independent of f ⋆ (i, ·). Hence within interval i, Alg effectively faces a non-contextual m-path instance of horizon τ with reward function drawn from Unif(G). Lemma 13 therefore yields iτ X √ max ⟨f ⋆ (i, ·), s⟩ − Es∼pt ⟨f ⋆ (i, ·), s⟩ ≥ Ω Amτ . Ef ⋆ ∼Unif(F ) t=(i−1)τ +1
s∈S
Summing over i and using τ = T /M with M = ⌊logA/m N ⌋, sup Regretf ⋆ (Alg) ≥ M · Ω
f ⋆ ∈F
p p √ e AmT /M = Ω AmT M = Ω AmT log N ,
e where the last step uses M = log N/ log(A/m) and absorbs the log(A/m) factor into Ω(·).
I
Supporting Lemmas
I.1
Off-policy evaluation lemma
The lemma in this subsection is stated and analyzed at a fixed context x ∈ X , so we omit the dependence on x for brevity: we write g(a), g ⋆ (a), and G to denote f (x, a), f ⋆ (x, a), and the per-context reward function class Fx := {f (x, ·) : f ∈ F} ⊆ RA , respectively. Lemma 14. Let g ⋆ ∈ G be the ground truth reward function. For any g ∈ G and any participation vectors p̄, q̄ ∈ S̄ with p̄(a) > 0 for all a ∈ A, we have q |⟨g, q̄⟩ − ⟨g ⋆ , q̄⟩| ≤ Coverage(p̄, q̄) · ||g − g ⋆ ||p̄2 . Proof of Lemma 14. Starting from the squared left-hand side, !2 ⋆
2
(⟨g, q̄⟩ − ⟨g , q̄⟩) =
X
⋆
q̄(a) (g(a) − g (a))
a∈A
!2 X q̄(a) p ⋆ p = p̄(a) (g(a) − g (a)) p̄(a) a∈A ! X q̄(a)2 X 2 ≤ · p̄(a) (g(a) − g ⋆ (a)) p̄(a) a∈A
(Cauchy-Schwarz inequality)
a∈A
=Coverage(p̄, q̄) · ||g − g ⋆ ||p̄2 . Taking a square root on both sides yields the lemma. In typical applications, we instantiate g = fˆm (x, ·) and g ⋆ = f ⋆ (x, ·) at the current context x, with p̄ = π̄m−1 (x) denoting the participation vector of the data-collection policy at epoch m − 1 and q̄ denoting a target participation vector. Then ||g − g ⋆ ||2p̄ is the on-policy model estimation error, which is controlled by the regression oracle, and Coverage(p̄, q̄) measures how well p̄ covers q̄. The lemma thus states that the off-policy evaluation error of any target policy q̄ is bounded by the on-policy estimation error and the coverage of p̄ over q̄.
29
I.2
Batch Mode Offline Regression Oracle Guarantees
In this section, we provide on-policy reward estimation error guarantees for the ERM estimator under full-bandit and semi-bandit feedback, where Lemma 15 establishes the former, while Lemma 16 establishes the latter. Recall from Section 3 that ri ∈ [0, 1]A and F ⊆ [0, 1]X ×A . The full-bandit guarantee is worse than the semi-bandit guarantee by a factor of m (the maximum size of a combinatorial action), which is expected since full-bandit feedback is less informative than semi-bandit feedback. Lemma 15 (On-policy model estimation error in full-bandit feedback). Let DX be the marginal distribution n over contexts. Suppose we collect a dataset Dn = {(xi , si , ⟨ri , si ⟩)}i=1 of n i.i.d. slate-level observations, where xi ∼ DX , si ∼ π(· | xi ), and the (hidden) reward vector ri ∈ [0, 1]A satisfies E [ri (a) | xi ] = f ⋆ (xi , a) for every Pn 2 a ∈ A. Let fˆ ∈ arg minf ∈F i=1 (⟨f (xi , ·), si ⟩ − ⟨ri , si ⟩) be the ERM estimator. Then for any δ ∈ (0, 1), with probability at least 1 − δ, D E2 m2 |F| ⋆ ˆ Ex∼DX Es∼π(·|x) f (x, ·) − f (x, ·), s ≲ log . n δ Proof of Lemma 15. For any f ∈ F, define the per-round excess loss 2
2
Zi (f ) := (⟨f (xi , ·), si ⟩ − ⟨ri , si ⟩) − (⟨f ⋆ (xi , ·), si ⟩ − ⟨ri , si ⟩) . Since E [⟨ri , si ⟩ | xi , si ] = ⟨f ⋆ (xi , ·), si ⟩, 2
E [Zi (f ) | xi , si ] = (⟨f (xi , ·) − f ⋆ (xi , ·), si ⟩) , and taking expectation over (xi , si ), h ii h 2 . E [Zi (f )] = Ex∼DX Es∼π(·|x) (⟨f (x, ·) − f ⋆ (x, ·), s⟩) Since f, f ⋆ ∈ [0, 1]X ×A , ri ∈ [0, 1]A , and ||si ||1 ≤ m, we have |⟨f (xi , ·), si ⟩| ≤ m and |⟨ri , si ⟩| ≤ m, so |Zi (f )| ≤ m2 . Factoring the excess loss as a difference of squares, Zi (f ) = ⟨f (xi , ·) − f ⋆ (xi , ·), si ⟩ · (⟨f (xi , ·) + f ⋆ (xi , ·), si ⟩ − 2 ⟨ri , si ⟩) , where the second factor is bounded by 2m in absolute value, so 2
Zi (f )2 ≤ 4m2 (⟨f (xi , ·) − f ⋆ (xi , ·), si ⟩) , and taking expectation gives E Zi (f )2 ≤ 4m2 E [Zi (f )]. Applying Bernstein’s inequality and a union bound over f ∈ F, with probability at least 1 − δ, simultaneously for all f ∈ F, r n 1X E [Zi (f )] log(|F| /δ) m2 |F| E [Z1 (f )] − Zi (f ) ≲ m + log . n i=1 n n δ Pn Substituting f = fˆ and using n1 i=1 Zi (fˆ) ≤ 0 (by the ERM property), the elementary implication √ x ≤ c xA + B ⇒ x ≲ c2 A + B for A, B ≥ 0 yields h i m2 |F| E Z1 (fˆ) ≲ log , n δ h i which is the desired bound by the expression for E Z1 (fˆ) derived above. 30
Lemma 16 (On-policy model estimation error in semi-bandit feedback). Let DX be the marginal distribution n over contexts. Suppose we collect a dataset Dn = {(xi , si , oi )}i=1 of n i.i.d. semi-bandit observations, where xi ∼ DX , si ∼ π(· | xi ), oi = {oi (a) : si (a) = 1} with oi (a) = ri (a), and the (hidden) reward vector ri ∈ [0, 1]A Pn P 2 satisfies E [ri (a) | xi ] = f ⋆ (xi , a) for every a ∈ A. Let fˆ ∈ arg minf ∈F i=1 a:si (a)=1 (f (xi , a) − oi (a)) be the ERM estimator. Then for any δ ∈ (0, 1), with probability at least 1 − δ, h i m |F| 2 log . Ex∼DX ||fˆ − f ⋆ ||π̄(x) ≲ n δ Proof of Lemma 16. For any f ∈ F, define the per-round semi-bandit excess loss i X h 2 2 Zi (f ) := (f (xi , a) − oi (a)) − (f ⋆ (xi , a) − oi (a)) . a:si (a)=1
Since E [oi (a) | xi , si ] = f ⋆ (xi , a) whenever si (a) = 1, the expected excess loss conditioned on (xi , si ) is X 2 E [Zi (f ) | xi , si ] = (f (xi , a) − f ⋆ (xi , a)) , a:si (a)=1
and taking expectation over (xi , si ),
E [Zi (f )] = Ex∼DX Es∼π(·|x)
X
h i 2 2 (f (x, a) − f ⋆ (x, a)) = Ex∼DX ||f − f ⋆ ||π̄(x) ,
a:s(a)=1
where the last equality uses π̄(x)(a) = Es∼π(·|x) [s(a)]. Since f, f ⋆ , oi (a) ∈ [0, 1] and ||si ||1 ≤ m, we have |Zi (f )| ≤ m. Factoring each term as a difference of squares, X Zi (f ) = (f (xi , a) − f ⋆ (xi , a)) (f (xi , a) + f ⋆ (xi , a) − 2oi (a)) , a:si (a)=1
so by the Cauchy–Schwarz inequality, X X 2 Zi (f )2 ≤ (f (xi , a) − f ⋆ (xi , a)) a:si (a)=1
2
(f (xi , a) + f ⋆ (xi , a) − 2oi (a))
a:si (a)=1
≤ 4m · E [Zi (f ) | xi , si ] , where we used that each summand in the second factor is at most 4 and there are at most m summands. Taking expectation gives E Zi (f )2 ≤ 4m E [Zi (f )]. Applying Bernstein’s inequality and a union bound over f ∈ F, with probability at least 1 − δ, simultaneously for all f ∈ F, r n 1X m E [Zi (f )] log(|F| /δ) m |F| E [Z1 (f )] − Zi (f ) ≲ + log . n i=1 n n δ Pn Substituting f = fˆ and using n1 i=1 Zi (fˆ) ≤ 0 (by the ERM property), the elementary implication √ x ≤ cxA + B ⇒ x ≲ cA + B for A, B ≥ 0 yields h i m |F| ˆ , E Z1 (f ) ≲ log n δ h i which is the desired bound by the expression for E Z1 (fˆ) derived above.
31