Offline Learning for Combinatorial Multi-armed Bandits
Authors: Xutong Liu
Xiangxiang Dai
Jinhang Zuo
Siwei Wang
Carlee Joe-Wong
John C.S. Lui
Wei Chen
Venue: ICML 2025 poster (2025)
Keywords: Multi-armed bandit
combinatorial multi-armed bandit
offline learning
data coverage
Primary area: theory->online_learning_and_bandits
TL;DR: Offline learning framework for combinatorial multi-armed bandit

Abstract: The combinatorial multi-armed bandit (CMAB) is a fundamental sequential decision-making framework, extensively studied over the past decade. However, existing work primarily focuses on the online setting, overlooking the substantial costs of online interactions and the readily available offline datasets.
To overcome these limitations, we introduce Off-CMAB, the first offline learning framework for CMAB. Central to our framework is the combinatorial lower confidence bound (CLCB) algorithm, which combines pessimistic reward estimations with combinatorial solvers. To characterize the quality of offline datasets, we propose two novel data coverage conditions and prove that, under these conditions, CLCB achieves a near-optimal suboptimality gap, matching the theoretical lower bound up to a logarithmic factor.
We validate Off-CMAB through practical applications, including learning to rank, large language model (LLM) caching, and social influence maximization, showing its ability to handle nonlinear reward functions, general feedback models, and out-of-distribution action samples that excludes optimal or even feasible actions. 
Extensive experiments on synthetic and real-world datasets further highlight the superior performance of CLCB.

Offline Learning for Combinatorial Multi-armed Bandits
Xutong Liu
Xiangxiang Dai
Jinhang Zuo
Siwei Wang*
Carlee Joe- Wong'
John C.S. Lui?
Wei Chen
Abstract
the past decade, CMAB has been extensively studied (Cesa-
Bianchi & Lugosi, 2012; Bubeck et al., 2012: Audibert et al., 2014; Neu, 2015; Gai et al., 2012; Kveton et al., 2015c; Combes et al., 2015; Chen et al., 2016; Wang & Chen, 2017; Merlis & Mannor, 2019; Saha & Gopalan, 2019; Zimmert et al., 2019; Liu et al., 2024b; Qin et al., 2014; Liu et al., 2023a: Choi et al., 2024; Hwang et al., 2023), driving ad- vancements in real-world applications like recommendation systems (Kveton al., 2015a; Li et al., 2016; Lattimore et al., 2018; Agrawal et al., 2019), healthcare (Lin & Boun- effouf, 2022; Verma et al., 2023; Bouneffouf et al., 2020), and cyber-physice systems (György et al., 2007; Kveton et al., 2015b; Li et al., 2019; Liu et al., 2023b).
The combinatorial multi-armed bandit (CMAB) fundamental sequential decision-making frame- work, extensively studied over the past decade. However, existing work primarily focuses on the online setting, overlooking the substantial costs of online interactions and the readily available offline datasets. To overcome these limitations, we introduce Off-CMAR the first offline learn- frame- work is the combinatorial lower confidence bound (CLCB) algorithm, which combines pessimistic reward estimations with combinatorial solvers. datasets,
ing framework for CMAB. Central
To characterize the quality of offline we propose two novel data coverage conditions and prove that, under these conditions, CLCB achieves a near-optimal suboptimality gap, match- ing the theoretical lower bound up a logarithmic factor. We validate Off-CMAB through practi- cal applications, including learning to rank, large language model (LLM) caching, and social in- fluence maximization, showing its ability to han- dle nonlinear reward functions, general feedback models, and out-of-distribution action samples that exclude optimal or even feasible actions. Ex- tensive experiments synthetic and real- world datasets for these applications further highlight the superior performance of CLCB.
Most success stories of CMAB have emerged within the realm of online CMAB', which relies on active data collec- tion through online exploration. While effective in certain scenarios, this framework faces two major limitations. On one hand, online exploration becomes impractical when it incurs prohibitive costs or raises ethical and safety concerns. On the other hand, they neglect offline datasets that are often readily available at little or no cost.
For instance, in healthcare systems (Liu et al., 2020), recommending optimal combinations of medical treat- ments- as drugs, surgical procedures, and radiation therapy-requires extreme caution. Experimenting directly on patients is ethically and practically infeasible. Instead, leveraging pre-collected datasets of prior treatments can help to make informed decisions while ensuring patient safety. Similar happens for recommendation systems (Chen et al., 2023) and autonomous driving (Kiran et al., 2020), offline datasets such as user click histories and human driv- ing logs are ubiquitous. Leveraging these offline datasets can guide learning agents to identify optimal policies while avoiding the significant costs associated with online explo- ration such as degrading user experience or risking car accidents. For more examples, see Appendix for details.
1. Introduction
Combinatorial
bandit (CMAB) is a funda- mental sequential decision-making framework, designed to tackle challenges in combinatorial action spaces. Over
'ECE Department, Carnegie Mellon University, Pitts- burgh PA, United States "CSE Department, Chinese Univer- sity of Hong Kong. Hong Kong SAR, China 'CS Depart- ment, City University of Hong Kong, Hong Kong SAR, China "Microsoft Research, Beijing, China. Conrespondence angxiang Dai <xxdai23@esee www.@eesec.ccckc.m edu.kkcdu.kk, Jinhang Zuo <jin- hang.zuo zuo@ Soluuouityuueeeee cityu.edu.hb. hdk. Wei Chen <weic @ microsoft.com.>
To address the limitations of online CMAB, we propose the first offline learning framework for CMAB (Off-CMAB), where we leverage a pre-collected dataset consisting of n samples of combinatorial actions and their corresponding feedback data. Our framework handles rewards that are
Xi-
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
See Appendix A for comprehensive discussion the related works.

---

