Cost-Effective Online Multi-LLM Selection with Versatile Reward Models

## Abstract

Abstract With the rapid advancement of large language models (LLMs), the diversity of multi-LLM tasks and the variability in their pricing structures have become increasingly important, as costs can vary greatly between different LLMs. To tackle these challenges, we introduce the C2MAB-V , a C ost-effective C ombinatorial M ulti-armed B andit with V ersatile reward models for optimal LLM selection and usage. This online model differs from traditional static approaches or those reliant on a single LLM without cost consideration. With multiple LLMs deployed on a scheduling cloud and a local server dedicated to handling user queries, C2MAB-V facilitates the selection of multiple LLMs over a combinatorial search space, specifically tailored for various collaborative task types with different reward models. Based on our designed online feedback mechanism and confidence bound technique, C2MAB-V can effectively address the multi-LLM selection challenge by managing the exploration-exploitation trade-off across different models, while also balancing cost and reward for diverse tasks. The NP-hard integer linear programming problem for selecting multiple LLMs with trade-off dilemmas is addressed by: i) decomposing the integer problem into a relaxed form by the local server, ii) utilizing a discretization rounding scheme that provides optimal LLM combinations by the scheduling cloud, and iii) continual online updates based on feedback. Theoretically, we prove that C2MAB-V offers strict guarantees over versatile reward models, matching state-of-the-art results for regret and violations in some degenerate cases. Empirically, we show that C2MAB-V effectively balances performance and cost-efficiency with nine LLMs for three application scenarios.

## 1 Introduction

In the digital era of today, large language models (LLMs) such as ChatGPT lead innovations in computational linguistics and cognitive processing [].
The emergence of numerous high-performance LLMs has sparked significant interest in the challenge of model selection [, ].
Typically, current schemes for selecting LLMs often rely on identifying the best-performing model in a static setting, such as selecting the LLM that achieves the lowest perplexity score [, ]. However, the diverse capabilities of various LLMs present an opportunity to adopt a task-specific selection approach, where different LLMs have their own strengths and weaknesses, e.g., Investlm [] is specifically designed for the financial sector and may better suit queries related to investments. Moreover, the limitations of static selection methods become more pronounced due to factors like “generation diversity”, where a less expensive LLM may perform better in certain scenarios [], and “data drift”, which refers to changes in the characteristics of answers generated in real-time compared to those of training data [].
Consequently, beyond large-scale pre-training methods, these issues highlight the need for an “online” approach to optimize decision-making in selecting the “appropriate” LLMs, which leverage continuous feedback to adapt to the varying performance levels of models and diverse application needs through ongoing user interaction.

Furthermore, scenarios combining multiple LLMs (or agents) to complete tasks have commonly emerged, moving beyond using a single LLM. Platforms like [] have spearheaded functionalities that integrate several bots within a single chat session. [] introduces a dynamic LLM-agent network through dynamic interaction architecture and intelligent agent team optimization. [] proposes a meta-programming framework that enhances the collaboration of multiple LLMs. [] explores the implementation of LLM cascades for generative tasks. However, previous works have not considered optimizations tailored to the characteristics of different tasks, which may feature different forms of rewards. Below, we present three streamlined collaborative combinations of LLMs for different tasks: 1. For user experience enhancement, multiple LLMs may be deployed to ensure satisfactory outcomes. 2. In educational tutoring, subject-specific LLMs operate in parallel, with failures in one not severely impacting others. 3. In project development, LLMs manage different sub-modules, where any module’s failure could jeopardize the entire project. These three examples underscore the importance of combining multiple suitable LLMs based on the specific “task structure”.

Additionally, it is crucial to recognize that the emergence of LLMs with diverse performance levels introduces varying costs in practical use, an important factor neglected in existing research. The operating expenses for LLMs are high; for example, it is estimated that running ChatGPT costs over $700,000 daily, and deploying GPT-4 for customer service could cost a small business upwards of $21,000 per month []. This implies the necessity of incorporating cost considerations into the selection and utilization strategies for LLMs.

Based on the discussions above, we introduce the Cost-effective Combinatorial Multi-armed Bandit with Versatile reward models (C2MAB-V), designed to synergize the integration of diverse LLMs across different task types. C2MAB-V manages the dual challenges of selecting LLMs that both achieve high performance and meet cost constraints. Additionally, C2MAB-V adapts to various multi-LLM collaborative tasks by utilizing a “combinatorial model selection strategy” which extends beyond traditional single-model limitations by encompassing a broad spectrum of LLM candidates. Finally, to address the NP-hard complexities of combinatorial LLM selection under cost considerations, we transform the initial problem into a continuous form. This process is executed on the local server, which is required to handle user queries. Meanwhile, our discretization method, which guarantees precise evaluation of LLM performance post-relaxation, is implemented on the scheduling cloud where multiple LLMs are deployed. This two-tiered approach can accommodate both the limited resources of the local server and strategically mitigate the scheduling cloud’s workload. We emphasize that this paper focuses on a fully online learning approach that operates without initial information and relies solely on user feedback with robust interpretation. Our method is designed to complement, not compete with, current approaches that utilize GPU resources for offline training, where offline training can streamline the search space and enhance the convergence speed of online learning.

In summary, our contributions are as follows.

Novel Multi-LLM Selection Formulation. We introduce a novel formulation of the cost-effective multi-LLM selection, designed for tasks requiring collaboration among multiple LLMs with versatile reward structures. This formulation emphasizes the essential balance between exploring new models and exploiting proven effective models, while adhering to long-term cost budget considerations and securing high rewards across diverse multi-LLM tasks.

Unique Online Algorithmic Framework. We developed the C2MAB-V framework for online multi-LLM selection, managing diverse collaborative LLM tasks and performance variability due to generation diversity and data drift. Our approach utilizes a “combinatorial bandit selection strategy” with a cost-conscious versatile reward structure. Based on a natural local-cloud architecture, the local server, with its limited resources, simplifies the selection process and alleviates the computational load on the scheduling cloud. The cloud coordinates and selects LLMs based on continualized feedback data from the local server, which also gathers user feedback to enhance LLM evaluations.

In-Depth Regret and Violation Analysis.
We conduct a thorough theoretical analysis of our online C2MAB-V framework, covering three distinct reward models. This analysis addresses the trade-offs between reward and violation, and between exploration and exploitation. We identify common properties across different reward models and employ “martingale construction techniques” to examine the stochastic properties of our model under varying collaborative tasks. Notably, our results on regret and violation analysis match the state-of-the-art results in several degenerate cases.

Comprehensive Empirical Validation. Our C2MAB-V framework has been empirically validated with superior performance outcomes across evaluations involving nine distinct LLMs.
These tests consistently confirm C2MAB-V’s capacity to adaptively navigate the trade-off dilemmas, resulting in amplified rewards or decreased costs. Moreover, detailed analysis from exploratory experiments provides deeper insights into the strategic design and utilization of the multi-LLM approach.

## 2 Related Work and Motivation

### 2.1 Related Work

Combinatorial Multi-Armed Bandit.
The field of online learning problems under the multi-armed bandit (MAB) model has been extensively studied. The MAB model was first introduced by the seminal work [] and has been expanded upon by many other researchers ( [, , ]). Traditional MAB models focus on selecting a single arm per trial; however, the more complex scenario of combinatorial MAB (CMAB) involves selecting multiple arms simultaneously. The stochastic CMAB has received much attention recently [, , , , ]. Initial research on stochastic CMAB is spearheaded by [], with subsequent improvements in regret bounds offered by [, ]. Later on, [, ] considers probabilistic feedback to extend
the feedback model. Recently, [] proposes the variance-adaptive algorithm BCUCB-T. [] incorporates the contextual information in CUCB. Our research builds on the CMAB settings but diverges significantly by addressing more complicated trade-off issues. Furthermore, to address various cooperative task types, we explore three different combinatorial reward formulations within versatile reward models.

Multi-LLM Combination.
The combination of multiple LLM models for enhanced performance has received considerable attention, aimed at bolstering output quality []. Techniques such as “knowledge distillation” [, ] facilitate the training of compact models to mimic the behavior of larger and more complex models, thus optimizing resource utilization. Meanwhile, “ensemble learning” [, ] leverages the collective predictions of independently trained models for superior results. Nonetheless, the prevalent practice of withholding model internals from commercial LLM, such as [], restricts knowledge distillation by obscuring the “teacher” model, which can decrease the replication efficacy of the “student” model. Concurrently, ensemble learning faces increased financial and procedural burdens due to the necessity of amalgamating various model outputs, a task complicated by the absence of open-source models. [, , ] primarily address one of the scenarios we have outlined, i.e., selecting a single LLM that best satisfies the user from multiple options. Moreover, these approaches do not incorporate user feedback.
Our approach distinctively accounts for the online aspects of model selection, the diversity of multi-LLM task types, and the associated costs, setting it apart from previous methods.

### 2.2 Motivation

We introduce the rationale behind our cost-effective combinatorial LLM online
selection strategy.

Limitations of Single and Static Model Policy.
Table 1 presents the commercial costs of various LLMs []. Economically, it may not be viable for businesses or government entities to consistently choose the most expensive option, such as GPT-4, for all applications. Therefore, a careful assessment of the trade-offs between cost and performance (termed as ‘reward’) is essential, as it allows for more strategic budget management across various tasks.

**Table 1: Cost comparison of various LLMs based on 10 million output tokens from [].**
| LLM | ChatGPT | GPT-3 | GPT-4 | ForeFrontAI | J1-Large | J1-Jumbo |
| --- | --- | --- | --- | --- | --- | --- |
| Cost ($) | 2 | 20 | 60 | 5.8 | 30 | 250 |
| LLM | Xlarge | GPT-Neox | GPT-J | GPT-Curie | FAIRSEQ | J1-Grande |
| Cost ($) | 10 | 35 | 5 | 2 | 15 | 80 |

Moreover, we evaluate the performance of various LLM, including GPT-4, GPT-3.5, Claude 1.2, Claude 2, Forefront [, , ], using the mathematics dataset [] and SciQ dataset [], which cover multiple topics including physics, chemistry, and biology. As shown in Fig. 2, comparing these LLMs across three randomly selected scenarios with problem sets (each containing 200 samples) reveals the inherent limitations of relying on a single LLM. This measurement highlights the limitations of advanced models like GPT-4 in various contexts, emphasizing the phenomena of “generation diversity” mentioned in Section 1 and the necessity of continual online learning to select the “appropriate” LLMs for different queries. Moreover, challenges like “distribution shift” [] and the “Matthew effect” [] can cause deviations in the performance of models presumed optimal in the offline settings. Subsequently, the adoption of an online learning framework becomes essential, with ongoing interaction utilized to refine LLM selection.

Figure: Figure 1: Accuracy of different LLMs across varied problem samples.
Refer to caption: x1.png

Benefits of Combinatorial LLMs. Among the various tasks, we select the multi-LLM collaboration task on ensuring user experience while minimizing costs as an example. As shown in Fig. 2, ForeFrontAI is the first option. If its response’s accuracy matches the right choice question label from the datasets [], the query is routed to GPT-3.5. For further refinement, GPT-4 is invoked. This combination of multi-LLMs in a cascading form is compared with the exclusive use of GPT-4 for identical queries. Cost evaluation, based on the statistical data of [], reveals that such combinatorial LLMs incurs only 60.1% of the expenses associated with relying solely on GPT-4. Accuracy assessments further highlight the merits of the combinatorial approach, achieving an accuracy of 0.824 on the dataset, surpassing the 0.732 accuracy obtained by using GPT-4 alone. Consequently, the strategy of using combinatorial LLMs demonstrates a promising and compelling alternative.

## 3 Problem Formulation

In this section, we introduce our online framework of a cost-effective combinatorial bandit for multi-LLM selection with versatile reward models, namely, C2MAB-V (Please refer to Fig. 3 for details).
A summary of the main symbols is provided in Appendix A.

Local-Cloud Architecture.
Given the large number of parameters and significant storage overhead of LLMs, a typical approach, if not opting for a streamlined but less capable version of LLMs, involves deploying multiple LLMs on a resource-abundant scheduling cloud. When responding to user queries, the local server first handles the requests and synchronizes communication with the cloud to initiate tasks (for discussions on asynchronous handling, see Appendix E.3). Subsequently, user feedback is stored on the local server.(^1^11Feedback can include both direct user input and data from techniques that quantify user behavior or responses, as well as preference simulators []. Regardless of the methods, we refer to all these collectively as “feedback” for simplicity.) While the scheduling cloud serves multiple local servers, for ease of presentation, we focus on describing the relationship between a single local server and the cloud.

Combinatorial LLM Instance. The scheduling cloud orchestrates multiple independent LLMs, to effectively fulfill requests from the local server. Let $\mathcal{K}=\{1,\ldots,K\}$ represent the set of all LLMs, where each index $k\in\mathcal{K}$ corresponds to a specific LLM (i.e., base arm), comprising a total of $K$ LLMs.
The system operates in a time-slotted manner, delineated by discrete intervals $\mathcal{T}=\{1,2,3,\ldots,T\}$. During each round $t\in\mathcal{T}$, the cloud coordinates and selects a subset $S_{t}$ of available LLMs from $\mathcal{K}$.
This selection process, termed an “action”, adapts dynamically based on real-time constraints and availability, with the cardinality $|S_{t}|\leq K$ indicating the number of selected LLMs. Let $\mathcal{S}$ represent the set of all possible combinations of actions.(^2^22Action $S_{t}$ is actually a set. Similar to previous CMAB works, we also do not use script font here.) For example, high demand workloads may cause GPT-4 to reach its usage limit, temporarily preventing its selection. Let $N=\max_{S\in\mathcal{S}}|S|$, denoting the maximum number of LLMs that can be simultaneously active.

Online Learning Protocol. A combinatorial LLM instance involves the sequential interaction between the local server, the scheduling cloud, and user queries within our local-cloud architecture. The local server processes user activity and feedback, particularly focusing on the users’ performance feedback regarding the utilized LLMs. This process involves locally recording and updating the performance evaluations of the LLM. Then, the local server will transmit these information to the scheduling cloud. The scheduling cloud undertakes the new coordination and selection of an action $S_{t}$ (i.e., selecting a subset of LLMs for service) after receiving the newly updated information from the local server. Such performance evaluations, termed as rewards, could, for instance, be based on the ROUGE-2 score for automatic summarization tasks [], and are represented by a random variable vector $\boldsymbol{X}_{t}=(X_{t,1},\ldots,X_{t,|S_{t}|})$. For simplification, we posit that $\boldsymbol{X}_{t}\in[0,1]^{|S_{t}|}$. Furthermore, for each LLM $k\in\mathcal{K}$ included in the action $S_{t}$, its associated cost $y_{t,k}$ is observable at round $t$. A detailed definition of this cost will be provided later.

Note that we demonstrate a fully online learning process here without any prior information for a clear description. In real-world scenarios, online learning can often be accelerated by incorporating offline pre-training. For example, for mathematical queries, narrowing the action space by offering fine-tuned LLMs for specific mathematical tasks, rather than selecting from a broad set, can significantly streamline the online selection process.

Versatile Reward Models.
Let $\boldsymbol{\mu}=(\mu_{1},...,\mu_{K})$ represent the “initially unknown” mean vector of outcomes for each LLM with $\mu_{k}=\mathbb{E}[X_{t,k}]$. We consider versatile reward models for different combinations of LLMs in multi-LLM tasks below.

- •
Any Win Combination (AWC): $r(S;\boldsymbol{\mu})=\left(1-\prod_{k\in S}(1-\mu_{k})\right).$ As illustrated in Fig. 2, this reward model is designed to safeguard user experience by selecting multiple LLMs to generate answers, with success defined as any LLM’s answer satisfying the user. This reward model aims to maximize user satisfaction by providing a range of possible solutions.
- •
Sum Up Combination (SUC): $r(S;\boldsymbol{\mu})=\sum_{k\in S}\mu_{k}.$ In this setup, domain-specific LLMs independently tackle tasks in parallel. Each LLM earns rewards for correctly answering questions in its field. This reward model aims to speed up task completion and reduces the workload on each LLM, enhancing overall task effectiveness.
- •
All In Combination (AIC): $r(S;\boldsymbol{\mu})=\prod_{k\in S}\mu_{k}.$ This reward model is exemplified in development tasks, where each LLM is responsible for developing sub-modules simultaneously. The key aspect of this reward model is that the failure of any LLM leads to the failure of the entire development task, thus ensuring the success of the whole collaborative work.

For more discussions (e.g., specify LLMs under the SUC and AIC reward models), please refer to Section C.1.
Compared to previous works [, , , ], which primarily focus on selecting a single LLM to satisfy the user, our versatile reward model accounts for the diversity of tasks, addressing scenarios where multi-LLMs collaborate to complete tasks, besides the distinction being our focus on an online learning setting.

Partial LLM Feedback. In the process of selecting and querying LLM in action $S_{t}$, not all LLMs may actually be queried in the muti-LLM tasks. Consequently, the local server often only observes outcomes from a subset of the selected LLMs. Formally, the local server observes feedback from the LLM subset $\mathcal{F}_{t}$ in action $S_{t}$, where the subset’s cardinality is denoted as $F_{t}$. If all LLMs in $S_{t}$ are queried, then $F_{t}=|S_{t}|$, which is worst-case scenario under the AWC reward model.

