  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 \textit{C2MAB-V}, a
\underline{C}ost-effective \underline{C}ombinatorial \underline{M}ulti-armed
\underline{B}andit with \underline{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, \textit{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, \textit{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 \textit{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 \textit{C2MAB-V} effectively balances performance and cost-efficiency
with nine LLMs for three application scenarios.