Offline Learning for Combinatorial Multi-armed Bandits
nonlinear functions of the chosen super arms and considers probabilistic feedback models that generalize the standard semi-bandit feedback model (Gai et al., 2010; Chen et al., 2013; Kveton et al., 2015c), supporting wide range of applications such as learning to rank (Liu et al., 2009), large language model (LLM) caching (Zhu et al., 2023), and in- fluence maximization (Kempe et al., 2003a). The objective to identify a combinatorial action that minimizes the sub- optimal gap, defined the reward difference between the optimal action and the identified action.
fully addresses key challenges, including handling nonlinear reward functions, confining uncertainties base arms rele- vant to the optimal action, and accounting for arm triggering probabilities, enabling CLCB to achieve state-of-the ff-the-art art per- formance with tighter bounds and relaxed assumptions for the real-world applications as discussed below.
Practical Applications: We show the practicality of Off- CMAB by fitting real-world problems into our framework and applying CLCB solve them, including (1) learning to rank, (2) LLM caching, and (3) social influence max- imization (IM). For the LLM cache problem, beyond di- rectly fitting it into our framework, we improve existing results by addressing full-feedback arms, extending our ap- proach to the online L.LM setting with similar improvements. For social IM, our framework handles nuanced node-level feedback by constructing base-arm LCBs via intermediate UCB/LCBs, with additional refinements using variance- adaptive confidence intervals for improved performance.
The key challenge of Off-CMAB lies in the absence of ac- cess to an online environment, which inherently limits the number of data samples available for each action. Further- more, this problem becomes even more challenging with the combinatorially large action space, which complicates the search for optimal solutions, and the potential presence of cutrof-distribution (OOD) samples, where the dataset may exclude optimal or even feasible actions. To tackle these challenges, this work makes progress in answering the following two open questions:
Empirical Validation: Finally, extensive experiments on both synthetic and real-world datasets for learning to rank and LLM caching validate the superior performance of CLCB compared to baseline algorithms.
(1) Can we design a
algorithm for Off- CMAB when the action space is combinatorially large? (2) How much data is necessary to find near-optimal action, given varying levels of dataset quality?
2. Problem Setting
We answer these questions from the following perspectives:
In this section, we introduce our model for combinatorial multi-armed bandits with probabilistically triggering arms (CMAB-T) and the offline learning problem for CMAB-T.
Algorithm Design: To address the first question, we pro- pose a novel combinatorial lower confidence bound (CLCB) algorithm that addresses the uncertainty inherent in pas- sively collected datasets by leveraging the pessimism princi- ple. At the base arm level, CLCB constructs lower confidence bounds (LCBs), penalizing arms with in- sufficient observations. At the combinatorial action level, CLCB utilizes an approximate combinatorial solver to han- dle nonlinear reward functions, effectively translating base- arm pessimism to action-level pessimism. This design pre- vents the selection of actions with fighttuuctttionn base arms, ensuring robust decision-making
2.1. Combinatorial Multi-armed Bandits with Probabilistically Triggered Arms
The original combinatorial multi- bandits problem with probabilistically triggered arms (CMAB-T) is an on- line learning game between learner and the environment in n rounds. We can specify a CMAB-T problem by tuple I == ([mi) D, S, Dmig R). where [m] are base arms, S is the set of feasible combinatorial actions, D is the set of feasible distributions for the base arm outcomes, Dang is the prob- abilistic triggering function, and is the reward function. The details of each component are described below:
Theoretical Analysis: For the second question, we intro- duce two novel data coverage conditions: (1) the infinity- norm and (2) 1-norm triggering probability modulated (TPM) data coverage conditions, which characterize the dataset quality. These conditions quantify the amount of data required to accurately estimate each action by decom- posing the data needs of each base arm and reweighting them based on their importance. Under these conditions, we prove that CLCB achieves a near-optimal suboptimality gap upper bound of Ō(K* /C*s/n), where K* is the size of the optimal action, C% is the data coverage coefficient, and n is the number of samples in the offline dataset. This result matches the lower bound Q(K" VC² /n) derived in this work up to logarithmic factor. Our analysis care-
Base arms The environment has set of [m] {1, 1I,2,..,mi base arms, Before the game starts, the en- vironment chooses an unknown distribution Iaam E D over the bounded support [0, 11rh. At each round t E [n], the envi- ronment draws random outcomes X, = (X,,,,...,,... ~ Dar- Note that for a fixed arm í, we assume outcomes Xr,,, are independent across different rounds t * t'. However, outcomes for different arms X,,, and X,, for # j can be dependent within the same round t. We use fa (J(1,..., to denote the unknown mean vector, where μ4 := Ex,-Da [X,,] for each base arm i.
2

---

Offline Learning for Combinatorial Multi-armed Bandits
Combinatorial actions. At each round 1. E [n]. the learner selects a combinatorial action St E S, where S is the set of feasible actions. Typically, St is a set of individual base arms S S [ml, which we refer to as a super arm. However, St can be more general than the super arm, e.g., continuous arms are useful for applying CMAB to resource allocation (Zuo & Joe-Wong, 2021), which we emphasize as needed.
vectors pt, ps, E |0,1]m, and for any action S S, we have Puns:S
- r(; Bi [ie(m) Ps |i - p4l--
Remark (Intuitions of Condition I and Condition 2). Con- dition indicates the reward is monotonically increasing when the parameter μa increases. Condition 2 bounds the reward smoothness/sensitivityy i.e., the amount of the reward change caused by the parameter change from ja ya'. In the learning to rank (Section 4.1), for example, these conditions upper bounds the difference in total number of purchases when the purchase probability for the items changes from l to n¹. For Condition 2, the key feature is that the pa- rameter change in each base arm is modulated by the triggering probability p! saving a Pmin factor in (Chen et al., 2016) where Puuin is the minimum positive triggering probability. Intuitively, for base arm i that is unlikely to be triggered/observed (small 5, Condition 2 ensures that large change in μ4 (due to insufficient observation) only causes a small change (multiplied by p!"".) in reward, sav- ing a Pmin factor in (Wang & Chen, 2017) where pmin is the minimum positive triggering probability. In learning to rank application, for example, since users will never purchase an item if it is not examined, increasing or decreasing the pur- chase probability of an item that is unlikely to be examined (i.e., with small S) does not significantly affect the total number of purchases.
Probabilistic arm triggering feedback. Motivated by the applications that will be introduced
properties of in detail in Section 4, we consider feedback process that involves scenarios where each base arm in super arm St does not always reveal its outcome, even probabilisticall. For example, a user might leave the system randomly at some point before examining the entire recommended list St, resulting in unobserved feedback for the unexamined items. To handle such probabilistic feedback, we assume that after the action St is selected, the base arms in ran- dom set T. ~ (Sig X,) are triggered depending on the outcome X,, where Drig (S, X) is an unknown probabilis- tic distribution over the subsets 2 given S and X. This means that the outcomes of the arms in Tr, i.e., (Xx,))er. are revealed as feedback to the learner, which could also be involved in determining the reward of action S, as we introduce later. To allow the algorithm to estimate the mean (4; directly from samples, we assume the outcome does not depend on whether the arm i is triggered, i.e., Ex=D (8. x (X, é E r] = Ex [X,]. We use Pi Sumis to denote the probability that base arm is triggered when the action is S and the mean vector is J..
2.2. Offline Data Collection and Performance Metric
Offline dataset. Fix any CMAB-T problem I together with its underlying distribution Damm We consider the offline learning setting, that is, the learner only has ac- cess to a dataset DD consisting of n feedback data D == {SS, Tr, (Xx,))er.)) )}== collected a priori by an experi- menter. Here, we assume the experimenter takes an un- known data collecting distribution D' over feasible actions S, such that S: is generated i.i.d. from S. ~ Dgg for any offline data t E [m]. After S, is sampled, the environment generates outcome X, ~ Dam- Then Ti ~ (S,, are triggered, whose outcome are recorded as (Xr,)) To this end, we use p; Pam:Ds to denote the data triggering probabil- ity, i.e., p; D.m.DD Eg-Ds B.-Ds.. X=-Dm.7~Duatf5 x) [T (i E 7}}, which indicates the frequency of observing arm i E [m]]
Reward function. At the end of round E [m]] the learner receives a nonnegative reward R₂ = R(S, X,, Tt). deter- mined by action St, outcome X,, and triggered arm set TH- Similarly to (Wang& & Chen, 2017), we assume the expected reward to be r(Se; pt)) == E[R(S,, X,,T)), T)), a function of the unknown mean vector fu, where the expectation is taken over the randomness of X, and Ta Bung( X.).
Reward conditions. Owing to the nonlinearity of the re- ward and the combinatorial structure of the action, it is essential to give some conditions for the reward function to achieve any meaningful theoretical guarantee (Wang & Chen, 2017). We consider the following conditions:
Condition (Monotonicity, Wang & Chen (2017)). We say that a CMAB-T problem satisfies the monotonicity con- dition, if for any action S E S, for any two distributions Darms ID E D with mean vectors μ. μt E 10, 11TH such that μ4 S u4 for all i E [m], we have r(S; S <rSSpp')
Approximation oracle and a approximate suboptimal- ity gap. The goal of the offline learning problem for CMAB-T is to identify the optimal combinatorial action that maximizes the expected reward. Correspondingly. the performance of an offline learning algorithm A is measured by the suboptimality-gar defined the differ- ence in the expected reward between the optimal action S* := argmax es r(S'; 11) and the action S chosen by algorithm A with dataset D as input. For many reward func- tions, it is NP-hard to compute the exact St even when μ is known, so similar to (Chen et al., 2013; Wang & Chen,
Condition 2 (1-norm TPM Bounded Smoothness, Wang & Chen (2017)). We say that a CMAB-T problem satisfies the 1-norm triggering probability modulated (TPM) bounded smoothness condition with coefficient B,, if there exists coefficient B₁ > 0 (referred to as smoothness coefficient), if for any two distributions Damm TV amm E DD with mean
3

---

Offline Learning for Combinatorial Multi-armed Bandits
2017; Liu et al., 2022; 2024a), we assume that algorithm A has access an offline a-approximation ORACLE,, which takes any mean vector μ E [0, 11th as input, and outputs an a-approximate solution S E S, i.e., S = ORACLE(H)
of arm i. Incorporating similar triggering probability mod- ulation as in Condition 2, we use p. Pamis to reweight the importance of cach arm i, and when p; D is small, the uncertainty associated with arm i has small impact on the estimation. Consequently, a large amount of data is not required for learning about arm i. Notably, because we com- pare against the optimal super arm S we only require the weight P; S of the optimal action S as the modulation. This is less restrictive than uniform coverage conditions that require adequate data for all possible actions, as used by Chen & Jiang (2019b); Jiang (2019).
satisfies
r(S: 2 a max r(S:: 14) S'ES
(l)
Given any action $ E S, the a-approximate suboptimality gap over the CMAB-T instance I with unknown base arm mean j is defined as
a =
r(S:( aa
r(S:
(2)
The primary difference between Condition 3 and Condi- tion 4 lies in the computation of the total expected data requirements for all arms. Condition 3 adopts a worst-case perspective using the max operator, whereas Condition 4 considers the total summation over i E [mx] Generally, the relationship Cj < K*C² holds. Depending on the application, different conditions may be preferable, offer- ing varying guarantees for the suboptimality gap. Detailed discussion is provided in Remark 4.
Our objective is to design algorithm A such that SubOpt(S; az I) is minimized with high probability 1 - 8, where the randomness is taken over the (Iss, Darm, Drig).
2.3. Data Coverage Conditions: Quality of the Dataset
Since the offline learning performance is closely related to the quality of the dataset D, we consider the following conditions about the offline dataset:
Remark 3 (Extension to handle -nttof-disttibbution Dg)), Note that Condition 3 and Condition 4 are restrictions on the hase arm level. Hence, our framework is flexible and can accommodate any data collection distribution DDs, including distributions over actions S' that may assign zero probability to the optimal action S or even extend beyond the feasible action set S. For example, in the LLM cache problem (Section 4.2), the experimenter might ensure arm feedback by using an empty cache in each round, leveraging cache misses to collect feedback. In this case, the distribution IDss assigns zero probability to the optimal cache configuration as well as any reasonable cache configurations.
Condition 3 (Infinity-oom TPM Data Coverage). For a CMAB-T instance I with unknown distribution Dam and mean vector p. let S = argmaxses r(S; μi).² We say that the data collecting distribution Ds satisfies the infinity-norm triggering probability modulated (TPM) data coverage con- dition, if there exists a coefficient C% > (referred to as coverage coefficient), such that
Sa
Pi Do
max
S Ooc.
(3)
|E[m] ml P.
Condition (1-norm TPM Data Coverage). For a CMAB-T instance I with unknown distribution Damm and mean vector μ.. let S* = argmax r(: 1t). We say that the data collecting distribution Tåg satisfies the I-norm triggering probability modulated (TPM) data coverage condition, if there exists coefficient C7 >
3. CLCB Algorithm and Theoretical Analysis
In this section, we first introduce the Combinatorial Lower Confidence Bound (CLCB) algorithm (Algorithm 1) and analyze its performance in Section 3. We then derive a lower bound on the suboptimality gap, and we show that our gap upper bound matches this lower bound up to logarithmic factors.
O, such that
Pt Su
I Cj.
(4)
Dom Ds
(c(m]
Ps
The CLCB algorithm first computes high-probability lower confidence bounds (LCBs) for each base arm (line 5). These LCB estimates are then used as inputs to a combinato- rial oracle to select an action S that approximately max- imizes the worst-case reward function r(S"; (4) (line 7). The key part of Algorithm is to conservatively use the LCB, penalizing each base arm by its confidence interval, v /log( 4mm //2N This approach, rooted in the pessimism principle (Jin et al., 2020a), mitigates the impact of high fluctuations in empirical estimates caused by limited obser- vations, effectively addressing the uncertainty inherent in
Remark 2 (Intuition of Condition 3 and Condition 4). Both Condition and Condition 4 evaluate the quality of the dataset D, which directly impacts the amount of data re- quired to accurately estimate the expected reward of the optimal S* The denominator P; Da represents the data generation rate for arm i, and "a corresponds to the expected number of samples needed to observe one instance
NNote that for simplicity, we choose an arbitrary optimal so- lution S* and in practice, we can choose one that leads the smallest coverage coefficient.
4

---

Offline Learning for Combinatorial Multi-armed Bandits
Algorithm CLCB: Combinatorial Lower Confidence Bound Algorithm for Off-CMAB
coefficient B1 and the approximation ratio a. For problems satisfying Eq. (5), the gap scales linearly with the fg-action size K2 and the the coverage coefficient C in Eq. (5), For problems satisfying Eq. (6), the gap depends on the action size K and the 1-norm data coverage coefficient
1: Input: Dataset D = {(St, Tt, (Xt,))e))) compu- tation oracle ORACLE, probability 6.
2: for arm i [m] do
3: Calculate counter N; ET=1 T() :.).
C1. To output an action that is e-close to S Eq. (5) and Eq. (6) need Ö(Bfa K2 C2o/e2 and Ö(Ba K / samples, respectively.
4: Calculate empirical mean ia; = Σts 1(Ee Na.
N1
loog( Smn2
5: Calculate LCB μi fis-
2N. V22.
In general, we have CJ S K and K R² ( cating that neither Eq. (5) nor Eq. (6) strictly dominates the other. For instance, for CMAB with semi-bandit feedback where p; Pam.S" =P₃ S
K indi-
6: end for
7: Call oracle S = ORACLE((1, Hmm)
8: Return: S.
for any i,j E S* and 0 other- wise, Eq. (6) is tighter than Eq. (5) since K K2 = K* and Ci S K'C Conversely, for the LLM cache to be introduced in Section 4.2, if the experimenter selects the Pmm.
passively collected data.
Theorem 1. Let I be a CMAB-T problem and D a dataset with data samples. Let S denote the action given by CLCB (Algorithm/ 1) using an a-approximate oracle. the problem satisfies (a) monotonicity (Condition 1), (b) 1-norm TPM smoothness (Condition 2) with coesficient B1 and (c) the infinity-ormm TPM data coverage condition ( (Condition 3) with coefficient C : and the number of samples satisfies llog( T.)
empty cache each time, such that a.
for S",
then we have Cf = KK Since R Z K so Eq. (5) is tighter than Eq. (6).
(R3)²
Lower bound result. In this section, we establish the lower bound for specific combinatorial multi-armed bandit (CMAB) problem: the stochastic k-path problem I. This problem was first introduced in (Kveton et al., 2015c) to derive lower bounds for the online CMAB problem.
n 2 min Pame Pt
Bumiiigg then, with probability at
least d (the randomness is taken over the all distributions DDs, Damny Dirigh, the suboptimality gap satisfies:
The k-path problem involves m. arms, representing path segments denoted as [m]] =
a,) S K
Co log( (m44m//))
(5)
m. Without loss of generality, we assume m/k is an integer. The feasi- ble combinatorial actions S consist of m/k paths, each containing k unique arms. Specifically, the j-th path for [m/k] includes the arms (j 1)k + I,...,jk. We de- fine k k-path(m, k. C=2) as the set of all possible outcome and data collection distribution pairs (Damm, IDs) satisfying the following conditions:
T2
where Kī = Eie(m Vp. S* is the E2-action size of S"
Further, if problem I satisfies the I-norm TPM data cover- age condition (Condition 4) with coefficient Cj. then, with probability at least - 5, the suboptimality gap satisfies:
K'C log(4mn/6)
a. 2BBBy V
(6)
(1) The outcome distribution Dam specifies that all arms in any path [m/k] are fully dependent Bernoulli random variables, i.e., X Xt.(j-1)++1 X1,(j-1)++2
n1
Xt,jk
where Kt == Eieim Pt S is the action size of S
all with the same expectation μt--
Proof Idea. The proof of Theorem consists of three key steps: (1) express the suboptimality gap in terms of the uncertainty gap r(S": 14) -r (S": (4) over the optimal action S*, rather than the on-policy error over the chosen action S as in online CMAB, (2) leverage Condition 2 to relate the uncertainty gap to the per-arm estimation gap, and (3) utilize Condition to deal with the arbitrary data collection probabilities and bound the per-arm estimation gap in terms of n. For detailed proof, see Appendix D.
(2) The pair (Bam, Ds) satisfies the infinity-norm TPM data coverage condition (Condition 3) with C i.e., Pen.s"
m|x 2am S S..o..
The feedback of the k-path problem follows the classi- cal semi-bandit feedback for any S E S, i.e., P. S...
if i E S and P. Sam.S D (St, (Xi,))iss, )i= to denote random offline k-path dataset of size n and D ~ D(Dum, Ds) to indicate dataset D is generated under the data collecting distribution DDs with the underlying arm distribution Darm-
otherwise. We use
Remark 4 (Discussion of Theorem 1). Looking at the sub- optimality gap result, both Eq. (5) and Eq. (6) decrease at va with respect to the number of offline data sam- ples n. Additionally, they scale linearly with the smoothness
rate of 1
Theorem 2.
Let us denote A(D) E S as the action returned by any algorithm A that takes a dataset D of n
5

---

Offline Learning for Combinatorial Multi-armed Bandits
samples as inpul. For any m, k E4, such that m/ k is an
feedback and the triggered arms are Ti { -.,, Dt.jt
integer, and any Co 22, 2, the following lower bound holds:
where je K if (at,1.....t.s)) = (0, or otherwise ji argmin E [k] Xt.a.. = 1}.
infA DS) Cx (DD.((B..Ds)) ())
r(A(D): 2 1 mim
1, V. C=
Learning from the offline dataset. We consider the of- fline learning setting for cascading bandits, where we are given a pre-collected dataset D = (Si, Tr, (Xr,)) )i=1 consisting of n ranked lists and the user feedback for these ranked lists, where each St is sampled from the data col- lecting distribution D's. Let us use qi to denote the prob- ability that arm i is sampled at the j-th position of the ranked list, for i E [m]]]] E [k]]. Then we have P; Den.Ds N
Comparing this result to the upper bound established in Theorem I for the k-path problem, we can verify that this problem satisfies Condition 2 with B₁ = 1 and K2- = k, meaning that our upper bound result matches the lower bound up logarithmic factors.
Σ 96y(1- (10(1-10 11)²-1 and p; Pam.SS -I (1 - H4)) There-
4. Applications of the Off-CMAB Framework
fore, we can derive that the 1-norm data coverage coefficient
in Condition 4 is Ci Σ 11:-30--)
In this section, we introduce three representative applica- tions that can fit into our Off-CMAB-T framework with new/improved results, which are summarized in Table We also provide empirical evaluations for the cascading bandit and the LLM cache in Section 5.
(1
Algorithm and result. This application fits into the CMAB-
T framework, satisfying Condition 2 with coefficient B₁ = 1 as in (Wang & Chen, 2017). The oracle is essentially to find the top-k items regarding LCB Hea which maximizes r(S; μ1) in O(m log k) time complexity using the max-heap. Plugging this oracle into line 7 of Algorithm I gives the algorithm, whose detail is in Algorithm 4 in Appendix F.
4.1. Offline Learning for Cascading Bandits
The cascading bandit problem (Kveton et al., 2015a; Li et al., 2016; Vial et al., 2022; Dai et al., 2025a) addresses the line learning to rank problem (Liu et al., 2009) under the cas- cade model (Craswell et al., 2008). The canonical cascading bandit problem considers a 7'-runn sequential decision- making process. At each round t E [T], a user t comes to the recommendation system (e.g.. Amazon), and the learner aims to recommend ranked list S. = (a.,1...., dt,x)) S [m]] of length le (i.e., super arm) from a total of m candidate products (i.e., base arms). Each item E St has un- known probability μi of being satisfactory and purchased by user i, which without loss of generality, is assumed to be in descending order μ1 2 P2 2 2 Mm-
Corollary 1. For cascading bandits with arms μn 2 P2... 2 Pm and a dataset 'D with n data points, suppose &logl 2mm
min,e(e) > 9:5(1 (oo(---))---- where qú is the probability that item is sampled at the j-th position regarding Dss- Letting $ be the ranked list returned by Algorithm 4, then with probability at least? 1 - 8,
r(S:: p1) - r (8:11)
k log( (fmm))
k
IT (1 (1-1)) (1y)
$ 2,
(7)
Ejm1 Fiz - -11)-11
Reward function and cascading feedback. Given the ranked list S,, the user examines the list from Gr to dr,k until they purchase the first satisfactory item (and leave the system) or exhaust the list without finding a satisfac- tory item. If the user purchases an item (suppose the je-th item), the learner receives a reward of I and observes out- comes of the form (Xt,a, .... ...,,,,,,, Xt,o,__, Xx, y ..., Xt, = (O...., 0, ..... -), meaning the first jr - 1 items are un- satisfactory (denoted as 0), the je-th item is satisfactory (denoted as 1), and the outcomes of the remaining items are unobserved (denoted as -). Otherwise, the learner receives a reward of 0 and observes Bernoulli outcomes (Xr,a) ..., Xx,
If Ws is a uniform distribution so that qu = 1 it holds that Cf S 81mm and
H)) - r -S:11) 22
k loog mph1
(8)
n
Pk
4.2. Offline Learning for LLM Cache
The LLM cache is a system designed to store and retrieve outputs of Large Language Models (LLMs), aiming to en- hance efficiency and reduce redundant computations during inference (Pope al., 2022; Bang. 2023; Zhu al., 2023; Dai et al., 2025b).
(0, 0, ..... 0). The expected reward is r(Se; 11) E E [k] : Xt.a, 1}] = 1- 1 (4) Since Wn 2 12... 2 Mm. we know that the optimal ranked list is the top-k items S* = 21, k). The goal of the cas- cading bandit problem is to maximize the expected number of user purchases by applying an online learning algorithm. For this setting, we can see that follows the cascading
In the LLM cache bandit (Zhu et al., 2023), which is a T-
round sequential learning problem, we consider a finite set of m distinct queries Q = {qI...., Im (m.)......... Each query q E Q is associated with an unknown expected cost c(g) E [0, 1]
6

---

Offline Learning for Combinatorial Multi-armed Bandits
Table I. Summary of the results of applying the Off-CMAB framework various applications. Application
Smoothness
Data Coverage
Suboptimality Gap
Improvements
Learning to Rank (Section 4.1)
B =1
C Paom
MHL Ô
PK
LLM Cache (Section 4.2)
B1 =
C7 = m
Ô (V
R2
Social Influence Maximization (Section 4.3)
B1 V
Assumption 1 Ö
V. (81
(V
V44 12 =xx
m, k, Ma,, Me denote the number of items, the length of the ranked list, and click probability for 1-st and k-th items, respectively;
m. k. Cj denote the number of LLM querics, the size of cachc, and the lower bound of the query cost, respectively;
** Similar to Chen et al. (2021), we depend directly on assumption for seed sampling probability bound y and the activation probubility bound m
$ V,, diax. o G).& & denote the number nodes, the max out-degree, optimal influence spread, and the number of seed nodes. respectively.
and unknown probability p(4) E [0, 1]. for a total of 2m base arms. When query g is input to the LLM system, the LLM processes and returns a corresponding response (i.e., answer) r()). Every round when the LLM processes q. it will incur a random cost (g)g) with mean c(q). representing floating point operations (FLOPs) or the price for API calls
the cache. In this context, the expected cost function can be rewritten as: c(S; c, p) = Enes p(g)c(q). The goal of LLM cache bandit is to find the optimal cache M storing the query-response pairs that are both likely be reused and associated with high costs, i.e., to find out the optimal super arm S argmingg Q: 512mm= (1
(Zhu et al., 2023). We assume that (g(g) = <(q) + e (g)., where (g) is a Gaussasssinn noise that captures the uncer- tainties in the cost, with (g) = O.
We separately consider the cache feedback for and P. For unknown costs c, we can see that Ft.c = qt if q: E MM, and
Tt. = 0 otherwise. For unknown probability distribution P. we observe full feedback Tt.p = Q since qe means qt arrives and all other queries do not arrive. For the triggering probability, we have that, for any S S, the triggering probability for unknown costs pape P.mm.S p(()) for q E S and O otherwise. The triggering probability for unknown arrival probability pa = for all E Q
The goal of LLM eache bandit is to find the optimal cache M storing the query-response pairs that are both likely to be reused and associated with high costs.
Expected cost function and cache feedback. In each round i, a user comes to the system with query qt, which is sam- pled from Q according to a fixed unknown distribution (p(2))ee with Egeg p(q) = 1. To save the cost of re- peatedly processing the queries, the LLM system maintains cache M, S Q. storing a small subset of queries of size k 2 0 with their corresponding results. After qt is sam- pled, the agent will first check the current cache Mr. If the query q: is found in the cache, i.e., l: E MM, we say the query hits the cache. In this case, the result of q: is directly returned without further processing by the LLM. The cost of processing this query 0 and will save a poten- tial cost Ct (g:), which is unobserved to the agent. If query q. does not hit the cache, the system processes the query, incurring cost Cz(q:) which is observed by the learner, and returns the result r(g)) Let us denote c = (c(4))yEQ and = (p(4))ee@ for convenience. Given any cache M and the query g, the random cost saved in round t is g) = I(q & (g). Thus the expected cost incurred is
Learning from the offiine dataset. We consider the offline learning setting for the LLM cache, where we are given pre-collected dataset D = (Mr, ft, Gt) consisting of the selected cache M,. the arrived query qt, and their cost feedback C₁ = (g.))) if q & .M or C2 = 9 is unobserved otherwise, where each MM is sampled from the data col- lecting distribution Dys- Let v(q) = Pr [4 & .M] be the probability that is not sampled in the experimenter's cache. Then we can derive that the 1-norm data coverage coefficient in Condition 4 is Ci Eges- ([q) m.
Algorithm and result. This application fits into the CMAB- T framework, satisfying the 1-norm TPM smoothness con- dition with coefficient B1 = 1 (see Appendix G.1 for the detailed proof). Since we are minimizing the cost rather than maximizing the reward, we use the UCB p(g)ε(q). The oracle is essentially to find the top-k queries regarding UCB p()) which minimizes c(5; 2, p) in O(m log k) time complexity using the max heap. The detailed algorithm and its result is provided in Algorithm 5.
c(M:c.p) = E
Σ c.(,.g) EE@
= Σ pla)c(1). (9) M
Since the arrival probabilities p are full-feedback categorical random variables, we can further improve our result by factor of vm by directly using the empirical mean of p instead of UCB p. The improved algorithm is shown in Algorithm 2 with its theoretical suboptimality guarantee:
From our CMAB-T point of view, selecting any cache M of size k can be regarded as selecting the super arm S = Q M with size m - k. which is the complement of M. Thus, our super arms represent the queries not entered into
7

---

Offline Learning for Combinatorial Multi-armed Bandits
Algorithm 2 CLCB-LLM, c: Combinatorial Lower Confi-
maximize the influence spread (S; G) from these nodes. IM has been intensively studied over the past two decades under various diffusion models, such as the independent cas- cade (IC) model (Kempe et al., 2003b), the linear threshold (L.T) model (Chen et al., 2010), as well as different feedback such as edge-level and node-level feedback models. For the edge-level feedback model, IM smoothly fits into our framework by viewing each edge weight Pue for (u, v) E as the base arm. In this section, we consider more re- alistic yet challenging setting where we can only obverse the node-level feedback (Chen et al., 2020; 2021), showing that our framework still applies as long as we can construct a high probability lower bound (LCB) for each base arm (edge). Due to space constraints, we present only our main result here. The detailed setting, algorithm, and theoretical analysis can be found in Appendix C.
dence Bound Algorithm for LLM Cache
1: Input: Dataset D {(Me, 2t Ci))== queries Q, solver Top-k, k, probability 6.
2: for query q Q do
3: Calculate counters N4) = Σ --= T(g-- = %o and
Ne(g) = Σi= I[gg- = qe and & MM}.
4: Calculate empirical means p(1)) = N(4) /'m and
Ce 1//g- = qt and qe $ M,JCr/NN(Q))
5: Calculate UCB E(q) = Ō(q) + V log( m
(N)
6: end for
7: Call M- Top-k k (p(a) (=(1) ) ..., ........ ((mm))
=
8: Return: M..
Theorem 3. For LLM cache bandit with a dataset 'D of 8 Blog(?) 2
Theorem 4. Under Assumption 1, suppose the number of data > 392 12 Letting $ be the seed set returned
n data samples, suppose n Z mingee-Me pla)r(a)' where v(q) is the probability that query q is not included in each offtine sampled cache. Letting M be the cache returned by algorithm Algorithm 5, then with probability at least - 5,
9-7
by Algorithm 3, then it holds with probability at least 1 8,
(o(S) (8:C)
(12)
cMM - < (M:c.P)
(10)
S <48VB (5 llog( 3
12nE
2 EGEE-MM v(g) log( 6mn
2m log( )
1 7-78-1
/2
21
n
where dmax is the maximum out-degree, 7 are lower bounds for seed sampling probability and the activation probability, respectively, as in Assumption 1.
If the experimenter samples empty cache Me = 0 in each
round as (Zhu et al., 2023) so that v(q)= 1, it holds that
Remark 6 (Discussion). To find out an action S such that ()) our algorithm requires that which improves the existing result by C
c(M';c.)) c (M:c..) s A
2m log( 6mn
($: G) (a
(11)
n
n 2 Ô
Remark 5 (Discussion of Theorem 3). Looking at Eq. (II), our result improves upon the state-of-the-art result (Zhu et al., 2023) Ö(k G >> 0 is assumed to be an lower bound of c(q) for q E Q This improvement comes from our tight analysis to deal with the triggering probability (the 1/C1 can be thought of as minimum triggering probability in their analysis) and from the way that we deal with full-feedback arm p. Fur- thermore, since we use the UCB č while they use LCB c. our algorithm in principle can be generalized to more complex distributions as long as the optimal queries are sufficiently covered. As a by-product, we also consider the online streaming LLM cache bandit setting as in (Zhu et al., 2023) from our CMAB-T point of view, which improves their result Ö( km by a factor of Ō kym)) details to Appendix G.3.
factor of Ô
P. owing to our variance-adaptive LCB construction and the tight CMAB-T analysis. We also relax the assumption of Chen et al. (2021) for the seed sampling probability and activation probability, owing to the usage of LCBs, rather than directly using the empirical mean of edge weight Pue. See Appendix C for the detailed discussion.
m by a factor of Ö(V )) where Cin
5. Experiments
10C2-Offlie EMP CLCB
BIR CUCD-OMin TNP
Cap (logu
Cup
CLCB
Ci ). We defer the
C₁
Offine Sample Size
Action
(a) Synthetic Dataset
(b) Real-world Dataset
4.3. Offline Learning for Influence Maximization with Extension to Node-level Feedback
Figure I. Suboptimality gaps for cascading bandit application.
Influence maximization (IM) is the task of selecting a small number of seed nodes S in social network G(V, E,p) to
We now present experimental results on both synthetic and real-world datasets. Each experiment was conducted over 20
8

---

Offline Learning for Combinatorial Multi-armed Bandits
Similarly, we conduct experiments in the LLM cache setting. In the synthetic setup, simulate 100 distinct queries with cache size of 40, following a power-law frequency distribution (a 0.9) as in (Zhu et al., 2023). As shown in Fig. 3a, our CL CI.CB-IIM--C afgorithm outperforms LFFU (which evicts the least frequently accessed items to optimize cache usage) (Zhu et al., 2023) and LEC (which minimizes inference cost by evicting items with the lowest estimated expected cost) (Zhu et al., 2023), achieving at least 1.32x improvement. For real-world evaluation, we use the SciQ dataset (Welbl et al., 2017). We evaluate GPT-4-o with the "o200k_base encoding with cache sizes K = 10 and K- = 20, where cost is defined by OpenAl's API pricing with the tiktoken library (OpenAI, 2025). Fig. 3b shows that CLCB-LLM-C (Algorithm 2) reduces costs by up to 36.01 % and 20.70%, compared to LFU and LEC. Moreover, a larger K shows lower suboptimality gap, which is consistent with Theorem 3. Further details on experimental setups, results, and additional comparisons can be found in Appendix J.
CUCB- Offline
Suboptimeltty Gap
EMP
0.20
CLCB
0.33
6.30
0.05
0.00
Gene
LCB Offiine Date Generation Method
Figure 2. Comparison different offline data generation methods.
UI LTU
LEC
CLCB
Subogranaltg
0-
EG
14
CA-
CLCB C
Offine Sample
0.c
K-10
Cache
K0
(a) Synthetic Dataset
(b) Real-world Dataset
Figure Suboptimality gaps for LLM cache application.
6. Conclusion and Future Directions
independent trials. For cascading bandits on the application of learning to rank, in the synthetic setting, item parameters M4 drawn from [0, 1], and in each round t, ranked list S, of K items is randomly sampled. Fig. Ia shows that compared to CUCB-Oftine (Chen et al., 2016), which is an offline adaptation of CUCB for our setting, and EMP (Liu et al., 2021), which always selects the action based on the empirical mean of rewards, CLCB (Algorithm 1) reduces suboptimality gaps by 47.75% and 20.02%, respectively. For real-world evaluation, we use the Yelp dataset', where users rate businesses (Dai et al., 2024c). We randomly select m = 200 rated items per user and recommend up to K items to maximize the probability of user engagement. The unknown probability μ4 is derived from Yelp, and cascading feedback is collected, Fig. 1b compares suboptimality gaps over 100 rounds for K 4, 8, with a logarithmic scale on the y-axis. Note that as K increases, the expected reward also changes, thus reducing suboptimality gaps. CLCB consistently achieves the lowest suboptimality gap.
In this paper, we introduce Off-CMAB, the first offline learning framework for CMAB. We propose two novel data coverage conditions and develop a provably sample-cfficient CLCB algorithm, matching the lower bound up to logarith- mie factors. We show the practical usefulness of our frame- work via three diverse applications-Icarinnn to rank, LLM caching, and social influence maximization-accieve or improved theoretical results. These results are further validated through extensive experiments both synthetic and real-world datasets. Looking ahead, an exciting direc- tion is to develop variance- improve our theoretical guarantees. Additionally, extend- ing our framework to offline RL with combinatorial action spaces is another promising direction for future research.
new
algorithms to further
A Acknowledgement
The work is supported by NSF CNS- and the Office of Naval Research under grant N000 N0000142412073. The work of John C.S. Lui was supported in part by the RGC GRF- 14202923. The work of Jinhang Zuo was supported by CityUHK 9610706.
Moreover, we generate offline datasets D with n = 100 in four different ways: random sampling, UCB-based genera- tion, LCB-based generation, and empirical tandee generation. For the UCB-based, LCB-based, and empirical-based data generation methods, select the top K 5 arms with the largest UCB, ICC, and empirical reward means, respec- tively. It can be observed in Fig. 2 that our method con- sistently maintains the smallest suboptimality gap. When using the UCB data generation method, our algorithm per- forms significantly better than the CUCB-Offlin and EMP baselines, which aligns with our theoretical results.
Impact Statement
This paper presents a theoretical study on multi-armed ban- dits and reinforcement learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Phttps:/ :/ww:////wwww/// www.wwwwllll... yelp pp com dataset.
9

---

Offline Learning for Combinatorial Multi-armed Bandits
References
learning from human feedback. ArXiv, abs/2307.15217,
2023. URL htttps://apl
Agarwal, R., Schuurmans, D., and Norouzi, M. An optimistic perspective on offline reinforcement learn- ing. In International Conference on Machine Learning, 2019. URL https: wtt.pp....mttttsssoooooooo.m.mee Drg/CorpusID: 212628904.
org/
N. and Lugosi, G. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404 1422, 2012.
Agrawal, S., Avadhanula, V., Goyal, V., and Zeevi, A. Mnl- bandit: A dynamic learning approach to assortment selec- tion. Operations Research, 67(5):1453-1443 2019.
Chang, D., Uchara, M., Sreenivas, D., Kidambi, R., and Sun, W. Mitigating covariate shift in im- itation learning via offline data with partial cover- age. In Neural Information Processing Systems, www.eessmaattsssss.e.e.eee....ee
Audibert, J.-Y., Bubeck, S., and Lugosi, G. Regret in online combinatorial optimization. Mathematics of Operations Research, 39(1):31-45 2014.
2021. URL https: http://://ppp...maaa..s.s.se org/ Cosp/CCrpssD::: : 248498378.
Chen, J. and Jiang, N. Information- considerations in batch reinforcement learning. In International Conference on Machine Learning, 2019a. URL https: / //api semantsemnttiio www.icccchll.ooooo /orrrs//Crrpss 141460093.
Bai, C., Wang, L.,, Yang. Z.,, Deng. Z.,, Garg, A., Liu, P., and Wang, Z. Pessimistic bootstrapping for uncertainty-driven offline reinforcement learning, 2022. URL https::/ arxiv. org/ abs 2202222222222 112...1666 11566.
Balkanski, E., Rubinstein, A., and Singer, Y. The limitations of optimization from samples. Proceedings of the 49th An- nual ACM SIGACT Symposium on Theory of Computing, 2015. URL https:/ htpppappaaaee/ sem.nt.entt.... www.semannntcchhla........o..... cscholar. 742580.
Chen, J. and Jiang, N. Inforration- considerations in batch reinforcement learning. In International Con- ference on Machine Learning, pp. 1042-1051. PMLR, 2019b.
Chen, L., Xu, J., and Lu, Z. Contextual combinatorial multi- armed bandits with volatile arms and submodular reward. Advances in Neural Information Processing Systems, 31, 2018
Balkanski, E., Rubinstein, A., and Singer, Y. The power of optimization from samples. In Neural Informa- tion Processing Systems, 2016. URL https://app semant cscchllrrrr...... .owlll...rrr...............oo... httrg/Corpusstt 153394444 5394546.
Chen, W. Wang. Y., and Yang. Efficient influence maximization in social networks. In Knowledge Dis- covery and Data Mining, 2009. URL https: /api. semantion wwtholaschlr....mmm wttp://oooss.:111111111...
Bang, F. Gptcache: An open-source semantic cache for Ilm applications enabling faster answers and cost savings. Proceedings of the 3rd Workshop for Natural Language Processing Open Source Softwure (NLP-OSS 2023), 2023. URL https: http:///a..aaaassssseeseeeeaaeee www.nticscholeee.....o.o #ttp/CorpusID:225566
Chen, W., Yuan, Y., and Zhang, Scalable influence max- imization in social networks under the linear threshold model. In 2010 IEEE international conference on data mining, pp. 88-97. IEEE, 2010.
Bouneffouf, D., Rish, I., and Aggarwal, C. Survey on appli-
cations of multi-armed and contextual bandits. In 2020
IEEE Congress on Evolutionary Computation (CEC), pp- 1-8. IEEE, 2020.
Chen, W., Wang, Y., and Yuan, Y. Combinatorial multi- armed bandit: General framework and applications. In International Conference Machine Learning, pp. 151- 159. PMLR, 2013.
Bubeck, S., Cesa-eeeaaaaa Bianchi, N., and Kakade, S. M. Towards minimax policies for online linear optimization with ban- dit feedback. Conference on Learning Theory, pp. 41- JMLR Workshop and Conference Proceedings, 2012.
Chen, W., Wang, Y., Yuan, Y., and Wang, Q. Combinatorial multi- anme bandit and its extension probabilistically triggered arms. The Journal of Machine Learning Re- search, 17(1):174-1777 2016.
Casper, S., Davies, X., Shi, C., Gilbert, K., Scheurer, J.. Rando, J.. Freedman, R., Korbak, T., Lindner, D., Freire, P., Wang, T., Marks, S., Ségerie, C.-R., Car- roll, M., Peng, A., Christoffersen, P. J. K., Damani, M., Slocum, S., Anwar, U., Siththaranjan, A., Nadeau, M., Michaud, E. J., Pfau, J., Krasheninnikov, D., Chen, X., di Langosco, L. L., Hase, P., Biyik, E., Dragan, A. D., Krueger, D... Sadigh, D., and Hadfield-Menell D. Open problems and fundamental limitations of reinforcement
Chen, W., Sun, X., Zhang, J., and Zhang, 7. Optimiza- tion from structured samples for coverage functions. In International Conference on Machine Learning, pp. 1715- 1724. PMLR, 2020.
Chen, W., Sun, X., Zhang, J., and Zhang, Z. Network inference and influence maximization from samples. In
10

---

Offline Learning for Combinatorial Multi-armed Bandits
International Conference Machine Learning, pp. 1707- 1716. PMIR, 2021.
Ernst D., Geurts, P., and Wehenkel, L.. Tree-based batch mode reinforcement learning. Journal of Machine Learn- ing Research, 6. 2005.
Chen, X., Zhou, Z., Wang, Z., Wang, C.. Wu, Y.,
Deng, Q. and Ross, K. W. Bail: Best-action imitation learning for batch deep reinforcement learn- ing. ArXiv, abs/1910.12173 2019. URL https: //api. www.etiiscooolee.e....... orgCooppssD: 204907199.
Feng, T., Shen, Y., and You, J. Graphrouter: A graph- based router for Ilm selections. ArXiv, abs/24000083334 2024. URL https: / /apii.
axg//oorpuSD::231165555
Fourati, F,, Aggarwal, V., Quinn, C., and Alouini, M.-S. Randomized greedy learning for non-monotone stochas- tic submodular maximization under full-bandit feedback. In International Conference on Artificial Intelliencce and Statistics, pp. 7455-7471. PMI.R 2023.
Chen, X., Wang, S., McAuley, J., Jannach, D., and Yao, I. On the opportunities and challenges of offline reinforcement learning for recommender sys- tems. ACM Transactions on Information Systems, 2023. URL https: http//pp....aaa.... httpss///ap..emmnnccccooooo... semanticscholar: hTr/CorppsID:221106
Fourati, F., Alouini, M.-S., and Aggarwal, V. Federated combinatorial multi-agent multi-armed bandits. arXiv preprint 24XXi::200.0595500 2024a.
Choi, H.-j., Udwani, R., and Oh, M.-h. Cascading contex- tual assortment bandits. Advances in Neural Information Processing Systems, 36, 2024.
Fourati, F, Quinn, C. J., Alouini, M.-S., and Aggarwal, V. Combinatorial stochastic-greedy bandit. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 12052-12060, 2024b.
Combes, R., Talebi Mazrach Shahi. M. S., Proutiere, A., et al. Combinatorial bandits revisited. Advances in neural information processing systems, 28, 2015.
Fujimoto, S. and Gu, S. S. A minimalist approach to of- fline reinforcement learning. ArXiv, abs/2106.06860, 2021. URL https: //aii. semanticscholea.
Craswell, N., Zoeter, O., Taylor, M., and Ramsey, B. An experimental comparison of click position-bing bias models. In Proceedings of the 2008 international conference on web search and data mining, pp. 87-94, 2008
Fujimoto, S., Meger, D., and Precup, D. Off-
Dai, X. Li. Liu, X., Yu, A., and Lui, J. C. S. Cost-effective online multi-llm selection with versatile reward models. ArXiv, abs/2405.16587, 2024a. URL https:ttt///tcttccttt http://:///pp....s..sseeseee semanticschollat org/CorpusID:270665
policy deep reinforcement learning without exploration. In International Conference on Machine Learning, 2018. URL https: / htppppapp.//////////aaa org CCCooosI:::4457222 httpp/////ppp.eeettacccaaaaaaaaa www.nticscoola......m.o
Gai, Y., Krishnamachari. B., and Jain, R. Learning mul- tiuser channel allocations in cognitive radio networks: A combinatorial multi-armed bandit formulation. In 2010 IEEE Symposium on New Frontiers Dynamic Spectrum (DySPAN), pp. 1-9. IEEE, 2010.
Dai, X., Wang, Z., Xie, J., Liu, X., and Lui, J. C. Con- versational recommendation with online Icarning and clustering on misspecified users. IEEE Transactions on Knowledge and Data Engineering, 36(12);7825-7838, 2024b.
Dai. X., Wang, Z., Xie, J., Yu, T., and Lui, J. C. Online learning and detecting corrupted users for conversational recommendation systems. IEEE Transactions Knowl- edge and Data Engineering, (6(12):8939-889 2024c.
Gai, Y., Krishnamachari, B., and Jain, R. Combinatorial net- work optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. IEEE/ACM Transactions Networking (TON), 20(5): 1466-1478, 2012.
Dai, X., Liu, X., Zuo, J., Xie, H., Joe-Wong C., and Lui, C. S. Variance-aware bandit framework for dynamic probabilistic maximum coverage problem with triggered self-reliant arms. IEEE Transactions on Networking, pp. 1-12, 2025a.
Gim, I., Chen, G., seob Lee, S., Sarda, N., Khandelwal, A., and Zhong, L. Prompt cache: Modular attention reuse for low-latency inference. ArXiv, abs/2311 0ts/23311.0492.. .04934, 2023. URL https: /api. semant. i cscholar Seg//oorpssD::25555
Dai, X., Xie, Y., Liu, M., Wang. X., Li, Z., Wang, H., and Lui, J. Multi-agent conversational online learning for adaptive Ilm response identification. arXiv preprint vrXiv:2501.018.. 2025b.
György, A., Linder, T., Lugosi, G., and Ottuesák, G. The on-line shortest path problem under partial monitoring. Journal of Machine Learning Research, 8(10), 2007.

---

Offline Learning for Combinatorial Multi-armed Bandits
Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S. Soft actor- critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. ArXiv, abs/1801.01290, 2018. URL https: / app.. www.nttemsnttsteeeeee icschooas arg/CorrpsTT:: 28202810.
Comput., 11:105-147, 2003b. URL https: //ppi. semanti www.sscccc....ccccoococoeeeeeeee :etppussD:2213355 7214363.
Kidambi, R., Rajeswaran, A., Netrapalli, P., and
Joachims, T. Morel Model-based offline reinforcement learning. ArXiv, abs/2005.0599
Han, Y., Wang, Y., and Chen, X. Adversarial combinatorial bandits with general non-linear reward functions. In International Conference on Machine Learning, pp. 4030- 4039. PMLR, 2021.
2020. URL https://api. www.mnttttiii.. cascooar... org/Corpps1D:211895555
Kiran, B. R., Sobh, I., Talpaent, V., Mannion, P. Sallab, A. A. A., Yogamani, S. K., and P'erez, P. Deep reinforcement learning for au- tonomous driving: A survey. IEEE Transactions on Intelligent Trunsportation Systems, 23:4909-4926, 2020. URL https: http:///app.smaanniicoccmm semanticscholar. prrg/CorpusDD:2111100
Hwang, T., Chai, K., and Oh, M.-h. Combinatorial neural bandits. In International Conference Machine Learn- ing, Pp. 14203-14236. PMLR, 2023.
Ito, S. Hybrid regret bounds for combinatorial semi-bandits and adversarial linear bandits. Advances Neural Infor- mation Processing Systems, 34:2654- 2667, 2021.
Kumar, A., Fu, J., Tucker, G., and Levine, S. Stabi- lizing off-policy q-learning via bootstrapping error re- duction. In Neural Information Processing Systems, 2019. URL https: http:///aapps.aaa..ee.e.mmm www.ee.iiaanoooa.......... org/CorpusID:1133900
Jiang, N. On value functions and the eeent-environment boundary. arXiv preprint arXiv: 1et../005...44 13341, 2019.
Jiang, N. and Li, L. Doubly robust off- off--ollcy value evalua- tion for reinforcement learning. In International Confer- ence on Machine Learning, 2015. URL ht stttpss:/appp semant www.ticcccoa......oomom.. org/ Beegg/oorre Corpus ID: 5806691.
Kumar, A., Zhou, A., Tucker, G., and Levine, S. Conservative q-learning for offline reinforcement learning. ArXiv, abs/2006.04779, 2020. URL https: www.attisccoolaa.........c. 219530894.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. Provably efficient reinforcement learning with linear function ap- proximation. In Conference on Learning Theory, pp- 2137-2143. PMLR, 2020a.
Kveton, B., Szepesvari, C., Wen, Z., and Ashkan, A. Cas- cading bandits: Learning rank in the cascade model. In International Conference on Machine Learning, pp. 767-776. PMLR, 2015a.
Jin, Y., Yang, Z., and Wang, Z. Is pessimism provably efficient for offline rI? In International Confer- ence on Machine Learning, 2020b. URL https: htt.ricssccooaooooooooououuu org/CorpusID:
Kveton, B., Wen, Z., Ashkan, A., and Szepesvári, C. Com- binatorial cascading bandits. In Proceedings of the 28th International Conference on Neural Information Process- ing Systems- Volume 1, pp. 1450-14555 2015b.
229923558.
Joachims, T. Optimizing search engines using click- through data. Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, 2002. URL https: //api. semanticscholar crr/Corp 207605508.
K Kveton, B., Wen, Z., Ashkan, A., and Szepesvari, C. Tight regret bounds for stochastic combinatorial semi-bandits. In AISTATS, 2015c.
Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C. H., Gonzalez, J. E., Zhang, H., and Stoica, I. Efficient memory management for large language model serving with pagedattention. Proceedings of the 29th Symposium on Operating Systems Principles, 2023. URL https: / api. semanticscholar. org/ ntg/CorpusTin ID: 261 697361.
Keane, M. T. and O'Brien, M. Modeling result-list search- ing in the world wide web: The role of relevance topologies and trust bias. 2006. URL https: //t::///pppp. semanti cwwnntisschlaas wescchola..oor/ooooussss.... 11000444. 00844.
Kempe, D., Kleinberg, J., and Tardos, É. Maximizing the spread of influence through a social network. In Proceed- ings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137-146, 2003a.
Lange, S.. Gabel, T., and Riedmiller, M. Batch reinforce- ment learning. In Reinforcement learning: State-of-the- art, pp. 45-73 Springer, 2012.
Kempe, D., Kleinberg, J. M., and Tardos, É. Maximizing the spread of influence through a social network. Theory
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam bridge University Press, 2020.
12

---

Offline Learning for Combinatorial Multi-armed Bandits
Lattimore, T., Kveton, B., Li, S., and Szepesvari, C. Toprank: A practical algorithm for online stochastic rank- ing, Advances in Neural Information Processing Systems, 31, 2018.
Liu, X., Zuo, J., Wang, S., J.JJJJWWngg. C., Lui, J., and Chen, W. Batch-size independent regret bounds for combina- torial semi-bandits with probabilistically triggered arms or independent arms. In Advances in Neural Information Processing Systems, 2022.
Le Cam, L. Asymptotic methods in statistical decision theory. Springer Science & Business Media, 2012.
Liu, X., Zuo, J., Wang, S., Lui, J. C., Hajiesmaili, M., Wierman, A., and Chen, W. Contextual combinatorial bandits with probabilistically triggered arms. In Inter- national Conference on Machine Learning, pp. 22559 22593, PMLR, 2023a.
Lee, S., Sco, Y., Lee, K., Abbeel, P., and Shin, J. Offline- to-online reinforcement learning via balanced replay and pessimistic q g-ensemble. In Conference on Robot Learn- ing. pp. 1702-1712. PMLR, 2022.
Liu, X., Zuo, J., Xie, H.. Joe-Wong, C., and Lui, C. Variance-adaption algorithm for probabilistie maximum coverage bandits with general feedback. In IEEE INFO- COM 2023-IEEE Conference Computer Communicu- tions, pp. 1-10. IEEE, 2023b.
Levine, S., Kumar, A., Tucker, G., and Fu, J. Offline rein- forcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint
0etr:00050.06443 2020.
Li, F., Liu, J., and Ji, B. Combinatorial sleeping bandits with fairness constraints. IEEE Transactions on Network Science and Engineering, 7(3):1799-1813, 2019.
Liu, X., Dai, X., Wang, X., Hajiesmaili, M., and Lui, J. Combinatorial logistic bandits. arXiv preprint arXiv:2410.17075, 2024a.
Li, G., Ma, C., and Srebro, N. Pessimism for offline linear contextual bandits using ell p confidence sets. Advances in Neural Information Processing Systems, 35:20974- 20987, 2022a.
Liu, X., Wang. S., Zuo, J., Zhong, H., Wang, X., Wang, 7., Li, S., Hajiesmaili, M., Lui, J., and Chen, W. Combina- torial multivariant multi-armed bandits with applications episodic reinforcement learning and beyond. arXiv preprint arXiv:2406.01388. 2024b.
Li, G., Shi, L., Chen, Y., Chi, Y., and Wei, Y. Settling the sample complexity of model-based of- fline reinforcement learning. ArXiv, abs/2204.05275, http://pp..mmmaaicccccc.eeeoeeoe 2022b. URL 248085555
Merlis, N. and Mannor, S. Batch-size independent regret bounds for the combinatorial multi-armed bandit prob- lem. In Conference Learning Theory, pp. 2465-2489. PMLR, 2019.
Li, S., Wang, B., Zhang, S., and Chen, W. Contextual com- binatorial cascading bandits. In International conference machine learning, pp. 1245 1253. PMLR, 2016.
Mnih, V., Kavukeuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M. Playing atari with deep reinforcement learning. arXiv preprint 1rXivv:331..00 2013.
Lin, B. and Bouneffouf, D. Optimal epidemic control as contextual combinatorial bandit with budget. In 2022 IEEE International Conference on Fuzzy Systems (FUZZ- IEEE), pp. 1-8. IEEE, 2022.
Nachum, O., Dai, B., Kostrikov, I., Chow, Y., Li, L., and Schuurmans, D. Algaedice: Policy gradient from arbitrary experience. ArXiv, abs/1912.02074. 2019. URL httpt: 209617844
Liu, S., See, K. C., Ngiam, K. Y., Celi, L. A., Sun, X. and Feng, M. Reinforcement learning for clini- cal decision support in critical care: Comprehensive review. Journal of Medical Internet Research, 22, 2020. URL https::/p////mc org/CorpusID 21 wwwppp..smattiiiiciiii......m.ee
semanticscho
Narasimhan, H., Parkes, D. C., and Singer, Y. Learnability of influence in networks. Advances in Neural Information Processing Systems, 28, 2015.
Liu, T.-Y. et al. Learning to rank for information retrieval. Foundations and Trends@ in Information Retrieval, 3(3); 225 00--31,,72 2009.
Neu, G. First-order regret bounds for combinatorial semi- bandits. In Conference on Learning Theory, pp. 1360- 1375. PMLR, 2015.
Liu, x., Zuo, J., Chen, X., Chen, W., and Lui, J. C. Multi-layered network exploration via random walks: From offline optimization to online learning. In Interna- tional Conference on Machine Learning, pp. 7057-7066. PMLR, 2021.
Nguyen- Tang, T., Gupta, S., Nguyen, A. T., and Venkatesh, S. Offline neural contextual bandits: Pessimism, optimiza- tion and generalization. arXiv preprint arX.v:2111.13807, 2021a.
13

---

Offline Learning for Combinatorial Multi-armed Bandits
Nguyen-Tang, T., Gupta, S., Tran-The, H., and Venkatesh, S. Sample complexity of offline reinforcement learning with deep relu networks. arXiv preprint arXiv:2103.06671, 2021b.
conference on Knowledge discovery and data mining, 2002. URL https://app wewanticsccooll.......m.. org/Corrus1D::575555
Riedmiller, M. Neural fitted iteration-first experiences with a data efficient neural reinforcement learning method. In Machine learning: ECML 2005: 16th European con- ference on machine learning, Porto, Portugal, October 3-7, 2005. proceedings 16, pp. 317-328. Springer, 2005.
Niazadeh, R., Golrezaei, N., Wang, J. R., Susan, F., and Badanidiyuru, A. Online learning via offline greedy algo- rithms: Applications in market design and optimization. In Proceedings of the 22nd ACM Conference on Eco- nomics and Computation, PP. 737-738, 2021.
Saha, A. and Gopalan, A. Combinatorial bandits with rela- tive feedback. Advances in Neural Information Process- ing Systems, 32, 2019.
Nie, G., Nadew, Y. Y., Zhu, Y., Aggarwal, V., and Quinn, C. J. A framework for adapting offline algorithms to solve combinatorial multi-armed bandit problems with bandit feedback. International Conference on Machine Learning, pp. 26166 16166-26198. PMLR, 2023.
Sheng, Y., Zheng, L., Yuan, B., Li, Z., Ryabinin, M., Fu, D. Y., Xie, Z.,, Chen, B., Barrett, C. W., Gonzalez, J., Liang, P., Ré, C., Stoica, I., and Zhang, C. High-throug the-uuhhoughput generative infer- ence of large language models with a single gpu. International Conference on Machine Learning, http://app..eemmaiiiccccoooooo
Nika, A., Elahi, S., and Tekin, C. Contextual combinatorial volatile multi armed bandit with adaptive discretization. In International Conference on Artificial Intelligence and Statistics, pp. 1486-1496. PMLR, 2020.
2023. URL org org/Corgp /ts///ooaIDD::549555555
OpenAL. OpenAl LLM API. https://platfot openai. com/, 2025.
Shi, L., Li, G., Wei, Y., Chen, Y. and Chi, Y. Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. ArXiv, abs/2202.13890, 2022. URL https: / /api. wwwanticschole. org/ Seg/CorppsID::220 :
Pope. R., Douglas, S., Chowdhery, A., Devlin, J., Bradbury, J., Levskaya, A., Heek, J., Xiao, K., Agrawal, S., and Dean, J. Efficiently scal- ing transformer inference. ArXiv, abs/2211.05109 2022. URL https: https////appsssaaiieieesme semanticschole.. /ttp//oouuID::234222222
Singh, B., Kumar, R., and Singh, V. P. Reinforce- ment learning in robotic applications: a comprehensive survey. Artificial Intelligence Review, 55:945 - 990, 2021. URL https: / api. www.nticscho.... org/ hts//CoruusD- : 234826155.
Qin, L., Chen, S., and Zhu, X. Contextual combinatorial bandit and its application diversified online recommen- dation. In Proceedings of the 2014 SIAM International Conference Data Mining, pp. 461-469. SIAM, 2014.
Sun, X., Guo, T., Han, C., and Zhang, H. Greedy algorithms for stochastic monotone k-submodular maximization der full-bandit feedback. Journal of Combinatorial Opti- mization, 49(1): 2025.
Qu, G., Chen, Q. Wei, W., Lin, Z., Chen, X., and Huang, K. Mobile edge intelligence for large language mod- cls: A contemporary survey. ArXiv, abs/2407.18921, 2024. URL https: www.pppp..paiii........ee..oppep www.nticschoolea..........c.c.ee ott//Co:pusID:27158...
Szepesvari, C. and Munos, R. Finite time bounds for sampling based fitted value iteration. Proceedings of the 22nd international conference on Machine learning. 2005. URL https: /tappp::///ppp /api. semant. semanticschooar escholar. org axg/CorppsID::81117
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. J. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. IEEE Transactions on Information Theory, 68:8156-18 1566,,9,, 2021.
Rashidinejad, P., Zhu, H., Yang. K., Russell, S. J., and Jiao, J. Optimal conservative offline rl with general function approximation via augmented la- grangian. ArXiv, abs/221 2022. URL https: //api. www.steesccoooooooe.o.. 253255046.
Takemura, K., Ito, S., Hatano, D., Sumita, H., Fukunaga, T., Kakimura, N., and Kawarabayashi, K.-i. Near-optimal regret bounds for combinatorial semi-bandits with linear payoff functions. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 9791-9798, 2021.
Tsuchiya, T., Ito, S., and Honda, J. Further adaptive best- of off-both-worlde algorithm for combinatorial semi-bandits. In International Conference on Artificial Intelligence and Statistics, pp. 8117-8144 8144. PMLR, 2023.
Richardson, M. and Domingos, P. M. Mining knowledge-sharing sites for viral marketing. Pro- ceedings of the eighth ACM SIGKDD international
14

---

Offline Learning for Combinatorial Multi-armed Bandits
Uchiya, T., Nakamura, A., and Kudo, M. Algorithms for adversarial bandit problems with multiple plays. In In- ternational Conference Algorithmic Learning Theory, pp. 375-389, Springer, 2010.
Wang, X., Golbandi, N., Bendersky, M., Metzler, D., and Najork, M. Position bias estimation for unbiased learning rank in personal search. Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, 2018. URL /ttpss//spppp... semanticscholl org/ http:/Coppus:::::0m :110p=4
Vaswani, S., Lakshmanan, L.. Schmidt, M., et al. In- fluence maximization with bandits. arXiv preprint arXiv:1503.00024 2015.
Wang, Y., Chen, W., and Vojnovié, M. Combinatorial ban- dits for maximum value reward function under max value- index feedback. arXiv preprint arXiv:2305. 16074, 2023.
Vaswani, S., Kveton, B., Wen, Z., Ghavamzadeh, M., Lak- shmanan, L., and Schmidt, M. Diffusion independent semi-bandit influence maximization. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017a.
Welbl, J., Liu, N. E., and Gardner, M. Crowdsoure- ing multiple choice science questions. arXiv preprint arXiv: ftfi::7707.060000 2017.
Vaswani, S., Kveton, B., Wen, Z., Ghavamzadeh, M., Lakshmanan, L. V. S., and Schmidt, M. W. Model- independent online learning for influence maximiza- tion. In International Conference on Machine Learning, 2017b. URL https: wttppppp...aaaatccsaeeeeoommeeee org/ arg/CorpusTID 32455974.
Wen, Z., Kveton, B., Valko, M., and Vaswani, Online in- fluence maximization under independent cascade model with semi aanibbandit feedback. Advances in neural informa- tion processing systems, 30, 2017.
Wu, Q., Li, Z.,, Wang, H., Chen, W., and Wang. H. Fac- torization bandits for online influence maximization. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019. URL https: / api. org/ htt//CorpuTD::: 82 :1: 952558.
Verma, S., Mate, A., Wang, K., Madhiwalla, N., Hegde, A., Taneja, A., and Tambe, M. Restless multi-armed bandits for maternal and child health: Results from decision- focused learning. In AAMAS, pp. 1312-1320, 2023.
Vial, D., Shakkottai, S., and Srikant, R. Minimax regret for cascading bandits. In Advances in Neural Information Processing Systems, 2022.
Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. Bellman-cconsisent pessimism for offline reinforee- ment learning. In Neural Information Processing Systems, 2021a. URL https: //p..s/eaaaanattttteeeeeee/ semant icshoolar. http:/CopusD:::335560
Wang, D., Cao, J., Zhang, Y., and Qi. W. Cascading ban- dits: optimizing recommendation frequency in delayed feedback environments. Advances in Neural Information Processing Systems, 36, 2024.
Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. Bellman--consisennt pessimism for offline reinforce- ment learning. Advances in neural information process- ing systems, 34:6683-6694, 2021b.
Wang, L., Cai, Q. Yang, Z. and Wang, Z. Neu- ral policy gradient methods: Global optimality and rates of convergence. ArXiv, abs/1909.01150) 2019. URL attps:://pi... stw.tpiimmatttcccooooo..... org/CorpusTD 202121359. 20000-pppuT::2222133333
Yin, M., Bai, Y., and Wang. Y.-.. Near-optimal offline reinforcement learning via double variance reduc- tion. ArXiv, abs/2102.01748, 2021. URL. https:
Wang, Q. and Chen, W. Improving regret bounds for com- binatorial semi-bandits with probabilistically triggered arms and its applications. In Advances in Neural Infor- mation Processing Systems, pp. 1 1161-1171 2017
serelleemmtticccchoeooo ort.:/rro///////eeoeooeeeeo 231786531.
Yu, T., Kumar, A., Rafailov, R., Rajeswaran, A., Levine, S., and Finn, C. Combo: Conservative offline model-based policy optimization. In Neural Infor- mation Processing Systems, 2021. URI. https: / deapi.ssmanticschhne 231934209.
Wang, S. and Chen, W. Thompson sampling for combi- natorial seni-bandits. In International Conference on Machine Learning, pp. 1112,112,,10 2018.
org/CorppsII:
Wang, X., Bendersky, M.. Metzler, D., and Najork, M. Learning to rank with selection bias in personal search. Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, 2016. URL https::/api. semant www.ttiicchhaa....om ortpoo/aar..ogr/ooousaa111111110
Zanette, A. and Wainwright, M. J. Bellman residual orthogo- nalization for offline reinforcement learning. Advances in Neural Information Processing Systems, 35:3137-3151 2022.
15

---

Offline Learning for Combinatorial Multi-armed Bandits
Zanette, A., Wainwright, M. J., and Brunskill, E. Provable
benefits of actor-critic methods for offiin reinforcement learning. Advances in neural information processing systems, 11136666133444 2021.
Zhang, Z., Su, Y.-H,, Yuan, H., Wu, Y., Balasub- ramanian, R., Wu, Q. Wang, H., and Wang, M.
Unified off-policy learning rank: reinforce- ment learning perspective. ArXiv, abs/2306.07528, 2023. URL https://appt sew.niicccmtiicccol...... http//oppuS:::55115500
Zhong, Z., Chueng. W. C., and Tan, V. Y. Thompson sam- pling algorithms for cascading bandits. Journal of Ma- chine Learning Research, 22(218): 2021.
Zhu, B., Sheng, Y., Zheng, L., Barrett, C., Jordan, M., and Jiao, J. Towards optimal caching and model selection for large model inference. 36:59062-59094, 2023.
Zimmert, J., Luo, H., and Wei, C.-Y. Beating stochastic and adversarial semi-bandits optimally and simultancously. In International Conference Machine Learning, pp- 7683-7692. PMLR, 2019.
Zuo, J. and Joe- Wong C. Combinatorial multi-armed ban- dits for resource allocation. In 2021 55th Annual Con- ference Information Sciences and Systems (CISS), pp- 1-4. IEEE, 2021.
16

---

Offline Learning for Combinatorial Multi-armed Bandits
The appendix is organized follows.
In Appendix A, we discuss the extended related works on
combinatorial multi-armed bandits,
offline bandit and reinforcement learning.
related offline learning applications.
In Appendix B we give more justification for studying the combinatorial multi-armed bandits (CMAB) with only the offline dataset.
In Appendix C, we provide the following details for
the influence maximization under node-level feedback setting
CLCB-ING -IM N algorithm
the gap upper bound
In Appendix D, we prove the upper bound the suboptimal gap
under the infinity-norm TPM data coverage condition (Condition 3)
under 1-norm TPM data coverage condition (Condition 4).
In Appendix E, prove
the lower bound of suboptimal gap for the k-path problem with semi-bandit feedback.
In Appendix F, we prove
the gap upper bound for the offline learning problem in cascading bandits.
In Appendix G, we prove
the standard gap upper bound of for offline learning in LLM cache
the improved gap upper bound for offline learning in LLM cache
the improved regret upper bound for online streaming LLM cache
In Appendix H. prove
the gap upper bound for the influence maximization under the node-level feedback.
In Appendix I, prove auxiliary lemmas that serve important ingredients for our analysis.
In Appendix J, we provide the additional experimental results.
A. Extended Related Works
A.1. Combinatorial Multi-armed Bandits
The combinatorial multi-armed bandit (CMAB) problem has been extensively studied over the past decade, covering domains such as stochastic CMAB (Gai et al., 2012; Kveton et al., 2015c; Combes et al., 2015; Chen et al., 2016; Wang & Chen, 2017; Merlis & Mannor, 2019; Saha & Gopalan, 2019: 9; Agrawal et al., 2019; Liu et al., 2022; 2024b), adversarial CMAB (György et al., 2007; Uchiya et al., 2010; Cesa-Bianchi Bianchi & Lugosi, 2012; Bubeck et al., 2012; Audibert et al., 2014; Neu, 2015; Han al., 2021), and hybrid
sit--offoot-worlldd settings (Zimmert al., 2019; Ito, 2021; Tsuchiya et al., 2023). Contextual extensions with linear or nonlinear function approximation have also been explored (Qin et al., 2014: Takemura al., 2021; Liu et al., 2023a; Chen et al., 2018 8; Nika et al., 2020: Choi et al., 2024; Hwang et al., 2023; Liu al., 2024b).
Our work falls within the stochastic CMAB with semi-bandit feedback domain, first introduced by Gai et al. (2012), with specific focus on CMAB with probabilistically triggered arms (CMAB-T). Chen et al. (2016) introduced the concept of arm triggering processes for applications like cascading bandits and influence maximization, proposing the CUCB algorithm with a regret bound of O(B, B/y//KKT log T (//min)) regret bound under the 1-norm smoothness condition with coefficient Bi Subsequently, Wang & Chen (2017) refined this result, proposed stronger 1-norm triggering probability modulated
17

---

Offline Learning for Combinatorial Multi-armed Bandits
(TPM) B1 smoothness condition, and employed triggering group analysis to eliminate the 1/Pmin factor from the previous regret bound. More recently, Liu et al. (2022) leveraged the variance- addativve principle to propose the BCUCB-T algorithm, which further reduces the regret's 's dependency on action-size from O(K) to Ollog K) under the new variance and triggering probability modulated (TPVM) condition. While inspired by these works, our study diverges by addressing the offline CMAB setting, where online exploration is unavailable, and the focus is on minimizing the suboptimality gap rather than regret.
Another notable line of work considers CMAB with full bandit feedback (György et al., 2007: Cesa- -iss-Biincch & Lugosi, 2012: Niazadeh et al., 2021; Fourati et al., 2023; Nie al., 2023; Fourati et al., 2024b;a; Sun et al., 2025). In their setting, the feedback only provides aggregate rewards for the entire super arm, often resulting in higher regret (e.g.. O(T2/3)) and requiring fundamentally different oracle designs. In contrast, our setting (CMAB with semi-bandit feedback) assumes semi- bani-bandit feedback, where the learner observes individual arm-level feedback for selected arms (i.c., components of the super arm). This enables more informative learning and allows us to construct accurate base-arm estimators for use in our oracles, leading to an (3T) regret bound. Moreover, prior full-bandit approaches often rely on additional structural assumptions such as submodularity to achieve these bounds. Similarly, our approach leverages smoothness assumptions on the reward function to ensure statistical efficiency in the offline regime.
A.2. Offline Bandit and Reinforcement Learning
Offline reinforcement learning (RL), also known as "batch RL", focuses on learning from pre-collected datasets to make sequential decisions without online exploration. Initially studied in the early 2000s (Ernst et al., 2005; Riedmiller, 2005; Lange al., 2012), offline RL has gained renewed interest in recent years (Levine et al., 2020).
From an empirical standpoint, offline RL has achieved impressive results across diverse domains, including robotics (Singh et al., 2021). healthcare (Liu et al., 2020), recommendation systems (Chen et al., 2023), autonomous driving (Kiran et al., 2020), and large language model fine-tuning and alignment (Casper et al., 2023). Algorithmically, offline RL approaches can be broadly categorized into policy constraint methods (Fujimoto et al., 2018; Kumar et al., 2019), pessimistic value/policy regularization (Haarnoja et al., 2018; Kumar et al., 2020), uncertainty estimation (Agarwal et al., 2019), importance sampling (Jiang& & Li. 2015; Nachum al., 2019), imitation learning (Fujimoto & Gu, 2021; Chen et al., 2019), and model-based methods (Kidambi et al., 2020; Yu et al., 2021).
Theoretically, early offline RL studies relied on strong uniform data coverage assumptions (Szepesvari & Munos, 2005; Chen & Jiang, 2019a; Wang et al., 2019; Xie et al., 2021a). Recent works have relaxed these assumptions to partial coverage for tabular Markov Decision Processes (MDPs) (Rashidinejad et al., 2021; Yin et al., 2021; Shi et al., 2022; Li et al., 2022b), linear MDPs (Jin et al., 2020b; Chang et al., 2021; Bai et al., 2022), and general function approximation settings (Rashidinejad et al., 2022; Zanette et al., 2021; Xie et al., 2021b; Zanette & Wainwright, 2022).
Offline bandit learning has also been explored in multi-armed bandits (MAB) (Rashidinejad al., 2021), contextual MABs (Rashidinejad et al., 2021; Jin et al., 2020b; Li et al., 2022a), and neural contextual bandits (Nguyen-Tang Tang al., b;a),
While our work leverages the pessimism principle and focuses on partial coverage settings, none of the aforementioned offline bandit or RL studies address the combinatorial action space, which is the central focus of our work. Conversely, recent work in the CMAB framework demonstrates that episodic tabular RL can be viewed as a special case of CMAB (Liu et al., 2024b). Building on this connection, our proposed framework can potentially extend certain offline RL problems, offering unified approach to tackle both combinatorial action spaces and offline learning.
A.3. Related Offline Learning Applications.
Cascading bandits, a classical online learning-to- -o-rnnk framework, have been extensively studied in the literature (Kveton et al., 2015a;b; Li et al., 2016; Wang & Chen, 2018; Vial al., 2022; Zhong al., 2021; Liu al., 2022; Wang et al., 2023; 2024). Offline cascading bandits, on the other hand, focus primarily on reducing bias in learning settings (Joachims, 2002; Wang et al., 2018; 2016; Keane& & O'Brien, 2006; Zhang al., 2023). Unlike these prior works, our study tackles the unbiased setting where data coverage is insufficient. Moreover, we are the first to provide theoretically guaranteed solution using a CMAB-based approach.
LLM caching is a memory management technique aimed at mitigating memory footprints and access overhead during training and inference. Previous studies have investigated LLM caching at various levels, including attention-leve (KV- cache) (Pope et al., 2022; Kwon et al., 2023; Sheng et al., 2023; Bang, 2023), query-level (Gim et al., 2023; Zhu et al., 2023).
18

---

Offline Learning for Combinatorial Multi-armed Bandits
and model/APP--evell (Qu et al., 2024; Dai et al., 2024a; Feng et al., 2024). Among these, the closest related work is the LLM cache bandit framework proposed by Zhu et al. (2023). However, their approach is ad hoc, whereas our CMAB-based framework systematically tackles the same problem and achieves improved results in both offline and online settings.
Influence Maximization (IM) was initially formulated as an algorithmic problem by Richardson & Domingos (2002) and has since been studied using greedy approximation algorithms (Kempe et al., 2003b; Chen et al., 2009). The online IM problem has also received significant attention (Wen et al., 2017; Vaswani et al., 2017a; Wu et al., 2019; Vaswani et al., 2017b; 2015; Wang & Chen, 2017). In the offline IM domain, our work aligns closely with the
taterratiioinoo-mmamm--a (OPS) framework (Balkanski et al., 2015; 2016; Chen et al., 2020; 2021), originally proposed by Balkanski et al. (2015). Specifically, our work falls under the subdomain of optimization-fromm wwwesssttuuuuuuannaeeet where samples include detailed diffusion step information (So..., Sv-1) instead of only the final influence spread o (So: G) in the standard OPS. Compared to Chen et al. (2021), which selects the best seed set using empirical means, our approach employs a variance-adaptive pessimistic LCB, improving the suboptimal gap under relaxed assumptions.
(OPSS) (Chen et al., 2020; 2021),
B. More Justification of Studying Offline CMAB
While online bandits are natural choice when online data is readily available and inexpensive, many real-world applications restrict access to only offline data as follows, which motivates the study of offline CMAB.
For instance, consider the cascading bandit model in recommendation systems (Kveton et al., 2015a). Online CMAB learning requires a tight feedback loop where the platform (i.e., the learner) updates its recommendation policy after every user interaction. However, in many practical scenarios, such fine-grained online feedback is unavailable as the platform cannot afford to update at such a high frequency. Instead, data collected in batches (e.g., over a week), logged, and then used update the policy in single offline training phase. This workflow aligns precisely with our offline CMAB setting.
Another motivating scenario involves outsourced system design. For example, if OpenAl or Anthropic outsources the design of an LLM caching system, the consultant (i.e., the learner) typically receives only anonymized user logs. They must learn user behavior and design the system purely based on this private offline dataset and cannot reach out for direct interaction with the users, which fits naturally into the offline CMAB framework.
Moreover, our work on CMAB also mirrors the development trajectory in reinforcement learning (RL). RL began with a focus on online learning (Mnih et al., 2013); then, around 2020, concerns over the cost and availability of online interactions led to growing emphasis offline Rl.-lennnig solely from logged data (Levine al., 2020). More recently, hybrid approaches (Lee et al., 2022) combining offline pretraining with online fine-tuning have emerged. Similarly, after establishing foundational results in online CMAB, we now focus on the offline setting as crucial step toward enabling future hybrid CMAB approaches.
C. Offline Learning for Influence Maximization with Extension to Node-level Feedback
Influence maximization (IM) is the task of selecting a small number of seed nodes in social network maximize the influence spread from these nodes, which has been applied in various important applications such as viral marketing, epidemic control, and political campaigning (Richardson & Domingos, 2002; Kempe et al., 2003b; Chen et al., 2009). IM has been intensively studied over the past two decades under various diffusion models, such as the independent cascade (IC) model (Kempe et al., 2003b), the linear threshold (LT) model (Chen et al., 2010), and the voter model (Narasimhan et al., 2015)], as well as different feedback such as edge-level and nove-level feedback models (Chen et al., 2020). For the edge-level feedback model, IM smoothly fits into our framework by viewing each edge as the base arm, which can obtain the theoretical result similar to our previous two applications. In this section, we consider a more realistic yet challenging setting where we can only obverse the node-level feedback, showing that our framework still applies long as we can construct high probability lower bound (LCB) for each basc arm (edge).
Influence maximization under the independent cascade diffusion model. We consider a weighted digraph G(V,E,) to model the social network, where V is the set of nodes and & is the set of edges, with cardinality V = V and F = [8]. respectively. For each edge (u, v) E E, it is associated with a weight or probability Pue E [0, 1]. We use N(v) = Ni)(w) to denote the in-neighbors of node u E V.
The diffusion model describes how the information propagates, which is detailed as follows. Denote So V as the seed nodes and Sp. C V as the set of active nodes at time steps h 2 1. By default, we let S_1 0. In the IC model,
19

---

Offline Learning for Combinatorial Multi-armed Bandits
at time step h 2 1, for each node & Sn-1. each newly activated node in the last step, u ((c) U (S--I\(S will try to active v independently with probability Puv- This indicates that will become activated with probability 1 N()uus 1),5k 2) Puv). Once activated, will be added into Sn. The propagation ends at step h when S₁. - It is obvious that the propagation process proceeds in at most V V- 1 time steps, so we use (So, Si, Sv-1) to denote the random sequence of the active nodes, which we refer as influence cascade. Let $ = Sy be the final active node set given the seed nodes S.. The influence maximization problem aims to select at most k seed nodes so as to maximize the expected number of active nodes a G) := E [| which we often refer to as the influence spread of So given the graph G. Formally, the IM problem aims to solve S* argmaxsgy (S; G).
Offline dataset and learning from the node-level feedback. We consider the offline learning setting for IM where the underlying graph is unknown. To find the optimal seed set S* we are given pre-collected dataset consisting of influence cascades D (S,,0, ,r,,, St,v-1)i=1 and a probability d. Our goal is to output seed node set S(D, 6), whose influence spread is large as possible with high probability 5.
Similar to (Chen et al., 2021), we assume these influence cascades are generated independently from a seed set distribution Sro ~ ss and given St,o. the cascades are generated according to the IC diffusion process. For each node E V, we use 9, = Pr v E S,,o| to denote the probability that the node v is selected by the experimenter in the seed set St,- We use pG( == Pr [u & St,1] to denote the probability that the node v is not activated in one time step when the graph is G. For any two nodes u, v E V, we use (ū u) == Pr [e & St, E St.o] and pa (o(ol) == Pr [v & St,lu & St,o] to denote the probability that the node is not activated in one time step conditioned on whether the node u is in the seed set S or not, respectively. We also assume Ws is product distribution, i.c., each node u E V is selected as seed node in St,0 independently. Similar to (Chen et al., 2021), we also need an additional Assumption 1.
Assumption (Bounded seed node sampling probability and bounded activation probability). Let E(S*) S E be the set of edges that can be triggered by the optimal seed set S There exist parameters 17 E (0, 1] and 10,1 such that for any (u, v)) E {S*), ), we have qu E [7, 1 -7] and pa (7) 2 1).
Algorithm that constructs variance-adaptive LCB using the node-level feedback. Note that in this setting, we cannot obtain edge-level feedback about which node influences which node in the dataset. It is extension which cannot be directly handled by Algorithm since one cannot directly estimate the edge weight from the node-level feedback. However, as long as we can obtain a high probability LCB for each arm (u, v) E E and replace the line 5 of Algorithm I with this new LCB, we can still follow a similar analysis to bound its suboptimality gap. Our algorithm is presented in Algorithm 3.
Inspired by (Chen et al., 2021), for each node-level feedback data / E [n]. we only use the seed set Si,0 and the active nodes in the first diffusion step 1 to construct the LCB.
Since each node is independently selected in St,0 with probability qu. and we consider only step activation for any node v. the event {u is activated by u) and the event (u is activated by other nodes G [u}} are independent. Thus, we have (T) = (1 (uPav) Paltu] (7) = (1 - quPwe) (Tlū). Rearranging terms, we have:
Pav (1
(T) PG (ū ū)
(13)
qu
Let us omit the graph G in the subscript of pa (6) and (G(()) when the context is clear.
We can observe that Puo is monotonically decreasing when qu or p(T) increases and when p(olu) decreases. Therefore, we separately construct intermediate UCB for qa, p(ū) and LCB for p(ola) and plug into Eq. (13) to construct an overall LCB Pun for each arm Pue in line 7. Based on the LCB for each edge, we construct the LCB graph G and call IM oracle over G. Also note that for each intermediate UCB/LCB, we use variance-adaptive confidence intervals to further reduce the estimation bias.
Theorem 5. Under Assumption suppose the number of data n
392 log( 12nE
Let S be the seed set returned by
Algorithm 3. then it holds with probability at least 1 - 8 that
d2 P ( G): log( 12n
aa (S* - (3:C) < 4
(14)
1.73 n
where dmax the maximum out-degree of the graph G.
20

---

Offline Learning for Combinatorial Multi-armed Bandits
Algorithm 3 CLCB-IM Combinatorial Lower Confidence Bound Algorithm for Influence Maximization with Node-level
Feedback
1: Input: Dataset = {(Sr,, -1 nodes V, edges &, cardinality k. influence maximization solver IM, probability 8.
2: for edge (u, v) E & Calculate counters no,u l(i [n] Stutl. 11,8 Hi E [n]
& S.,.l.ni,a. K8 E [n] u
Sa.0 and é 1
4: Calculate empirical means C. no,u/n, ((T) 11 (() 2) 71,0.0/ 00,.0///.111 /n1,00
5: Calculate variance-adaptive intervals Pa 611 Tu loR 12p2)
log( 12
611 0(1-5(()))(() log 12
p(())
+
log(( 12nE)
6(1 6 =( log( 1 + 9 g 12n
p V
no.ea
n0.
6: Compute intermediate UCB/LCB Qu min au Pu: 1}, min (p(()) + p(o), ((6),,1,((0) ((.()) max (7
p(Tlū),03 0}:
7:
Compute edge-level LCB Pue = min { max {0, (1-
p(nla) p(o1a))
((a)
}}} for (u, E
8: end for
9:
Construct LCB graph G = EV,E.) with edge-level LCB p = (u,o)E
10: Call IM sovler $ k.)
11:
Return: S.
Remark 7 (Discussion). To find out an action S such that ($:G) 2 (a G)) our algorithm requires that Ô V2 which improves the existing result by least a factor of Ö LCB construction and the tight CMAB-T analysis. We also relax the assumption regarding Assumption 1, where we require bounded qu p(ø) only for (u, v) E E(*), since we use LCB Puv. Chen et al. (2021), instead, needs bounded qu. p(ū) for all (u, v) E E as they directly use the empirical mean of Puv.
V
F owing our variance-adaptive
D. Proof for the Upper Bound Result
Proof of Theorem 1. We first show the regret bound under the infinity-norm TPM data coverage condition (Condition 3):
Let (D) be the counter for arm i as defined in line 3 of Algorithm 1, given the dataset D and the failure probability
Let (DD) = (D,(D,6), (D,6)) be the empirical mean defined in line 4 of Algorithm 1.
Let (D, (H2 ... (D, 8)) be the LCB vector defined in line 5 of Algorithm
Let 5(D,5) 6) be the action returned by Algorithm in line 7.
Ds be the data collecting probability that for arm i.e., the probability of observing arm i in each offline data. Let p;
Let 5* {i E [m] p. S > 0} be the arms that can triggered by the optimal action S* and p = min p. Ds be the minimum data collection probability.
We first define the events Earn and Ecounter follows.
log( 2mn
Earm (i,(D) mal
for any i [m]
(15)
(D,
Y1 Ps Ds
8 8lgg m
Egounter
N.(D)
for any i E S*
2
5
(16)
2
p"
When > 8log m p
and under the events Earn and Ecounters we have the following gap decomposition:
or(S": (1) (S(D,6):1
(17)
21

---

Offline Learning for Combinatorial Multi-armed Bandits
ar(S*: (L) or (5": (D,))))
(18)
uncertainily
+ ar (e": 8)) - (); +r (S(D,0): - (S((
oracle
pessinissm gup
(6)
a (r(S": 11) - (5" (e(,
(19)
aBi
Σ
Pi
Damig
(mi ()(D)))
(20)
ic(m]
(d)
log( 2mm
2a B1
Σ
St
(21)
(D)
iE [m(m]
(c)
log( 2mm
I 20B1
Ps
Samii
6 Bana D5
(22)
:E|ml
n P.
log( 2mn Pt 18
5
St Pi
2a
(23)
ic/m]
log(
2mm
C
B, K
(24)
inequality (b) is due to oracle gap < 0 by Eq. (1) as well as pessimism gap < 0 by monotonicity (Condition 1) and Lemma 5, inequality (c) is due to 1-norm TPM smoothness condition (Condition 2), inequality (d) due to Lemma 5, inequality (e) is due to event Ecounter, inequality (f) due to infinity-norm TPM data coverage condition (Condition 3).
where inequality (a) is due to adding and subtracting (S*: ()) and
Next, we show the regret bound under the I-nrom TPM data coverage condition (Condition 4).
When n 2 8 llog and under the events Eam and Ecounters we follow the proof from Eq. (17) to Eq. (23) and proceed as:
ar(S": (1) (S(D, 6):
(25)
=ar(S"; - ar 1
(26)
uncertainty
+ oo (St; ((D, 8)) (); +r (S()))))((0.))) -r (S(D),)));
oracle
pessimism gap
Sa (r(S -r (S 8)))
(27)
SaBı Σ Pi T" (14 - (D, 5))
(28)
+E(m)
log( 2mn
St
< 2aB
Ps
Dan:Ds n. P:
o
(29)
1E/m]
(0)
2mn log(
Pi
St
B0
Pi
Ban Dig
(30)
ic(m]
xm(m)
n Pi
(8)
_ BaBB\
K' K log(
2mn
(31)
T2.
where inequality (a) is due to Cauchy Schwarz inequality, and inequality (b) is due 1-norm TPM data coverage condition
22

---

Offline Learning for Combinatorial Multi-armed Bandits
Condition 4.
The final step is to show event Earm and Ecounter hold with high probability. By Lemma 5 and Lemma 6, event &arm and Econnte both hold with probability at least with 6. By setting 8' = 6/2 concludes the proof.
E. Proof for the Lower Bound Result
Proof of T'hoormm 2. Let A [0, + be a gap to be tuned later and let C% 2 2. We consider k-path problem with
two problem instances Pi and P2, where m/k path's mean vectors are f41 = (2 2 A, O, O,.., 0) E Rm/k and μ22
1
(5 2 + A, 0, 0) E Rm// respectively. For the data collecting distribution, 13s follows p C5 1 C o,....
,,, 0) for
both P1 and P2. We have that the optimal action Si (1, ..., k) for Pı and S (k 1, 2, .... 2k) for P2.
For the triggering probability, p. Pi.S" = for = I,... k and otherwise and p Pa.S" = 1 for = k + 1,... 2k and 0 otherwise.
We then show that both problem instances Pı; P2 satisfy Condition 3. For Pi and P2, we have
P
P
max
[m] P1
1.
I
C
(32)
C
Pj
p
1
(a)
max
mm] P;
Pz.Ds
C
Cx
(33)
where inequality (a) is due to C 2 2.
Let us define suboptimality gap of any action as:
(34)
where St (44) is the optimal super arm under μa.
For any action S E S, we have
g(5: + u2) 2 RA
(35)
Recall that A(D) the action returned by algorithm A and we use the Le Cam's method (Le Cam, 2012):
inf sup
ED Ds) ir(": r(A(D):
(36)
A
(Dim.Ds)Ekppthmmm...C
2
inf sup
Ed (D()(A(D):
(37)
pEpi:u2
(a)
1
2 inf ( [1)1
(38)
2
(0) kA
exp (-KT. (P (Pp@ m. ))))
(39)
4
where inequality (a) is due to max b 2 (a + 2)/ and inequality (b) is due to the following derivation:
Let event & = {((A(()) p1) < A On E it holds that g(A(D): p1) 2
kA
and on E it holds that ((A(D);H2) 2
2
kA - (g(((D); (1) > Ad 2. Thus, we have:
inf (Epony (A(A))) [1)) + Epery (o(A(D);
(40)
A
(Ppon (-E) + P. Ppop:
(41)
(4) AA
exp (-KL (P p X mi Pro
(42)
8
23

---

Offline Learning for Combinatorial Multi-armed Bandits
(b)
k
Co
min
4' V
(43)
8e
20n
(44)
XKL(F pL
PP2))
where inequality (a) is due to Lemma 8 and inequality (b) comes from: KL (P (PP@.. |P (PP))) n(2A)²
(1/4142277 S 20nA2//C, Here we use the fact that each arm the path are fully dependent Bernoulli random variables,
KT (Bern(p)) (err(())))))((()))
(p-g)² and that A E [0, a)- By taking A min 4(1-g)
Cis
concludes Theorem 2.
20m
F. Proof for the Application of Offline Learning for Cascading Bandits
Proof of Corollary For the cascading bandit application, need prove how it satisfies the monotonicity condition (Condition 1), the 1-norm TPM condition (Condition 2), the 1-norm data coverage condition (Condition 4), and then settle down the corresponding smoothness factor B,, data coverage coefficient C1, action size K
Algorithm 4 CLCB- Combinatorial Lower Confidence Bound Algorithm for Cascading Bandits
1: Input: Dataset "D {(Sts To, (x..)sen))) cardinality k 0, solver Top- k, probability 6.
2: for arm i [m] do
3: Calculate counter N; E Et)
4: Calculate empirical mean i4; Dn )(Een) Xes.
N.
5: Calculate LCB = jas V
Toox( Amm
2N:
6: end for
7: Call oracle $ = Top k(H1, ... pm).
8: Return: $.
For the monotonicity condition (Condition 1), the 1-norm TPM condition (Condition 2), Lemma in Wang & Chen (2017)
yields B1 = 1.
For the 1-norm data coverage condition (Condition 4), recall that we assume the arm means are in descending order #1 2 p2 ... 2 pm therefore we have S* k), and
I1 13), if k.
Pi Pani8"
(45)
0. clse if k 1.
As for pi DanDs we have
Pi
Dan De > Σ (1,(1-1)-1 413-1
(46)
1=1
where di the probability that arm is sampled the j-th position of the random ranked list sampled by the experimenter. By math calculation, we have
I (1)1-)))) 14))
Σ Pi
C1
(47)
Ds
ΣØ=1 Uzg
m1)
8E(m]
and
K" Σ
P
Damn S*
1=k
(48)
(e(m)
KE(k)
24

---

Offline Learning for Combinatorial Multi-armed Bandits
(1- Σ 96 1, K k into our general result Theorem 1 yields the general result of Plugging B 1, C₁ Ei
Corollary 1.
When we assume that the data collecting distribution Dss follows the uniform distribution from all possible ordered lists
S = {[a1,... 0&) E [m]] for all i E [m], and a, # aj for all i o j}. Then we have qu = m. and using Eq. (46) we have
m1)3-1
1 (1 14))
P.
Ds
(49)
m
m
We use Eq. (47) and Eq. (45) to bound
Ps St
P S
Ci
(50)
Ds
1- 11
iE [m]
Ps
iE(ml
Pr m
14 )
(51)
1- (1-111
(41 m7
(1 (1-14))
(52)
1-(1-
M1 772
(53)
Pk
Plugging B1 1, pn K k into our general result Theorem concludes Corollary 1.
G. Algorithm and Proof for the LLM Cache Application
G.1. Offline Learning for the LLM Cache under the Standard CMAB-T View
Algorithm 5 CCCBBLLM--C Combinatorial Lower Confidence Bound Algorithm for LLM Cache
1: Input: Dataset = ((Me, (t, () queries Q, solver Top-k, probability 6.
2: for arm E do
qe and qe & Mi): 4: Calculate empirical probability p(g)= N N(4) / E(g) Ene(n] TTq a: and qi M.)oc/No(a):
3: Calculate counter N(q)) Σ Ifqq } and Ne(g) = " Ii= I{q
5: Calculate UCB of the cost ē(q) = E(q)) + v
logí Aim
and UCB of the arrival probability p(4) = pp4)) +
log(
2N.(g)
2n
6: end for
7: Call M = Top-ooo--occ
8: Return: M
For this LLM cache problem, we first show the corresponding base arms, super arm, and triggering probability. Then we prove this problem satisfies the 1-norm TPM smoothness condition (Condition 2) and 1-norm TPM data coverage condition (Condition 4). Finally, we give the upper bound result by using Theorem 1.
From the CMAB-T point view, we have 2m base arms: the first m arms correspond the unknown costs c(g) E [0. 1] for q Q, and the last m arms corresponds the arrival probability p(g) E [0, 1] for q E Q.
Let us denote EE and p (p(4))EE for convenience.
Recall that we treat the queries S E S outside the cache M as the super arm, where S = -Q- M k).
We can write the expected cost for each super arm S E S as c(S:c,p) p) = Eyes p(g)c(q).
Then we know that argmax c(S: c, C,P), which contains the top h queries regarding p(g)c(q).
25

---

Offline Learning for Combinatorial Multi-armed Bandits
For the triggering probability, have that, for any S E S, the triggering probability for unknown costs p. p(q) for q E S and 0 otherwise. The triggering probability for unknown arrival probability pe. for all g E Q
Now we can prove that this problem satisfies the 1-norm TPM smoothness condition (Condition with B1 That for any S E S, any p. p.p's c, d' [0. 1|mh have
-
p\) - p) ((SC.) ds;c
(54)
S ccS:,, c(S:d.)) + ((S: c(:d.p))
(55)
Σ (()(((1)) p())
Ep(g)e(a) - (1)
(56)
RES
HES
Σ p(g) lc(g) c( + Σ c'(2) (p()) -p' p'(1
(57)
Σ p(g) (dq) d'(g) +
Σ
[p(g)
p')
(58)
QES
QEQ
Next, we prove that this problem satisfies the 1-norm TPM data coverage condition (Condition 3).
Let v())= = PrM-Ds lq E M] be the probability that is not sampled in the experimenter's cache M ~ Dzg. Then the data collecting probability for unknown costs Pq.c pa.... = (q)) and P. We can prove that the LLM cache satisfies Condition by
Ds = 1 for unknown arrival probability, for g E Q
Σ
P Pg.c
+
D'm.S' P.p
Σ
pl ( S*) p(g)v(g)
+1) - Σ
+ = C₁.
(59)
Ds Pq.c
Da
v(g)
QEQ
Pq.
DEE
QES-
Finally, we have K = EyEO Bommss
+
Pq
Dem.s))
= E p(q)Ifq E + < 11+m m.
Plugging into Theorem 1 with Bi 1, Ci Enes 1 bound.
v()) m, K + m, have the following suboptimality upper
Lemma (Standard Upper Bound for LLM Cache), For LLM cache bandit with a dataset 'D of n. data samples, let M be 8 Blog(+)
the optimal cache and suppose n 2 minGee-M- pla)ula)' where v(g) is the probability that query q not included in each offline sampled cache. Let M be the cache returned by algorithm Algorithum 5, then holds with probability at least 1 that
SubOpt(MM,,,c.p) = c(M':c,p) c (M.
(60)
(m (m++1)(nge0-
1 vlg)
+ m log( (Bra
s 2
(61)
if the experimenter samples empty cache in each round as in (Zhu et al., 2023) so that v(g) = 1, it holds that Cf S 2m and
SubOpt(MM; u) = c(M' p, c) (M)
(62)
2m(m + 1) log( Gran
S 2
(63)
G.2. Improved Offfine Learning for the LLM Cache by Leveraging the Full-feedback Property and the Vector-valued Concentration Inequality
Theorem (Improved Upper Bound for L.LM Cache). For L.LM cache bandit with dataset of n data samples, let M 8log(t)
be the optimal cache and suppose min.eo-M M p(g)a(a]' where v(g) is the probability that query q is not included in
26

---

Offline Learning for Combinatorial Multi-armed Bandits
each offline sampled cache. Let M be the cache returned by algorithm Algorithm 5, then it holds with probability least
1 6 that
SubOpt 1)) = c(MM: - c (M:P.c)
(64)
2 E v(a) log( 6mn
2m log( 2
< 2
+ V
(65)
n
the experimenter samples empty cache each round as (Zhu al., 2023) so that vla) holds that C S and
SubOpt(M;;, u) = c(M' p. (M:D.c)
(66)
2m log( 6mn
s <
(67)
n
In this section, we use an improved CMAB-T view by clustering m arrival probabilities p(4) as a vector-valued arm, which fully observed in each data sample (observing y means observing one hot vector Eg E {0, 1)mh with at the q-th entry and elsewhere).
Specifically, have 1 base arms: the first arms correspond to the unknown costs c(q) for g Q, and the last (vector-valued) arm corresponds to the arrival probability vector (p(4))EEO.
Let us denote (c and p (P( for convenience.
For the triggering probability, for any action S, we only consider unknown costs PRea = p(4) for g E S and 0 otherwise.
For the 1-norm TPM smoothness condition (Condition 2), directly following Eq. (58), we have that for any S E S, any p.P. c.p' e 10m
((S:c..))c($;c.pp))) -lgg)lda))- - d(())
Σ lp(g) - p'(1)1= Σ p(1)) d(()) + 1p p'll, (68) TE
9ES
9ES
Recall that the empirical arrival probability vector is P and the UCB of the cost is č.
Recall that M = arrgmax M| Eqem (()) given by line 7 in Algorithm 2, which from the CMAB-T view, corresponds the super arm Š Q M argminses c(S c, p).
Since treat p single vector-valued base and consider the cost function (and minimizing the cost) instead of the reward function (and maximizing the reward), need slight adaptation of the proof of Eq. (17) follows:
Recall that the dataset D = {(M,, -=
Recall that Ne(g) = Σm= I(q- = and qt & M,} is the number of times that g is not in cache Mr Recall that v(g) is the probability that query q included each offline sampled cache M, Let p" Q- p()) be the minimum data collecting probability. First, we need new concentration event for the vector-valued Earp and two previous events as follows.
2m log 2 n
Eary
1p pll
(69)
log 2mn
Eam
(Ō(g)
c())l
for any g Q
(70)
(N
27

---

Offline Learning for Combinatorial Multi-armed Bandits
n1 Bom
8 log
Equanter Ne(1)= 2
for any E Q - -M n 2
(71)
2
Following the derivation of Eq. (17), we have:
c(S",c)
(72)
(a) c(() +
- -c(" c(, + (5:c.) (((.cc))) - (5;ee,))
(73)
uncertainty
oracle gap
pessimism gap
2 - (S:.p) - c (5:c.p)
(74)
(c)
1 (( ( (52.p) - (3:2.0)
(75)
3
1 - pll
(76)
p(1) ((()) d1) + 1 pll
(77)
9ES*
IAS Σ ((4) c(2)) +( 2/
2m log( !3
(78)
OES*
where inequality (a) is due adding and subtracting c p) and (S:c. inequality (b) is due to oracle gap S 0 by line 7 of Algorithm 2, inequality (c) is due to the monotonicity, inequality (d) due to Eq. (58), inequality (e) is also due to Eq. (58), inequality (f) due to the event Eare-
Then for the first term of Eq. (78), we follow Eq. (28) Eq. (31):
2K - Cj log(
2mn B
2m log )
Σ p()))((())) - c(g)] S B0BB1 -
21
(79)
2K Cj log( 1
2man 0
2aBi
(80)
2Σ -E v(g)
2mn log
$ 21
5
(81)
71
where the last inequality is plugging in B, a 1, K*
En Panis
Eneeplo)llt S*3 s 1, and
C1 = EyEs v(g)
Putting together Eq. (81) and Eq. (78), we have
2 E M v(g)
log(
2mn
2m log (#)
(S:c.p)
2
+ -1
(82)
n
72
Finally, by Lemma 5, Lemma 6, and Lemma 7 we can show that event Earn Ecounter. Eare all hold with probability at least
with Setting 8' 35 concludes the theorem.
G.3. Online learning for LLM Cache
For the online setting, we consider a T-round online learning game between the environment and the learner. In each round t, there will a query 4: coming to the system. Our goal to select a cache M, (or equivalently the complement set Q M, in each round [TT] as minimize the regret:
Reg(T)= = Σ -
(83)
28

---

Offline Learning for Combinatorial Multi-armed Bandits
Similar to Zhu al. (2023), consider the streaming setting where the cache of size l is the only space we can save the query's response. That is, after receive query q each round, if the cache misses the current cache Mc, then we can choose update the cache MM by adding the current query and response to the cache, and replacing the one of the existing cached items if the cache M₁ is full. This means that the feasible set Q++1 needs to be subset of the Me U qt, for E [T'.
For this setting, we propose the CUCB-LLM-S algorithm (Algorithm 6).
Algorithm 6 CUCB-LLAM S: Combinatorial Upper Confidence Bound Algorithm for Online Streaming LLM Cache
1: Input: Queries 2, cache size k, probability 6.
2: Initialize: Counter. empirical mean, LCB for unknown costs No,0(4) = 0, () = 0, (o = 0. Empirical mean for arrival probability (o) = 0, for all q E Q. Initial cache M1 = 0.
3: for = 2..,.., do
4: User arrives with query gr-
5: if' q: Mr then
6: Incur cost C, but does not receive any feedback.
Update (e( (t- 1)- 1(m)+1 I and (et) (t (--)) 1())+0 for q + qc-
7:
8: Keep No, (q) (2), (q) = ( for oorge E Q.
9: Keep Me+1 .Mc.
10:
else
11:
The Cache misses and the system pay random cost Ct with mean e(g:) to compute the response of 4:-
Update (q)) (t- 1)rf, +( and pe(qt) (t- 1(1)+0 for q * qc-
2 Update (9)) Ne,1-1 19)) (o(2)) No.1 (a))) & ((a))
13:
No.-1(91)-1
14:
Keep (T)(4)) = Ne), (4) = (4) for + 96-
Compute Ca (4) = max ((((g) - 2Nc..()) 0) for all EQ
1og(2m(T3)
15:
16:
[M]] < k then
17:
Add d:'s s response into M₁ so that Me+1 = MM
else if mingeM, (r())c((q) S pe()))c(q))) then
19:
Replace mi response with qi ss, i.e, Me+1 MM Itmii + qt, where ut argmin nEM, (c)))
20:
else
21:
Keep M1+1 M,
22:
end if
23:
end if
24:
end for
The key difference from the traditional CUCB algorithm, where any super arm S E S can be selected, is that the feasible future cache M in round + 1 is restricted to Mr+1 S M,, Ug. where M, is the current cache and the query that comes the system. This means that we cannot directly utilize the top-k oracle as in line of Algorithm 2 and other online CMAB-T works (Wang & Chen, 2017: Liu al., 2023b) due to the restricted feasible action set. To tackle this challenge, design new streaming procedure (lines 16-22), which leverages the previous cache M, and newly coming Φr to get the top-k queries regarding Pe (g)
We can prove the following lemma:
Lemma 2 (Streaming procedure yields the global top-k queries). Let Me be the cache selected by Algorithm in each round, then we have M. = arggaaxMg@.MM EyEm (4)
Proof. We prove this lemma by induction.
Base case when
Since co(g) (o(g) = 0 for any a E Q, we have Mi wngnax..ce.MMgaaa 0.
For t 2 2:
Suppose M₁ = wngmaxMMqe.aa EGEM Pi- (19)))119)))))))
Then we prove that M411 = argmax EyEm De (g) as follows:
29

---

Offline Learning for Combinatorial Multi-armed Bandits
Case I (line 5): q. M₁, then (g) - (e- cc-((1))) remain unchanged for y E 2. For the arrival probability, de( (
increased, and (e) = (t-1)))e-119) are scaled with an equal ratio of t-1 for * qt- Therefore, the relative order of queries 9 E Q - qe remain unchanged regarding (t-1(9)(--(()) and pe (g))) Moreover,
S (c(
increased while other queries are decreased, so qt remains in the top-|Me| queries. Thus, Mr+1 Mr remains the top-|MMs| queries.
Case 2 (line 16): qe & Mr and [M]] k, then we know that all the queries q (M, + q)) never arrives, and (g O. 2 (e(1)ca(a) = 0 for any q & (Mz + ge). and Mr + d: are top-|M + 1| queries.
Therefore,
Case 3 (line 18): If q: $ Mr and |Mel = k, then (x(g) ct- (4) remain unchanged for E Q - and (x(2)
(t-1))b-14)) scaled with an equal ratio of - for q * 9t, the relative order of queries g Q qe remain unchanged regarding ( (4) and (g) The only changed query is the Qt, so we only need to replace the minimum
query ft.min = argmingee., (g) with qu. if mi.gm min) S pe(4 cc (gt), which is exactly the line 19, This guarantees that M Me+1 are top-k queries regarding Pe (())))())) concluding our induction.
Now we go back to the CMAB-T view by using St = 2 - -Mr, and by the above Lemma 2, we have S. argminsç@+11124 P (t-1(1))t-14))
Then we have the following theorem.
Theorem 7. For the online streaming LLM cache problem, the regret of Algorithm 6 upper bounded by O (v mT (mT log( ( with probability at least 1 5.
Proof. We also define two high-probability events:
2m log( 2T
Eary =
1p: - pp11 S
for any t E [T]
(84)
log( 2m122
Earn ==
|cr(a) - -c(a) S
for any g E 2 [T]
(85)
2Nc..
Now we can have the following regret decomposition under Eary and Ear::
Reg(1) (T)
E
(((S:c.))c(($')
(86)
E
((S(ic,))- c
uncertainty gap
+ c (Sri 11
Cr- pt + (..," c - c(p)
(87)
oracle
optimisticc
c (
(88)
E
- -
(89)
2m log 2T
E
c(S..c,)) -(S.cc.-)- +
(90)
S
2m log( 22 )
Σ p(g) (g) c(g)) + +
E
(91)
g.
30

---

Offline Learning for Combinatorial Multi-armed Bandits
T
log 2
2mlog(
2T 5
E
Σ 2p(1)
+ +// 2N 2N, 2N),
(92)
1=1
gES,
2mT log(
27
<B
p(o)
B Ne.--19)
+ +VV 2mT 2mTlog(
(93)
8
qESt
(0)
2MT
27
- 1 2mK K Tlog(
)+ 2m + 4/ 2m log
(94)
2 / 2mT log(
2mT + 2m
(95)
where incquality (a) is due to adding and subtracting terms, inequality (b) is due to oracle gap & by S. argminsgo (11 EgEs (1-1(9)0-1(9) (indicated by Lemma 2), inequality (c) due to the monotonicity, inequality (d) is due to Eq. (58) and event Earv, inequality (e) is also due Eq. (58), inequality (f) is due to the event Earms and
inequality (g) is by the same derivation of Appendix C.I starting from inequality (50) in Liu et al. (2023a) by recognizing Ps P. p(g). Ft, (--1 14 elg). inequality (f) is due to K Ene P Ene p(q) E S*) s 1.
Letting 6 = 1/T and considering the failure of the events Earv, Earm that produces (11) regret concludes the theorem.
H. Proof for the Influence Maximization Application under the Node-level feedback
Proof for Theorem 4. Recall that the underlying graph is G(V,E.p) and our offline dataset is D (15,,,,S,,1--. -1.v-
For each node-level feedback data / E [n]. recall that we only use the seed set S.n and the active nodes in the first diffusion step 1t to construct the LCB.
We use qe = Pr [u E St,u] to denote the probability that the node e is selected by the experimenter in the seed set Si.p-
We use p(0) = Pr [u & St,]] to denote the probability that the node is not activated one time step.
We use u() Pr [v & S tu St,o] and p(olū)= Pr [u St, lu & Seool to denote the probability that the node is not activated in one time step conditioned whether the node u is in the seed set St,0 not, respectively.
Recall that we use the following notations to denote the set of counters, which are helpful in constructing the unbiased estimator and the high probability confidence interval of the above probabilities qe, p(ū) and p(ūlū):
no.a = {t E [n] u S,,o3l.
(96)
No.a (t [m] u S,,)].
(97)
71,6 {1 [x] S,13),
(98)
110,0 (t [n]: :l:uu $ St, and & St,13l
(99)
Recall that for any v. E V and given probability 8, we construct the UCB Zu. (()), and LCB p(ū(ū) as follows.
Tu min + Pu: 1),
(100)
p(ō) min p()), 1}.
(101)
p Tt)
p(
(102)
where the unbiased estimators are:
TN = no,-/ n,
(103)
((0) n1, n,
(104)
p ()) n,1, no0
(105)
and the variance-adaptive confidence intervals are:
6(1 qu Tu log())
9log(1))
Pu
(106)
31

---

Offline Learning for Combinatorial Multi-armed Bandits
p(6) 6(1 p(o))p(U) log(
9 log(())
(107)
n
61 (o)a)) (( log())
9 log( !)
(
(108)
70,a
Ro,a
Based on the above unbiased estimators and confidence intervals, we define the following events to bound the difference between the true parameter and their UCB/L.CBs:
qu + Av3/ qu qu) log(
log(t)
(u)m
9u S Tu I min
+28
(109)
n
n
p())(1 p(t)) log( +
log( ()
Earm,((0)
p(ū) S ((0) & min p(0) + Av3
28
(110)
n
n
p(ū (1 p(ū 2)) log(3) }
log(?)
Earm,3(ū, 0)
max p()]u) 4v3/
28
0
S p(0|u) s p()[a)
(111)
no,a
no,a
10,5 2 n(1 qu)
8 log d 12 2
Ecounter =
(112)
log 8
Eomp,1 (0) ==
p(0) S 2p(r)
(113)
p(ū)
log p
E 0) p(olū) 2 p(0la\/2
no.
2
(114)
ū)
Recall that the relationship between Pue and qus pT)) and p(ū)u) is:
p(0)
Puv
Gn
1
p(ūlū)
(115)
Then we construct the LCB Puu based on the above intermediate UCB Tns ((J), and LCB p(olu):
{0, 1 ((0) p()lu)
Puo min 1, max
(116)
Qu
(1) It is obvious that Pu,y is lower bound of Puvs i.., Pu.v I Puvs since qu I qu. (() S p(T))) < p(olū) under event Earm, (u), 2 Earm,3(ū, t).
(2) Our next key step is to show that the difference between Pu.. and Pau is very small and decreases as the number of data samples n increases:
Fix any two nodes u, v, we define two intermediate LCBs for Puo where only one parameter changes at a time:
p(ō)
Plav
1
(117)
4n
p())
P2,00
1
p(ū|ū)
(118)
392 log! }) 1
Suppose 7 S 9n S (.)(() 2 7,, and
32

---

Offline Learning for Combinatorial Multi-armed Bandits
We bound each term under event Earm, (u), Earm.2 Earm,3 0) by:
p(ū)
(1 p(T)
Puv
Pi,u0
(119)
p 21
9u
p( a))
qu
qu
p(ū)
(120)
qu
pl T U
(a)
Ju
Puv
(121)
qu
(6)
4v3
log(
28 (
Puv
(122)
qu
Qui log( #1
8/3v
Puv
(123)
qu
log( nifa
Pun
(124)
log(?)
8/3
Puus
(125)
- n
where equality (a) is due to Eq. (115), inequality (b) is due to the event Eurm, inequality (c) is due to 28 log(
4v3, 2a log( when
392 (x)
49
log(#),
inequality (d) is due to gu 2 7
17"
qu
1
((ū)
1
p(0) ( ④
P2, 2,000
(126)
4u
( ④)
4u
1
((6) P()
(127)
4n
p( ū)
(
1
p(D) p(U)
(128)
p( T 77)
p(0) log t)
28 log(?)
(6)
1 14v3y
IA
n
(129)
p(u
p(0) logl
(130)
((olu)
(4) 8/3
log( +
(131)
7
((ū) n
8/3 (e)
(og(
(132)
7
v) n
where inequality (a) is due qt 2 qu 2 7, inequality (b) is due to the event ( inequality (c) is due to 28 log(
n
4v33/ p(0) p()) log(?) when >
392 log(
49 log(t) p(D)
inequality (d) is due to p(0) S (()()) inequality (e) is due to p( 2 n
7.7
Before we bound P2,uv Puu. we first show that p(vlu) 2 p((())) > 0 for any (u, v) E E. That is:
(0) p(u]))
p(o log())
28 log !)
p(jaa)
4/3//
(133)
no.a
33

---

Offline Learning for Combinatorial Multi-armed Bandits
p log(
p(o
8V3
(134)
p() 0
(135)
where inequality (a) is due to event Earm, a (ū, 8), inequality (b) is due to 4/3v p(ola) log
28 (8log(
when Ro,a
11.00
1o..0
log(H) 3 p(ulaj' which is guaranteed when n
98 (8R((())
2
under the event Ecounter (u) and lu 2 7 (i.e., 110,a 2
2),
inequality
3777
(c) is due to 4v3 p(aje) log(
no.5 1 p(ø 1))
when na,a >
196 log( ( which guaranteed when n 2 p(faa)
392 log( ( under the event
2
n77
Ecounter (u) and qu 2 2 (i.e., nA,,
).).
When min max (0, 4u (1
Fl0)
}}}
have
((0)))
1 (1
p())
11
P2,0
min
1, max
0,
Uu
p
S O.
(136)
When min {L max {0. 5m
(1
F(o)
}}
have
(()
1
(())
22 min
1. max
0,
(137)
qu
((0)
= P2,00
max
0,
(138)
qu
p
p(u)
S
P2,00
(139)
Qu
p(olu) (
1
((ū)
1
((6))
(140)
4u
p ④
p
p(0)
((((()
pl 1
(141)
4u
p ()p((
p(0)
4v3
p(" ()) logt
28 log ! na.a
no.4
(142)
Tn
p( ū p i
(6) p(0)
8/3
log( +
(143)
Ju
2 T 7)pp
IN3
((0)
8/3
p(F) a) log( na.5
(144)
RaP(T/Z)
1
(
(()) + 4/3
p(0) log(?) (
+ 28 log(3)
8/3///
p (a) logt )
(145)
(up(TTa)
3 i
(0) p()) + 8/3
p(D) log(t)
8/3
p(s (l) log(() )
no.a 2
(146)
(..((()))
34

---

Offline Learning for Combinatorial Multi-armed Bandits
2p(T)
8v3v
p(o log(
no.a
(147)
(.P(()))
2P(D)2)
32v3 p(()
log(?)
(148)
4u p(ū|ū)
p (6)
/
log(t)
(149)
Qu
p()) no,,
32/6
log(E)
(150)
Qu
r)
qu)
(8)
log(t)
32v6
(151)
17 703 n
where incquality (a) is due to event Earm,3 (u, 8), incquality (b) is due to 4/3v p[c lox }
28 long + when no,a
11.00
19 log(t) which is guaranteed when n 98 log( under the event Ecounter (u) and qu 2 7 (i.e., no,a 2 7 inequality
3 p(nja))
37.77
(c) is due to Eq. (135), inequality (d) is due to the event Earm.2(0), (T), inequality (c) is due to 3/3 p()) logt
28 log(
when > 49 1))()) inequality (f) is due to p(o) 2 8v3/ (()) (og(;) when 2 102()) 1), inequality (g) is due to
p(t) 2 p(olu), inequality (h) is due the event Ecounter (u), inequality (i) due to qu 2 qu 7, qu 2 7
Combining Eq. (136) and Eq. (151), we have
log( +
P2, Puo I 32
(152)
17 7-733
Combining Eq. (125), Eq. (132), Eq. (152), the difference then can be bounded by:
Puv
Puo
Pur
Pl,av + Pl.ev P2,uv + 12,u0 Puv
(153)
log(t)
log(t)
log( (t)
I 8/3/
n.m
Pav
+ 8/3
17 7,22.
+ +32/6
17 7,733
(154)
log(3)
48V6
(155)
17 77333
Combining the above inequality with Eq. (20) yields:
G) - (S(D..0))
(156)
aBBi Σ
Dun
St
(Pur Pu.w)
(157)
(M.DEE
(
log(t)
$ 48V66BB
Σ
P
SunrS
(158)
73,,. n (u,D)E
(c)
log(?)
48VbaV
V.
17 n33
Pau
Sa
(159)
(u,v)E
(d)
log(H)
48 aV.
V
n.73. d (S G)
(160)
35

---

Offline Learning for Combinatorial Multi-armed Bandits
where inequality (a) is due the same derivation of Eq. (20), inequality (b) due Eq. (155), inequality (c) is due B1 & V by Lemma 2 of (Wang & Chen, 2017). For the last inequality (d), since G)) = Luev Py where pi is the probability node u is triggered by the optimal action S* and Pu,, dSax0(S"; G), where dmax is the maximum out-degree.
5" Pu. we have (in,)e Purm.S" dmax Enev
Finally, we can set 8' 5 1 so that events Earm,1 (t)m, Earm, (ū, B), Ecounter (u), Eemp, E 8) for any (u,v) v) E S* hold with probability at least 8', by Lemma and taking union bound over all these events and (u, v) E E.
Auxiliary Lemmas
Lemma 3 (Hoelfding's inequality). Let X1,..,,,, E [0, 1] be independent and identically distributed random variables with common mean Let = =>i=1 X, Then, for any a 2 0,
Pr[|X - npp 2 a) v 2e 20 /n
(161)
Lemma (Multiplicative Chernoff bound). Let X1,X2, Xn be independent random variables in {0,1) with Pr [r[X, = 1] = Ps. Let X Ei= X2 and μ Ei= Ps. Then, for < a 1,
Pr[X 2 (1+ a)n| S E -
(162)
and
Pr[X S (1--a) a)p{ S e p2
(163)
Lemma 5 (Concentration the base arm). Recall that the event Earn = {
(R((D) - 14 S
log( 2mm 2N.(D) for any E [m]
Then holds that Earm) 2 1 with respect the randomness D..
D. And under Earm we have
log( 2mn
log( (2mm 6
P4 2/
8 <A((D) -V
(D, p4
(164)
(D)
for all [m]]
Proof.
Pr(-Eam) Pr 3i E [m]. (Dx Hil 2 log 2mn
(165)
(D)
log( 2mm
Σ Pr (D:(D) - mil [m(m]
(166)
2N:
log( (N)
Er N = j)(A(()) pil [l(m) jE[n
(167)
Since S, are sampled from i.i.d. distribution Ds. X,,,, X1, are i.i.d. random variables fixing and N₂(D) = Then we use Lemma 3 to obtain:
Pr N.(D)= = (.) -n12
log( 2mm 5 2N.(D)
2e (D)
2N
2mm
<
8
(168)
mn
Combining Eq. (167) gives Pr(Eum! 2116. 6.
And under Eum. (D)
Ing( 2mm
$ 44 S (D) +
lng( and rearranging terms gives Eq. (164).
(N,
2N,(D)
36

---

Offline Learning for Combinatorial Multi-armed Bandits
Lemma
(Concentration of the base
arm
counter). Recall that the event Ecounter
(i(D) 2 P.P. Ds
for any E [m]]
2
Blgg +
Then it holds that Pr[Eaml 2 - 8 with respect to the ran-
2
domness of
Proof.
nt. D
m log
Pr( Epwunter
= Pr
E N:())
2
n1 2
B
(169)
2
p
72 Ds
log
m 8
Σ Pr (D)
2
n1 2
(170)
2
sE|m]
on Ps 18
rp,
(171)
3Emm)
8 log mo Dost
Pan Pi P.
(172)
ie(m]
8,
(173)
where inequality (a) is due to the union bound over i [m]. inequality (b) is due to Lemma 4 by setting a 1/2 with the random (D) being the summation of n i...d. Bernoulli random variables with mean p, Pam.Ds inequality (c) due to 8 log log Samingg
for any i S
p
Lemma 7 (Concentration of the vector-valued arrival probability). Recall that the event Eorv 11i pll S
2m log #
holds that Pr[Ear] 2 1
The following lemma is extracted from Theorem 14.2 Lattimore Szepesvárí (2020).
Lemma (Hardness of testing). Let P and Q be probability measures on the same measurable space (2, and let A E F be an arbitrary event. Then,
P(A)+Q(A9) cxp(-KT(PP.))
where A = =Q' is the complement of A.
Lemma (Variance-adaptiie concentration of the UCBs, LCBs, and counters in the influence maximization application). holds that Pr(Earm.1(u)) 2 26, Pr(Earm,21 (8)) 2 - 26, Pr(form,a 8)} 2 1 -2nô, Pr(Eeounter (u)} 2
Pr Pr(Eemp,1 (T)) 2 8. ( 5)} 2 where
qu(1 qu log(3) + 28
log(:)
Earm, (1) =
S Tu S min
Iu + +/3/
(174)
n
p(t) S 50(1)= < min p(t) (p(e) + +433
p(0)(1 p(u)) log(1) 1
log(1)
Earm,2 ==
28
(175)
p(vla)(1
p( ū)) log(?)
log(t)
Earm,y(ū, D) =
max p(ū(ū)) 4V3
28
.
s p(ōlu)
s p(Tpa)
(176)
Ro.a
no.5
n11 - qu)
8 log 8
Ecounter (1) = no,5 >
>
(177)
1 qu
37

---

Offline Learning for Combinatorial Multi-armed Bandits
8 Blgg3 8 p(o)
Ecmp, (8) ((0)= 2p(d)
n 2
(178)
log p(J/T)
Eemp,2(ū, (ū, 0) = p(öla) 2 p()lu)/2
no,u 2
(179)
Proof. For Pr(Earm, (4)) 2 1 11-22 26, Pr(Earm,22 2 (0)} 2 1 - 28 they are extracted from Lemma 8 from Liu et al. (2022)
without taking union bound on t, u, as in Liu et al. (2022). For Pr[Earm,3(0 f)} 2 1 2nd, it is extracted from Lemma
8 from Liu et al. (2022) by only taking union bound on no,a. For Pr (r(Ecounte(()) (u)} 2 1 - 5, Pr(Eemp.1(T) (7) 2 1 5, Pr(Eemp,2 0)} 2 1 - 6, they follow the proof of Lemma 6 without taking union bound on i E [m].
J. Detailed Experiments
In this section, we present experiments assess the performance of our proposed algorithms using both synthetic and real-world datasets. Each experiment was conducted over 20 independent trials to ensure reliability, All tests were performed on macOS system equipped with Apple M3 Pro processor and 18 GB of RAM.
J.1. Offline Learning for Cascading Bandits
We evaluate our algorithm (Algorithm 4) in the cascading bandit scenario by comparing it against the following bascline methods: 1. CUCB-Ofiline (Chen et al., 2016), an offline variant of the non-parametric CUCB algorithm, adapted for our setting. We refer to this modified version as CUCB-Offine. 2. EMP (Liu et al., 2021), which always selects the action based on the empirical mean of rewards.
Synthetic Dataset. We conduct experiments on cascading bandits for the online learning-to-rant application described in Section 4.1, where the objective is to select K 5 items from set of m 100 to maximize the reward (Dai et al., 2025a). To simulate the unknown parameter (4;, we draw samples from a uniform distribution U10, 1] over the interval [0, 1). In each round t of the offline pre-collected dataset, ranked list S₁ (at,1..... (t,x) S [m]] is randomly selected. The outcome X for each i E S, is generated from Bernoulli distribution with mean μ4; The reward at round / is set to 1 if there exists an item 0t,k with index k such that Xt.o. = 1. In this case, the learner observes the outcomes for the first k items of S,. Otherwise, if no such item exists, the reward is O, and the learner observes all K item outcomes as X = O for E S, Fig. la presents the average suboptimality gaps of the algorithms across different ranked lists n. The proposed CLCB algorithm outperforms the baseline methods, achieving average reductions in suboptimality gaps of 47.75% and 20.02%, compared to CUCB-Offine and EMP algorithms, respectively. These results demonstrate the superior performance of CLCB in offline environments.
Real- World Dataset. We conduct experiments on a real-world recommendation dataset, the Yelp dataser', which is collected by Yelp (Dai et al., 2024b). On this platform, users contribute reviews and ratings for various businesses such as restaurants and shops. Our offline data collection process is as follows: we select a user and randomly draw 200 items (e.g., restaurants or shops) that the user has rated as candidates for recommendation. The agent (i.e., the recommender system) attempts to recommend at most K items the user to maximize the probability that the user is attracted to at least one item in the recommended list. Each item has an unknown probability μ4, derived from the Yelp dataset, indicating whether the user finds it attractive. Regarding feedback, the agent collects cascading user feedback offline, observing a subset of the chosen K items until the first one is marked as attractive (feedback of 1). If the user finds none of the items in the recommended list S, attractive, the feedback is 0 for all items. Fig. 1b shows the average suboptimality gaps of different algorithms over n = 100 rounds across two action sizes (K = 4, 8). Notably, as K changes, the optimal reward also adjusts according to the expected reward r(S;; 1u) = 1- Ile,, (1 - 14), which explains why the suboptimality gap for smaller K tends to be larger compared to that for larger K. CLCB achieves the lowest suboptimality gap compared to CUCB and EMP algorithms, demonstrating its strong performance even on real-world data.
J.2. Offline Learning for LLM Cache
In the LLM Cache scenario, we compare our algorithm (Algorithm 2) against two additional baselines: LFU (Least Frequently Used), which is a caching strategy that evicts the least frequently accessed items to optimize cache usage (Zhu
*https: htttts:://wwyyetr yelp. com det
38

---

Offline Learning for Combinatorial Multi-armed Bandits
al., 2023), and Least Expected Cost (LEC), which is advanced caching algorithm that minimizes inference cost by evicting items with the lowest estimated expected cost (Zhu al., 2023).
Synthetic Dataset. For the LLM cache application described in Section 4.2, we simulate the scenario using 100 distinct queries and set the cache size to 40. Consistent with (Zhu et al., 2023), the frequency distribution follows power law with a = 0.9, and the ground truth cost for each query processed is drawn from a Bernoulli distribution with parameter 0.5. The simulation is repeated 20 times to ensure robustness, and we report the mean and standard deviation of the results across different dataset sizes = {2, 4, 16, 32, 64, 128, 256, 512, 1024, 2048) in Fig. 3a. Our normalized results suggest that ELCB-LLM-C significantly outperforms the baseline algorithms, LFU and LEC, achieving an average improvement of 1.32x. These results highlight the effectiveness of CLCB-LLM-C in optimizing cache performance for LLM applications.
Real-World Dataset. We use the SciQ dataset (Welbl et al., 2017), which covers a variety of topics, including physics, chemistry, and biology, to evaluate the performance of our proposed CLCB-LLM-C algorithm using OpenAl's LLMs. The cost is defined as the price for API calls, based on OpenAl's official API pricing. Since the cost heavily depends on the token count of the input text, we utilize OpenAI's tiktoken library, designed tokenize text for various GPT models. We consider two different LLMs with distinct encoding strategies. Specifically, we use GPT-4-o with the "o200k_hase" encoding to present the main experimental results. Additionally, we experiment with another variant, GPT- 4-turbo, which employs the "cl100k base" encoding (OpenAI, 2025). For the evaluation, we work with 100 distinct prompts from the SciQ dataset in an offline setting. performing a total of 10,000 queries with cache sizes of K 10 and
0.5
LFU LEC CLCB-LIM-C
Subaptimality Gap
0.4
0.1
0.0
K=10
K=
Cache Size
Figure 4. Algorithms another LLM.
K 20, respectively. Fig. 3b presents the normalized suboptimality gap of cost over n 100 rounds. CLCB-LLM-C achieves 36.01% % and 20.70%. less cost compared to LFU and LEC, respectively. Moreover, larger K shows lower suboptimality gap, which is consistent with Theorem 3. In addition to the results presented in the main text using GPT-4-o with the "o200k_bass" encoding, we experiment with another LLM, GPT-4-turbo with the 1a1100kbbase encoding. Fig. 4 demonstrates the robustness of our algorithm across different LLMs.
39


Reviews:
[{"review_id": "mGvlsBh2Zi", "reviewer": "Reviewer_mMZh", "summary": "This paper studies the offline version of the combinatorial multi-arm bandit (CMAB) problem, which is different from most CMAB papers that consider the online version. The authors provide solid theoretical results on the sample complexity of the offline CMAB problem that is minimax optimal. Moreover, the authors demonstrate the offline CMAB framework through three applications: cascading bandits, LLM caching, and influence maximization. The authors present both theoretical guarantees and numerical results for these applications (except for influence maximization).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing our work's connection to a broad literature, which offers new insights for RL with combinatorial action spaces and novel new applications.\n\n**Q1. About the motivation of studying the offline CMAB problem.**\n\n**A1.** While online bandits are a natural choice when online data is readily available and inexpensive, many real-world applications restrict access to only offline data as follows, which motivates the study of offline CMAB.\n\nFor instance, consider the cascading bandit model in recommendation systems. Online CMAB learning requires a tight feedback loop where the platform (i.e., the learner) updates its recommendation policy after every user interaction. However, in many practical scenarios, such fine-grained online feedback is unavailable as the platform cannot afford to update at such a high frequency. Instead, data is collected in batches (e.g., over a week), logged, and then used to update the policy in a single offline training phase. This workflow aligns precisely with our offline CMAB setting.\n\nAnother motivating scenario involves outsourced system design. For example, if OpenAI or Anthropic outsources the design of an LLM caching system, the consultant (i.e., the learner) typically receives only anonymized user logs. They must learn user behavior and design the system purely based on this private offline dataset and cannot reach out for direct interaction with the users, which fits naturally into the offline CMAB framework.\n\nMoreover, our work on CMAB also mirrors the development trajectory in reinforcement learning (RL). RL began with a focus on online learning [1]; then, around 2020, concerns over the cost and availability of online interactions led to a growing emphasis on offline RL—learning solely from offline data [2]. More recently, hybrid approaches [3] combining offline pretraining with online fine-tuning have emerged. Similarly, after establishing foundational results in online CMAB, we now focus on the offline setting as a crucial step toward enabling future hybrid CMAB approaches.\n\nWe will incorporate this discussion and examples into the final version of the paper.\n\nReferences:\n\n[1] Mnih et al., Playing Atari with Deep Reinforcement Learning, arXiv:1312.5602 (2013).\n\n[2] Levine et al., Offline Reinforcement Learning: Tutorial, Review, and Perspectives, arXiv:2005.01643 (2020).\n\n[3] Lee et al., Offline-to-Online Reinforcement Learning via Balanced Replay and Pessimistic Q-Ensemble, CoRL, 2022.\n\n**Q2.  Justification of baseline algorithms.**\n\n**A2.** In the revised manuscript, we will include a dedicated paragraph in Section 5 to justify our baselines. Specifically, as detailed in Appendix J.1, we evaluate our proposed Algorithm 1 in the cascading bandit scenario by comparing it against the following baselines: (1) CUCB-Offline [1]: An offline variant of the non-parametric Combinatorial Upper Confidence Bound (CUCB) algorithm, adapted to our setting by changing the LCB in line 5 of Algorithm 1 to its UCB counterpart. This baseline is chosen because it represents a well-established approach in combinatorial multi-armed bandit problems.  (2) EMP [2]: A method that selects actions based on the empirical mean of rewards. We include EMP as a simple yet effective baseline that relies on historical data without sophisticated exploration.  \n\nIn the LLM cache scenario, we compare our Algorithm 2 against:  (1) LFU (Least Frequently Used) [3]: A caching strategy that evicts the least frequently accessed items to optimize cache usage. This is a standard baseline widely used in caching.  (2) LEC (Least Expected Cost) [3]: An advanced caching algorithm that minimizes inference cost by evicting items with the lowest estimated expected cost. We include LEC as it directly aligns with our objective of optimizing inference cost, serving as a strong competitor to our approach.  \n\nReferences:\n\n[1] Chen et al. \"Combinatorial multi-armed bandit and its extension to probabilistically triggered arms.\" JMLR, 2016. \n\n[2] Liu et al. \"Multi-layered network exploration via random walks: From offline optimization to online learning.\" ICML, 2021.\n\n[3] Zhu et al. \"On optimal caching and model multiplexing for large model inference.\" arXiv, 2023.\n\n**Q3. Discussion on how to use offline bandit learning to facilitate online bandit learning.**\n\n**A3.** Our offline CMAB framework provides a solid foundation for developing hybrid offline-online CMAB methods. One promising future direction is to leverage the output of offline CMAB as a baseline policy to ensure stable average performance, while selectively conducting targeted exploration over a small set of promising policies identified during offline training. This strategy can significantly accelerate online learning by reducing the exploration space and focusing only on high-potential actions, effectively combining the strengths of both offline and online approaches. We will add this discussion in the final version.", "claims_and_evidence": "Yes, the main contributions are clearly stated and justified.", "methods_and_evaluation_criteria": "The benchmark datasets and synthetic datasets in Section 5 are reasonable.", "theoretical_claims": "I followed the proofs of Theorem 1 & 2, which are the main theoretical results of the paper. They are correct.", "experimental_designs_or_analyses": "In Section 5 (Experiments), discussions on the choice of benchmark algorithms are missing.", "relation_to_broader_scientific_literature": "I can see the work relates to many pieces of literature, i.e., offline RL, combinatorial bandits, cascade bandit, LLM caching optimization, and influence maximization. The work offers new insights into efficient RL with combinatorial action spaces (with special structure), and suggests some novel new applications.", "essential_references_not_discussed": "To better motivate the study of offline bandits, a literature review of papers discussing the complexity and value of offline learning in MAB settings is necessary.", "other_strengths_and_weaknesses": "The paper is very well-written. All the mathematical statements are written in a clear manner, and the paper itself also presents a complete story: a new theory of offline CMAB, extensive applications, and experiments.\n\nOne major weakness is the lack of motivation of the offline CMAB. I believe it is more natural to consider the online version of bandits since they are naturally experimentation methods. In the Introduction section, the authors use the healthcare system as an example where experimentation might be infeasible, but they work on applications other than healthcare systems later.", "other_comments_or_suggestions": "In general, the authors need a stronger justification of why a complete offline learning framework for CMAB is necessary since the problem seems to be just some kind of a best subset selection problem in one shot. For the LLM caching problem, both the offline and the online learning approach would make sense [1]. \n\nIt will be helpful for the authors to discuss how to leverage the offline data in the online learning setting and how to adapt the offline learning algorithm into an online learning algorithm\n\n[1] Zhu, Banghua, et al. \"Towards Optimal Caching and Model Selection for Large Model Inference.\" Advances in Neural Information Processing Systems 36 (2023): 59062-59094.", "questions_for_authors": "As mentioned above, can the authors give a stronger justification of the significance of the offline CMAB problem?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eTM7gtiqys", "reviewer": "Reviewer_Feh9", "summary": "This paper proposes a framework of offline learning for combinatorial multi-armed bandit (Off-CMAB). The authors first provide an algorithm, CLCB, based on constructing the lower confidence bound for each base arms from the offline dataset. In order to theoretically measure the performance of the algorithm in terms of sub-optimality gap with sample complexity (size of the offline dataset), they provides two data coverage conditions to qualify the quality of the dataset: (1) Infinity-norm TPM Data Coverage, and (2) 1-norm TPM Data Coverage. The paper then provides theoretical upper bound on the sub-optimality gap of their CLCB by the two conditions, respectively, and shows that the bound regarding the condition (1) is tight under the special instance, $k-$path problem, up to log factors. Finally, the authors introduces three applications of their framework: Cascading Bandits, LLM cache Bandit, and Influence Maximization, with numerical experiments for the first two applications.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback about our work's insights and on building connection between traditional combinatorial bandits and LLM.\n\n\n**Q1. On the technical challenges and novelty.**\n\n**A1.** Our main contribution is a **general and minimalistic framework for offline learning in CMAB**, which we validate through three important and diverse applications. While the idea of pessimism is widely used in offline bandits and RL, its effectiveness and applicability to **combinatorial bandits with large action spaces**—a setting motivated by many real-world applications—remains unclear. Key open questions include whether pessimism works in such settings, under what conditions it succeeds, and how various structural factors influence performance. Our work provides the first steps toward addressing these questions.\n\nFrom a **framework perspective**, we propose the general **offline CMAB-T framework**, and introduce two novel data coverage conditions (Conditions 3 and 4), i.e., the **1-norm and infinity-norm TPM data coverage conditions**. These conditions are minimal yet insightful, offering a practical way to assess dataset quality when this offline dataset is collected under an aribtrary policy. A critical technical novelty is the use of $p_i^{D\\_{\\text{arm}}, S^*}$, the arm-wise observation probability under the optimal super arm, as an importance weight. Naively defining coverage without this weighting would incur an additional $1/p^*$ factor in the suboptimality gap. Furthermore, unlike what might be intuitively expected, our framework only requires this importance weight with respect to the **optimal super arm** $S^*$, rather than all super arms, making the condition weaker but still sufficient for achieving near-optimal guarantees.\n\nIn **Theorems 1 and 2**, we intentionally present the analysis in a clean and minimalist form to maximize accessibility and generality. Many of the technical challenges are addressed in the **application-specific sections**:\n\n- In the **LLM cache** scenario, it is nontrivial to verify that the problem satisfies the data coverage conditions. Moreover, our analysis must jointly handle the **full-feedback arrival probability** and **semi-bandit feedback cost**, which interact in subtle ways. Our improvements (Theorem 3) over Zhu et al. stem from both satisfying the conditions and carefully handling these feedback structures.  \n\n- In the **influence maximization** application, we integrate **variance-adaptive confidence intervals** and consider **node-level feedback**, achieving state-of-the-art results. While these techniques (e.g., constructing confidence intervals for intermediate random variables using Bernstein-type concentration) could be unified under the general framework, we choose to separate them for clarity. This design decision keeps Theorems 1 and 2 clean, but it may mask some of the technical depth—such as advanced estimation strategies and additional uncertainty terms arising from variance-based bounds.\n\nIn summary, although our general results are presented in a minimal form, they are backed by nontrivial challenges when instantiated in realistic applications.  We will add a discussion of how these application-motivated extensions could be generalized into the main results to the paper.\n\n**Q2. About the typo in Remark 4.**\n\n**A2.** We thank the reviewer for pointing out the typo in Line 233. We will correct it in the final version of the paper.", "claims_and_evidence": "Yes. Very clear.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n1. This paper proposes a clear and general framework for offline combinatorial bandits.\n2. This paper provides two novel data coverage conditions to measure the quality of offline datasets.\n3. This paper provides insights of their model to LLM related problem. \n4. This paper is completed and well-written. The authors clearly conveys and validates their message.\n\nWeaknesses and Questions:\n1. There are some typos (for example in remark 4 Line 233).\n2. I am quite curious about the technical novelty. For me, the algorithm design and theoretical analysis (theorem 1) is natural and a bit \"simple\". Specifically, although there is no work studying offline learning in combinatorial bandit previously, it is quite natural to directly leverage the idea of pessimism principle to penalize the arms that have not been explored enough. Based on this principle, the corresponding theoretical analysis is also straightforward. In my opinion, the proof for theorem 1 and 2 consists of proper use of standard techniques and smart extraction of key influencing factors (data coverage condition).\n\nComments:\n1. Given that the paper provides some new insights of data coverage conditions and provides some new connection between traditional combinatorial bandits and LLM, I believe the paper should be accepted, although I am not quite sure whether the technical novelty is enough. I will be happy to further increase my score if I miss something important regarding the technical novelty.", "other_comments_or_suggestions": "See Strengths And Weaknesses.", "questions_for_authors": "See Strengths And Weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GH50aqSOWy", "reviewer": "Reviewer_qESa", "summary": "The authors study a problem within the combinatorial multi-armed bandit (CMAB) setting, in the presence of offline datasets. The authors introduce Off-CMAB, the first offline learning framework for CMAB. The authors propose the combinatorial lower confidence bound (CLCB) algorithm, which combines pessimistic reward estimations with approximation algorithms and propose two data coverage conditions and prove that, under these conditions, CLCB achieves a near-optimal suboptimality gap, matching the theoretical lower bound up to a logarithmic factor. The authors validate Off-CMAB through various applications, including learning to rank, large language model caching, and social influence maximization.\n\n## update after rebuttal\n\nWe expressed some concerns clearly in both the review and rebuttal. Unfortunately, the authors appear to have ignored our suggestions and continued to respond with incorrect or misleading assertions. We are not dismissing the contributions of this work. We recognize that semi-bandit feedback and offline learning are both legitimate and practical problem settings, and the paper contributes in these directions. However, our key concern remains: the over-claiming, wrong statements (semi-bandit settings allow for tighter and even exact approximation guarantees), and mischaracterization of related work. Hence, we downgrade the initial score.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments regarding the claims of our paper and the comparison with related work.\n\n**Q1. Clarification on our claim regarding nonlinear reward functions and general feedback models.**\n\n**A1.** We appreciate the reviewer’s suggestion. In the final version, we will clarify in both the abstract and introduction that our framework addresses CMAB problems with semi-bandit feedback under nonlinear reward functions, where the oracles operate on arm-level estimations.\n\n**Q2. Missing references and comparison with combinatorial bandit under full-bandit feedback works.**\n\n**A2.** We appreciate the reviewer pointing out the relevant line of work on online combinatorial bandits with full-bandit feedback [1–7]. We will include these references in the related work section. However, we would like to emphasize two key distinctions:\n\n(1) Online vs. offline setting: The cited works [1–7] focus on online learning, while our work addresses the offline CMAB setting, which poses different challenges and requires different algorithmic strategies.\n\n(2) Semi-bandit vs. full-bandit feedback: Our setting assumes semi-bandit feedback, where the learner observes individual arm-level feedback for selected arms (i.e., components of the super arm). This enables more informative learning and allows us to construct accurate base-arm estimators for use in our oracles, leading to an $O(T^{1/2})$ regret bound. In contrast, full-bandit feedback only provides aggregate rewards for the entire super arm, often resulting in higher regret (e.g., $O(T^{2/3})$) and requiring fundamentally different oracle designs. Moreover, prior full-bandit approaches often rely on additional structural assumptions such as submodularity to achieve these bounds. Similarly, our approach leverages smoothness assumptions on the reward function to ensure statistical efficiency in the offline regime.\n\nWe agree that assuming semi-bandit feedback precludes applying our work to some settings, but we point out that such feedback is available in a wide range of applications of interest, and that both full-bandit CMAB [1-7] and semi-bandit CMAB (Gai et al., 2012; Kveton et al., 2015c; Combes et al., 2015; Chen et al., 2016; Wang\n\\& Chen, 2017; Merlis \\& Mannor, 2019; Saha \\& Gopalan, 2019; Agrawal et al., 2019; Liu et al., 2022; 2024, Zimmert et al., 2019; Ito, 2021; Tsuchiya et al., 2023.) have long been studied as distinct lines of work in the literature. \nOur choice of the semi-bandit model is motivated by its natural presence in many real-world domains (beyond the three applications already discussed in this paper), including:\n\n- Online recommendation: Click/no-click feedback is available per item in the recommended list.\n\n- Online routing: The delay or cost of each edge in a chosen path can be observed.\n\n- Crowdsourcing: The quality of individual workers’ contributions is directly measurable or computable.\n\nThese applications offer fine-grained, arm-level feedback, making the semi-bandit setting not only realistic but essential. Nevertheless, we agree that exploring offline CMAB under full-bandit feedback is a compelling future direction and will add such a discussion to the paper.\n\n**Q3. On the practicality of the offline CMAB setting.**\n\n**A3.**\nWe respectfully refer the reviewer to our response for the Q1 asked by Reviewer mMZh, where we discuss motivating applications and the relevance of the offline CMAB setting in real-world systems.\n\n\n\n**Q4. On combining offline and online CMAB.**\n\n**A4.**\nPlease refer to our response for Q3 asked by Reviewer mMZh, where we outline our vision for hybrid offline-online CMAB approaches as a promising future direction.\n\n**Q5. On the novelty and technical contribution of our work.**\n\n**A5.**\nWe respectfully refer the reviewer to our response for Q1 asked by Reviewer Feh9, which provides a detailed discussion of the challenges addressed and the key innovations of our framework and theoretical results.\n\n\n**Q6. Clarification on experimental details**\n\n**A6.**\n As noted in Lines 1962-1963, at the beginning of the experimental setup, each experiment was conducted over 20 independent trials to ensure reliability. This applies to both the cascading bandit scenario and the LLM cache scenario. To avoid ambiguity, we will explicitly reiterate this detail in the final version of Section 5.", "claims_and_evidence": "The claims made in the submission were supported by proved theoretical results and were validated by experiments. \nHowever, some claims should be relaxed such as: “We validate Off-CMAB through practical applications, … , showing its ability to handle nonlinear reward functions, general feedback models” Should be rather “We validate Off-CMAB through practical applications, … , showing its ability to handle ““some”” nonlinear reward functions”. For example their approach cannot handle submodular reward functions under bandit-feedback (where the reward function is black-box).", "methods_and_evaluation_criteria": "The considered methods make sense for the problem at hand.", "theoretical_claims": "Checked the proof ideas and briefly skimmed through the proof.", "experimental_designs_or_analyses": "The experiments seem fine. However, they lack some details (even in the appendix). For example, while it is mentioned in the Appendix for the LLM experiment that the number of repetitions is 20 times. For the other ones this detail was not mentioned.", "relation_to_broader_scientific_literature": "This work studies a problem at the intersection of offline learning and combinatorial bandits literatures. While there are several works on offline learning and several other works on online bandits. A few works studies offline bandits. This work proposes a first framework for offline combinatorial bandits. The work derives theoretical guarantees for the proposed framework and shows, under some condition, near-optimal regret matching the lower bound with logarithmic factor.", "essential_references_not_discussed": "The paper does not cite recent related works on combinatorial bandits, which similarly rely on offline approximation algorithms (ORACLE) [1-7], dealing with non-linear rewards (for submodular [2, 4, 6] and general rewards [1, 3, 5, 7]), some of which study the same problem of social influence maximization [3, 4]. \n\n(minor) Moreover, the authors compare in the experiments to some approaches such as EMP [8], which was cited in the main paper but not discussed or cited within the related works. EMP is directly mentioned in the experiments without an introduction or explanation. \n\n**Reference**\n\n[1] Niazadeh, R., Golrezaei, N., Wang, J. R., Susan, F., & Badanidiyuru, A. (2021, July). Online learning via offline greedy algorithms: Applications in market design and optimization. In Proceedings of the 22nd ACM Conference on Economics and Computation (pp. 737-738).\n\n[2] Fourati, F., Aggarwal, V., Quinn, C., & Alouini, M. S. (2023, April). Randomized greedy learning for non-monotone stochastic submodular maximization under full-bandit feedback. In International Conference on Artificial Intelligence and Statistics (pp. 7455-7471). PMLR.\n\n[3] Nie, G., Nadew, Y. Y., Zhu, Y., Aggarwal, V., & Quinn, C. J. (2023, July). A framework for adapting offline algorithms to solve combinatorial multi-armed bandit problems with bandit feedback. In International Conference on Machine Learning (pp. 26166-26198). PMLR.\n\n[4] Fourati, F., Quinn, C. J., Alouini, M. S., & Aggarwal, V. (2024, March). Combinatorial stochastic-greedy bandit. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 11, pp. 12052-12060).\n\n[5] Fourati, F., Alouini, M. S., & Aggarwal, V. (2024, July). Federated Combinatorial Multi-Agent Multi-Armed Bandits. In International Conference on Machine Learning (pp. 13760-13782). PMLR.\n\n[6] Sun, X., Guo, T., Han, C., & Zhang, H. (2025). Greedy algorithms for stochastic monotone k-submodular maximization under full-bandit feedback. Journal of Combinatorial Optimization, 49(1), 1-25.\n\n[7] Oki, T., & Sakaue, S. (2025). No-Regret M ${}^{\\natural} $-Concave Function Maximization: Stochastic Bandit Algorithms and NP-Hardness of Adversarial Full-Information Setting. Advances in Neural Information Processing Systems, 37, 57418-57438. \n\n[8] Liu, X., Zuo, J., Chen, X., Chen, W., and Lui, J. C. Multi-layered network exploration via random walks: From offline optimization to online learning. In Interna tional Conference on Machine Learning, pp. 7057–7066. PMLR, 2021.", "other_strengths_and_weaknesses": "**Strengths**\n\n(1)\tThe authors study an important problem in machine learning which is combinatorial bandits.\n\n(2)\tThe authors propose CLCB algorithm and derive its theoretical guarantees.\n\n(3)\tThe authors propose data coverage conditions and prove that, under these conditions, the proposed algorithm is near-optimal matching the lower bound regret guarantees up to a logarithmic term.\n\n(4)\tThe proposed algorithm is assessed empirically against three different datasets. \n\n**Weaknesses**\n\n(1) *Novelty*: The algorithm is very similar to the online CMAB-T approaches [10, 11] with the key modification to rely on the principle of pessimism, which is borrowed from previous works [12]. Moreover, the idea to use pessimism in the offline bandits can be found in previous bandits works such as [13]. \n\n(2) *Limitation in the Algorithm*: While the CLCB algorithm is proposed to consider a given approximation oracle (Algorithm 1, line 7), the oracle is constrained to require as input the estimated arm rewards. However, several optimal approximation oracles do not work this way, as they require the set of arms as input rather than the estimated value of each arm, such as the approximation oracle adapted in the references above [1-7]. For example, the greedy algorithm in [8] or the stochastic-greedy algorithm in [9] cannot be used, unlike the frameworks in [3, 5] or the specialized algorithms in [2, 4, 6], which employ oracles that do not require the estimated reward of arms. \n\n(4) (minor) *Limitation in the Considered Setting*: The paper considers semi-bandit feedback, which is of interest to the community. However, several problems require full-bandit feedback (also called bandit feedback), which limits the applicability of the approach in several settings.\n\n(5) (minor) *Limitation in the Considered Setting*: The paper assumes the presence of an offline data, which can sometimes be available, however, not always, which limits the applicability of the approach in various settings. \n\n**References**\n\n[1-7] *See references above.*\n\n[8] Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions—I. Mathematical programming, 14, 265-294.\n\n[9] Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondrák, J., & Krause, A. (2015, February). Lazier than lazy greedy. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 29, No. 1).\n\n[10] Chen, W., Wang, Y., & Yuan, Y. (2013, February). Combinatorial multi-armed bandit: General framework and applications. In International conference on machine learning (pp. 151-159). PMLR.\n\n[11] Wang, Q., & Chen, W. (2017). Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications. Advances in Neural Information Processing Systems, 30.\n\n[12] Jin, C., Yang, Z., Wang, Z., & Jordan, M. I. (2020, July). Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory (pp. 2137-2143). PMLR.\n\n[13] Li, G., Ma, C., & Srebro, N. (2022). Pessimism for Offline Linear Contextual Bandits using $\\ell_p $ Confidence Sets. Advances in Neural Information Processing Systems, 35, 20974-20987.", "other_comments_or_suggestions": "It should be clear from the beginning (perhaps even from the abstract) whether the considered algorithm is for bandit feedback or semi-bandit feedback settings.", "questions_for_authors": "In the presence of offline data and the possibility of online learning, we can always use the offline data to warm up the learning agent and then start standard online learning. Given this, how practical is the off-CMAB setting? What types of problems do not allow for any amount of online learning?\n\nHow would your approach perform with submodular rewards? Is there any discussion on extensions to bandit feedback settings?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies the offline setting of combinatorial bandits problem with semi-bandit feedback. They consider non-linear reward functions and employ an offline optimization oracle that enjoys approximate guarantees. The main contribution of this work are necessary and sufficient conditions for when learning (using pessimism) works. Given the familiar tools used, some reviewers questioned how novel the approach actually was but most were convinced of the final contribution. For a theoretical paper, this paper placed an unusual focus on applications to bolster its claims of its coverage conditions and other assumptions--this is well appreciated.
Decision: Accept (poster)