Statistically-Based Cost Model. Drawing inspiration from [], which charges based on statistical computational resource utilization (with 1 CU supporting an average of 10 interactions), [], which offers unlimited token pricing without the consideration of token limits, and [], which bills based on exclusive resource groups, we propose a statistically-based cost model. Specifically, for any query $q$ from a set $\mathcal{Q}$, LLM $k\in\mathcal{K}$ processes the query using a deterministic number of input tokens, $l^{\text{in}}_{k}(q)$, and generates a random number of output tokens, denoted as $l^{\text{out}}_{k}(q)\sim D^{\text{out}}_{k}(q)$, representing the probabilistic nature of LLMs [, ]. Given a distribution $D_{q}$ over $\mathcal{Q}$, a user selects a query $q_{t}\sim D_{q}$ in each round, and the cost for LLM $k$ is $y_{t,k}=(l^{\text{in}}_{k}(q_{t})+l^{\text{out}}_{k}(q_{t}))C_{k}$, where $C_{k}$ is the cost per token. The goal is to estimate the unknown expected cost $c_{k}=\mathbb{E}[y_{t,k}]$.

Budget Violation Consideration. The total cost of executing action $S_{t}$ on the utilized LLM subset $\mathcal{F}_{t}$, selected by the scheduling cloud at round $t$, is given by $\sum_{k\in\mathcal{F}_{t}}y_{t,k}$. Furthermore, there is a predetermined budget guarantee threshold $\rho>0$ exists for the combinatorial set of LLM, requiring the cumulative cost of the selected action to remain below this threshold $\rho$ for the long term. This mechanism allows organizations, including enterprises and governmental bodies, to manage LLM usage efficiently and align with budgetary constraints. To assess compliance with this budgetary constraint, the concept of constraint violation [] is introduced as follows, with $[x]^{+}:=\max(x,0)$:

$$ $V(T)=\left[\frac{1}{T}\sum_{t=1}^{T}\sum_{k\in\mathcal{F}_{t}}y_{t,k}-\rho \right]^{+},$ (1) $$

Although it is conceivable to occasionally exceed this cost constraint during the online learning process, significant overruns are not permissible, thus necessitating the violation metric. A violation rate decreasing as $\tilde{O}\left(T^{-\gamma}\right)$ signifies effective constraint adherence, indicating that $V(T)$ diminishes at this rate, where $\gamma>0$ illustrates the rate of reduction in violations with $T$ [].

$\alpha$-Approximate Regret.
The performance of an online learning algorithm $A$ is evaluated by its “regret”, which is the discrepancy between the expected cumulative reward of consistently choosing the optimal action $S^{*}_{t}\triangleq\operatorname*{arg\,max}_{S\in\mathcal{S}}r(S;\boldsymbol{
\mu})$ at each round $t$, with $\mathcal{S}$ representing the set of all viable actions, and the expected cumulative reward resulting from the actions selected by algorithm $A$. The challenge, however, lies in the computational difficulty of determining the exact $S^{*}_{t}$, even when $\boldsymbol{\mu}$ is known, as this can be NP-hard []. Thus, following [, , , ], we presume that algorithm $A$ utilizes an offline $\alpha$-approximation oracle. This oracle, upon receiving a mean vector $\boldsymbol{\mu}$, outputs an action $S$ that guarantees $r(S;\boldsymbol{\mu})\geq\alpha\cdot r(S^{*}_{t};\boldsymbol{\mu})$. With the $\alpha$-approximation oracle, the $\alpha$-approximate regret over $T$ rounds is defined as:

$$ $\textstyle R(T)=\mathbb{E}\left[\sum_{t=1}^{T}\left(\alpha\cdot r(S^{*}_{t}; \boldsymbol{\mu})-r(S_{t};\boldsymbol{\mu})\right)\right],$ (2) $$

where the expectation accounts for the randomness in outcomes $\boldsymbol{X}_{1},...,\boldsymbol{X}_{T}$, and algorithm $A$ itself.

## 4 Algorithm Design

Figure: Figure 3: Design of C2MAB-V workflow, with detailed process descriptions provided on the left main text.
Refer to caption: x3.png

We present the design of the online C2MAB-V framework, as depicted in Algorithm 1. Our method addresses the challenge of estimating unknown rewards and costs associated with using corresponding LLMs. As shown in Fig. 3, given the NP-hardness complexity of selecting a combination of LLMs under cost constraints, we transform the original integer problem into a continuous space. Utilizing the limited resources of a local server, we solve this relaxed optimization problem, which can also ease the computational load on the scheduling cloud when supporting multiple local-server query requests. A scheduling cloud with multiple LLMs coordinates and selects based on continuous data transmitted from the local server. Meanwhile, the local server collects user feedback to enhance the online evaluations of LLMs. Additionally, the cloud does not have access to the original sensitive user data, enhancing future privacy protection prospects. Next, we describe the processes undertaken by the local server and the scheduling cloud.

Figure: Algorithm 1 Online Update of C2MAB-V with Feedback

### 4.1 Procedures by Local Server

Confidence Bound for Reward and Cost.
To avoid the limitations of a greedy LLM selection strategy, i.e., $\operatorname*{arg\,max}_{k\in\mathcal{K}}$ $\hat{\mu}_{t,k}$ with $\hat{\mu}_{t,k}$ denoting the empirical estimate of the true mean of LLM $k$, which might result in the risk of overlooking superior LLM options, we implement the confidence bound (CB) method [, ]. This “optimistic” strategy promotes exploration among various LLM alternatives, thereby reducing the likelihood of consistently choosing sub-optimal options without considering potentially better LLMs. We define the confidence radius of CB as $\rho_{t,\mu_{k}}=\sqrt{\ln\left(\frac{2\pi^{2}Kt^{3}}{3\delta}\right)/2T_{t,
\mu_{k}}}$, which quantifies the exploration potential for the reward of LLM $k$ at round $t$, with $\delta$ in the range $(0,1]$. The term $T_{t,\mu_{k}}$ represents the number of times LLM $k$ has been selected in action $S_{t}$. Accordingly, the adjusted reward prediction for LLM $k$ is defined as $\bar{\mu}_{t,k}=\min\{\hat{\mu}_{t,k}+\alpha_{\mu}\rho_{t,\mu_{k}},1\}$, with $\alpha_{\mu}$ denoted as a positive control parameter.
Furthermore, we take into account the cost associated with each LLM. In light of the uncertainty introduced by complex queries, we adopt a cautious approach based on “pessimistic” strategy to ensure adherence to the cost budget. Specifically, the adjusted cost estimate for LLM $k$ at round $t$, $\underaccent{\bar}{c}_{t,k}$, is determined by $\underaccent{\bar}{c}_{t,k}=\max\{\hat{c}_{t,k}-\alpha_{c}\rho_{t,c_{k}},0\}$. Here, $\hat{c}_{t,k}$ is the empirical cost, $\alpha_{c}$ is a positive adjustment parameter, and confidence radiu $\rho_{t,c_{k}}=\sqrt{\ln\left(\frac{2\pi^{2}Kt^{3}}{3\delta}\right)/2T_{t,c_{k
}}}$, with $T_{t,c_{k}}$ denoting the count of LLM $k$ selection up to round $t$. Using this CB approach, we have the following lemma.

###### Lemma 1 .

For each round $t$ and LLM $k\in\mathcal{K}$, define $\mathcal{N}_{\mu}$ as the event where $\left|\hat{\mu}_{t,k}-\mu_{k}\right|<\rho_{t,\mu_{k}}$, and $\mathcal{N}_{c}$ as $\left|\hat{c}_{t,k}-c_{k}\right|<\rho_{t,c_{k}}$. Then, the probability of $\mathcal{N}_{\mu},\mathcal{N}_{c}$ occurring is at least $1-\delta/2$, i.e., $\operatorname{Pr}\{\mathcal{N}_{\mu}\}\geq 1-\delta/2$, $\operatorname{Pr}\{\mathcal{N}_{c}\}\geq 1-\delta/2$.

Please refer to Appendix D.1 for the proof. Lemma 1 underscores the high-probability events wherein the empirical estimates for both reward and cost closely align with their true means of LLMs.

Relaxation Strategy for LLM Combination Selection.
To mitigate the computational hardness of the LLM selection problem, the local server adopts a relaxed strategy while also ensuring that original sensitive user information is not transmitted to the scheduling cloud.
Specifically, let indicator variable $\mathbb{I}_{S}=\{z_{1},z_{2},\cdots,z_{K}\}\in\{0,1\}^{K}$ denote the selection status of LLM in $\mathcal{K}$, where $z_{k}=1$ indicates LLM $k$ is selected, and $z_{k}=0$ otherwise. $z_{k}\in\mathbb{I}_{S}$ is regarded as a continuous variable $\tilde{z}_{k}\in[0,1]$, with $\tilde{\boldsymbol{Z}}=\{\tilde{z}_{1},\tilde{z}_{2},\cdots,\tilde{z}_{K}\}$. We then introduce the three different relaxation strategies.

- •
Any Win Combination (AWC): Treating $r(S;\boldsymbol{\mu})=\left(1-\prod_{k\in S}(1-\mu_{k})\right)$ as a submodular function, we apply its multi-linear extension to accommodate the relaxed problem form:
$\tilde{r}\left(\tilde{\boldsymbol{Z}},\bar{\boldsymbol{\mu}}\right)=\sum_{S
\subseteq\mathcal{K}}\prod_{k\in S}\tilde{z}_{k}\prod_{k\notin S}(1-\tilde{z}_
{k}),$
ensuring convexity across any direction $\mathbb{I}_{\{i\}}-\mathbb{I}_{\{j\}}$ for distinct $i,j\in\mathcal{K}$ []. The closed form, $\tilde{r}\left(\tilde{\boldsymbol{Z}},\bar{\boldsymbol{\mu}}\right)=\left(1-
\prod_{k\in\mathcal{K}}(1-\bar{\mu}_{k}\tilde{z}_{k})\right)$, of this extension leads to the following relaxed optimization problem:
$\displaystyle\{\max\left(1-\prod_{k\in\mathcal{K}}\left(1-\bar{\mu}_{k}\tilde{
z}_{k}\right)\right):\sum_{k\in\mathcal{K}}\tilde{z}_{k}\leq N,\,\sum_{k\in
\mathcal{K}}\underline{c}_{t,k}\tilde{z}_{k}\leq\rho,\,0\leq\tilde{z}_{k}\leq 1
,\forall k\in\mathcal{K}\}.$
(3)
The common greedy algorithms, apt for such constrained continuous problems, can efficiently select $\tilde{z}_{k}$ values that optimize $1-\bar{\mu}_{k}\tilde{z}_{k}$ within constraints []. Subsequently, this optimization problem can be easily and effectively solved.
- •
Sum Up Combination (SUC): For $r(S;\boldsymbol{\mu})=\sum_{k\in S}\mu_{k}$, we choose the relaxed reward function to be $\tilde{r}(\tilde{\boldsymbol{Z}},\bar{\boldsymbol{\mu}})=\sum_{k\in\mathcal{K}
}\bar{\mu}_{k}\tilde{z}_{k}$ and the relaxed constraint optimization problem is:
$\displaystyle\{\max\sum_{k\in\mathcal{K}}\bar{\mu}_{k}\tilde{z}_{k}:\sum_{k\in
\mathcal{K}}\tilde{z}_{k}=N,\,\sum_{k\in\mathcal{K}}\underline{c}_{t,k}\tilde{
z}_{k}\leq\rho,\,0\leq\tilde{z}_{k}\leq 1,\forall k\in\mathcal{K}\}.$
(4)
For such relaxed linear programming, it can be easily solved in polynomial time [].
- •
All In Combination (AIC): Since the reward function $r(S;\boldsymbol{\mu})=\prod_{k\in S}\mu_{k}$ is the conjunctive reward function and the feasible actions are $\mathcal{S}_{2}=\{S\subseteq\mathcal{K}:|S|=N\}$, we select the relaxed function to be $\tilde{r}(\tilde{\boldsymbol{Z}},\bar{\boldsymbol{\mu}})=\prod_{k\in\mathcal{K
}}{\bar{\mu}_{k}}^{\tilde{z}_{k}}$, with the following optimization problem:
$\max\{\prod_{k\in\mathcal{K}}{\bar{\mu}_{k}}^{\tilde{z}_{k}}:\sum_{k\in
\mathcal{K}}\tilde{z}_{k}=N,\,\sum_{k\in\mathcal{K}}\underline{c}_{t,k}\tilde{
z}_{k}\leq\rho,\,0\leq\tilde{z}_{k}\leq 1,\forall k\in\mathcal{K}\}.$
(5)
The optimal solution in Eq. 5 is equivalent to solving the logarithmic linear programming $\arg\max\{\sum_{k\in\mathcal{K}}\tilde{z}_{k}\ln{\bar{\mu}_{k}}:\sum_{k\in
\mathcal{K}}\tilde{z}_{k}=N,\,\sum_{k\in\mathcal{K}}\underline{c}_{t,k}\tilde{
z}_{k}\leq\rho,\,0\leq\tilde{z}_{k}\leq 1\}$ by taking $\ln r(S;\bar{\boldsymbol{\mu}})$ as our objective, thus making the optimization problem more tractable.

The commonalities in the above three types of reward forms are in Appendix C.2. We will further describe the selection of multiple LLMs based on the continuous variable $\tilde{\boldsymbol{Z}}_{t}=\{\tilde{z}_{t,1},\tilde{z}_{t,2},\cdots,\tilde{z}_
{t,K}\}\in[0,1]^{K}$ at round $t$ in Section 4.2 on Procedures by Scheduling Cloud.

Online Update for Combinatorial LLMs.
In contrast to traditional offline approaches that use relaxation methods to address constrained optimization problems [, ], our strategy enables the local server to dynamically adapt LLM performance estimations for both reward and cost, leveraging continual feedback from the combinatorial LLM selection process.

Specifically, the partial combinatorial feedback model is employed to enhance reward prediction and cost estimation based on the LLM in the chosen actions, which are updated as follows:

$$ $\displaystyle\hat{\mu}_{t+1,k}=\cfrac{T_{t,\mu_{k}}\hat{\mu}_{t,k}+X_{t,k}}{T_ {t+1,\mu_{k}}},\quad\hat{c}_{t+1,k}=\cfrac{T_{t,c_{k}}\hat{c}_{t,k}+y_{t,k}}{T _{t+1,c_{k}}},\quad k\in\mathcal{F}_{t}.$ (6) $$

Note that for an action $S_{t}$, the local server only monitors the performance of the LLMs that are actually used in $S_{t}$, as not all LLMs are utilized for every type of task. For example, in the case of an AWC task type, if one LLM provides a satisfactory answer, the remaining LLMs are not utilized. In the AWC scenario, we use a conservative approach by ensuring that the budget threshold is met even if all selected LLMs $S_{t}$ are used, representing a “cautious” economic strategy.

###### Lemma 1 .

### 4.2 Procedures by Scheduling Cloud

Discretization Rounding for LLM Selection. In our architecture, the scheduling cloud can communicate with each local server, while the local servers do not directly communicate with each other. As described in Section 3, our focus is on elucidating the one-to-one relationship between a local server and the cloud. With fully original user data stored locally, the local server sends the relaxed continuous data $\tilde{\boldsymbol{Z}}_{t}$ to the scheduling cloud, which then coordinates various LLMs and selects a new action in response to requests. Inspired by the works of [, ], the synchronized cloud employs specialized discretization rounding algorithms based on reward models to convert the relaxed continuous data back into discrete form. By discretizing $\tilde{\boldsymbol{Z}}_{t}$, the scheduling cloud identifies a feasible set of LLMs $S_{t}$ to schedule and select for the current round $t$ (line 7 in Algorithm 1). The corresponding algorithms are tailored solutions for our versatile reward model and represent a significant effort to find suitable methods for our specific setup. However, since the design of these algorithms is not our core contribution, details are provided in Appendix B. Note that discretization rounding can reduce the complexity of LLM combination selection, as detailed in the computational efficiency comparison with direct discrete constrained optimization in Appendix E.3.

## 5 Performance Analysis

In this section, we conduct a comprehensive analysis of the theoretical performance (regret in Eq. (2), and violation in Eq. (1)) of C2MAB-V. Due to the page limit, we put the proof in Appendix D.

To state the analysis, we firstly give some definitions.
Let $o_{t,S}$ represent the probability that all LLMs within a selected action $S$ are observed at round $t$, and $r^{*}=\max_{S\in\mathcal{S}}r(S;\boldsymbol{\mu})\leq NL$ be the maximum reward for the $L$-Lipschitz reward function $r(S;\boldsymbol{\mu})$. Following [, ], we define $o^{*}=\min_{t\in\mathcal{T},S\in\mathcal{S}}o_{t,S}$ as the minimum observation probability across all feasible combinations of LLM selection, within the context of partial feedback mechanisms.
For the AWC scenario, as previously discussed, a subset may be chosen from multiple available options for an action $S_{t}$. In such cases, we provide the violation upper bound under the worst-case scenario, where each LLM in action $S_{t}$ fails to satisfy the user until the last one, i.e., $S_{t}=\mathcal{F}_{t}$ for all $t\in\mathcal{T}$.

###### Theorem 1 (Regret Bound) .

With $\delta=1/T$ in the confidence radius, the $\alpha$-approximate regret for the multi-LLM selection problem is bounded as follows, with probability at least $1-1/T$:

