Combinatorial multi-armed bandits provide a fundamental online decision-making environment where a decision-maker interacts with an environment across T time steps, each time selecting an action and learning the cost of that action. The goal is to minimize regret, defined as the loss compared to the optimal fixed action in hindsight under full-information. There has been substantial interest in leveraging what is known about offline algorithm design in this online setting. Offline greedy and linear optimization algorithms (both exact and approximate) have been shown to provide useful guarantees when deployed online. We investigate local search methods, a broad class of algorithms used widely in both theory and practice, which have thus far been under-explored in this context. We focus on problems where offline local search terminates in an approximately optimal solution and give a generic method for converting such an offline algorithm into an online stochastic combinatorial bandit algorithm with O(log3T) (approximate) regret. In contrast, existing offline-to-online frameworks yield regret (and approximate regret) which depend sub-linearly, but polynomially on T. We demonstrate the flexibility of our framework by applying it to three online stochastic combinatorial optimization problems: scheduling to minimize total completion time, finding a minimum cost base of a matroid and uncertain clustering.
We study online learning with an additional offline dataset in the stochastic linear bandit setting. Although this problem arises frequently in practice, the offline-to-online tradeoff remains poorly understood in structured environments. We propose a linear bandit algorithm that balances this tradeoff: it relies on offline data during early rounds, and increasingly favors exploration as the horizon grows. We establish regret bounds showing that our method is simultaneously competitive with both purely online and purely offline solutions. In particular, it achieves sublinear regret relative to the optimal action in the number of online interactions, while its regret relative to an offline reference decreases as the number of offline samples grows. Empirical results further demonstrate its effectiveness across various problem parameters.
Kushagra Chandak, Toshinori Kitamura, Xiaoqi Tan
Department of Computing Science, University of Alberta, Canada
A matching platform is a system that matches participants of different types, such as companies and job-seekers. In such a platform, maximizing matches may concentrate assignments on popular participants, increasing dissatisfaction among others, and eventually causing churn, which reduces the platform's profit opportunities. To address this issue, we propose a novel online learning problem, Combinatorial Allocation Bandits (CAB), which incorporates the notion of arm satisfaction. In CAB, at each round, the learner observes feature vectors for K arms and N users, assigns users to arms, and observes feedback following a generalized linear model (GLM). Unlike prior work, the objective is to maximize arm satisfaction rather than the number of positive feedback. For CAB, we develop an upper confidence bound algorithm that uses an approximate optimization oracle and achieves an approximate regret upper bound, whose dependence on d, T, and N matches the known lower bound for contextual combinatorial linear bandits up to logarithmic factors. We also analyze a Thompson sampling algorithm with a standard regret bound under an exact optimization oracle, and propose a cheaper one-pass variant retaining sublinear approximate regret under a self-concordance assumption. Experiments on synthetic data support the objective and show that CAB-UCB achieves higher cumulative satisfaction than baselines.
Yuki Shibukawa, Koichi Tanaka, Yuta Saito +1
The University of Tokyo and RIKEN · Keio University · Hanuku-kaso, Co., Ltd.
We study nonnegative submodular maximization on n elements subject to a general matroid of rank k, 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, given an error bound ξ≥0, 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, where OPT is the feasible optimum. The implementation uses a deterministically bounded budget of O(nk2ε−2lognlog2(1/ε)) oracle calls. As a consequence, an offline-to-online reduction yields full-bandit combinatorial multi-armed 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 over T rounds. These online guarantees allow exploration to play sets that become independent after deleting at most one element; exploitation and the benchmark remain matroid-feasible. For unit-capacity partition matroids we obtain O(n1/5k3/5T4/5) under the same exploration relaxation. We establish a deterministic query budget by truncating the Poisson process and identify the enlarged action set needed to answer its offline queries.
Vaneet Aggarwal
V. Aggarwal is with Purdue University, West Lafayette IN, USA