Offline Learning for Combinatorial Multi-armed Bandits

We thank the reviewer for their comments regarding the claims of our paper and the comparison with related work.

Q1. Clarification on our claim regarding nonlinear reward functions and general feedback models.

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.

Q2. Missing references and comparison with combinatorial bandit under full-bandit feedback works.

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:

(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.

(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.

We 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 & 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. Our 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:

• Online recommendation: Click/no-click feedback is available per item in the recommended list.

• Online routing: The delay or cost of each edge in a chosen path can be observed.

• Crowdsourcing: The quality of individual workers’ contributions is directly measurable or computable.

These 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.

Q3. On the practicality of the offline CMAB setting.

A3. We 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.

Q4. On combining offline and online CMAB.

A4. Please 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.

Q5. On the novelty and technical contribution of our work.

A5. We 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.

Q6. Clarification on experimental details

A6. 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.

We thank the reviewer for their positive feedback about our work's insights and on building connection between traditional combinatorial bandits and LLM.

Q1. On the technical challenges and novelty.

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.

From 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.

In 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:

• 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.

• 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.

In 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.

Q2. About the typo in Remark 4.

A2. We thank the reviewer for pointing out the typo in Line 233. We will correct it in the final version of the paper.

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.

Q1. About the motivation of studying the offline CMAB problem.

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.

For 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.

Another 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.

Moreover, 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.

We will incorporate this discussion and examples into the final version of the paper.

References:

[1] Mnih et al., Playing Atari with Deep Reinforcement Learning, arXiv:1312.5602 (2013).

[2] Levine et al., Offline Reinforcement Learning: Tutorial, Review, and Perspectives, arXiv:2005.01643 (2020).

[3] Lee et al., Offline-to-Online Reinforcement Learning via Balanced Replay and Pessimistic Q-Ensemble, CoRL, 2022.

Q2. Justification of baseline algorithms.

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.

In 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.

References:

[1] Chen et al. "Combinatorial multi-armed bandit and its extension to probabilistically triggered arms." JMLR, 2016.

[2] Liu et al. "Multi-layered network exploration via random walks: From offline optimization to online learning." ICML, 2021.

[3] Zhu et al. "On optimal caching and model multiplexing for large model inference." arXiv, 2023.

Q3. Discussion on how to use offline bandit learning to facilitate online bandit learning.

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.