$$ $R(T)\leq\frac{2L}{o^{*}}\sqrt{2NKT\ln\left(\frac{2\pi^{2}KT}{3}\right)}+\left( K+1\right)r^{*}.$ (7) $$

###### Remark 1 .

The C2MAB-V framework extends the capabilities of existing CMAB models by incorporating long-term cost considerations, which is typically not present in previous works [, , , ]. When comparing with the linear CMAB model analyzed by [], which focuses on full rather than partial feedback, by setting $L=1$ and $o^{*}=1$, our regret bound aligns with theirs, adhering to the lower bound $\Omega(\sqrt{NKT})$ in [], up to a $\sqrt{\ln T}$ factor.
The comparability of our regret bound with other CMAB frameworks primarily stems from the efficient management of uncertainty in parameter estimation. A unique difference in our approach, however, is the implementation of a discretization process for the relaxed NP-hard problem. Despite this modification, due to our efforts on the shared attributes of different reward functions (which is not an easy task), the regret of C2MAB-V under the long-term cost constraint maintains the same order as those observed in other CMAB studies.

###### Theorem 2 (Violation Bound) .

With $\delta=1/T$ in the confidence radius, the constraint violation under the worst case is bounded as follows, with probability at least $1-1/T$:

$$ $V(T)\leq\sqrt{NK/T}\left(2\sqrt{2\ln\left(\frac{2\pi^{2}KT}{3}\right)}+\sqrt{ NK/T}\right).$ (8) $$

###### Remark 2 .

As discussed in Section 3, achieving a violation that diminishes rapidly is paramount. Our analysis reveals that the violation decreases at a rate of $\tilde{O}(\sqrt{\frac{K}{T}})$. As $T$ grows large, $V(T)$ approaches zero, suggesting an eventual elimination of violation. Furthermore, the overall violation is shown to be $\tilde{O}(\sqrt{KT})$, which is comparable to the order of regret. An interesting comparison arises with the work of [], which studies non-linear submodular rewards and linear costs within the context of knapsack constraints, specifically focusing on scenarios with known and fixed costs. This contrasts with our exploration of scenarios characterized by unknown stochastic costs. Despite the inherent challenges posed by unknown costs, our framework manages to attain an $\tilde{O}(\sqrt{T})$ approximate regret with an approximation ratio of $\alpha_{1}=1-\frac{1}{e}\approx 0.632$ under knapsack constraints. In contrast, the method from [] achieves an $\tilde{O}(\sqrt{T})$ approximate regret with a lower approximation ratio $\alpha_{2}\leq 0.5$. Thus, our approach secures a regret improvement of at least $\left(\alpha_{1}-\alpha_{2}\right)T\geq 0.132T$. Compared to [], which focuses on addressing constraints, our work expands to include non-linear rewards.

###### Theorem 1 (Regret Bound) .

###### Remark 1 .

###### Theorem 2 (Violation Bound) .

###### Remark 2 .

## 6 Performance Evaluation

Experiment Settings. We evaluate the three multi-LLM reward models (AWC, SUC, AIC) to represent different task types using the SciQ dataset [] across nine LLMs: ChatGPT-3.5, ERNIE 3.5, ChatGPT-4, ChatGLM2, Llama 2-7B, Llama 2-13B, Llama 2-70B, Mixtral-8x7B, and Claude 2 [, , , , ].(^3^33Our evaluation focuses exclusively on online learning from continuous feedback, incorporating offline pre-training, requiring offline training or GPU resources, or addressing cold-start issues. Studies, such as [], on accelerating online learning to overcome cold-start challenges, can be seamlessly integrated.) Costs are determined based on the official pricing. Results are averaged over 10 seeds with a 95% confidence interval; for more setting details, refer to Section E.1. The maximum number $N$ is set uniformly to 4, according to the size of the LLM set. Budget threshold $\rho$ is 0.45 for AWC, 0.5 for SUC, and 0.3 for AIC, according to reward models and official LLM pricing. More experiments (e.g., varying budget threshold, impacts of maximum number, and comparison to scenarios without relaxation or where only two LLMs are provided, or runtime) are available in Appendix E.

Comparison Benchmarks. Comparisons include consistently utilizing the expensive ChatGPT-4 [] and the cheap ChatGLM2 [], the online CMAB algorithm CUCB, [, ], which ignores constraints, Thompson Sampling, a mainstream probabilistic Bayesian online learning approach, [] and $\epsilon$-Greedy [], which alternates between using empirical means and selecting uniformly based on the adaptive $\epsilon_{t}=\text{min}\{1,\frac{2\sqrt{K}}{\sqrt{t}}\}$ (Here, works of [, ] are not compared due to being restricted to fixed costs or linear reward). The robustness of C2MAB-V is validated by varying the parameters $\alpha_{\mu},\alpha_{c}$ with values of (0.3, 0.05), (1, 0.05), (0.3, 0.01), and (1, 0.01), referred to as (a), (b), (c), (d).
Although the setting in [, , , ] totally differs from our online learning setting, we also pre-learned a fixed combination of multi-LLMs offline, which we applied to online queries. This enables to explore how online learning based on feedback can complement the adjustment of LLM selections in the offline domain. The results are provided in Appendix E.3 due to space constraints.

Performance Metric. To balance both reward and cost considerations, we assess performance using a reward/violation ratio, defined as the average per-round reward divided by the average per-round violation, i.e., $\frac{\sum_{\tau=1}^{t}r(S_{\tau},\boldsymbol{\mu})/t}{\sum_{\tau=1}^{t}V(\tau
)/t}$, with higher ratios indicating superior performance. More extended experimental results with the varying budget threshold and a greater emphasis on performance, along with detailed results for individual reward and violation, are provided in Appendix E.2.

Figure: (a) AWC
Refer to caption: x4.png

Evaluation Results. The performance of the reward/ violation ratio is illustrated in Fig. 4. ChatGLM2 is excluded since its rewards are significantly low, below 0.18, 0.10, and 0.0001 in the AWC, SUC, AIC models, despite no violations.
In the AWC model (Fig. 4(a)), C2MAB-V consistently outperforms other algorithms in all four parameter settings, achieving the highest reward/violation ratio. This underscores C2MAB-V’s superior ability to balance rewards against violations. Our algorithms converge in fewer than 1,000 rounds, significantly faster than the $\epsilon$-greedy algorithm, which requires nearly 10,000 rounds, even without incorporating offline information and relying entirely on online learning from scratch. The patterns observed for the SUC and AIC models (Fig. 4(b) and Fig. 4(c)) mirror those of the AWC model, further showing the robustness of C2MAB-V across different settings. When randomly evaluating C2MAB-V(c), it improves by at least 64.72% over $\epsilon$-Greedy, performs 3.9$\times$ better than Thompson Sampling, 4$\times$that of CUCB, and 6$\times$ that of Always using ChatGPT-4 across three tasks.
In summary, C2MAB-V maintains the highest reward/violation ratio under different $(\alpha_{\mu},\alpha_{c})$ for the ablation study on multi-LLM tasks aligning with our theoretical analysis.

## 7 Conclusion

In this paper, we introduce C2MAB-V, a cost-effective combinatorial online model with a versatile reward structure, designed to efficiently select multiple LLMs based on specific task requirements while adhering to budget constraints. C2MAB-V incorporates continual online feedback, and transform the NP-hard multi-LLM selection problem into a manageable relaxed form, with specified discretization rounding schemes designed to coordinate LLMs within a local-cloud architecture. Theoretical analysis of C2MAB-V provides novel and robust guarantees for the efficacy of the framework, including sublinear regret and a rapidly decreasing violation. Moreover, empirical evaluations with nine LLMs demonstrate C2MAB-V’s capability to balance performance with cost efficiency across three distinct types of collaborative multi-LLM tasks.

Looking ahead, there are several compelling directions for future research. For example, further development could focus on enhancing privacy protection and improving communication between multiple local servers within our local-cloud architecture. Additionally, incorporating contextual combinatorial multi-armed bandit approaches could more effectively capture user preferences.

## Appendix A Description Supplement

**Table 2: Summary of the main symbols.**
| Symbol | Description |
| --- | --- |
| $\mathcal{K}$ | Set of all LLMs, where $k$ indexes an LLM |
| $\mathcal{T}$ | Set of discrete time intervals or rounds |
| $S_{t}$ | Set of LLMs selected at round $t$, i.e., an action |
| $\mathcal{S}$ | Set of all possible combinations of LLM actions |
| $N$ | Maximum number of LLMs active simultaneously |
| $X_{t,k}$ | Reward associated with LLM $k$ at round $t$ |
| $y_{t,k}$ | Cost associated with LLM $k$ at round $t$ |
| $\mu_{k}$ | Unknown expected performance reward for LLM $k$ |
| $c_{k}$ | Unknown expected cost for LLM $k$ |
| $D_{q}$ | Distribution over queries |
| $l^{\text{in}}_{k}(q)$ | Number of input tokens by LLM $k$ for query $q$ |
| $l^{\text{out}}_{k}(q)$ | Random number of output tokens by LLM $k$ for query $q$ |
| $C_{k}$ | Cost per token for LLM $k$ |
| $D^{\text{out}}_{k}(q)$ | Distribution of output tokens for LLM $k$ given query $q$ |
| $\mathcal{Q}$ | Set of all queries |
| $\mathcal{F}_{t}$ | Subset of LLMs from which feedback is observed at round $t$ |
| $F_{t}$ | Cardinality of the subset $\mathcal{F}_{t}$ |
| $V(T)$ | Total budget violation over $T$ rounds |
| $R(T)$ | Total regret over $T$ rounds |
| $\rho$ | Budget guarantee threshold |
| $\delta$ | Probability parameter |
| $\hat{\mu}_{t,k}$ | Empirical estimate of the mean reward for LLM $k$ at round $t$ |
| $\hat{c}_{t,k}$ | Empirical estimate of the cost for LLM $k$ at round $t$ |
| $\alpha_{\mu}$ | Control parameter for adjusting the reward confidence bound |
| $\alpha_{c}$ | Control parameter for adjusting the cost confidence bound |
| $\rho_{t,\mu_{k}}$ | Confidence radius for the reward of LLM $k$ at round $t$ |
| $\rho_{t,c_{k}}$ | Confidence radius for the cost of LLM $k$ at round $t$ |
| $T_{t,\mu_{k}}$ | Count of selections of LLM $k$ concerning the reward up to round $t$ |
| $T_{t,c_{k}}$ | Count of selections of LLM $k$ concerning the cost up to round $t$ |
| $\tilde{z}_{k}$ | Continuous variable representing the selection status of LLM $k$ |
| $\tilde{\boldsymbol{Z}}$ | Vector of $\tilde{z}_{k}$ for all LLMs |
| $o_{t,S}$ | Probability all LLMs within action $S$ are observed at round $t$ |
| $r^{*}$ | Maximum reward for the $L$-Lipschitz reward function |
| $o^{*}$ | Minimum observation probability across all LLM combinations |
| $L$ | Lipschitz constant for the reward function |

## Appendix B Discretization Rounding Algorithms

Figure: Algorithm 2 Discretization Rounding for LLM Selection with AWC Reward Model

For the AWC reward, as detailed in Algorithm 2, the scheduling cloud initiates the process by setting up a vector $\boldsymbol{v}$ and identifying $K$ sets $\{\mathcal{B}_{1},\cdots,\mathcal{B}_{K}\}$ (line 2). Following this initialization, Algorithm 2 enters an iterative phase where it fine-tunes the composition of the sets $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$, aiming to keep the evolving solution within acceptable bounds while also seeking to optimize the reward (lines 4-10).
Subsequent steps involve refining $\mathcal{B}_{1}$ by excluding all elements found in set $\mathcal{G}$, and updating $\mathcal{A}_{i+1}$ to reflect the current state of $\mathcal{B}_{1}$ (line 11), which are designed to
gradually construct the final integrated solution.
Finally, Algorithm 2 designates $\mathcal{A}_{K}$ as the final action of selected LLM $S_{t}$ (line 13).
The validity of the resultant solution for LLM selection is underpinned by the lemma that follows (more discussions are in Section C.1).

###### Lemma 2 (Theorem 2.1 in [ 11 ] ) .

For a matroid $\mathcal{M}=(K,\mathcal{S})$ with a rank function $r:2^{N}\rightarrow{Z}_{+}$, the matroid polytope $P(\mathcal{M})$ is defined as the convex hull of the characteristic vectors of the independent sets $\mathcal{S}$, and the base polytope $B(\mathcal{M})$ as the convex hull of the characteristic vectors of the bases $\mathcal{B}$. For any two bases $\mathcal{B}_{1},\mathcal{B}_{2}\in\mathcal{B}$ and an element $i\in\mathcal{B}_{1}\backslash\mathcal{B}_{2}$, there exists an element $j\in\mathcal{B}_{2}\backslash\mathcal{B}_{1}$ such that $(\mathcal{B}_{1}\backslash\{i\})\cup\{j\}$ and $(\mathcal{B}_{2}\backslash\{j\})\cup\{i\}$ also belong to $\mathcal{B}$.

Figure: Algorithm 3 Discretization Rounding for LLM Selection with SUC/AIC Reward Models

For the SUC and AIC reward, as elucidated in Algorithm 3, the process commences with the examination of set $\mathcal{K}$ to identify LLM $k$ such that their corresponding value $\tilde{z}_{t,k}$ lies strictly between 0 and 1 (line 2). Subsequently, Algorithm 3 progresses by identifying a pair of distinct LLM, $k$ and $j$, within $\mathcal{K}$, both of which satisfy the criterion $0<\tilde{z}_{t,k},\tilde{z}_{t,j}<1$ (line 3).
The core of the discretization procedure involves computing the probabilities for adjusting the values of $\tilde{z}_{t,k}$ and $\tilde{z}_{t,j}$. This is achieved by determining $p$ and $q$, which represent the minimum increments and decrements needed for the adjustment, ensuring the discretization stays within bounds (line 4). With these parameters, Algorithm 3 probabilistically updates the pair $(\tilde{z}_{t,k},\tilde{z}_{t,j})$ to either increase $\tilde{z}_{t,k}$ and decrease $\tilde{z}_{t,j}$, or vice versa, thus balancing the overall distribution (line 5).
Finally, Algorithm 3 concludes by assembling the set $S_{t}$ comprised of all $k\in\mathcal{K}$ for which $\tilde{z}_{t,k}=1$, marking them as the selected LLM for the given timestep (line 7). This discrete selection process, grounded in the probabilistic adjustments of the $\tilde{z}$ values, systematically refines the selection of LLM.

One fundamental aspect of the reward $r(S;\boldsymbol{\mu})$ is its demonstration of the “diminishing marginal” property. Specifically, when a new LLM $k\in\mathcal{K}$ is added into action $S_{j}$ with a relatively larger set size, the resultant increase in reward is less than or equal to the increase observed when the same LLM $k$ is added to a smaller set $S_{i}$, given $S_{i}\subseteq S_{j}\subseteq\mathcal{S},i,j\in\mathcal{T}$. This behavior exemplifies a submodular function, formally expressed as follows:

$$ $r(S_{i}\cup\{k\};\boldsymbol{\mu})-r(S_{i};\boldsymbol{\mu})\geq r(S_{j}\cup\{ k\};\boldsymbol{\mu})-r(S_{j};\boldsymbol{\mu}).$ (9) $$

By applying the common greedy algorithm to solve the maximization of submodular function problem, we have the following lemma:

###### Lemma 3 (Theorem 1 in [ 63 ] ) .

The problem of maximizing a submodular function can be efficiently solved by a greedy algorithm, achieving an approximate ratio of $\alpha=(1-1/e)$ relative to the theoretical optimum.

This lemma indicates a significant efficiency in approximating the optimal solution of the submodular reward function $r(S;\boldsymbol{\mu})$.
Attentive readers will recognize that the previously discussed three different reward functions (AWC, SUC, and AIC reward) are actually special cases of submodular functions, all with monotonicity and Lipschitz coninuity
condition satisfied. However, we focus on designing and discussing different algorithmic components that offer better performance guarantees with $\alpha=1$ for SUC and AIC, rather than merely categorizing them as submodular functions.

###### Lemma 2 (Theorem 2.1 in [ 11 ] ) .

###### Lemma 3 (Theorem 1 in [ 63 ] ) .

## Appendix C Constraint and Reward Analysis

### C.1 Discussions on Constraint Type and Extended Task Type

In the context of C2MAB-V, we define ground base arms as $\mathcal{K}=\{1,...,K\}$ and denote $\mathcal{S}$ as combinatorially feasible sets, structured by specific combinatorial frameworks. A set $\mathcal{S}$ is linearizable if its convex hull forms a polytope in $\mathbb{R}^{K}$, meaning we can describe it using a finite number of linear constraints in $\mathbb{R}^{K}$, with $\mathcal{S}$ representing the integral solutions.
Matroids represent a prominent category of linearizable combinatorial sets, characterized by:

- •
Containment of the empty set: $\emptyset\in\mathcal{S}$.
- •
Downward closure: For any $S\in\mathcal{S}$ and $S^{\prime}\subset S$, it follows that $S^{\prime}\in\mathcal{S}$.
- •
Exchange property: For $S,S^{\prime}\in\mathcal{S}$ with $|S^{\prime}|>|S|$, there exists an $i\in S^{\prime}\setminus S$ such that $S\cup\{i\}\in\mathcal{S}$.

