# Offline Local Search for Online Stochastic Bandits

arXiv: https://arxiv.org/abs/2604.09423 · HTML: https://mlsanity.com/paper/2604.09423/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 56 references that are in the map.
- First posted on arXiv 10 Apr 2026.

## Builds on (most cited first, 16 of 16)

- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Efficient Learning in Large-Scale Combinatorial Semi-Bandits](https://mlsanity.com/paper/1406.7443/) (2014)
- [Oracle-Efficient Online Learning and Auction Design](https://mlsanity.com/paper/1611.01688/) (2016)
- [Logarithmic Regret in Feature-based Dynamic Pricing](https://mlsanity.com/paper/2102.10221/) (2021)
- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits](https://mlsanity.com/paper/1503.05087/) (2015)
- [Online Allocation and Pricing: Constant Regret via Bellman Inequalities](https://mlsanity.com/paper/1906.06361/) (2019)
- [Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Bandits](https://mlsanity.com/paper/2002.07258/) (2020)
- [Linear Bandit Algorithms with Sublinear Time Complexity](https://mlsanity.com/paper/2103.02729/) (2021)
- [An Improved Local Search Algorithm for k-Median](https://mlsanity.com/paper/2111.04589/) (2021)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Partitioning into Expanders](https://mlsanity.com/paper/1309.3223/) (2013)
- [BandMaxSAT: A Local Search MaxSAT Solver with Multi-armed Bandit](https://mlsanity.com/paper/2201.05544/) (2022)
- [Local-Search based Approximation Algorithms for Mobile Facility Location Problems](https://mlsanity.com/paper/1301.4478/) (2013)
- [A Local Search-Based Approach for Set Covering](https://mlsanity.com/paper/2211.04444/) (2022)

## Abstract (arXiv)

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(log3 T) (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.