We show upper and lower bounds on the regret of m-set adversarial bandits for different utilities (winner reward or sum of rewards) and feedback models (winner index, winner reward, sum of rewards, and their combinations). By comparing to standard bounds for combinatorial and MNL bandits, our results reveal how subtle changes in the setting can have a dramatic impact on the learning rates. Our main technical contributions are the information-theoretic lower bounds on the regret. Experiments on synthetic data confirm our theoretical analyses.
Nicolò Cesa-Bianchi, Matteo Papini
Universit`a degli Studi di Milano · Politecnico di Milano
Active Feature Acquisition (AFA) is a classification problem in which an agent decides which costly features to acquire before predicting each sample's label. Unlike batch AFA, which trains a fixed policy and classifier offline on fully observed data, online AFA updates its predictor from revealed labels as samples arrive. Existing online methods either use deep reinforcement learning (RL) without performance guarantees or maximize cost-adjusted reward rather than enforce a global budget. We formulate online AFA as a combinatorial Bandits with Knapsacks (BwK) problem that couples acquisition and prediction. Unlike prior bandit-based AFA and classical BwK, our setting has combinatorial complexity, evolving rewards, a global budget, and structured side information. We obtain an improved regret upper bound over standard BwK bounds in this framework, leveraging a cardinality-aware confidence bound and the subset update structure. To avoid an exponentially large action space, we propose \emph{LP-Chain}, a variant that searches a cost-aware chain of feature subsets with a size that grows linearly with the number of features. While the regret upper bound is specific to the combinatorial framework, \emph{LP-Chain} empirically achieves comparable predictive performance. On synthetic data, \emph{LP-Chain} outperforms HEDGE-based BwK and deep RL-based online AFA baselines and scales favorably to more features.
AbdAlRahman Odeh, Teng-Hui Huang, Hesham El Gamal
The University of Sydney School of Electrical and Computer Engineering Sydney 2006, NSW, Australia · The University of Sydney Faculty of Engineering Sydney 2006, NSW, Australia
Combinatorial Thompson sampling (CTS) draws independent posterior samples for every arm, so its exploration dynamics ignore any relation among arms. We study a minimal change to those dynamics: an LLM is queried once for a partition of the arms, the partition becomes a positive-definite correlation matrix Σ through an RBF kernel on cluster ranks, and the per-round posterior sample is drawn with covariance Σ while the Beta posteriors are updated from real rewards only, so the LLM shapes how the sampler moves, not what it believes. We give a self-contained Bayesian regret bound for the idealized Gaussian sampler whose information gain splits into a KlogT term from the K-cluster structure and a ridge term that grows to dlogT: the d/K improvement over independent sampling is a finite-horizon transient, exact only as the within-cluster correlation tends to one. The correlated sampler reduces regret by 19% over CTS on 16 synthetic Bernoulli families at T=2,500 (6-7% at T=25,000 with data-adaptive kernels) and by 41% on the Microsoft MIND-small news benchmark (d=200 real articles), while pseudo-observation warm starts give nothing. An LLM-free ablation with a simulated oracle of controlled quality shows that on unstructured instances the gain is a property of the kernel shape (a random partition, or a plain tempering of the sampling noise, reproduces it), while belief injection at matched oracle quality never helps.
Many recommender services repeatedly encounter cold-start cohorts, where new users arrive with little or no interaction history. This creates two challenges: learning user preferences quickly from limited feedback and sustaining useful recommendations when each user has a finite catalog that can become repetitive or depleted over time. We propose CohortMix-TS, a warm-started mixture bandit that learns latent user groups from earlier cohorts and uses available metadata to construct group-informed priors for new users. Starting from these fixed priors, the model personalizes independently as feedback from each user becomes available. Session slates combine Thompson sampling with diversity and inventory-depletion controls. We evaluate CohortMix-TS through simulation, semi-synthetic experiments, and a 25-day randomized in-the-wild deployment with 713 registered participants in a Campus Games quiz application. Our evaluations show that cross-cohort transfer improves early recommendation quality and user-level regret, while inventory-aware slate construction helps prevent premature exhaustion of preferred items. In the field deployment, treatment users also showed a larger early-to-late change in correctness than users receiving random recommendations. Together, these results show how warm-start transfer and inventory-aware recommendations can support personalization for short-lived, repeatedly cold-starting cohorts.
Serafima Lebedeva, Sumantrak Mukherjee, Ali Arshad Sadal +8
German Research Center for Artificial Intelligence (DFKI), Kaiserslautern · RPTU, Kaiserslautern-Landau · LMU, Munich
We study adversarial combinatorial bandits with m-set actions, where at each round the learner selects m out of d items and observes only the aggregate loss of the selected items. The resulting action set contains K=(md) elements and can therefore be exponentially large. Nevertheless, the loss of every action is determined by the same d-dimensional vector of item losses. We propose a computationally efficient algorithm that exploits this structure without explicitly enumerating the action set. Against adaptive non-anticipating adversaries, it guarantees, with probability at least 1−δ, regret against the best fixed action of
RT=O(dTlog(K/δ)).
This matches the high-probability regret bound of the finite-action EXP3-KW algorithm of Zimmert and Lattimore, whose direct implementation may require exponential space. Our algorithm instead represents each sampling distribution with d parameters and runs in polynomial time without enumerating the action set. Thus, it resolves the open problem posed by Maiti et al.
Francesco Bacchiocchi, Tommaso Cesari, Roberto Colomboni
DEIB, Politecnico di Milano, Milano, Italy · School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada · School of Mathematics, University of Bristol, Bristol, United Kingdom
We study nonnegative submodular maximization subject to a general matroid when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity, single-element exchange rule, or spiteful drop step, the algorithm retains limiting approximation factors 1/e for non-monotone objectives and 1−1/e for monotone objectives. More precisely, under every controlled oracle f satisfying ∣f(S)−f(S)∣≤ξ for every set S, our implementation returns a feasible set with expected value at least (1/e−ε)\OPT−O(kξ) and (1−1/e−ε)\OPT−O(kξ), respectively, using O(nk2ε−2) oracle calls. As a consequence, the offline-to-online reduction yields full-bandit CMAB algorithms for general matroid-constrained submodular rewards with exact limiting approximation-regret factors 1/e and 1−1/e and O(n1/5k4/5T4/5) regret.
Vaneet Aggarwal
V. Aggarwal is with Purdue University, West Lafayette IN, USA
This paper studies generalized low-rank matrix bandits with multiple prioritized objectives. At each round, the learner selects a matrix-valued arm and observes a vector-valued reward, whose components correspond to multiple objectives with different priority levels. Each objective is governed by an objective-specific generalized low-rank matrix model, and the learner evaluates arms according to a lexicographic preference order, prioritizing higher-level objectives before lower-level ones. We propose \textsc{Lexi-LowGLM}, an efficient online algorithm that first estimates objective-specific low-rank subspaces and then performs lexicographic learning in the reduced feature spaces. Unlike existing single-objective algorithms that repeatedly solve a batch generalized linear estimator using all historical observations, \textsc{Lexi-LowGLM} updates each objective-specific estimator via an online Newton step, reducing the estimator-update complexity over T rounds from O(T2) to O(T). We establish a regret bound of O(Wilexm(d1+d2)rT) for each objective i∈[m], where r is an upper bound on the ranks of the objective-specific parameter matrices and Wilex characterizes the lexicographic trade-off effect. This bound depends on the effective low-rank dimension (d1+d2)r rather than the ambient dimension d1d2. Numerical experiments further validate the effectiveness and computational efficiency of the proposed method.
Bo Xue, Ji Cheng, Haodong Jing +2
City University of Hong Kong. · Xi’an Jiaotong University. · Northwestern Polytechnical University.
We consider a stochastic multi-objective bandit problem where, at each round, the agent selects a slate of k arms and observes their d-dimensional reward vectors under semi-bandit feedback. We do not aim at identifying a single optimal arm; instead, we consider the problem of maintaining a small set of actions that jointly approximate the Pareto frontier. We formalize this objective through the dominated hypervolume induced by the selected subset of arms, and define an α-approximate hypervolume regret with respect to the best size-k subset achievable in hindsight, where α=1−1/e reflects the approximation guarantee of greedy maximization for monotone submodular functions. To address this problem, we introduce \textit{THV-UCB}, an optimistic algorithm that selects arms greedily based on optimistic estimates of their marginal hypervolume contributions. We establish a gap-free regret bound O~(dnkT) that holds on every instance, together with a gap-dependent bound O~(nk2.5/Δmin) that becomes polylogarithmic in T once the arms are sufficiently well separated. Our results provide theoretical support for using small subsets to approximate Pareto fronts in various multi-objective applications.
Nicolas Gutowski, Fabien Chhel, Alexandre Letard +1
Université d’Angers, LERIA, SFR MATHSTIC, Angers, France · ESEO, ERIS, Angers, France · AlphaEdge, Saint-Barthélémy-d’Anjou, France +1
Reliable wireless connectivity is essential for urban air mobility (UAM) networks in dense urban environments. It is therefore imperative to carefully plan the supporting communication infrastructure for UAM flight corridors. Most existing works optimize communication infrastructure and UAV flight paths independently, often leading to unnecessary base station (BS) deployment or excessive flight detours. This paper studies the joint optimization of BS deployment and UAV flight corridors in complex urban environments, aiming to minimize both infrastructure investment and flight distance while satisfying communication quality constraints. We propose CR-CMAB, a channel reciprocity-guided combinatorial multi-armed bandit framework. The framework constructs high-fidelity radio maps using 3D ray tracing, selects BS combinations via coverage-aware CMAB search, and dynamically expands the search space by identifying promising BS locations through channel reciprocity. Experimental results from a detailed case study demonstrate that CR-CMAB outperforms baseline methods with moderate computational time, yielding more strategically positioned BSs and shorter flight corridors. This study offers a practical planning perspective for cost-effective and communication-reliable UAM deployment in future smart cities.
We study the contextual combinatorial semi-bandit (CCSB) problem with general reward function approximation. At each round, the learner observes a context, selects a combinatorial action consisting of a subset of basic arms, and receives the reward of each selected arm; the goal is to maximize the cumulative reward over time. We propose SquareCB.Comb, a computationally efficient algorithm that, at each round, solves a convex optimization problem to sample a combinatorial action that balances exploration and exploitation. SquareCB.Comb scales to large arm sets and imposes no structural assumptions on the action set beyond a cardinality bound of m on each combinatorial action. We prove that SquareCB.Comb achieves a minimax optimal regret bound of O(mATlog∣F∣), where A is the number of arms, m is the maximum number of arms in a combinatorial action, T is the time horizon, and F is the reward function class. In the realizable setting, this bound matches the state-of-the-art regret guarantees achieved by policy search-based algorithms in the more restricted slate recommendation settings, while simultaneously generalizing to arbitrary combinatorial action structures and general reward function approximation.
We investigate the contextual slate bandit problem with generalized linear rewards under limited adaptivity. At each round, the learner is presented with N sets of items, where each item is represented by a d-dimensional feature vector. The learner then constructs a slate by selecting one item per set; the resulting slate yields a scalar reward sampled from a Generalized Linear Model (GLM). We propose algorithms under two limited-adaptivity settings: (a) Batched and (b) Rarely-Switching. For the batched setting, we introduce B-SlateGLinCB, which partitions the time horizon into O(loglogT) batches such that each batch's policy relies only on data from previous batches. For the rarely-switching setting, we propose RS-SlateGLinCB, which adaptively performs only O(NdlogT) parameter updates. Under a diversity assumption on the item sequences, we prove that B-SlateGLinCB and RS-SlateGLinCB achieve regret bounds of O(Nd3/2T) and O(NdT), respectively. Notably, both bounds are independent of the non-linearity parameter κ that is typically found to scale the regret of GLM bandit algorithms. Our algorithms are computationally efficient, requiring only poly(N) time per round despite 2Ω(N) possible slates. Simulations show our algorithms outperform existing baselines with limited adaptivity and remain competitive with Slate-GLM-OFU, a fully adaptive state-of-the-art algorithm. Notably, a slightly modified B-SlateGLinCB empirically matches this baseline. Finally, we demonstrate strong performance in a practical in-context example selection task for language models.
Selective ensemble for modern machine learning systems requires choosing promising model candidates under limited evaluation budgets, while downstream tasks often specify only partial preferences over capabilities such as accuracy, robustness, and reasoning. This setting naturally gives rise to a sequential decision problem under partially specified linear preferences. We formalize it as preference-directed multi-objective bandits (PDMOB), where admissible trade-offs are represented by a polyhedral preference cone. Based on this formulation, we introduce Pareto C-optimality, which recovers standard Pareto optimality and single-weight scalarization as special cases. We then propose the preference-directed upper confidence bound (PrefUCB) algorithm, which maintains directional confidence intervals to guide exploration. We analyze both indicator-based and gap-weighted regret, and establish instance-dependent logarithmic bounds for both criteria, recovering the optimal logarithmic dependence on the horizon T in classical special cases. Experiments on large pre-trained model selective ensemble tasks and online asset allocation under institutional mandates validate the efficacy of our method.
Lanjihong Ma, Zhen-Yu Zhang, Masashi Sugiyama +1
Department of Computer Science, Zhejiang Gongshang University, China · Center for Advanced Intelligence Project, RIKEN, Japan · Graduate School of Frontier Sciences, The University of Tokyo, Japan +1
Identifying Pareto optimal solutions is critical to support multi-objective decision-making. We introduce the first anytime Multi-Objective Multi-Armed Bandit algorithm for the Pareto Set Identification problem, taking a Bayesian approach: Top-Two Pareto Front Thompson Sampling (TTPFTS). We benchmark TTPFTS against state-of-the-art fixed-budget Pareto Set Identification algorithms on synthetic environments. Next, we demonstrate its practical utility in a challenging multi-objective molecular discovery setting by efficiently exploring an ultra-large synthesis-on-demand molecular library. Furthermore, we introduce a novel uncertainty quantification metric that estimates our algorithm's confidence in the predicted Pareto set. We demonstrate that this metric effectively proxies true performance, yielding a robust methodology for monitoring learning progress in complex settings. Finally, we complement these empirical findings with a theoretical proof of the algorithm's asymptotic correctness.
Lennert Saerens, Bram Silue, Eleni Litsa +2
Artificial Intelligence Lab, Departement of Computer Science, Vrije Universiteit Brussel, Brussels, Belgium · imec, Leuven, Belgium
Personalized decision-making in multi-objective bandits requires learning user-specific trade-offs among competing objectives. Since arm utility depends on both unknown rewards and unknown preferences, existing methods infer preferences only from utility feedback, entangling preference learning with reward exploration. In practice, however, users often reveal their priorities through proactive conversational queries (e.g., "cheap and clean hotel"), yet this structured signal is not leveraged. We formalize a proactive query-based framework in which user queries provide structured preference signals. Modeling these signals via a Plackett-Luce subset choice model, we show that query-only learning is insufficient due to a fundamental shift-invariance barrier. To resolve this, we introduce MO-PQUCB, a hybrid algorithm that integrates query-based preference anchoring with bandit feedback through shift-invariant regularization and dual-exploration UCB. We prove that proactive queries accelerate preference estimation and yield improved regret scaling over prior preference-aware MO-MAB methods. Under corrupted queries, we further characterize statistical limits and design a robust estimator achieving near-optimal performance when the corruption is sparse. Experiments validate both theoretical and practical gains.
Linfeng Cao, Ming Shi, Ness B. Shroff
Department of Computer Science and Engineering, The Ohio State University · Department of Electrical Engineering, University at Buffalo · Department of Electrical and Computer Engineering, The Ohio State University
Prompt engineering has become central to eliciting the capabilities of large language models (LLMs). At its core lies prompt selection -- efficiently identifying the most effective prompts. However, most prior investigations overlook a key challenge: the inherently multi-faceted nature of prompt performance, which cannot be captured by a single metric. To fill this gap, we study the multi-objective prompt selection problem under two practical settings: Pareto prompt set recovery and best feasible prompt identification. Casting the problem into the pure-exploration bandits framework, we adapt provably efficient algorithms from multi-objective bandits and further introduce a novel design for best feasible arm identification in structured bandits, with theoretical guarantees on the identification error in the linear case. Extensive experiments across multiple LLMs show that the bandit-based approaches yield significant improvements over baselines, establishing a principled and efficient framework for multi-objective prompt optimization.
Donghao Li, Chengshuai Shi, Weijuan Ou +2
University of Virginia, Charlottesville, VA 22904, USA · Princeton University, Princeton, NJ 08544, USA · Southern University of Science and Technology, Shenzhen, Guangdong 518055, China
We revisit combinatorial Thompson sampling (CTS) for semi-bandits with sleeping arms, where arm availability varies over time and actions must satisfy combinatorial constraints, as in wireless mesh routing with fluctuating link availability. Despite its practical relevance, CTS has been hindered by several long-standing problems: (i) the absence of worst-case regret guarantees in the semi-bandit setting even without sleeping arms, (ii) the lack of theory under adversarially varying availability, and (iii) the consistently weak empirical performance of CTS with Gaussian priors (CTS-G). This paper resolves these long-standing issues by providing the first worst-case regret analysis of CTS-G, proving an upper bound of O~(mNT) and a matching lower bound of Ω~(mNT). To bridge the gap between theory and practice, we further propose CL-SG, a simple CTS-G variant that samples a single shared Gaussian seed each round to coordinate exploration across arms. We show that CL-SG achieves an improved regret bound of O~(mNT), together with a matching lower bound Ω(mNT). Experiments on real-world datasets demonstrate that CL-SG consistently outperforms strong baselines including CTS-G and CTS-B, and we open-source our implementation for reproducibility.
Zhiming Huang, Bingshan Hu, Jianping Pan
Paul G. Allen School of Computer Science & Engineering, University of Washington, WA, USA · Department of Computer Science, University of British Columbia, BC, Canada · Department of Computer Science, University of Victoria, BC, Canada
We propose a new framework for meritocratic fairness in budgeted combinatorial multi-armed bandits with full-bandit feedback (BCMAB-FBF). Unlike semi-bandit feedback, the contribution of individual arms is not received in full-bandit feedback, making the setting significantly more challenging. To compute arm contributions in BCMAB-FBF, we first extend the Shapley value, a classical solution concept from cooperative game theory, to the K-Shapley value, which captures the marginal contribution of an agent restricted to a set of size at most K. We show that K-Shapley value is a unique solution concept that satisfies Symmetry, Linearity, Null player, and efficiency properties. We next propose K-SVFair-FBF, a fairness-aware bandit algorithm that adaptively estimates K-Shapley value with unknown valuation function. Unlike standard bandit literature on full bandit feedback, K-SVFair-FBF not only learns the valuation function under full feedback setting but also mitigates the noise arising from Monte Carlo approximations. Theoretically, we prove that K-SVFair-FBF achieves O(T3/4) regret bound on fairness regret. Through experiments on federated learning and social influence maximization datasets, we demonstrate that our approach achieves fairness and performs more effectively than existing baselines.
The K-Max combinatorial multi-armed bandit problem arises in applications such as recommendation and distributed decision making, where the reward is determined by the maximum outcome among K selected arms. When outcomes are continuous and only the maximum value together with the winner's index is observed, this problem introduces unprecedented difficulties including discretization errors, non-deterministic tie-breaking, and severe estimation biases. To overcome these barriers, we introduce DCK-UCB, an efficient algorithm combining adaptive discretization with bias-corrected confidence bounds. We prove that DCK-UCB achieves a O(T3/4) regret bound, the first sublinear guarantee in this setting. Numerical experiments show strong performance over baseline methods. Furthermore, for the specific case of exponential distributions under full-bandit feedback, we propose the MLE-Exp algorithm that attains a near-optimal O(T) regret bound. This work establishes fundamental theoretical guarantees and provides a powerful algorithmic solution for continuous combinatorial bandits.
Yu Chen, Siwei Wang, Longbo Huang +1
Institute for Interdisciplinary Information Sciences, Tsinghua University · 2Microsoft Research Asia