For any $S\in\mathcal{S}$, the rank function $rank(S)$ is defined as the maximal size of independent subsets in $S$, and $\mathbb{I}_{S}$ indicates a vector in $\{0,1\}^{K}$ representing the membership of elements in $S$. The polytope induced by $\mathcal{S}$, denoted as $P(\mathcal{S})$, is defined as the convex hull of these characteristic vectors, encapsulating the feasible integral solutions for $\mathcal{S}$.

The base of a matroid, $\mathcal{B}$, consists of independent sets of maximum size $N$, and the base polytope, $B(\mathcal{S})$, is the intersection of $P(\mathcal{S})$ with a hyperplane defined by $\sum_{k\in\mathcal{K}}\tilde{z}_{k}=N$.
Examples of matroids include:

- 1.
Cardinality-constrained subsets: Where $\mathcal{S}=\{S\subseteq\mathcal{K}:|S|\leq N\}$.
- 2.
Partition matroids: Defined over disjoint subsets $\mathcal{D}_{1},...,\mathcal{D}_{M}$ of $\mathcal{K}$ with cardinality constraints $d_{1},...,d_{M}$.
- 3.
Spanning trees: For a graph $G=(V,\mathcal{K})$, $\mathcal{S}$ includes all subsets of $\mathcal{K}$ that form a tree covering all vertices in $V$.

For each matroid type, the corresponding polytope $P(\mathcal{S})$ is detailed by a linear program, reflecting its combinatorial structure and constraints.

Attentive readers may have noticed that our main text’s discussion of three different types of tasks involving LLM collaboration, namely the AWC, SUC, and AIC rewards, as well as their corresponding constraints, fundamentally relates to concepts associated with matroids and their bases constrained by cardinality. To facilitate better understanding, we have organized this information as follows:

Matroids and Their Bases Subject to Cardinality Constraints. For a given fixed $N$, a subset $S\subset\mathcal{K}$ can belong to $\mathcal{S}$ either if $|S|\leq N$ or $|S|=N$. The former is considered in the AWC application to guarantee user satisfaction and experience, where each feasible action selects at most $N$ LLMs. The latter case is used in settings of SUC on independently tackling tasks and AIC on developing a whole project, where exactly $N$ LLMs are selected.

The corresponding induced polytopes $P(\mathcal{S})$ can be described by a vector $\tilde{\boldsymbol{Z}}\in\mathbb{R}^{K}$ that adheres to the following linear programs:

- 1.
For subsets with size at most $N$ (Inclusive Matroids):
$\displaystyle\sum_{k\in\mathcal{K}}\tilde{z}_{k}\leq N,$
(10)
$\displaystyle\tilde{z}_{k}\in[0,1],\,\text{for}\,\forall\,k\in\mathcal{K}.$
(11)
- 2.
For subsets with size exactly $N$ (Base Matroids):
$\displaystyle\sum_{k\in\mathcal{K}}\tilde{z}_{k}=N,$
(12)
$\displaystyle\tilde{z}_{k}\in[0,1],\,\text{for}\,\forall\,k\in\mathcal{K}.$
(13)

This structure clarifies the types of constraints applied to different combination of multiple LLMs for different task types.

However, the generalization of our framework design extends beyond this; it is also applicable to other types of settings. To illustrate this, consider a specific analytical example that employs Partition matroids as the foundational structure. Suppose we have a collection of disjoint subsets $\mathcal{D}_{1},\ldots,\mathcal{D}_{M}$ of $\mathcal{K}$, with $\mathcal{M}=\{1,2,...,M\}$. This can be interpreted as further domain-specific divisions within a complete set of LLMs, $\mathcal{K}$, such as dedicating groups of non-overlapping LLMs specialized in different subjects like mathematics and physics, or each LLM being responsible for a specific submodule within a large project. Additionally, the constraints can be expanded further; for example, each submodule may have different budget requirements. Formally, this involves $M$ cardinality constraints $d_{1},\ldots,d_{M}$. A subset $S\subset\mathcal{K}$ belongs to $\mathcal{S}$ if and only if $|S\cap\mathcal{D}_{i}|\leq d_{i}$ for some fixed $N$, where $\mathcal{S}=\{S\subseteq\mathcal{K}:|S\cap\mathcal{D}_{i}|\leq d_{i},\,i\in
\mathcal{M}\}$. This combinatorial feasible set $\mathcal{S}$ can model products that belong to mutually exclusive categories.

The corresponding induced polytope $P(\mathcal{S})$ can be described by $\tilde{\boldsymbol{Z}}\in\mathbb{R}^{K}$ that follows the linear program:

$$ $\displaystyle\sum_{i\in\mathcal{D}_{j}}\tilde{z}_{k}\leq d_{j},\,\forall\,j\in \mathcal{M}$ $\displaystyle\tilde{z}_{k}\in[0,1],\,\text{for}\,\forall\,k\in\mathcal{K}.$ $$

For instance, utilizing the constraints outlined above, combined with the AIC reward structure, we can easily apply our model to coordinate tasks like a development project where each LLM is responsible for different non-overlapping modules. This allows for online selection of an optimal combination of multiple LLMs tailored to the specific needs of the project. Alternatively, by combining partition matroids and SUC reward, it is possible to address a unified teaching task with different LLMs focusing on independent but complementary academic disciplines. Thus, within the S framework, based on our defined reward structure and various types of constraints, we can effectively handle a wide range of collaborative tasks among multiple LLMs.

Based on the above analysis, regarding extended tasks, such as identifying the set of LLMs to be deployed, are addressed, the strategy lacks specificity on which LLM should be assigned to a particular task (as in the SUC case) or which LLM should handle a given sub-module (as in the AIC case). This issue can be mitigated by transitioning from cardinality-constrained subsets to partition matroids. Specifically, a smaller and more suitable subset of LLMs can be preselected for specific query tasks. For example, in mathematical problems, the selection space for LLMs could be restricted to those fine-tuned for mathematical queries, rather than choosing from the full set of LLMs. This targeted selection not only reduces the search space but also accelerates the online learning process by avoiding the misallocation of resources.

Alternatively, the selection process can rely entirely on online learning through match bandit. The match bandit problem, a variant of the maximum weight matching problem, is modeled as a bipartite graph $G=(Q,K,E)$, where $Q$ represents query tasks, $K$ represents LLMs, and $E$ represents weighted edges denoting the probability of assigning a query task $q$ to an LLM $k$. The Combinatorial MAB proposed in our paper can naturally be transformed into this bipartite graph structure based on .[, ].

### C.2 Exploration on Attributes of Reward Functions

Next, we examine the common attributes of the three defined reward functions. All three corresponding constraint optimization problems (defined in Eq. 3, Eq. 4, and Eq. 5) are linear programming (LP) models with $K$ variables. The optimal solutions for these models, i.e., $\alpha=1-e$ for the AWC reward and $\alpha=1$ for the SUC and AIC rewards, can be determined in polynomial time [, , ].

Next, we define the discretization procedure $\sigma$ used in Algorithm 2 and Algorithm 3 as $S_{t}=\sigma(\tilde{\boldsymbol{Z}}_{t})$, where $\mathbb{I}_{S^{*}_{t}}$ represents the feasible solutions of the optimization problem. The indicator variable $\mathbb{I}_{S}=\{z_{1},z_{2},\cdots,z_{K}\}\in\{0,1\}^{K}$ denotes the selection status of LLMs in the set $\mathcal{K}$. Referencing Theorem 1.1 in [] for Algorithm 2 and Properties P1 and P2 in [] for Algorithm 3, it is established that $\mathbb{E}_{S\sim\sigma(\tilde{\boldsymbol{Z}}_{t})}[\mathbb{I}_{S}]=\tilde{
\boldsymbol{Z}}_{t}$ for any $S\sim\sigma(\tilde{\boldsymbol{Z}}_{t})$ within the feasible set $\mathcal{S}$. Consequently, we can conclude that:

$$ $r\left(S,\boldsymbol{\mu}\right)=\begin{cases}\left(1-\prod_{k\in S}(1-\mu_{k} )\right)&=\quad\tilde{r}\left(\mathbb{I}_{S},\boldsymbol{\mu}\right),\quad \text{AWC reward},\\ \qquad\sum_{k\in S}\mu_{k}&=\quad\tilde{r}\left(\mathbb{I}_{S},\boldsymbol{\mu }\right),\quad\text{SUC reward},\\ \qquad\prod_{k\in S}\mu_{k}&=\quad\tilde{r}\left(\mathbb{I}_{S},\boldsymbol{ \mu}\right),\quad\text{AIC reward}.\end{cases}$ (14) $$

Following Eq. 14, we can then deduce that
$r\left(S^{*}_{t},\bar{\boldsymbol{\mu}}_{t}\right)=\tilde{r}\left(\mathbb{I}_{
S_{t}^{*}},\bar{\boldsymbol{\mu}}_{t}\right)$.

Finally, we establish a relationship between the actual reward function and its relaxed counterpart by demonstrating the inequality $\mathbb{E}\left[\tilde{r}\left(\mathbb{I}_{S_{t}},\boldsymbol{\mu}\right)
\right]\geq\tilde{r}(\tilde{\boldsymbol{Z}}_{t},\boldsymbol{\mu})$.

❶ For the AWC reward, the proof can be streamlined as follows:
Based on Algorithm 2, the process transitions from an initial continuous solution $\tilde{\boldsymbol{Z}}$ to a final integral solution $\boldsymbol{X}_{s}=\mathbb{I}_{\mathcal{S}}$ over $s$ steps, resulting in the sequence $(\boldsymbol{X}_{1},...,\boldsymbol{X}_{s})$, where $\boldsymbol{X}_{1}=\tilde{\boldsymbol{Z}}$ and $\boldsymbol{X}_{s}=\mathbb{I}_{\mathcal{S}}$.
Utilizing Lemma B.1 and Lemma 4.1 from [], at any round $t$, we can represent $\boldsymbol{X}_{t}$ as a weighted sum of indicator functions for bases, $\boldsymbol{X}_{t}=\sum_{l=1}^{k}p_{l}\mathbb{I}_{\mathcal{B}_{l}}$, where $\mathcal{B}_{l}$ represents the bases. The state transition to $\boldsymbol{X}_{t+1}$ is modeled as follows:

$$ $\boldsymbol{X}_{t+1}=\begin{cases}\boldsymbol{X}_{t}+p_{2}(\mathbb{I}_{\{i\}}- \mathbb{I}_{\{j\}}),&\text{with probability}\frac{p_{1}}{p_{1}+p_{2}},\\ \boldsymbol{X}_{t}-p_{1}(\mathbb{I}_{\{i\}}-\mathbb{I}_{\{j\}}),&\text{with probability}\frac{p_{2}}{p_{1}+p_{2}}.\end{cases}$ $$

Defining $a=\boldsymbol{X}_{t}$ and $\vartheta=\mathbb{I}_{\{i\}}-\mathbb{I}_{\{j\}}$, we let $h(p)=\tilde{r}(\boldsymbol{X}_{t}+p\vartheta,\boldsymbol{\mu})$. The expected value of $\tilde{r}$ at $t+1$ given $\boldsymbol{X}_{t}$ is then

$$ $\mathbb{E}[\tilde{r}(\boldsymbol{X}_{t+1},\boldsymbol{\mu})|\boldsymbol{X}_{t} ]=\frac{p_{1}}{p_{1}+p_{2}}\tilde{r}(\boldsymbol{X}_{t}+p_{2}\vartheta, \boldsymbol{\mu})+\frac{p_{2}}{p_{1}+p_{2}}\tilde{r}(\boldsymbol{X}_{t}-p_{1} \vartheta,\boldsymbol{\mu}),$ $$

which simplifies to $\frac{p_{1}}{p_{1}+p_{2}}h(p_{2})+(1-\frac{p_{1}}{p_{1}+p_{2}})h(-p_{1})$. Due to the convexity of $h$, this is at least $h(0)=\tilde{r}(\boldsymbol{X}_{t},\boldsymbol{\mu})$.
Applying this inequality recursively from $t=1$ to $s-1$ via the tower rule, we conclude that $\mathbb{E}[\tilde{r}(\boldsymbol{X}_{s},\boldsymbol{\mu})]\geq\tilde{r}(
\boldsymbol{X}_{1},\boldsymbol{\mu})=\tilde{r}(\tilde{\boldsymbol{Z}},
\boldsymbol{\mu})$, thereby satisfying $\mathbb{E}\left[\tilde{r}\left(\mathbb{I}_{S_{t}},\boldsymbol{\mu}\right)
\right]\geq\tilde{r}(\tilde{\boldsymbol{Z}}_{t},\boldsymbol{\mu})$.

❷ For the SUC reward, recall that
indicator variable $\mathbb{I}_{S}=\{z_{1},z_{2},\cdots,z_{K}\}\in\mathbb{R}^{K}$, with $z_{k}=1$ indicating LLM $k$ selected, and $z_{k}=0$ otherwise, and $\tilde{z}_{k}\in[0,1]$ is a continuous variable
, with $\tilde{\boldsymbol{Z}}=\{\tilde{z}_{1},\tilde{z}_{2},\cdots,\tilde{z}_{K}\}$. On the basis of Eq. 14, it holds that $\mathbb{E}_{S\sim\sigma(\tilde{\boldsymbol{Z}})}[\tilde{r}(\mathbb{I}_{S},
\boldsymbol{\mu})]=\sum_{k\in\mathcal{K}}\mathbb{E}[z_{k}]\mu_{k}=\sum_{k\in
\mathcal{K}}\tilde{z}_{k}\mu_{k}=\tilde{r}(\tilde{\boldsymbol{Z}},\boldsymbol{
\mu})$. This fulfills that $\mathbb{E}\left[\tilde{r}\left(\mathbb{I}_{S_{t}},\boldsymbol{\mu}\right)
\right]\geq\tilde{r}(\tilde{\boldsymbol{Z}}_{t},\boldsymbol{\mu})$.

❸ For the AIC reward, consider the vector $\boldsymbol{Z}\vcentcolon=(z_{1},\dots,z_{K})\in\mathbb{R}^{K}$, where $\tilde{r}(\boldsymbol{Z},\boldsymbol{\mu})=\exp\left(\sum_{k\in\mathcal{K}}z_{
k}\ln\mu_{k}\right)$ is demonstrated to be a convex function with respect to $\boldsymbol{Z}$. This is evidenced by the Hessian matrix of $\tilde{r}(\boldsymbol{Z},\boldsymbol{\mu})$, denoted as $H_{\tilde{r}}(\boldsymbol{Z})\in\mathbb{R}^{K}\times\mathbb{R}^{K}$. The entries of $H_{\tilde{r}}(\boldsymbol{Z})$ are given by $H_{\tilde{r}}(\boldsymbol{Z})_{i,j}=\ln\mu_{i}\ln\mu_{j}\tilde{r}(\boldsymbol{
Z},\boldsymbol{\mu})$. The Hessian can be expressed as $H_{\tilde{r}}(\boldsymbol{Z})=\tilde{r}(\boldsymbol{Z},\boldsymbol{\mu})
\boldsymbol{W}\boldsymbol{W}^{T}$, where $\boldsymbol{W}$ is the column vector $\boldsymbol{W}\vcentcolon=(\ln\mu_{1},\dots,\ln\mu_{K})$. Consequently, $H_{\tilde{r}}(\boldsymbol{Z})$ is positive semi-definite because for any vector $\boldsymbol{x}\in\mathbb{R}^{K}$, we have $\boldsymbol{x}^{T}H_{\tilde{r}}(\boldsymbol{Z})\boldsymbol{x}=\tilde{r}(
\boldsymbol{Z},\boldsymbol{\mu})(\boldsymbol{W}^{T}x)^{2}\geq 0$, given that $\tilde{r}(\boldsymbol{Z},\boldsymbol{\mu})\geq 0$ and $(\boldsymbol{W}^{T}\boldsymbol{x})^{2}\geq 0$. Applying Jensen’s inequality and acknowledging that $\mathbb{E}_{\boldsymbol{Z}}[z_{k}]=\tilde{z}_{k}$ as per Eq. 14, it follows that $\mathbb{E}_{\boldsymbol{Z}}[\exp\left(\sum_{k\in\mathcal{K}}z_{k}\ln\mu_{k}
\right)]\geq\exp\left(\sum_{k\in\mathcal{K}}\mathbb{E}_{\boldsymbol{Z}}[z_{k}]
\ln\mu_{k}\right)=\tilde{r}(\tilde{\boldsymbol{Z}},\boldsymbol{\mu})$, thereby ensuring that $\mathbb{E}\left[\tilde{r}\left(\mathbb{I}{S_{t}},\boldsymbol{\mu}\right)\right
]\geq\tilde{r}(\tilde{\boldsymbol{Z}}_{t},\boldsymbol{\mu})$.

## Appendix D Proof Appendix

### D.1 Proof of Lemma 1

###### Proof.

We aim to establish a bound for the probability given by:

$$ $\Pr\{\neg\mathcal{K}_{\mu}\}=\Pr\left\{\exists t\in\mathcal{T},k\in\mathcal{K} ,|\hat{\mu}_{t,k}-\mu_{k}|\geq\sqrt{\frac{\ln(\frac{2\pi^{2}Kt^{3}}{3\delta})} {2T_{t,\mu_{k}}}}\right\}$ $$

which can be expressed as follows:

$$ $\displaystyle\leq\sum_{k=1}^{K}\sum_{t=1}^{T}\sum_{s=1}^{t}\Pr\left\{|\hat{\mu }_{t,k}-\mu_{k}|\geq\sqrt{\frac{\ln(\frac{2\pi^{2}Kt^{3}}{3\delta})}{2T_{t,\mu _{k}}}},T_{t,\mu_{k}}=s\right\}$ $\displaystyle\leq\sum_{k=1}^{K}\sum_{t=1}^{T}\sum_{s=1}^{t}\frac{3\delta}{\pi^ {2}K}\frac{1}{t^{3}}$ $\displaystyle\leq\frac{\delta}{2}.$ $$

The initial inequality employs the union bound over the indices $k,t,$ and $s$. The subsequent inequality leverages the Chernoff-Hoeffding inequality (see Lemma 5) when $T_{s,\mu_{k}}=s$ and $\hat{\mu}_{t,k}=\frac{1}{s}\sum_{j=1}^{s}\mu_{k}^{j}$ is the sample mean of $s$ independent and identically distributed random variables $\mu_{k}^{1},\ldots,\mu_{k}^{s}$, each representing the $j$-th observation of index $k$. The final inequality is justified by the series sum $\sum_{k=1}^{\infty}\frac{1}{k^{2}}=\frac{\pi^{2}}{6}$.

Analogously, for the probability concerning $\neg\mathcal{K}_{c}$, we derive:

$$ $\displaystyle\Pr\{\neg\mathcal{K}_{c}\}$ $\displaystyle=\Pr\left\{\exists t\in\mathcal{T},k\in\mathcal{K},|\hat{c}_{t,k} -c_{k}|\geq\sqrt{\frac{\ln(\frac{2\pi^{2}Kt^{3}}{3\delta})}{2T_{t,c_{k}}}}\right\}$ $\displaystyle\leq\sum_{k=1}^{K}\sum_{t=1}^{T}\sum_{s=1}^{t}\Pr\left\{|\hat{c}_ {t,k}-c_{k}|\geq\sqrt{\frac{\ln(\frac{2\pi^{2}Kt^{3}}{3\delta})}{2T_{t,c_{k}}} },T_{t,c_{k}}=s\right\}$ $\displaystyle\leq\sum_{k=1}^{K}\sum_{t=1}^{T}\sum_{s=1}^{t}\frac{3\delta}{\pi^ {2}K}\frac{1}{t^{3}}$ $\displaystyle\leq\frac{\delta}{2}.$ $$

Through consideration of the complementary events, we ascertain that the events $\mathcal{K}_{\mu}$ and $\mathcal{K}_{c}$ each occur with a probability of at least $1-\frac{\delta}{2}$, respectively.
∎

###### Proof.

### D.2 Comprehensive Proof of Theorem 1

General regret proof analysis

The proof of Theorem 1 is structured into three pivotal segments. Initially, it focuses on transforming the total regret into over-estimation regret (Step 1: Reduce to the over-estimation regret). Subsequently, it addresses the conversion of partially observed actions to fully observed ones, leveraging the Lipschitz condition to dissect the regret associated with an action into the regrets of its constituent base arms (Step 2: Deal with the partial observation and apply the $L$-Lipschitz condition). The final segment synthesizes these elements through meticulous mathematical manipulations (Step 3: Derivation to get the final regret bound).

We begin with a sketch of the proof to enhance comprehension. From Lemma 1, for every round $t\in\mathcal{T}$ and LLM $k\in\mathcal{K}$, the inequality $\left|\hat{\mu}_{t,k}-\mu_{k}\right|<$ $\sqrt{\ln\left(\frac{2\pi^{2}Kt^{3}}{3\delta}\right)/2T_{t,\mu_{k}}}$ is satisfied with probability at least $1-\delta/2$. By setting $\delta=1/T$, we can assert with high probability that $\mu_{k}\leq\hat{\mu}_{t,k}+\rho_{\mu,t,k}=\bar{\mu}_{t,k}$ and $c_{k}\geq\hat{c}_{t,k}-\rho_{c,t,k}=\underaccent{\bar}{c}_{t,k}$.

Given the monotonicity property of reward function $r(S;\boldsymbol{\mu})$ and $r\left(S^{*}_{t},\bar{\boldsymbol{\mu}}_{t}\right)=\tilde{r}\left(\mathbb{I}_{
S_{t}^{*}},\bar{\boldsymbol{\mu}}_{t}\right)$, we derive the following inequality:

$$ $\displaystyle R(T)\leq\mathbb{E}\left[\alpha r\left(S^{*}_{t},\bar{\boldsymbol {\mu}}_{t}\right)-r\left(S_{t},\boldsymbol{\mu}\right)\right]\leq\mathbb{E} \left[\tilde{r}\left(\tilde{\boldsymbol{Z}}_{t},\bar{\boldsymbol{\mu}}_{t} \right)-r\left(S_{t},\boldsymbol{\mu}\right)\right].$ (15) $$

Substituting $\mathbb{E}\left[\mathbb{E}\left[\tilde{r}\left(\mathbb{I}_{S_{t}},\bar{
\boldsymbol{\mu}}_{t}\right)\right]\right]=$ $\mathbb{E}\left[\tilde{r}\left(\mathbb{I}_{S_{t}},\bar{\boldsymbol{\mu}}_{t}
\right)\right]=\mathbb{E}\left[R\left(S_{t},\bar{\boldsymbol{\mu}}_{t}\right)\right]$ into Eq. (15), we obtain:

$$ $\displaystyle R(T)\leq\mathbb{E}\underbrace{\left[\tilde{r}\left(\tilde{ \boldsymbol{Z}}_{t},\bar{\boldsymbol{\mu}}_{t}\right)-\mathbb{E}\left[\tilde{r }\left(\mathbb{I}_{S_{t}},\bar{\boldsymbol{\mu}}_{t}\right)\right]\right]}_{ \text{regret (a)}}+\mathbb{E}\underbrace{\left[r\left(S_{t},\bar{\boldsymbol{ \mu}}_{t}\right)-r\left(S_{t},\boldsymbol{\mu}\right)\right]}_{\text{regret (b ) }}.$ (16) $$

Regret (a) arises from the relaxation and discretization
, which is no greater than zero due to the inequality $\mathbb{E}\left[\tilde{r}\left(\mathbb{I}_{S_{t}},\bar{\boldsymbol{\mu}}_{t}
\right)\right]$$\geq\tilde{r}\left(\tilde{\boldsymbol{Z}}_{t},\bar{\boldsymbol{\mu}}_{t}\right)$. Regret (b) is a result of the overestimating of rewards. Following the analysis idea in [] to bound this over-estimation regret, the observation probability $o^{*}$ is used to derive:

$$ $\displaystyle\quad\mathbb{E}\left[r\left(S_{t},\bar{\boldsymbol{\mu}}_{t} \right)-r\left(S_{t},\boldsymbol{\mu}\right)\right]$ $\displaystyle\leq\frac{1}{o^{*}}\mathbb{E}\left[\sum_{t=1}^{T}r\left(S_{t}, \bar{\boldsymbol{\mu}}_{t}\right)-r\left(S_{t},\boldsymbol{\mu}\right)\mathbb{ I}\left\{F_{t}=\left|S_{t}\right|\right\}\right]$ $\displaystyle\leq\frac{L}{o^{*}}\mathbb{E}\left[\sum_{t=1}^{T}\sum_{\begin{ subarray}{c}k\in\mathcal{F}_{t}\end{subarray}}\left|\bar{\mu}_{t,k}-\mu_{t,k} \right|\right]$ $\displaystyle\leq\frac{L}{o^{*}}\mathbb{E}\left[\sum_{t=1}^{T}\sum_{\begin{ subarray}{c}k\in\mathcal{F}_{t}\end{subarray}}2\rho_{t,\mu_{k}}\right].$ $$

By synthesizing the bounds of regret components (a) and (b), we can establish an upper bound for the regret.

We proceed with a comprehensive proof. This detailed analysis is predicated on the concurrent occurrence of both $\mathcal{K}_{\mu}$ and $\mathcal{K}_{c}$ events, with probability at least $1-\delta$ (by Lemma 1).
In scenarios where $\mathcal{K}_{\mu}$ and $\mathcal{K}_{c}$ fail to occur, the expected additional regret is bounded by $r^{*}\delta T$.

Step 1: Reduce to the over-estimation regret

We begin by recalling the definition of the optimal action $S^{*}_{t}\triangleq\operatorname*{arg\,max}_{S\in\mathcal{S}}r(S;\boldsymbol{
\mu}_{t})$ for each round $t$, where $\mathcal{S}$ encompasses all feasible actions.
And $\tilde{\boldsymbol{Z}}_{t}$ is the $\alpha$-approximate solution of $\{\max\tilde{r}(\tilde{\boldsymbol{Z}},\bar{\boldsymbol{\mu}}):\tilde{
\boldsymbol{Z}}\in P(\mathcal{S}),\sum_{k\in\mathcal{K}}\underline{c}_{t,k}
\tilde{z}_{k}\leq\rho\}$, where $P(\mathcal{S})$ is defined as the convex hull induced by $\mathcal{S}$:

$$ $P(\mathcal{S})\coloneqq\text{conv}\{\mathbb{I}_{S}:S\in\mathcal{S}\}=\{\tilde{ \boldsymbol{Z}}\in\mathbb{R}^{K}:\tilde{z}_{k}\in[0,1],\sum_{k\in S}\tilde{z}_ {k}\leq rank(S),\,\text{for}\,\forall k\in\mathcal{K},\forall S\subseteq \mathcal{K}\}.$ $$

Denote the discretization procedure $\sigma$ for Algorithm 2 and Algorithm 3 as $S_{t}=\sigma(\tilde{\boldsymbol{Z}}_{t})$.
The feasible solution $S_{t}=\sigma(\tilde{\boldsymbol{Z}}_{t})$ guarantees $r(S;\boldsymbol{\mu})\geq\alpha\cdot r(S^{*};\boldsymbol{\mu})$. Under high probability events $\mathcal{K}_{\mu}$ and $\mathcal{K}_{c}$, the constraints $\mu_{k}\leq\hat{\mu}_{t,k}+\rho_{t,\mu_{k}}=\bar{\mu}_{t,k}$ and $c_{k}\geq\hat{c}_{t,k}-\rho_{t,c_{k}}=\underline{c}_{t,k}$ are satisfied.
We first apply the monotonicity of the reward function and the property of the multi-linear extension to reduce the total regret to the over-estimation regret,

$$ $\displaystyle\quad\,\mathbb{E}[(\alpha r(S^{*}_{t},\boldsymbol{\mu})-r(S_{t}, \boldsymbol{\mu}))]$ $\displaystyle\leq\mathbb{E}[(\alpha r(S^{*}_{t},\bar{\boldsymbol{\mu}}_{t})-r( S_{t},\boldsymbol{\mu}))]$ (17) $\displaystyle\leq\mathbb{E}[(\tilde{r}(\tilde{\boldsymbol{Z}}_{t},\bar{ \boldsymbol{\mu}}_{t})-r(S_{t},\boldsymbol{\mu}))]$ (18) $\displaystyle=\mathbb{E}[(\underbrace{\tilde{r}(\tilde{\boldsymbol{Z}}_{t}, \bar{\boldsymbol{\mu}}_{t})-\mathbb{E}_{S_{t}\sim{\sigma(\tilde{\boldsymbol{Z} }_{t})}}[\tilde{r}(\mathbb{I}_{S_{t}},\bar{\boldsymbol{\mu}}_{t})])}_{\text{ regret (a)}}+\underbrace{(r(S_{t},\bar{\boldsymbol{\mu}}_{t})-r(S_{t}, \boldsymbol{\mu})}_{\text{ regret (b)}})]$ (19) $\displaystyle\leq\mathbb{E}[\underbrace{r(S_{t},\bar{\boldsymbol{\mu}}_{t})-r( S_{t},\boldsymbol{\mu})}_{{\text{Over-estimation regret}}}]$ (20) $$

Here, Eq. 17 exploits the action reward function’s monotonicity, while Eq. 18 is due to the equivalency of $r(S^{*}_{t},\bar{\boldsymbol{\mu}}_{t})$ and $\tilde{r}(\mathbb{I}_{S^{*}_{t}},\bar{\boldsymbol{\mu}}_{t})$ for any feasible action $S\in\mathcal{S}$, i.e., $r(S^{*}_{t},\bar{\boldsymbol{\mu}}_{t})=\tilde{r}(\mathbb{I}_{S^{*}_{t}},\bar{
\boldsymbol{\mu}}_{t})$. Recall that $\mathbb{I}_{S^{*}_{t}}=\{z_{1},z_{2},\cdots,z_{K}\}\in\{0,1\}^{K}$ denotes one feasible solution for the optimal selection status of base arms in $\mathcal{K}$ at round $t$
of the following three relaxed continuous optimization problems:

- 1.
Any Win Combination (AWC):
$\displaystyle\max\tilde{r}(\tilde{\boldsymbol{Z}},\bar{\boldsymbol{\mu}})=
\left(1-\prod_{k\in\mathcal{K}}\left(1-\bar{\mu}_{k}\bar{\tilde{z}}_{k}\right)\right)$
$\displaystyle\mathrm{s.t.}$
$\displaystyle\sum_{k\in\mathcal{K}}\tilde{z}_{k}\leq N,$
$\displaystyle\sum_{k\in\mathcal{K}}\underline{c}_{t,k}\tilde{z}_{k}\leq\rho,$
$\displaystyle 0\leq\tilde{z}_{k}\leq 1,\forall k\in\mathcal{K},$
where $\tilde{r}\left(\tilde{\boldsymbol{Z}},\bar{\boldsymbol{\mu}}\right)=\left(1-
\prod_{k\in\mathcal{K}}(1-\bar{\mu}_{k}\tilde{z}_{k})\right)$ is the closed form of the multi-linear extension
$\tilde{r}\left(\tilde{\boldsymbol{Z}},\bar{\boldsymbol{\mu}}\right)=\sum_{S
\subseteq\mathcal{K}}\prod_{k\in S}\tilde{z}_{k}\prod_{k\notin S}(1-\tilde{z}_
{k})$.
- 2.
Sum Up Combination (SUC):
$\displaystyle\max\tilde{r}(\tilde{\boldsymbol{Z}},\bar{\boldsymbol{\mu}})=\sum
_{k\in\mathcal{K}}\bar{\mu}_{k}\tilde{z}_{k}$
$\displaystyle\mathrm{s.t.}$
$\displaystyle\sum_{k\in\mathcal{K}}\tilde{z}_{k}=N,$
$\displaystyle\sum_{k\in\mathcal{K}}\underline{c}_{t,k}\tilde{z}_{k}\leq\rho,$
$\displaystyle 0\leq\tilde{z}_{k}\leq 1,\forall k\in\mathcal{K}.$
- 3.
All In Combination (AIC):
$\displaystyle\max\tilde{r}(\tilde{\boldsymbol{Z}},\bar{\boldsymbol{\mu}})=
\prod_{k\in\mathcal{K}}{\bar{\mu}_{k}}^{\tilde{z}_{k}}$
$\displaystyle\mathrm{s.t.}$
$\displaystyle\sum_{k\in\mathcal{K}}\tilde{z}_{k}=N,$
$\displaystyle\sum_{k\in\mathcal{K}}\underline{c}_{t,k}\tilde{z}_{k}\leq\rho,$
$\displaystyle 0\leq\tilde{z}_{k}\leq 1,\forall k\in\mathcal{K},$
whose optimal solution is equivalent to solving the LP program $\arg\max\{\sum_{k\in\mathcal{K}}\tilde{z}_{k}\ln{\bar{\mu}_{k}}:\sum_{k\in
\mathcal{K}}\tilde{z}_{k}=N,\,\sum_{k\in\mathcal{K}}\underline{c}_{t,k}\tilde{
z}_{k}\leq\rho,\,0\leq\tilde{z}_{k}\leq 1\}$ by taking $\ln r(S;\boldsymbol{\mu})$ as our objective.

Here,
$\tilde{\boldsymbol{Z}}=\{\tilde{z}_{1},\tilde{z}_{2},\cdots,\tilde{z}_{K}\}$ represents the selected probability for each base arm, with $\tilde{z}_{k}\in[0,1]$ reflecting the probability of selecting the $k$-th base arm.

Moreover, Eq. 19 is because $\mathbb{E}[\mathbb{E}_{S_{t}\sim{\sigma(\tilde{\boldsymbol{Z}}_{t})}}[\tilde{r
}(\mathbb{I}_{S_{t}},\bar{\boldsymbol{\mu}}_{t})]]=\mathbb{E}[\tilde{r}(
\mathbb{I}_{S_{t}},\bar{\boldsymbol{\mu}}_{t})]=\mathbb{E}[r(S_{t},\bar{
\boldsymbol{\mu}}_{t})]$ ($S_{t}\sim{\sigma(\tilde{\boldsymbol{Z}}_{t})}$ denotes selecting $S_{t}$ from Algorithm 2 and Algorithm 3), and Eq. 20 holds because of the convex-preserving property: $\mathbb{E}\left[\tilde{r}\left(\mathbb{I}_{S_{t}},\bar{\boldsymbol{\mu}}_{t}
\right)\right]$$\geq\tilde{r}\left(\tilde{\boldsymbol{Z}}_{t},\bar{\boldsymbol{\mu}}_{t}\right)$.
Here we can see paralleling approaches in [, , ] that bounds the over-estimation regret $\mathbb{E}[r(S_{t},\bar{\boldsymbol{\mu}}_{t})-r(S_{t},\boldsymbol{\mu})]$.
We will follow the idea in [] but a more simplified proof to deal with this over-estimation regret.

Step 2: Deal with the partial observation and apply the $L$-Lipschitz condition

Define the over-estimation regret for C2MAB-V at round $t$ as $\bar{reg}(S_{t},\bar{\boldsymbol{\mu}}_{t})=r(S_{t},\bar{\boldsymbol{\mu}}_{t}
)-r(S_{t},\boldsymbol{\mu})$, where $S_{t}$ denotes the action and $\bar{\boldsymbol{\mu}}_{t}$ represents the upper confidence bound (UCB) value of base arms at round $t$. The history of C2MAB-V prior to selecting action $S_{t}$, denoted as $\mathcal{H}_{t}$, encompasses the sequence of actions and observations up to round $t-1$, expressed as $\mathcal{H}_{t}=((S_{1},\mathcal{F}_{1},\boldsymbol{\mu}_{1,\mathcal{F}_{1}},
\boldsymbol{c}_{1,S_{1}}),\dots,$ $(S_{t-1},\mathcal{F}_{t-1},\boldsymbol{\mu}_{t-1,\mathcal{F}_{t-1}},
\boldsymbol{c}_{t-1,S_{t-1}}))$. Here, $\boldsymbol{\mu}_{t,\mathcal{F}_{t}}=(\boldsymbol{\mu}_{t,S_{t,1}},...,
\boldsymbol{\mu}_{t,S_{t,F_{t}}})$ and $\boldsymbol{c}_{t,S_{t}}=(c_{t,S_{t,1}},...,c_{t,S_{t,|S_{t}|}})$ detail the partial observed rewards and full costs of LLM for the $t^{th}$ action, respectively.

Introduce $\Omega_{t}$ as the random seed influencing the discretization procedure $\sigma$ from Algorithm 2 and Algorithm 3 at round $t$, ensuring that $S_{t}=\sigma(\tilde{\boldsymbol{Z}}_{t})$ is deterministic given $\Omega_{t}$ and $\tilde{\boldsymbol{Z}}_{t}$. The notation $\mathbb{E}[\cdot|\mathcal{H}_{t},\Omega_{t}]$ specifies the conditional expectation given the historical context $\mathcal{H}_{t}$ and the random seed $\Omega_{t}$.

Our analysis proceeds under the premise that all base arms (i.e., LLM) in the selected set $S_{t}$ are observed, yielding the expected regret at round $t$, conditioned on history $\mathcal{H}_{t}$ and random seed $\Omega_{t}$, as follows:

$$ $\displaystyle\qquad\mathbb{E}[\bar{reg}(S_{t},\bar{\boldsymbol{\mu}}_{t})| \mathcal{H}_{t},\Omega_{t}]$ (21) $\displaystyle=\mathbb{E}\left[\bar{reg}(S_{t},\bar{\boldsymbol{\mu}}_{t}) \mathbb{E}\left[\frac{1}{o_{t,S_{t}}}\mathbb{I}\{F_{t}=|S_{t}|\}|S_{t}\right]| \mathcal{H}_{t},\Omega_{t}\right]$ (22) $\displaystyle=\mathbb{E}\left[\bar{reg}(S_{t},\bar{\boldsymbol{\mu}}_{t})\frac {1}{o_{t,S_{t}}}\mathbb{I}\{F_{t}=|S_{t}|\}|\mathcal{H}_{t},\Omega_{t}\right]$ (23) $\displaystyle\leq\frac{1}{o^{*}}\mathbb{E}[\bar{reg}(S_{t},\bar{\boldsymbol{ \mu}}_{t})\mathbb{I}\{F_{t}=|S_{t}|\}|\mathcal{H}_{t},\Omega_{t}]$ (24) $$

where Eq. 22 utilizes the fact that, with $S_{t}$ determined, $o_{t,S_{t}}$ represents the probability of observing $F_{t}=|S_{t}|$, Eq. 23 simplifies the expression by considering the conditions where $\mathcal{H}_{t}$ and $\Omega_{t}$ are fixed, thus fixing $S_{t}$. And the last inequality in Eq. 24 emerges from defining $o^{*}=\min_{t\in\mathcal{T},S\in\mathcal{S}}o_{t,S}$ as the minimum observation probability, highlighting the analysis within the framework of partial feedback mechanisms and its implications for LLM selections.

Integrating the results from Eq. 2, Eq. 20, and Eq. 24, the expected cumulative regret $R(T)$ can be expressed and bounded as follows:

$$ $\displaystyle R(T)$ $\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}\mathbb{E}[\mathbb{E}[r(S_{t},\bar {\boldsymbol{\mu}}_{t})-r(S_{t},\boldsymbol{\mu})]|\mathcal{H}_{t},\Omega_{t}]\right]$ $\displaystyle\leq\mathbb{E}\left[\sum_{t=1}^{T}\mathbb{E}[\bar{reg}(S_{t},\bar {\boldsymbol{\mu}}_{t})|\mathcal{H}_{t},\Omega_{t}]\right]$ (25) $\displaystyle\leq\frac{1}{o^{*}}\mathbb{E}\left[\mathbb{E}[\sum_{t=1}^{T}\bar{ reg}(S_{t},\bar{\boldsymbol{\mu}}_{t})\mathbb{I}\{F_{t}=|S_{t}|\}|\mathcal{H}_ {t},\Omega_{t}]\right]$ (26) $\displaystyle=\frac{1}{o^{*}}\mathbb{E}\left[\sum_{t=1}^{T}r(S_{t},\bar{ \boldsymbol{\mu}}_{t})-r(S_{t},\boldsymbol{\mu})\mathbb{I}\{F_{t}=|S_{t}|\}\right]$ (27) $\displaystyle\leq\frac{L}{o^{*}}\mathbb{E}\left[\sum_{t=1}^{T}\sum_{k=1}^{F_{t }}|\bar{\mu}_{t,S_{t,k}}-\mu_{t,S_{t,k}}|\right]$ (28) $\displaystyle\leq\frac{L}{o^{*}}\mathbb{E}\left[\sum_{t=1}^{T}\sum_{k=1}^{F_{t }}2\sqrt{\frac{\ln(\frac{2\pi^{2}Kt^{3}}{3\delta})}{2T_{t,\mu_{k}}}}\right],k \in S_{t}$ (29) $\displaystyle=\frac{L}{o^{*}}\mathbb{E}\left[\sum_{k=1}^{K}\sum_{s=1}^{T_{T+1, \mu_{k}}}\sqrt{\frac{2\ln(\frac{2\pi^{2}KT^{3}}{3\delta})}{s}}\right]$ (30) $$

where Eq. 25 follows from Eq. 20, Eq. 26 is due to Eq. 24, Eq. 27 is by the tower rule of expectation ($\mathbb{E}[X]=\mathbb{E}[\mathbb{E}[X|Y]]$ for two random variables $\tilde{\boldsymbol{Z}}$ and $Y$)
and the definition $\bar{reg}(S_{t},\bar{\boldsymbol{\mu}}_{t})$, Eq. 28 leverages the $L$-Lipschitz continuity of $r(S;\boldsymbol{\mu})$, Eq. 29 employs the bound $0\leq\bar{\mu}_{t,k}-\mu_{t,k}\leq 2\rho_{t,\mu_{k}}$ $k\in S_{t}$, given event $\mathcal{K}_{\mu}$, Eq. 30 accounts for the observation counter $T_{t,\mu_{k}}$ increasing by one whenever the weight of base arm $k$ is observed.

where Eq. 41 is due to $0\leq c_{i}-\underline{\boldsymbol{c}}_{t,i}\leq 2\rho_{c,t,i}$, Eq. 42 is because the counter $\boldsymbol{T}_{w,t,i}$ increase by 1 if and only if $i$’s cost has been observed, Eq. 43 is by replacing summation with integral, Eq. 44 is due to the Cauchy-Schwarz inequality, Eq. 45 is because $\sum_{i=1}^{L}\sum_{i=1}^{L}\boldsymbol{T}_{w,T+1,i}\leq KT$.

Step 3: Derivation to get the final regret bound

To get the final regret bound, we proceed with the following mathematical derivation:

$$ $\displaystyle R(T)$ $\displaystyle\leq\frac{L}{o^{*}}\mathbb{E}\left[\sum_{k=1}^{K}\sum_{s=1}^{T_{T +1,\mu_{k}}}\sqrt{2\frac{\ln(\frac{2\pi^{2}KT^{3}}{3\delta})}{s}}\right]$ $\displaystyle\leq\frac{L}{o^{*}}\mathbb{E}\left[\sum_{k=1}^{K}\int_{s=0}^{T_{T +1,\mu_{k}}}\sqrt{\frac{2\ln(\frac{2\pi^{2}KT^{3}}{3\delta})}{s}}ds\right]$ (31) $\displaystyle=\frac{2L}{o^{*}}\mathbb{E}\left[\sum_{k=1}^{K}\sqrt{T_{T+1,\mu_{ k}}2\ln(\frac{2\pi^{2}KT^{3}}{3\delta})}\right]$ $\displaystyle\leq\frac{2L}{o^{*}}\mathbb{E}\left[\sqrt{2K\sum_{k=1}^{K}T_{T+1, \mu_{k}}\ln(\frac{2\pi^{2}KT^{3}}{3\delta})}\right]$ (32) $\displaystyle\leq\frac{2L}{o^{*}}\sqrt{2NKT\ln(\frac{2\pi^{2}KT^{3}}{3\delta})},$ (33) $$

where Eq. 31 approximates the discrete sum with an integral for a smoother upper bound, Eq. 32 applies the Cauchy-Schwarz inequality to transition from the sum of square roots to the square root of a sum, and Eq. 33 recognizes that the total number of times base arms are observed is bounded by $NT$, considering $N$ as the maximum selection size, i.e., $\sum_{k=1}^{K}\sum_{k=1}^{K}T_{T+1,\mu_{k}}\leq NT$.

The proof concludes by acknowledging that the initial $K$ rounds contribute at most $r^{*}K$ to the regret, combined with the bound established in Eq. 33 and setting $\delta=1/T$ for the regret analysis.

### D.3 Comprehensive Proof of Theorem 2

General violation proof analysis

To prove the violation bound, we focus on the scenario where event $\mathcal{K}_{c}$ occurs with a probability of at least $1-\delta/2$ (by Lemma 1), specifically:

$$ $\Pr\{\neg\mathcal{K}_{c}\}=\Pr\left\{\exists t\in\mathcal{T},k\in\mathcal{K},| \hat{c}_{t,k}-c_{k}|\geq\sqrt{\frac{\ln(\frac{2\pi^{2}Kt^{3}}{3\delta})}{2T_{t ,c_{k}}}}\right\}\leq\frac{\delta}{2}.$ $$

Given the occurrence of $\mathcal{K}_{c}$, it follows that $0\leq c_{k}-\underline{c}_{t,k}\leq 2\rho_{t,c_{k}}$.
From Algorithm 2 and Algorithm 3, we know that $\rho\geq\sum_{k\in\mathcal{K}}\underline{c}_{t,k}\tilde{z}_{t,k}=\underline{
\boldsymbol{c}}_{t}\cdot\tilde{\boldsymbol{Z}}_{t}$, where $\underline{\boldsymbol{c}}_{t}\coloneqq\{\underline{c}_{t,1},\underline{c}_{t,
2},\ldots,\underline{c}_{t,K}\}$, and we also denote $\boldsymbol{c}_{t}\coloneqq\{c_{t,1},c_{t,2},\ldots,c_{t,K}\}$. This setup allows us to estimate the per-round violation as follows:

$$ $\displaystyle\quad V(T)\leq\left|\frac{1}{T}\sum_{t=1}^{T}\sum_{k\in S_{t}}y_{ t,k}-\rho\right|$ (34) $\displaystyle\leq\frac{1}{T}\left|\sum_{t=1}^{T}\left(\sum_{k\in S_{t}}y_{t,k} -\underline{\boldsymbol{c}}_{t}\cdot\tilde{\boldsymbol{Z}}_{t}\right)\right|$ (35) $\displaystyle\leq\frac{1}{T}\bigg{(}\underbrace{\left|\sum_{t=1}^{T}\left(\sum _{k\in S_{t}}y_{t,k}-\sum_{k\in S_{t}}c_{k}\right)\right|}_{\text{violation (a )}}+\underbrace{\left|\sum_{t=1}^{T}\left(\sum_{k\in S_{t}}c_{k}-\sum_{k\in S_ {t}}\underline{c}_{t,k}\right)\right|}_{\text{violation (b)}}$ (36) $\displaystyle\quad+\underbrace{\left|\sum_{t=1}^{T}\left(\sum_{k\in S_{t}} \underline{c}_{t,k}-\underline{\boldsymbol{c}}_{t}\cdot\tilde{\boldsymbol{Z}}_ {t}\right)\right|}_{\text{violation (c)}}\bigg{)}$ (37) $$

where Eq. 34 originates from the violation definition, Eq. 35 leverages the inequality $\rho\geq\underline{\boldsymbol{c}}_{t}\cdot\tilde{\boldsymbol{Z}}_{t}$ illustrated above, and Eq. 37 utilizes the inequality $|a+b+c|\leq|a|+|b|+|c|$ for separation of terms.

Similarly, we begin with a sketch of the proof to enhance comprehension. For every round $t\in\mathcal{T}$ and LLM $k\in\mathcal{K}$, the event $\left|\hat{c}_{t,k}-c_{k}\right|<$ $\sqrt{\ln\left(\frac{2\pi^{2}Kt^{3}}{3\delta}\right)/2T_{c,t,k}}$ occurs with probability at least $1-\delta/2$, from Lemma 1, thus resulting in $c_{k}\geq\hat{c}_{t,k}-\rho_{c,t,k}=\underaccent{\bar}{y}_{t,k}$ via setting $\delta=1-1/T$. From Eq. (3), we have that $\rho\geq\sum_{k\in\mathcal{K}}\underaccent{\bar}{c}_{t,k}\tilde{z}_{t,k}$, $\forall t\in\mathcal{T}$.
Then $V(T)=\left[\frac{1}{T}\sum_{t=1}^{T}\sum_{k\in S_{t}}y_{t,k}-\rho\right]^{+}$ is bounded by:

$$ $\displaystyle V(T)\leq\frac{1}{T}\bigg{(}\underbrace{\left|\sum_{t=1}^{T}\sum_ {k\in S_{t}}(y_{t,k}-c_{k})\right|}_{\text{violation (a) }}+\underbrace{\left| \sum_{t=1}^{T}\sum_{k\in S_{t}}(c_{k}-\underline{c}_{t,k})\right|}_{\text{ violation (b) }}+\underbrace{\left|\sum_{t=1}^{T}\sum_{k\in S_{t}}(\underline{ c}_{t,k}-\underline{c}_{t,k}\tilde{z}_{t,k})\right|}_{\text{violation (c) }} \bigg{)}.$ (38) $$

By constructing martingale sequences and applying Azuma-Hoeffding inequality, we can bound violation (a) by $\left(N\sqrt{2T\ln(8T)}\right)$ with probability at least $1-1/4T$. Similarly, violation (c) is bounded by $\left(N\sqrt{2T\ln(8T)}\right)$ with probability at least $1-1/4T$. With $c_{k}\geq\hat{c}_{t,k}-\rho_{c,t,k}=\underaccent{\bar}{c}_{t,k}$ satisfied at least $1-1/2T$ probability, violation (b) is bounded by $4\sqrt{2NKT\ln\left(\frac{2\pi^{2}KT}{3}\right)}$. Utilizing the union bounds, we get the desired results in Eq. (8).

Next, we individually bound violations (a), (b), and (c) to further quantify the violation and finally use the union bounds for violation (a), (b), (c) with the initialization process that causes at most $NK$ violation to prove the desired terms in Eq. 8.

Step 1: Bound violation (a)

To address violation (a), we introduce a series of random variables $\{Y_{1},Y_{2},\dots,Y_{T}\}$, constructing a martingale sequence relative to the historical data of C2MAB-V, denoted $\mathcal{H}_{t}$. The history $\mathcal{H}_{t}$ encompasses the sequence of actions and observed outcomes up to round $t-1$, encapsulating both the actions taken and the corresponding observed rewards and full costs. Formally, $\mathcal{H}_{t}$ includes tuples $((S_{1},\mathcal{F}_{1},\boldsymbol{\mu}_{1,\mathcal{F}_{1}},\boldsymbol{c}_{1
,S_{1}}),\dots,$ $(S_{t-1},\mathcal{F}_{t-1},\boldsymbol{\mu}_{t-1,\mathcal{F}_{t-1}},
\boldsymbol{c}_{t-1,S_{t-1}}))$, where $\boldsymbol{\mu}_{t,\mathcal{F}_{t}}=(\boldsymbol{\mu}_{t,S_{t,1}},...,
\boldsymbol{\mu}_{t,S_{t,F_{t}}})$ and $\boldsymbol{c}_{t,S_{t}}=(c_{t,S_{t,1}},...,c_{t,S_{t,|S_{t}|}})$, representing the observed rewards and costs, respectively, for the action set $S_{t}$.

The martingale is recursively defined starting with $\boldsymbol{Y}_{0}=0$, and for each round $t=1,\dots,T$,

$$ $\boldsymbol{Y}_{t}-\boldsymbol{Y}_{t-1}=\sum_{k\in S_{t}}y_{t,k}-\sum_{k\in S_ {t}}c_{k}$ (39) $$

where $\boldsymbol{W}_{t}=\boldsymbol{Y}_{t}-\boldsymbol{Y}_{t-1}$ denotes the change in the martingale value from round $t-1$ to $t$.
Given the construction of $\boldsymbol{W}_{t}$, we assert that $\mathbb{E}[\boldsymbol{W}_{t}|\mathcal{H}_{t}]=0$ and the absolute change $|\boldsymbol{W}_{t}|$ is bounded by the maximum size of the action set, denoted as $N$, i.e., $|\boldsymbol{W}_{t}|\leq N$.
Therefore, applying the Azuma-Hoeffding inequality (Lemma 6), we derive that

$$ $\left|\sum_{t=1}^{T}\left(\sum_{k\in S_{t}}y_{t,k}-\sum_{k\in S_{t}}c_{k} \right)\right|\leq\sqrt{2N^{2}T\ln\frac{8}{\delta}}$ (40) $$

holds with a probability of at least $1-\delta/4$.
This step bounds the expected deviation arising from the selection of actions and their associated costs.

Step 2: Bound violation (b)

In addressing violation (b), we focus on the scenario where event $\mathcal{K}_{c}$ occurs, which holds with a probability of at least $1-\delta/2$. Under this condition, we estimate the cumulative difference between the actual costs $c_{k}$ and their lower confidence bounds $\underline{c}_{t,k}$ for all actions in $S_{t}$ across all rounds $t$. The bound is derived as follows:

$$ $\displaystyle\left|\sum_{t=1}^{T}\left(\sum_{k\in S_{t}}c_{k}-\sum_{i\in S_{t} }\underline{c}_{t,k}\right)\right|$ $\displaystyle\leq\sum_{t=1}^{T}\sum_{k\in S_{t}}2\sqrt{\frac{\ln(\frac{2\pi^{2 }Kt^{3}}{3\delta})}{2\boldsymbol{T}_{c,t,i}}}$ (41) $\displaystyle=\sum_{k=1}^{K}\sum_{s=1}^{T_{T+1,c_{k}}}\sqrt{\frac{2\ln(\frac{2 \pi^{2}KT^{3}}{3\delta})}{s}}$ (42) $\displaystyle\leq\sum_{k=1}^{K}\int_{s=0}^{T_{T+1,c_{k}}}\sqrt{\frac{2\ln( \frac{2\pi^{2}KT^{3}}{3\delta})}{2s}}ds$ (43) $\displaystyle=2\sum_{k=1}^{K}\sqrt{T_{T+1,c_{k}}2\ln(\frac{2\pi^{2}KT^{3}}{3 \delta})}$ $\displaystyle\leq 2\sqrt{2K\sum_{k=1}^{K}T_{T+1,c_{k}}\ln(\frac{2\pi^{2}KT^{3} }{3\delta})}$ (44) $\displaystyle\leq 2\sqrt{2NKT\ln(\frac{2\pi^{2}KT^{3}}{3\delta})}$ (45) $$

where Eq. 41 utilizes the confidence interval for cost estimation under event $\mathcal{K}_{c}$, i.e., $0\leq c_{k}-\underline{c}_{t,k}\leq 2\rho_{t,c_{k}}$, Eq. 42 rearranges the summation to account for the total observations of cost $c_{k}$ for each action based on the fact that the counter $T_{t,c_{k}}$ increase by 1 if and only if base arm $k$’s cost has been observed, Eq. 43 replaces the summation with an integral to provide an upper bound, given the increasing sequence of $\frac{1}{\sqrt{s}}$, the final two inequalities, Eq. 44 and Eq. 45, apply the Cauchy-Schwarz inequality and the total number of selections to conclude the bound $\sum_{k=1}^{K}\sum_{k=1}^{K}T_{T+1,c_{k}}\leq NT$. This derivation quantifies the discrepancy between the actual costs and their estimated lower bounds over all rounds.

Step 3: Bound violation (c)

Similar to how we prove violation (a), we will define a series of random variables $\{Y_{1},\dots,Y_{T}\}$ to form a martingale with respect to history of C2MAB-V $\mathcal{H}_{t}$, defined as $\mathcal{H}_{t}=((S_{1},\mathcal{F}_{1},\boldsymbol{\mu}_{1,\mathcal{F}_{1}},
\boldsymbol{c}_{1,\mathcal{F}_{1}}),\dots,$ $(S_{t-1},\mathcal{F}_{t-1},\boldsymbol{\mu}_{t-1,\mathcal{F}_{t-1}},c_{t-1,
\mathcal{F}_{t-1}}))$ to encompasses the sequence of actions and observations up to round $t-1$, before choosing the action $S_{t}$ which includes the first $t-1$ actions and first $t-1$ partial observed rewards and full costs, where $\boldsymbol{\mu}_{t,\mathcal{F}_{t}}=(\boldsymbol{\mu}_{t,S_{t,1}},...,
\boldsymbol{\mu}_{t,S_{t,F_{t}}})$ and $\boldsymbol{c}_{t,S_{t}}=(c_{t,S_{t,1}},...,\boldsymbol{c}_{t,S_{t,F_{t}}})$.
The martingale sequence is defined recursively starting with $\boldsymbol{Y}_{0}=0$. For each round $t=1,\dots,T$, the incremental change is given by:

$$ $\boldsymbol{Y}_{t}-\boldsymbol{Y}_{t-1}=\sum_{k\in S_{t}}\underline{c}_{t,k}- \underline{\boldsymbol{c}}_{t}\cdot\tilde{\boldsymbol{Z}}_{t},$ (46) $$

where $\boldsymbol{W}_{t}=\boldsymbol{Y}_{t}-\boldsymbol{Y}_{t-1}$ denotes the change in the martingale value from round $t-1$ to $t$. Recall that the discretization procedure $\sigma$ is denoted for Algorithm 2 and Algorithm 3 as $S_{t}=\sigma(\tilde{\boldsymbol{Z}}_{t})$ and $N=\max_{S\in\mathcal{S}}|S|$. Given that $\mathbb{E}[\boldsymbol{W}_{t}|\mathcal{H}_{t}]=0$ follows from the expectation
$\mathbb{E}_{S_{t}\sim\sigma(\tilde{\boldsymbol{Z}}_{t})}[\mathbb{I}_{S_{t}}]=
\tilde{\boldsymbol{Z}}_{t}$ and and the bound $|\boldsymbol{W}_{t}|\leq N$.
Therefore, we can apply the Azuma-Hoeffding inequality (Lemma 6) to obtain:

$$ $\left|\sum_{t=1}^{T}\left(\sum_{k\in S_{t}}\underline{c}_{t,k}-\underline{ \boldsymbol{c}}_{t}\cdot\tilde{\boldsymbol{Z}}_{t}\right)\right|\leq\sqrt{2K^{ 2}T\ln\frac{8}{\delta}}$ (47) $$

with probability at least $1-\delta/4$.

Employing the union bound across violations (a), (b), and (c), and accounting for the initial setup contributing a maximum of $KN$ to the violation, we affirm the desired bounds as specified in Eq. 8 with a collective probability of at least $1-\delta$. The proof concludes by setting $\delta=1/T$ for the violation analysis.

### D.4 Technical Inequalities

We finally introduce some well-known fundamental results without proofs that serve as pivotal tools in probability theory and statistical inference, particularly in the realms of concentration inequalities and martingale sequences.

###### Lemma 4 (Subgaussian random variables) .

Suppose that random variables $X$ is $\sigma$-subgaussian, $X_{1}$ and $X_{2}$ are independent and $\sigma_{1}$ and $\sigma_{2}$-subgaussian, respectively, then

- 1.
For any $\varepsilon>0$, $\Pr\left[X\geq\varepsilon\right]\leq\exp\left(-\frac{\varepsilon^{2}}{2\sigma^
{2}}\right)$.
- 2.
$X_{1}+X_{2}$ is $\sqrt{\sigma_{1}^{2}+\sigma_{2}^{2}}$-subgaussian.

###### Lemma 5 (Chernoff-Hoeffding inequality [ 19 ] .) .

Let $Y_{1},...,Y_{n}$ be independent and identically distributed (i.e., i.i.d.) random variables with common support $[0,1]$ and mean $\mu$. Let $Z=Y_{1}+...+Y_{n}.$ Then for any $\epsilon>0$,

$$ $\Pr\{|Z-n\mu|\geq\epsilon\}\leq 2e^{-\frac{2\epsilon^{2}}{n}}.$ $$

###### Lemma 6 (Azuma-Hoeffding inequality [ 4 ] .) .

Let $\{z_{k}:i=0,1,2,\dots,n\}$ be a martingale and $|Y_{k}-Y_{k-1}|\leq c_{k}$ for $k\in[n]$ almost surely, then for any $\epsilon>0$

$$ $\Pr\{|Y_{n}-Y_{0}|\geq\epsilon\}\leq 2e^{-\frac{\epsilon^{2}}{2\sum_{i=1}^{n}c _{k}^{2}}}.$ $$

###### Lemma 4 (Subgaussian random variables) .

###### Lemma 5 (Chernoff-Hoeffding inequality [ 19 ] .) .

###### Lemma 6 (Azuma-Hoeffding inequality [ 4 ] .) .

## Appendix E More Experiments

### E.1 Experimental Details

Figure: Figure 5: Sample conversation with LLM on biology, chemistry, geography, and physics.
Refer to caption: x7.png

Consistent with Section 6, we conduct all experiments on a device equipped with an Intel Core i5-13600KF CPU @ 3.50GHz and 32 GB of memory.
Gurobi, a powerful mathematical optimization solver that supports various programming models, is utilized to solve relaxed constraint optimization problems, employing version 11.0.1 []. Fig. 5 depicts a sample interaction involving large language models (LLMs) across various scientific disciplines—Biology, Chemistry, Geography, and Physics—utilizing the SciQ dataset []. Table 3 lists the LLMs used in the experiments (refer to Section 6), detailing each model’s name with parameters, cost per 1,000 tokens in USD, and size in gigabytes. The models range from smaller configurations, such as ChatGLM2-6B-32K, to larger ones like Llama 2-70B. Considering the variability in generating answers when using LLMs, as well as potential non-responses, we specify reward allocations based on different LLM return scenarios in addition to comparisons with the SciQ dataset’s labels. If the question is answered accurately and adheres to the prescribed prompt format, the reward is set at 0.5. In the event of an incorrect response, no reward is granted. However, if factors such as network congestion or potential issues with the LLM result in an empty response, a reward of 0.1 is allocated. Should the response adhere to the format guidelines yet fail to meet the specified requirements, a reward of 0.3 is assigned. We simulate user feedback for each round using the public SciQ dataset to function as a binary feedback [], and our algorithm learns the performance of LLMs based on this feedback. Our entire framework is built on the popular bandit framework [], which continuously updates and adjusts decisions based on a steady stream of data (i.e., user feedback) to address the classic exploration-exploitation dilemma regarding LLM performance and cost.

**Table 3: List of utilized large language models in Section 6, associated cost per usage.**
| LLM_ID | Model Name (with Parameters) | Cost (USD/1k tokens) | Size (GB) |
| --- | --- | --- | --- |
| 1 | ChatGLM2-6B-32K [] | 0.005 | 12.5 |
| 2 | ChatGPT-3.5 [] | 0.02 | / |
| 3 | Claude 2 [] | 0.08 | / |
| 4 | ERNIE 3.5-8K [] | 0.015 | / |
| 5 | Llama 2-7B [] | 0.005 | 12.6 |
| 6 | Llama 2-13B [] | 0.008 | 24.3 |
| 7 | Llama 2-70B [] | 0.05 | 128.3 |
| 8 | Mixtral-8x7B-Instruct [] | 0.05 | 93.37 |
| 9 | ChatGPT-4 [] | 0.12 | / |

### E.2 Respective Results for Reward and Violation

Figure: (a) AWC
Refer to caption: x8.png

Figure: (a) AWC
Refer to caption: x11.png

Per-round Reward and Violation.
Fig. 6 and Fig. 7 display the experimental rewards and violations for three different task types. In Fig. 6, C2MAB-V consistently outperforms or matches the $\epsilon$-Greedy baseline in terms of rewards per round. The parameters on $\alpha_{\mu}$ and $\alpha_{c}$ used are (0.3, 0.05), (1, 0.05), (0.3, 0.01), and (1, 0.01), respectively denoted as (a), (b), (c), and (d).
Adjusting the values of $\alpha_{\mu}$ and $\alpha_{c}$ consistently results in higher rewards for C2MAB-V settings. These settings also significantly reduce violations per round compared to the $\epsilon$-Greedy approach. Although the CUCB algorithm achieves the highest per-round rewards, it does so completely ignoring cost constraints, leading to a per-round violation rate at least four times higher than that of C2MAB-V, as shown in Fig. 7. This figure also indicates that C2MAB-V’s violations are lower than those of the $\epsilon$-Greedy baseline, highlighting its ability to effectively manage constraints. Additionally, since Thompson Sampling relies on Bayesian updates, which can be highly variable, this method may lack stability and potentially cause severe oscillations, as observed in scenarios like the AIC task.

Additionally, as shown in Fig. 6(c), we can observe a convergence trend in the rewards of C2MAB-V. This trend suggests that the initial actions selected might have had higher rewards but also higher violations. Over time, the cost-aware online learning strategy adjusts by slightly reducing rewards to achieve greater cost savings, demonstrating its effectiveness in managing long-term constraints.

Figure: (a) AWC
Refer to caption: x14.png

Varying Budget Threshold. We then examine the influence of the budget threshold $\rho$. As depicted in Fig. 8, the optimal action of combinatorial LLMs varies with the change in the budget threshold $\rho$. This variation in both arm and action selection space results in fluctuations in reward and violation. Furthermore, it is evident that across different values of $\rho$, our proposed C2MAB-V with $\alpha_{\mu}=1,\alpha_{c}=0.01$ consistently outperforms the benchmarks CUCB and $\epsilon$-Greedy by at least 356.0% and 55.7% improvment, highlighting the robustness of our algorithm.

Figure: (a) Average Reward
Refer to caption: x17.png

Performance-Driven Scenarios.
Our study explores a range of trade-offs, extending beyond the typical exploration-exploitation dichotomy to include cost and reward considerations. Given the anticipated reduction in costs over time with the development of LLMs, our analysis focuses on scenarios that have a generous budget and prioritize performance. In such performance-driven scenarios, our theoretical analysis suggests setting the cost exploration parameter $\alpha_{c}$ higher to better emphasize performance outcomes, which means exploring enough to have good empirical performance. Consequently, we adjust both $\alpha_{\mu}$ and $\alpha_{c}$ as follows: Performance-driven1 with $(\alpha_{\mu},\alpha_{c})=(0.3,1)$, Performance-driven2 with $(\alpha_{\mu},\alpha_{c})=(1,1)$, Cost-driven1 with $(\alpha_{\mu},\alpha_{c})=(0.3,0.01)$, and Cost-driven2 with $(\alpha_{\mu},\alpha_{c})=(1,0.01)$. As shown in Fig. 9, the performance-driven types of C2MAB-V yield higher rewards, whereas the cost-driven types exhibit fewer cost violations. The preferable approach varies, depending on the specific needs and constraints of the task at hand.

### E.3 In-depth Analysis of Exploratory Results.

Figure: Figure 10: Impact of varying the maximum number $N$ on performance metrics over 3000 rounds.
Refer to caption: x19.png

Impacts of Maximum Number of LLMs.
To investigate how the maximum number of selectable LLMs, denoted as $N$, impacts performance, we present the reward/violation ratio for different $N$ values after $T=3,000$ rounds in Fig. 10. Recognizing that different task types should not adhere to a universal budget threshold, we specifically use AWC as an example to underscore the influence of $N$, while keeping the budget threshold constant. It is important to note that as $N$ changes, the optimal combination of LLMs, i.e., the optimal action, also changes. Under the same budget threshold $\rho$, increasing $N$ expands the selection space, adding complexity and thus affecting the efficiency of all algorithms. However, we observe that with an increase in $N$, C2MAB-V consistently outperforms both the CUCB and $\epsilon$-Greedy baselines.

Comparison of Computational Efficiency on Relaxation.

Figure: (a) Average Reward
Refer to caption: x20.png

C2MAB-V-Direct is an adjusted version that finds the best feasible solution by directly solving the discrete constrained optimization Eq. 48 via enumeration, rather than using relaxation techniques:

$$ $\begin{cases}\max 1-\prod_{k\in\mathcal{K}}\left(1-\bar{\mu}_{k}z_{k}\right),& \sum_{k\in\mathcal{K}}\underline{c}_{t,k}z_{k}\leq\rho,z_{k}\in\{0,1\},\forall k \in\mathcal{K},\\ \max\qquad\sum_{k\in\mathcal{K}}\bar{\mu}_{k}z_{k},&\sum_{k\in\mathcal{K}} \underline{c}_{t,k}z_{k}\leq\rho,z_{k}\in\{0,1\},\forall k\in\mathcal{K},\\ \max\qquad\prod_{k\in\mathcal{K}}{\bar{\mu}_{k}}^{z_{k}},&\sum_{k\in\mathcal{K }}\underline{c}_{t,k}z_{k}\leq\rho,z_{k}\in\{0,1\},\forall k\in\mathcal{K}. \end{cases}$ (48) $$

The objective of this study is to compare the computational efficiency between C2MAB-V, and C2MAB-V-Direct, which directly solves the constrained integer optimization problem without this approach. As illustrated in Fig. 11, using the AwC reward function as an example, the comparison of reward and violation shows that C2MAB-V-Direct almost completely avoids violations, while the reward for C2MAB-V at four different parameter pair settings ($\alpha_{\mu},\alpha_{c}$) ((0.3, 0.05) = (a), (1, 0.05) = (b), (0.3, 0.01) = (c), and (1, 0.01) = (d)) is higher than that of C2MAB-V-Direct.

**Table 4: Comparison of runtime between C2MAB-V and C2MAB-V-Direct methods.**
| Runtime (s) | C2MAB-V | C2MAB-V-Direct |
| --- | --- | --- |
| AWC | 221.78 | 1464.33 |
| SUC | 267.20 | 16890.91 |
| AIC | 283.06 | 17320.47 |

Next, we compare the runtime of the two methods. Due to response latency fluctuations when directly invoking the LLM, which may be influenced by network conditions or query tokens (with observed delays ranging from 1 ms to 4 s), we employ a synthetic setting to focus solely on the comparative analysis of algorithmic runtime. The specifics are as follows:
For each arm $k$, we independently simulate $\mu_{i}$ and $c_{i}$ from a uniform distribution $U[0,1]$. All tasks are recorded over 10,000 rounds. Regarding parameter settings: in the AWC reward, $K=16$, $N=8$, and $\rho=2.5$; in the SUC reward, $K=25$, $N=8$, and $\rho=1.4$; and in the AIC reward, $K=25$, $N=8$, and $\rho=1.6$.

As shown in Table 4, the computational efficiency of C2MAB-V-Direct is significantly lower than that of C2MAB-V. Specifically, C2MAB-V is at least 6 times faster across three different reward scenarios. Due to our relaxation and discretization design, the time complexity of C2MAB-V is polynomial, whereas C2MAB-V-Direct likely requires exponential time for the constrained integer problem, particularly when the search space is large. Nevertheless, for scenarios requiring stricter adherence to constraints, C2MAB-V-Direct remains a viable option. In summary, in practical applications, C2MAB-V and C2MAB-V-Direct each serve distinct purposes, offering targeted choices between computational efficiency and strict constraint compliance.

Enhancing LLM Selection: From Two-Tier to Multi-Tier.
We further demonstrate the benefits of transitioning from a traditional “two-tier” to a more complex “multi-tier” LLM selection strategy in online settings. In the simpler two-tier system, selections are limited to just two levels of LLM engagement, which might not adequately address the diverse range of queries typically encountered in dynamic environments. By adopting a multi-tier strategy, our system can more precisely match the complexity and specificity of incoming queries with an appropriate level of computational resources and LLM expertise. The ratio comparison is not displayed in Fig. 12, as the denominator may be zero. Fig. 12 underscores the necessity and effectiveness of our advanced multi-tier strategy in enhancing response quality and system adaptability in real-time online interactions.

Figure: (a) Reward
Refer to caption: x22.png

Figure: (a) Reward
Refer to caption: x24.png

Necessity of Online Learning for LLM Selection.
As discussed in Section 6, our approach emphasizes online learning methodologies that incorporate continuous feedback. To highlight the significance of ongoing online adjustments in LLM selection, we present a comparison. Initially, we pre-learned a fixed combination of multiple LLMs offline, which was then utilized to manage online queries. As illustrated in Fig. 13, our feedback-driven adjustments significantly enhance the effectiveness of pre-set LLM selections. By comparing our method with purely offline-learned, cascaded combinations of multi-LLMs for the AWC task type, we demonstrate the essential role of continuous online adaptations in optimizing LLM selection for real-time queries.

Figure: (a) Reward
Refer to caption: x27.png

Exploring Asynchronous Local-Cloud Architecture.
Recall the flow of the C2MAB-V algorithm:
Based on our online learning-based multi-LLM selection algorithm C2MAB-V, multiple LLMs are coordinated and selected through a scheduling cloud. When new user data feedback is received, the local server adjusts the performance evaluation of the corresponding LLMs and notifies the scheduling cloud to update the multi-LLM selection strategy.

In the main text, we primarily demonstrate a synchronized local-cloud setting. However, in practice, the local server may not receive user feedback every round, and local-cloud communication may not be entirely synchronous. Therefore, we explore an asynchronous local-cloud architecture with a batch size. Specifically, when the batch size $B$ is reached, the local server sends new relaxed continuous data to the scheduling cloud after storing $B$ pieces of user feedback. This prompts the cloud to re-coordinate multiple LLMs and adjust the multi-model selection strategy. Until then, the previous multi-LLM selection strategy remains in use. We investigate the changes in reward and violation for batch sizes of 10, 50, 100, and 200. As shown in Fig. 14, the largest batch size of 200 exhibits relatively lower rewards and higher violations, which is intuitive. However, there is no significant difference in the reward and violation values of C2MAB-V under different batch sizes. This indicates that the choice of batch size may not critically impact the overall performance within the tested range for our proposed C2MAB-V algorithm.

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: No direct questions, but I welcome responses from the authors on the deployability and other aspects raised above.
soundness: 3
strengths: I think the core explore-exploit algorithm that was introduced is new (to this reviewer), interesting, and also comes with potentially new regret guarantees.
summary: Main problem statement: the problem statement is clear and well-motivated (i.e. the setup of selecting a subset of LLMs/experts to answer a given query, in a cost and reward-sensitive environment. I do think combinatorial bandits are a reasonable way to model this problem, although I do have some nits about it which I’ll mention below).
Idea - the technical/intellectual contribution of the paper isn’t inherently about LLMs, in my opinion.I think the main idea is a new combinatorial bandit algorithm (which they dub C2MAB-V), which attempts to do exploration/exploitation and bandit-feedback updates in tandem with solving the submodular optimization described in Eq.3. I certainly have not seen this algorithm in the literature before, but I should caveat by saying that I am not an expert on combinatorial bandits. (As an aside, I do see a paper of Karthik’s referenced here on comb. bandits, so it may be worth getting his gut-check?) In addition to the new algorithm, the authors also derive a regret bound.
Novelty - Both the C2MAB-V and its regret analysis (Theorem 1) are novel as far as I (a non-expert) know.
Evaluation - the empirical evaluations are interesting and suggest that C2MAB-V does empirically outperform other “naive” alternatives such as always going with the best/most expensive model. I am curious to know why the y-axis in Fig 4 is reward / budget violation. The presence of the budget violation term there is a bit puzzling to me. Any feasible solution of (3) should be budget feasible and so budget should never really be violated (i.e. the denominator should always be zero)?
Benchmark - In Fig 4., evaluation is done against a good set of benchmarks including eps-greedy, Thompson sampling, and combinatorial UCB
Practical deployability?
I have some “weak” concerns about the practical “deployability” of the ideas proposed here in the context of LLMs. Some alternative ways that cost and performance tradeoffs may potentially be navigated for practical large-scale systems involve avoiding the appeal to MAB altogether, and its unclear whether this paper can prescribe into any insights about the relative merits of leveraging MAB versus other approaches. One such approach is Mixture-of-Experts (MoE) where the experts are directly absorbed as “sub-models” inside a larger model and the task of identifying which expert to direct a task to is also captured inside the model and learnt in the pre-training phase. Another approach is to appeal to “Composition of Experts (https://arxiv.org/pdf/2405.07518)”, where given some expert models, a new model is trained to learn to route a given task to the best set of experts. Based on this paper, can we draw any conclusions vis-a-vis MoE vs CoE vs MAB-combination of different LLMs?
One other deployability challenge that I see (and I don’t think was adequately addressed in the paper) is the contextual nature of the problem. Given a task, it seems to me that the context for that task (e.g. the required expertise e.g. medicine vs biology vs math) is needed to meaningfully identify the potential reward and also cost, and we’d need the bandit feedback to be contextual. In the method described by the authors, it is unclear whether and how the context is captured. I do believe the regret analysis itsef would also change substantially based on whether the algorithm describes a non-contextual vs a contextual implementation (since uncertainty quantification is far more nuanced in the contextual setup)
weaknesses: I have some concerns about the practical deployability of the approach.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: Please see the questions above.
soundness: 2
strengths: This paper has the following strengths:
+ This paper consider an interesting problem which selects LLM models on cloud. 
+ This paper provides good formulations for online LLM selection problem. Different reward models are considered. Budget constraint of the scheduling cloud is also modeled.
+ Performance analysis is provided for the combinatorial bandit problem.
summary: This paper formulates the multi-LLM selection problem as a combinatorial bandit problem. The authors develop an online bandit algorithm for online multi-LLM selection where different types of reward modes are applied. Also, the authors consider a computational cost constraint on the LLM selection. The paper provides analysis for regret and constraint violation.  The performance is evaluated based on  the SciQ dataset.
weaknesses: The paper can be improved in the following aspects.
- This paper considers the LLM selection problem. However the reward are modeled as some simple equations in page 5 and look like some toy models. These models cannot accurately reflect the real evaluation of combinatorial LLMs.
- The algorithm design is a simple extension of combinatorial bandits. The analysis of the algorithm also loos similar as the previous results on combinatorial bandits. It would be better if the authors can present the new challenges and techniques used in the algorithm and analysis.
- The empirical results are carried out for only one dataset.  Also, the choices of the parameters like budget threshold, $\alpha$, etc are not explained. This is not enough to verify the proposed algorithms.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. I noticed that LLaMA 2 was used for comparison in the experiments, but LLaMA 3 has also been released. I am curious why there was no comparison with LLaMA 3 in the experiments.

2. When the reward function is linear, can instance-dependent performance bounds be derived based on a sub-optimality gap defined by the extreme points?
soundness: 3
strengths: 1. The formulation of the problem as a cost-effective combinatorial multi-armed bandit with versatile reward models is interesting and applicable in real-world scenarios where cost-efficiency is crucial. The paper reads well and includes examples/intuition to help the reader.

2.  The authors provide a rigorous theoretical analysis of the regret and budget violations of the proposed algorithm, achieving results that match the state-of-the-art in several degenerate cases. Plus, the case-by-case analysis for different reward models provides enough insights about the discretization rounding procedure, which is crucial for understanding the proposed method.

3. The paper presents extensive empirical evaluations using various LLMs across three application scenarios, providing strong evidence for the proposed method's effectiveness.
summary: This paper introduces a model of Cost-effective Combinatorial Multi-armed Bandit with Versatile reward for the optimal selection of multiple large language models (LLMs). The proposed approach aims to manage the exploration-exploitation trade-off while balancing costs and rewards in a collaborative LLM setting, using an online learning framework. The paper provides a theoretical analysis of regret and budget violation bounds, demonstrating that the proposed approach C2MAB-V matches state-of-the-art results in certain degenerate cases. Empirical experiments validate its effectiveness in balancing cost-efficiency and performance across three scenarios with nine LLMs.
weaknesses: 1. The algorithms and theoretical analysis presented are natural extensions of previous approaches, specifically in the combinatorial multi-armed bandit literature. Also, I do not believe that non-linear rewards pose a significant challenge for the analysis, as the paper assumes that the reward function is Monotone and Lipschitz. Therefore, the regret analysis can be converted to the accumulated impact of overestimating rewards, just as most of the literature does. Hence, I cannot give a score higher than 6 (accept).

2. Lines 1240-1241 contain content that seems unrelated to the context and should be revised or removed.

3. The literature on Combinatorial Multi-Armed Bandit with Knapsack Constraints is highly relevant to this paper's content, yet it has not been formally reviewed in Section 2.1 (Related Work). I highly recommend the authors Incorporate a formal review of these works in the revised paper.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: - In section 3, a subset $S_t$ is selected from the available LLMs set $\mathcal{K}$. This is termed as an "action" and satisfies $|S_t|\leq K$. Right after that, $N=\max_{S\in\mathcal{S}}|S|$ is defined as the maximum number of LLMs that can be simultaneously active. What are the differences or the relations between $K$ and $N$? 
- This paper introduces three reward models, i.e., AWC, SUC, AIC. What are the fundamental differences between these models? What are the impacts on the algorithm designs and analysis? The performance analysis in Section 5 is only for AWC. What about the performance guarantees under SUC and AIC. If there is no such results, what's the point to present these models in Sections 3 and 4, which make the paper very dense and hard to follow. 
- For a budget constraint $\rho$, why does the definition of $V(T)$ require a max operator? In many constrained RL or constrained MDPs, the violation constraint is naturally defined without a max operator. Can you elaborate on this? 
- In Section 4.1, several relaxation strategies for LLM selection have been discussed. However, are the solutions to these relaxations feasible to the "original" problem defined in Section 3 with the constraint that must be satisfied? This may be obviously infeasible. Can you clarify how to further design the solutions on top of the solutions to these relaxation problems? 
- For the violation bound in Theorem 2, the right hand size of (8) has two terms, one in the order of $\mathcal{O}(\sqrt{K/T})$ and the other $\mathcal{O}(K/T)$. The authors claimed that the violation decreases at a rate of $\mathcal{O}(\sqrt{K/T})$. In addition, why "the overall violation is shown to be $\mathcal{O}(\sqrt{KT})$ as claimed in lines 457-458? 
- How tight is the upper bound in Theorem 1? The coefficient can be extremely large on the right hand size of (7) associated with the $T$ terms. similarly for the constant term $(K+1)r^*$ that is in the order of $(K+1)NL$.
soundness: 2
strengths: - This paper studies a timely and interesting problem in the context of LLMs, in particular considering the selection of multiple LLMs with versatile reward models and in an online manner 
- A new framework named C2MAB-V, i.e., a cost-effective combinatorial online model with a versatile reward structure, has been proposed to select multiple LLMs based on specific task and requirements while adhering to the budget constraint.
- Both the regret and violation bounds for C2MAB-V have been provided.
- The performance of C2MAB-V is further evaluated via extensive experiments, e.g., including nine LLMs under various settings.
summary: This paper investigates the problem of the selection of multiple large language models (LLMs) with versatile reward models in an online manner. A framework named C2MAB-V, i.e., a cost-effective combinatorial online model with a versatile reward structure, has been proposed to select multiple LLMs based on specific task and requirements while adhering to the budget constraint. The performance of C2MAB-V has been both analyzed theoretically and evaluated via experiments. On the theoretical side, both the regret and violation bounds are provided. On the numerical side, the performance of C2MAB-V has been evaluated with nine LLMs under various settings.
weaknesses: - Despite the studied problem is timely and interesting, the intrinsic nature of the problem is not quite new. In other words, it is still a combinatorial online optimization problem but simply framed in a new LLM setting. 
- Likewise, the proposed online algorithm C2MAB-V is not much in difference with the exiting methods as mentioned in the related works. 
- The paper is very dense and sometimes hard to understand. For instance, it introduces three reward models, i.e., AWC, SUC, AIC. What are the fundamental differences between these models? What are the impacts on the algorithm designs and analysis? It is not quite clear and the analysis seems to only focus on one model, and not sure if you need to present all of them in the main paper. For instance, it may be better to just present AWC which has the regret analysis in Section 5, and then has a new section just to discuss the extension to SUC and AIC models with numerical evaluations. 

Minor:
- This paper is framed very densely and many spaces are squeezed. For instance, there is almost no space between lines 243 and 244.

Meta-review: The paper proposes a new algorithm for selecting a subset of large language models (LLMs) to answer a given query, considering both cost and reward. The algorithm, called C2MAB-V, is based on combinatorial bandits and attempts to balance exploration and exploitation while solving a submodular optimization problem. The paper also derives a regret bound for the algorithm.


The problem statement is clear and well-motivated, and the use of combinatorial bandits is a natural approach to address the trade-off between cost and reward (WQ9G, hptZ) in this setup. The paper provides a regret bound for the algorithm (WQ9G, hptZ), which involves a number of novel moving parts. The empirical evaluations are interesting and suggest that C2MAB-V outperforms other naive alternatives (WQ9G, hptZ).

However, while the application to LLMs is timely, reviewers found the algorithm to be not substantially different from existing methods, and the analysis is similar to previous results on combinatorial bandits (RM4A, XJC9).   RM4A points out that reward models used in the paper are simple and may not accurately reflect real-world scenarios. The paper only evaluates the algorithm on one dataset and does not provide enough information on the choice of parameters (RM4A). Moreover, the paper does not address the practical deployability of the algorithm, particularly in the context of LLMs (WQ9G, XJC9), and does not provide a clear comparison with other approaches, such as Mixture-of-Experts (MoE) and Composition of Experts (CoE) (WQ9G). One reviewer found the paper to be dense and hard to follow (XJC9), perhaps because this is more of a bandit paper.

Given the weaknesses and the lack of clarity around the contribution,  I would recommend rejecting this paper.  The authors should address whether this is solving a generalizable bandit problem that is a durable contribution to the literature, in which case framing the contribution as such (with an appropriate title, and cases beyond the LLM routing problem) would be appropriate.  If it is simply solving a specific problem with deployment of LLMs, more practical evaluation must be done (and perhaps breaking up the work into two papers may be logical).

Decision: Reject