Offline Local Search for Online Stochastic Bandits Gerdus Benadè∗
Rathish Das†
Thomas Lavastida‡
arXiv:2604.09423v1 [cs.LG] 10 Apr 2026
Abstract 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.
1
Introduction
Online learning is a cornerstone of modern algorithm design. The bandit setting, in which the learner only receives cost feedback, epitomizes the trade-off between exploration and exploitation [5, 6, 35]. Here, an algorithm makes a sequence of decisions x1 , x2 , . . . , xT over a series of T discrete time periods. In response to each decision xt , the environment generates a cost ct (xt ) (either adversarially [6] or stochastically [5]), and the algorithm’s objective is to minimize its cumulative cost across all T periods. As feedback to improve future decisions, the algorithm observes each cost ct (xt ), which is known as bandit feedback. Notably, the algorithm does not observe what the cost would have been if, instead, a different action was chosen at each period, necessitating a trade-off between exploring the action space to find promising solutions and exploiting previously discovered low-cost solutions. Regret measures the difference between the cumulative cost achieved by an algorithm and that of the best fixed solution under full information. A common objective is to construct algorithms with regret that is sub-linear in T , i.e., o(T ). In the combinatorial bandit setting [4, 14, 16], the learner must additionally navigate an exponentially large space of actions, rendering some approaches computationally infeasible. There is substantial interest in developing general frameworks for designing online algorithms, especially frameworks that convert offline algorithms (in either a black- or white-box fashion) into effective bandit algorithms; see, for example, Dudík et al. [21], Kakade et al. [32], Kalai and Vempala [33], Niazadeh ∗
Boston University, MA, USA. [email protected]. University of Houston, TX, USA. [email protected]. ‡ University of Texas at Dallas, TX, USA. [email protected]. †
1
Algorithm 1: Generic Local Search Data: Feasible set X , neighborhood map N , cost function Cost, and parameter β ∈ (0, 1) Result: Approximate locally optimal solution 1 Procedure LocalSearch(X , N , Cost): 2 x0 ← any feasible solution from X 3 t←0 4 while True do 5 xt+1 ← arg minx′ ∈N (xt ) Cost(x′ ) 6 if Cost(xt+1 ) ≤ β Cost(xt ) then 7 t ← t + 1 //Move to the next iteration 8 else 9 return xt //Approximate local optimum found et al. [42], and Agarwal et al. [1]. Such frameworks allow us to leverage the wealth of knowledge about offline algorithms to construct online learning algorithms. Notable techniques for designing offline algorithms that have proven to be successful in ‘offline-to-online’ frameworks include greedy algorithms [24, 42, 43] and offline linear optimization in both exact [33] and approximate [32, 33] settings. These all utilize sophisticated algorithm design and analysis techniques to convert the offline algorithm to an effective bandit learning algorithm with regret (or γ-regret [27, 32, 42]) which scales sub-linearly in T , more specifically, with regret which scales as T ρ for some ρ ∈ (0, 1) (usually ρ = 1/2 or ρ = 2/3). The focus of our paper is local search — another technique widely used in the design of offline algorithms. A local search algorithm consists of three components: a set of feasible solutions X , a neighborhood map N : X → 2X , and a cost function Cost : X → R. Starting from an initial feasible solution x0 ∈ X , local search methods iteratively set xt+1 = arg minx′ ∈N (xt ) Cost(x′ ), for t = 1, 2, . . . (for a minimization problem), continuing until a locally optimal solution, i.e., a solution x ∈ X such that Cost(x) ≤ Cost(x′ ) for all x′ ∈ N (x), is found. Often, to increase efficiency, a local move is accepted only if it improves upon the current solution by a β-factor, for some β ∈ (0, 1), and we instead converge to an approximate locally optimal solution. This method is more formally described in Algorithm 1. By setting β sufficiently close to 1, the resulting local search method can often be shown to converge in a polynomial number of iterations. In practice, local search methods are appealing due to their ease of implementation, efficiency, and ability to find good solutions quickly [8, 12, 40]. Theoretical approximation guarantees have also been established for local search methods for a variety of problems [2, 3, 9, 13, 15, 26, 31]. Despite this widespread use in offline algorithm design, local search has been under-explored as a framework for designing combinatorial bandit algorithms. In fact, as far as we are aware, the connection between local search and bandit algorithms has been in the opposite direction — several papers use multi-armed bandit algorithms to improve the performance of local search algorithms in practical settings [34, 39, 51, 52]. Thus, the main question we study in this paper is: Can we convert a good offline local search algorithm into an effective online bandit learning algorithm? If so, what regret guarantees can be achieved using this framework?
1.1
Our Approach and Results
Our main contribution is the development of a general framework for converting an offline local search algorithm to an online stochastic bandit algorithm. It requires that the local search neighborhood 2
must admit (β, γ)-improving moves which, informally, means that the neighborhood of a solution x with Cost(x) > γ Cost(x∗ ), where x∗ is an optimal solution, must contain a solution x′ which is a β-factor improvement over x, in other words, Cost(x′ ) ≤ β Cost(x). In particular, it is straightforward to verify that any problem on which Algorithm 1 terminates in an approximately optimal solution permits (β, γ)-improving moves for appropriate choices of β and γ. Our main result is that local search algorithms with (β, γ)-improving neighbourhoods can be used online to guarantee γ-regret with O(log3 T ) dependence on T . Theorem 1.1 (Informal version of Lemma 3.1). Suppose a problem admits (β, γ)-improving moves. Then we can construct an algorithm for the stochastic online variant with bandit feedback with O M · Cmax · poly(β −1 ) · log3 T γ-regret after T rounds, where Cmax = maxx∈X ,z∈Z Cost(x, z) is an upper bound on solution costs and M = maxx∈X |N (x)| is the largest neighborhood of a feasible solution. We remark that M , Cmax , and β −1 all can be bounded polynomially in problem specific parameters for each of the applications we consider, and are thus independent of T . Note that β may depend on γ, so the regret bound may deteriorate as we get closer to exact (γ = 1) regret. Intuitively, more samples are required to distinguish between solutions with objective function value OPT and γ · OPT. The poly-logarithmic dependence on T is perhaps most surprising. While direct comparisons between offline-to-online frameworks is difficult, this is a substantially better dependence on T than the O(T 2/3 ) γ-regret guarantee obtained by Niazadeh et al. [42] via offline greedy algorithms, at the cost of multiplicative factors that depend on the problem and local search neighborhood. The resulting algorithm, in essence, attempts to mimic Algorithm 1 while handling the complications that sprout from the fact that only the stochastically realized cost of the solution submitted in each period is observed. First, the cost of a solution must be estimated by sampling for several time periods. The algorithm attempts to maintain, with high probability, a solution with expected cost below a threshold, which decreases geometrically over time. Whenever the estimated cost of the current solution exceeds this threshold, the solutions in its neighborhood is explored. Neighboring solutions must be carefully sampled to ensure that even neighbors with very high costs do not incur large regret, at the same time, we need enough samples to identify β-improving moves with high probability whenever the current solution is not a γ-approximation of the optimal solution. This is done by using a successive-elimination style algorithm [22, 23] on the neighborhood. When a β-improving move is found during exploration it becomes the new current solution. This process repeats until time T or a local optimum is found. To round out our results, we apply our framework to the repeated online bandit feedback versions of three problems: scheduling to minimize total completion time under stochastic job sizes, finding a minimum cost base in a matroid under stochastic element costs, and uncertain k-median clustering. Scheduling to Minimize Total Completion Time: When scheduling to minimize total completion time, a feasible solution is a permutation π of n jobs which schedules job j ∈ [n] in position π(j). In each time step the size Pj of each job jPis drawn from a distribution. Given job sizes P1 , . . . , Pn , the cost of solution π is Cost(π, P ) = nj=1 (n − π(j) + 1)Pj , the total makespan. We show the neighborhood consisting of swapping a single pair of jobs is (1 − ϵ/n2 , 1 + ϵ)-improving. As a result, we have an algorithm for minimizing online total completion time with (1 + ϵ)-regret in the order of O n12 log3 T /ϵ4 .
3
Minimum Cost Base in a Matroid: For the problem of finding a minimum cost base for a matroid, a feasible solution is a base, or maximal independent set, B. Given stochastic realizations P of element costs Z, the cost of base B is Cost(B) = s∈B Zs . We show the neigborhood which consist of bases constructed by adding an arbitrary element to the current solution and removing an element from the resulting circuit is (1 − ϵ/(2r), 1 + ϵ)-improving, where r is the rank of the matroid. This implies an online algorithm with (1 + ϵ)-regret in the order of O nr6 log3 T /ϵ4 , where n is the size of the ground set. A special case of this result establishes a similar regret bound for the problem of finding minimum cost spanning trees in a graph. Uncertain k-Median Clustering: In the uncertain k-median clustering problem the locations of n points are sampled in a metric space with diameter 1 and the task is to select k cluster centers from a set of m potential centers to minimize the cost, defined as the sum of distances from each point to its closest cluster center. We use a local search algorithm analysed by Arya et al. [3] and Cormode and McGregor [17] to show the single swap neighbourhood is (1 − 1/n2 , 5(1 − 1/n))-improving, 3 9 2 implying 5(1 − 1/n))-regret which is O n m log T .
1.2
Additional Related Work
As discussed above, we study a combinatorial bandit setting [4, 14, 16], and our work is closest to other ‘offline-to-online’ frameworks including Kalai and Vempala [33] and Dudík et al. [21], where it is assumed that the offline version of the problem can be easily solved, and Niazadeh et al. [42], which considers problems with robust greedy approximation algorithms satisfying a property called Blackwell reducibility. We also highlight the recent work of Agarwal et al. [1] which gives √ a general framework for online learning in monotone stochastic optimization problems achieving O( T log T ) regret against the best approximation algorithm for the offline problem under known distributions. Notably, their results hold in the semi-bandit setting in which the algorithm observes realizations of some (but not all) of the underlying random variables in addition to the realized cost. Our results hold for the pure bandit setting where only the cost information is observed. Next, we briefly touch on other related topics. Logarithmic Regret in Online Learning: Due to the existence of strong lower bounds in many online learning settings [5, 35], it is typically necessary to make additional assumptions concerning the environment, or relax the benchmark, in order to achieve regret bounds improving beyond the typical O(T ρ ) for some ρ ∈ (0, 1). For example, in online convex optimization, logarithmic regret is achievable if the sequence of convex functions satisfies strong convexity [30, 45]. Similarly, logarithmic regret may be possible if certain problem-dependent parameters are bounded appropriately. For example, Xu and Wang [49] achieve logarithmic regret in feature-based dynamic pricing whenever the minimum eigenvalue of a problem-dependent matrix is bounded from below, and Vera et al. [47] achieve logarithmic regret for contextual bandits with knapsacks whenever the weight of an item is bounded from below. In contrast to assuming additional structure, we give poly-logarithmic regret guarantees against a relaxed benchmark, so-called γ-regret. Our bound is not problem-dependent, and holds for a wide class of instances as long as the local search neighborhood admits (β, γ)-improving moves. For settings where the corresponding offline problem is NP-hard, it is necessary to allow a multiplicative approximation factor. our result is especially interesting in this context, since we achieve γ-regret that scales as O(log3 T ) while prior frameworks including those due to Kakade et al. [32] and Niazadeh et al. [42] have γ-regret which scales as T 2/3 .
4
Efficient Bandit Algorithms: The exploration strategies specified by many standard approaches to bandit problems can be computationally intractable for large action spaces [36]. As a result, there is significant interest in developing algorithms with more efficient implementations [7, 18, 41, 43, 48, 50]. Since our algorithm is based on local search and performs exploration locally, it naturally lends itself to a computationally efficient implementation.
1.3
Roadmap
We organize the rest of this paper as follows. Section 2 formally sets up our model and recalls preliminary results we need for our analysis. Then we describe our ‘offline-to-online’ algorithm utilizing local search and provide a high-level overview of its analysis in Section 3. Following this, Section 4 demonstrates the applicability of our framework on the problems we discussed above. Section 5 concludes the paper and discusses potential directions for future work.
2
Preliminaries
We now formally define the general problem setting we consider — stochastic combinatorial bandits with local search. First, each instance is associated with a set X of feasible solutions1 and for each x ∈ X there is a random non-negative cost associated with it. We model the randomness as a collection of latent variables taking values in some space Z, for which there is an unknown distribution D ∈ ∆(Z) over the possible values the latent variables can take. Thus we can model the cost as a function Cost : X × Z → R+ , which induces a distribution on the realized cost for a fixed x ∈ X as Cost(x, Z), where Z ∼ D. To streamline our notation, we let Cost(x) := EZ∼D [Cost(x, Z)] be the expected cost of playing x ∈ X and set OPT := minx∈X Cost(x) to be the minimum expected cost of any feasible solution. In the online bandit setting, we consider making a sequence of decisions {xt }Tt=1 , where each xt ∈ X , in order to optimize an objective over a time horizon of T periods in the presence of bandit (cost) feedback. An algorithm (or policy) A is a sequence of maps {At : Ht−1 → X }Tt=1 which each takes the observed history H t−1 up to period t − 1 and returns a new solution xt to be used in period t 2 . In the bandit setting, a history up to period t is a sequence {Xs , Ys }ts=1 , where Ys = Cost(Xs , Zs ) is the observed random cost at step s for some independent sample Zs ∼ D. Notice {Zs }Ts=1 , the realizations of randomness that underlying the cost or reward, is unobserved. Formally, histories are random variables over (X × R+ )t . We let Ht = (X × R+ )t be the set of all length t sequences over solution-cost pairs. For simplicity, we let A1 be a constant function since no history has been observed at period 1. Our main interest is giving algorithms with low γ-regret, which measures the difference in cumulative expected cost between the algorithm and using a γ-approximate solution for all T periods, which we can now define formally. Definition 2.1 (γ-Regret). For an algorithm A, latent distribution D, time horizon T , and γ ≥ 1, we define Regretγ (A, D, T ) :=
T X
E [Cost(Xt , Zt )] − γ · T · OPT
(1)
t=1 1 We are mainly interested in the case where X is finite (but potentially large), so minimizing a function over X is well-defined. 2 We focus on deterministic algorithms. We can extend to randomized algorithms by letting At be a map to ∆(X ) and taking an additional expectation over the realized distribution of actions.
5
to be the T -period γ-regret of algorithm A on distribution D, where the expectation is taken with respect to the independent samples (Z1 , Z2 , . . . , ZT ) ∼ DT and any internal randomness utilized by A. We say that algorithm A has γ-regret R(T ) if for all distributions D, Regretγ (A, D, T ) ≤ R(T ). We remark that if γ = 1, then we recover the standard definition of regret used in stochastic multi-armed bandits. As discussed in Section 1.1, our goal is to find algorithms with γ-regret whose dependence on T is not just o(T ) but is O(poly(log T )), which is o(T ρ ) for any ρ ∈ (0, 1). Local search will allow us to avoid some of the difficulties that arise with exploring the large action spaces that can arise in stochastic combinatorial bandit problems. For a feasible solution space X , let N : X → 2X be its neighborhood map so that for each x ∈ X , N (x) is a set of neighboring solutions to x. We assume that M := maxx∈X |N (x)| is a priori known to the algorithm, which holds in all the examples we consider. The key property of a neighborhood map that we require to achieve strong γ-regret bounds is that any solution which has expected cost worse than γOPT has a neighboring solution which has multiplicative improvement to its cost. Definition 2.2 ((β, γ)-improving moves). Consider the problem specified by feasible set X , neighborhood map N , and expected cost function Cost : X → R+ as defined above. We say the problem admits (β, γ)-improving moves if, for any x ∈ X with Cost(x) > γOPT, there exists x′ ∈ N (x) with Cost(x′ ) ≤ β Cost(x). The parameters β and γ can depend on the structure of the problem (e.g., the number of jobs in completion time scheduling) and β can depend on γ (e.g., if γ = 1 + ϵ, then β can depend on ϵ). A priori, it is perhaps unclear how to establish whether a problem permits (β, γ)-improving moves. Fortunately, there is a straightforward correspondence showing that all problems where Algorithm 1 terminates in an approximate solution must permit (β, γ)-improving moves. Observation 1. Given instance (X , N , Cost), whenever Algorithm 1 is guaranteed to terminate in a γ-approximation for some choice of β, then (X , N , Cost) permits (β, γ)-improving moves. Proof. We proceed by contradiction. Suppose that Algorithm 1 with parameter β terminates in a γ-approximation on a problem defined by (X , N , Cost), but the problem does not permit (β, γ) improving moves. Then there exists solution x ∈ X such that Cost(x) > γOPT and Cost(x′ ) > β Cost(x) for all x′ ∈ N (x). However, when using x as the starting x0 in Algorithm 1, the algorithm converges in some solution x◦ with Cost(x◦ ) ≤ γOPT. Now either x = x◦ , or the algorithm proceeds to a subsequent solution which yields a β-factor improvement en route to x◦ . In either case, this contradicts (X , N , Cost) not permitting (β, γ)-improving moves. Finally, we require the following version of the Chernoff bounds, see, e.g., [20] for a reference. Theorem P 2.3. Suppose that X1 ,P X2 , . . . , XN are independent random variables in the interval [0, 1]. Let µ = N1 i E[Xi ] and X̄ = N1 s Xs , then for all δ ∈ (0, 1) and any µH , µL such that µ ∈ [µL , µH ] we have: 2 2 δ N µH δ N µL Pr X̄ > (1 + δ)µH ≤ exp − and Pr X̄ < (1 − δ)µL ≤ exp − . 3 3
3
Stochastic Combinatorial Bandits from Offline Local Search
Our algorithm is formally described in Algorithms 2 and 3. The algorithm operates in a sequence of phases ℓ = 1, 2, . . . which are managed by the “for” loop in Algorithm 2. Each phase keeps track of a solution xℓ and a cost threshold θℓ := αℓ−1 Cmax = β (ℓ−1)/2 Cmax . The invariant which, due 6
to stochasticity, we wish to maintain with high probability is that Cost(xℓ ) ≤ θℓ . Thus, assuming Cost(xℓ ) ≤ θℓ , in phase ℓ we wish to either determine that Cost(xℓ ) ≤ αθℓ = θℓ+1 , find some x′ ∈ N (xℓ ) with Cost(x′ ) ≤ α Cost(xℓ ) ≤ αθℓ = θℓ+1 , or determine that no such x′ exists. In the first case we may set xℓ+1 = xℓ to maintain the invariant, while in the second we may set xℓ+1 = x′ to maintain the invariant. In the last case, we will use the fact that N satisfies Lemma 2.2 and no x′ was found to conclude that Cost(xℓ ) ≤ γOPT, and thus we use the current solution xℓ for all remaining periods. To achieve this, Algorithm 2 first uses solution xℓ for Nℓ time steps to get a rough estimate of its cost, then compares it to a threshold. The threshold is set so that if Cost(xℓ ) ≤ α2 θℓ then the estimated cost is highly likely to be smaller than the threshold. As discussed above, we then move to phase ℓ + 1 with xℓ+1 = xℓ . If instead, the estimated cost is larger than the threshold, we run the subroutine in Algorithm 3 which explores the neighborhood of xℓ . This subroutine returns a solution xNew , which is either some x′ ∈ N (x) or xℓ . If xNew is some x′ ∈ N (x), then we set xℓ+1 = xNew and move to phase ℓ + 1. Critically, we will show that with high probability Cost(xNew ) ≤ αθℓ = θℓ+1 to maintain the invariant in this case. Finally if xNew = xℓ , this indicates that nothing significantly better was found and so we break out of the “for” loop over phase ℓ, setting xLast = xℓ and using xLast until period T since, by Lemma 2.2, xLast will satisfy Cost(xLast ) ≤ γOPT with high probability. As discussed, we want Algorithm 3 to either find a neighboring solution which improves upon xℓ by at least an α-factor or indicate that no such improvement exists in N (xℓ ), and for this to hold with high probability. It is thus inevitable that a significant number of time steps are spent exploring the neighbourhood of xℓ . Doing so without incurring high regret requires some care. A first attempt might involve sampling each neighboring solution Nℓ times, as we did for xℓ in Algorithm 2, and comparing to an appropriate threshold. This may potentially incur linear regret in later phases when a neighboring solution could be significantly worse than the current solution xℓ . To avoid this, we sample neighboring solutions cautiously over a series of “sub-phases” of increasing length (Algorithm 3, line 4), where we progressively increase the amount of sampling only while the neighbouring solution has the potential to improve over xℓ . As a result, poor neighbours are eliminated in early subphases, reminiscent of the successive-elimination algorithm for stochastic multi-armed bandits [22], and sampled geometrically fewer times than the best solutions (and xℓ ). Let ALocal denote the algorithm described by Algorithms 2 and 3. Our main result is that the regret of ALocal scales poly-logarithmically with T as long as the underlying problem admits (β, γ)-improving moves. Theorem 3.1. Suppose that X , N , and the cost function Cost(·) = Ez∼D [Cost(·, z)] induced by D admit (β, γ)-improving moves. Then for all distributions D and all sufficiently large T , we have ! M Cmax log2 T Regretγ (ALocal , D, T ) = O (log T + log M ) , δ 2 α2 log2 α1 where ALocal is given by Algorithms 2 and 3, α =
3.1
√
β, Cmax = maxx∈X ,z∈Z Cost(x, z), and δ = 1−α 1+α .
Analysis
We now perform the analysis which will yield Lemma 3.1. First, we encapsulate our applications of concentration inequalities into the following lemma which we will apply several times. Lemma 3.2. Fix a solution x ∈ X and let z1 , z2 , . . . , zN be N := 3Cmax (4 log T + log M )/(δ 2 α2 θ) independent samples from D, where ℓ, M ∈ N, θ > 0, α ∈ (0, 1), and δ = 1−α 1+α ∈ (0, 1). Let P N 1 d Cost(x) = Cost(x, zs ). Then N
s=1
7
Algorithm 2: Local Search for Stochastic Combinatorial Bandits Data: Feasible set X , Max cost Cmax , M = supx∈X |N (x)|, and Parameters β, γ from Lemma 2.2 Result: Sequence of solutions with O(log3 T ) γ-regret 1 Procedure BanditLocalSearch(X , Cmax , β, γ): 2 x1 ←√any solution in X 3 α← β 4 δ ← (1 − α)/(1 + α) 5 θ1 ← Cmax 6 for phase ℓ = 1, 2, . . . do //Test the solution xℓ for the current phase ℓ 7 Nℓ ← 3Cmax (4 log T + log M ) / δ 2 α2 θℓ 8 Use solution xℓ for Nℓ periods d ℓ ) ← average cost of using x in these periods 9 Cost(x d ℓ ) > 2α2 θℓ then 10 if Cost(x 1+α
11 12
13 14 15
16 17 18 19 20
xNew ← TestNeighborhood(xℓ , ℓ, N ) if xNew = xℓ then //xℓ is locally optimal with high probability xLast ← xℓ break else //xNew is better than xℓ with high probability xℓ+1 ← xNew else xℓ+1 ← xℓ θℓ+1 ← αθℓ Use solution xLast until period T
i h 2α2 d θ ≤ M −1 T −4 , and (a) Cost(x) ≤ α2 θ =⇒ Prz1 ,z2 ,...,zN ∼DN Cost(x) > 1+α h i 2α2 d (b) Cost(x) ≥ αθ =⇒ Prz1 ,z2 ,...,zN ∼DN Cost(x) θ ≤ M −1 T −4 . ≤ 1+α Proof. For brevity, we write Pr[·] := Prz1 ,z2 ,...,zN ∼DN [·]. Setting Xs = Cost(x, zs )/Cmax for all s ∈ [N ], 2α2 we have that Xs ∈ [0, 1] and E[Xs ] = Cost(x)/Cmax . Observe that 1+α = (1 + δ)α2 = (1 − δ)α for 2 our choice of δ. For part (a), when Cost(x) ≤ α θ, observe that " # " # N 2θ 2θ 2 X d 2α Cost(x) α 1 α d Pr Cost(x) > θ = Pr > (1 + δ) = Pr Xs > (1 + δ) . 1+α Cmax Cmax N Cmax s=1
Since Xs ∈ [0, 1] and E[Xs ] ≤ α2 θ/Cmax , we may bound the right hand side using Lemma 2.3 as " # 2 N 1 X α2 θ δ N α2 θ Xs > (1 + δ) = M −1 T −4 , Pr ≤ exp − N Cmax 3Cmax s=1
where the right hand side follows from our choice of N . 8
Algorithm 3: Neighboring Solution Tester Data: Current solution xℓ , Phase number ℓ, Neighborhood N Result: Some solution x′ ∈ N (xℓ ) or xℓ 1 Procedure TestNeighborhood(xℓ , ℓ, N ): 2 for x′ ∈ N (xℓ ) do //Test the solution x′ 3 Better ← True 4 for sub-phase ℓ′ = 1, 2, . . . , ℓ do 5 Nℓ′ ← 3Cmax (4 log T + log M ) / δ 2 α2 θℓ′ 6 Use solution x′ for Nℓ′ periods d ′ ) ← average cost of using x′ in these periods 7 Cost(x //If x′ is not significantly better than x, move on from x′ d ′ ) > 2α2 θℓ′ then 8 if Cost(x 1+α
Better ← False break //If x′ passes all tests, update xℓ+1 to be x′ if Better = True then return x′ //Nothing significantly better found return xℓ
9 10
11 12
13
For part (b), when Cost(x) ≥ αθ, it follows that " # " # N 2 X d 2α αθ 1 αθ Cost(x) d Pr Cost(x) ≤ θ = Pr ≤ (1 − δ) = Pr Xs ≤ (1 − δ) . 1+α Cmax Cmax N Cmax s=1
Again, since Xs ∈ [0, 1] and E[Xs ] ≥ αθ/Cmax , we bound the right hand side using Lemma 2.3 as # " 2 N αθ 1 X δ N αθ Xs ≤ (1 − δ) Pr ≤ exp − ≤ M −1 T −4 , N Cmax 3Cmax s=1
where the right hand side follows from our choice of N and α ≤ 1. This completes the proof. 3.1.1
Handling Bad Events
Let L be the index of the (random) last phase that is encountered in Algorithm 2. To bound the overall regret, we will bound the total regret in phases with index ℓ < L and also show that the regret in the last phase L is negligible. Before we can do that, we need to define an appropriate sequence of “bad events” which are exceedingly unlikely, for which will be able to bound the regret when conditioning on their negation, as is standard. Definition 3.3. For each phase ℓ, let Mℓ be the event that Algorithm 2 makes it to phase ℓ and let Cℓ be the event that Cost(xℓ ) > θℓ . Then we define the bad event in phase ℓ as Bℓ := Mℓ ∧ Cℓ and Gℓ = ¬Bℓ . We will show that these events are unlikely. Intuitively, this will follow inductively by assuming that Bℓ is unlikely, and then we can use the definition of our algorithm to bound Pr[Bℓ+1 | Gℓ ] 9
and show that Bℓ+1 is unlikely via a standard decomposition. The key step involves bounding Pr[Bℓ+1 | Gℓ ]. Lemma 3.4. For each ℓ, we have Pr[Bℓ+1 | Gℓ ] ≤ T −3 Proving this lemma requires careful analysis of the TestNeighborhood subroutine (Algorithm 3), which we postpone momentarily. For now, we show Lemma 3.4 implies a bound on Pr[Bℓ ]. Corollary 3.5. For each ℓ, we have Pr[Bℓ ] ≤ ℓT −3 . Proof. We proceed by induction on ℓ. For the base case when ℓ = 1, we have that Cost(x1 ) ≤ Cmax ≤ θ1 , and so Pr[B1 ] = 0 ≤ T −3 , proving the base case. Inductively, we assume that Pr[Bℓ ] ≤ ℓT −3 and aim to bound Pr[Bℓ+1 ]. By the law of total probability we have Pr[Bℓ+1 ] = Pr[Bℓ+1 | Bℓ ] Pr[Bℓ ] + Pr[Bℓ+1 | Gℓ ] Pr[Gℓ ] ≤ Pr[Bℓ ] + Pr[Bℓ+1 | Gℓ ] ≤ ℓT −3 + T −3 = (ℓ + 1)T −3 completing the proof of the inductive case and giving the corollary. 3.1.2
Analysis of the TestNeighborhood Subroutine
We now turn to analyzing Algorithm 3. Consider a phase ℓ of Algorithm 2 in which Algorithm 3 is called on solution xℓ and fix an iteration of the outer ‘for’ loop in Algorithm 3 in which solution x′ ∈ N (xℓ ) is considered. We call each iteration of the inner ‘for’ loop in Algorithm 3 a sub-phase, of which there are at most ℓ for each neighboring solution x′ ∈ N (x). Ideally, if Cost(x′ ) > αθℓ , then we do not make it past sub-phase ℓ when considering solution x′ (and actually, we need to be slightly more careful than this). The tools we develop here are needed to bound the regret incurred by using each neighboring solution x′ across each sub-phase. To start, we introduce the following definitions. Definition 3.6. For each x′ ∈ N (x), we say that x′ is a bad neighbor of x if Cost(x′ ) ≥ αθℓ . Additionally, let NB (x) ⊆ N (x) be the set of bad neighbors of x and let ℓ′ (x′ ) ∈ [ℓ] be the sub-phase index such that Cost(x′ ) ∈ [αθℓ′ (x′ ) , θℓ′ (x′ ) ] for each x′ ∈ NB (x). Definition 3.7. Let Bℓ′ be the event that in phase ℓ some bad neighbor x′ ∈ NB (xℓ ) makes it past sub-phase ℓ′ (x′ ) when Algorithm 3 is called. Note that if any bad neighbor x′ makes it past sub-phase ℓ, then Algorithm 3 returns x′ . Further, if any bad neighbor x′ makes it past sub-phase ℓ′ (x′ ), then we may incur too much regret from testing x′ in later sub-phases since Cost(x′ ) ≥ αθℓ′ (x′ ) . We show that Bℓ′ is unlikely, and conclude that bad neighbors are highly likely to be removed from contention early enough to avoid incurring high regret. Lemma 3.8. Pr[Bℓ′ ] ≤ T −4 . Proof. In the case that Algorithm 3 is not called in phase ℓ, then the probability is at most 0 since Bℓ′ cannot happen. Formalizing this, let Tℓ be the event that Algorithm 3 is called in phase ℓ, then we have Pr[Bℓ′ | ¬Tℓ ] = 0. In the other case where Algorithm 3 is called in phase ℓ, then we need to show that it is unlikely for any bad neighbor x′ to make it past sub-phase ℓ′ (x′ ). To this end, fix a bad neighbor x′ . If x′ doesn’t make it to sub-phase ℓ′ (x′ ) ≤ ℓ, then it clearly doesn’t make it past sub-phase ℓ. Thus in order for event Bℓ′ to happen due to x′ , we must have that x′ makes it to 10
sub-phase ℓ′ (x′ ) and makes it past this sub-phase. Now, x′ only makes it past sub-phase ℓ′ (x′ ) when d ′ ) ≤ (2α2 /(1 + α))θℓ′ (x′ ) , where Cost(x d ′ ) is the average of Nℓ′ (x′ ) independent samples with Cost(x ′ distribution Cost(x , Z), where Z ∼ D. By part(b) of Lemma 3.2, the probability of this is at most M −1 T −4 . It follows that 2 [ 2α d ′) ≤ Pr[Bℓ′ | Tℓ ] ≤ Pr Cost(x θ′ ′ 1 + α ℓ (x ) ′ x ∈NB (x) X 2α2 ′ d Pr Cost(x ) ≤ θℓ′ (x′ ) ≤ T −4 ≤ 1 + α ′ x ∈NB (x)
Finally, observe that Pr[Bℓ′ ] = Pr[Bℓ′ | Tℓ ] Pr[Tℓ ] + Pr[Bℓ′ | ¬Tℓ ] Pr[¬Tℓ ] ≤ T −4 (Pr[Tℓ ] + Pr[¬Tℓ ]) = T −4 which completes the proof. Lemma 3.8 establishes that Algorithm 3 filters out bad neighboring solutions with high probability. In order to prove Lemma 3.4, we also need to show that good neighboring solutions are unlikely to be filtered out. More specifically, there are three situations to consider (all under the condition that Cost(xℓ ) ≤ θℓ ): (1) every solution in N (xℓ ) is a bad neighbor, (2) some solution x′ ∈ N (xℓ ) satisfies Cost(x′ ) ≤ α2 θℓ , and (3) not all neighboring solutions are bad, but all solutions that are not bad have Cost(x′ ) ∈ [α2 θℓ , αθℓ ]. In situation (1), it is a simple corollary of Lemma 3.8 that Algorithm 3 will output xℓ with high probability, indicating that we did not find an improved solution (and therefore Cost(xℓ ) ≤ γOPT). In situation (2), where there is a neighboring solution x′ with Cost(x′ ) ≤ α2 θℓ , it is possible that Algorithm 3 considers and returns a different neighboring solution x′′ with Cost(x′′ ) ∈ [α2 θℓ , αθℓ ] (again it is unlikely to return a bad neighbor due to Lemma 3.8). However, if x′ is ever considered it will survive past sub-phase ℓ with high probability (Lemmas 3.2 and 3.8) and thus be returned by Algorithm 3. Either outcome is acceptable and guarantees at least an α-factor improvement. In situation (3), Algorithm 3 may output xℓ , indicating no improved solution. This follows since, under the event that Cost(xℓ ) ≤ θℓ , each neighboring solution has Cost(x′ ) ≥ αθℓ ≥ β Cost(xℓ ), which by the (β, γ)-improving moves condition implies that Cost(xℓ ) ≤ γOPT. It is also acceptable for Algorithm 3 to output a solution with cost in the interval [α2 θℓ , αθℓ ], since that guarantees an α-factor improvement. The following lemma formalizes this. Lemma 3.9. Suppose that Algorithm 3 is run in phase ℓ with solution xℓ and let xNew be the random solution which it outputs. Define the events Fℓ,1 , Fℓ,2 , Fℓ,3 as follows: • Fℓ,1 = {NB (xℓ ) = N (xℓ )} (all neighbors of xℓ are bad) • Fℓ,2 = {∃x′ ∈ N (xℓ ), Cost(x′ ) ≤ α2 θℓ } (there is a neighbor with a β = α2 -factor decrease) • Fℓ,3 = {∀x′ ∈ N (xℓ ) \ NB (xℓ ) ̸= ∅, Cost(x′ ) ∈ [α2 θℓ , αθℓ ]} (no neighbor has an β = α2 -factor decrease, but there is one with an α-factor decrease). Then (a) Pr[xNew ̸= xℓ | ∧Fℓ,1 ] ≤ T −4 (b) Pr[Cost(xNew ) > αθℓ | Fℓ,2 ] ≤ (ℓ + 1)T −4 11
(c) Pr[(Cost(xNew ) > αθℓ ) ∧ (xNew ̸= xℓ ) | Fℓ,3 ] ≤ T −4 Proof. Part (a): Conditioned on Fℓ,1 , the only way that xNew ̸= xℓ is if a bad neighboring solution makes it past sub-phase ℓ. This implies that event Bℓ′ occurs, and it follows by Lemma 3.8 that Pr[xNew ̸= xℓ | Fℓ,1 ] ≤ Pr[Bℓ′ ] ≤ T −4 . Part (b): There are two ways we can have Cost(xNew ) > αθℓ under condition Fℓ,2 . One way is that a bad neighbor has been output as xNew , and thus Bℓ′ has occurred as discussed previously. The other way is if xNew = xℓ and Cost(xℓ ) > αθℓ , in which case it must be that the solution x′ with Cost(xℓ ) ≤ α2 θℓ was considered but did not make it past sub-phase ℓ. Let Bℓ′ (x′ ) denote this latter event. Thus by a union bound we have Pr[Cost(xNew ) > αθℓ | Fℓ,2 ] ≤ Pr[Bℓ′ ] + Pr[Bℓ′ (x′ )]. Again, from Lemma 3.8, Pr[Bℓ′ ] ≤ T −4 . It remains to bound Pr[Bℓ′ (x′ )]. This event happens if x′ fails at least one of the checks that occur when x′ is considered in the inner ‘for’ loop of Algorithm 3. By part (a) of Lemma 3.2 and a union bound, we have Pr[Bℓ′ (x′ )] ≤ ℓM −1 T −4 ≤ ℓT −4 . Combining these bounds completes part (b). Part (c): We can only have Cost(xℓ ) > αθℓ and xNew ̸= xℓ if some bad neighbor makes it past sub-phase ℓ, which can only occur if Bℓ′ has occurred. Thus we have Pr[(Cost(xNew ) > αθℓ ) ∧ (xNew ̸= xℓ ) | Fℓ,3 ] ≤ Pr[Bℓ′ ] ≤ T −4 by Lemma 3.8. This yields the claim for the last case and completes the proof of the lemma. As a direct corollary of Lemma 3.9, we get that Algorithm 3 is unlikely to output a solution with cost more than αθℓ when run in phase ℓ. Corollary 3.10. Suppose that Algorithm 3 is run in phase ℓ with solution xℓ and let xNew be the random solution which it outputs. Then we have that Pr[Cost(xNew ) > αθℓ ] ≤ (ℓ + 1)T −4 . Proof. Under event Fℓ,1 , the only way for Algorithm 3 to output a bad solution is to output something other than xℓ . Similarly, the only for Algorithm 3 to output a bad solution under event Fℓ,3 is to output something other than xℓ which happens to be bad. Then it follows from the law of total probability and Lemma 3.9 that Pr[Cost(xNew ) > αθℓ ] = Pr[xNew ̸= xℓ | Fℓ,1 ] Pr[Fℓ,1 ] + Pr[Cost(xNew ) > αθℓ | Fℓ,2 ] Pr[Fℓ,2 ] + Pr[(Cost(xNew ) > αθℓ ) ∧ (xNew ̸= xℓ ) | Fℓ,3 ] Pr[Fℓ,3 ] ≤(ℓ + 1)T −4 (Pr[Fℓ,1 ] + Pr[Fℓ,2 ] + Pr[Fℓ,3 ]) =(ℓ + 1)T −4 .
12
3.1.3
Proof of Lemma 3.4
Now we return to the proof of Lemma 3.4 which will utilize the tools we developed from the analysis of Algorithm 3. Proof of Lemma 3.4. Recall that Gℓ = ¬Cℓ ∨ ¬Mℓ , i.e., the good event for phase ℓ happens if either Algorithm 2 doesn’t make it to phase ℓ or we have Cost(xℓ ) ≤ θℓ . First, we claim that Pr[Bℓ+1 | Gℓ ] ≤ Pr[Bℓ+1 | ¬Cℓ ]. To see this, we have: Pr[Bℓ+1 ∧ (¬Cℓ ∨ ¬Mℓ )] Pr[¬Cℓ ∨ ¬Mℓ ] Pr[(Bℓ+1 ∧ ¬Cℓ ) ∨ (Bℓ+1 ∧ ¬Mℓ )] = Pr[¬Cℓ ∨ ¬Mℓ ] Pr[Bℓ+1 ∧ ¬Cℓ ] Pr[Bℓ+1 ∧ ¬Mℓ ] ≤ + Pr[¬Cℓ ∨ ¬Mℓ ] Pr[¬Cℓ ∨ ¬Mℓ ] Pr[Bℓ+1 ∧ ¬Cℓ ] Pr[Bℓ+1 ∧ ¬Mℓ ] ≤ + Pr[¬Cℓ ] Pr[¬Mℓ ] = Pr[Bℓ+1 | ¬Cℓ ] + Pr[Bℓ+1 | ¬Mℓ ]
Pr[Bℓ+1 | Gℓ ] =
= Pr[Bℓ+1 | ¬Cℓ ] The first line follows from the definition of Gℓ and conditional probability while the second line follows from the distributive law for ∧ and ∨. We use a union bound in the third line and the observation that Gℓ contains both ¬Cℓ and ¬Mℓ in the fourth line. To finish, the fifth line is again the definition of conditional probability and the last step uses the observation that Pr[Bℓ+1 | ¬Mℓ ] = 0 since it is impossible for the algorithm to make it to phase ℓ + 1 if it has not made it to phase ℓ. Thus we may focus on bounding Pr[Bℓ+1 | ¬Cℓ ]. Under condition ¬Cℓ , Cost(xℓ ) ≤ θℓ by definition. We analyze three cases depending on how Cost(xℓ ) relates to θℓ . Case 1: Cost(xℓ ) ≤ α2 θℓ . In this case, we have Cost(xℓ ) ≤ αθℓ+1 and the current cost is small enough to move to phase ℓ + 1. Denote the event that Cost(xℓ ) ≤ α2 θℓ by Eℓ,1 . We will show that Pr[Bℓ+1 | ¬Cℓ ∧ Eℓ,1 ] is small. If Algorithm 2 moves to phase ℓ + 1 with xℓ+1 = xℓ , then Cost(xℓ+1 ) < θℓ+1 so Bℓ+1 doesn’t happen. Thus the only way for Bℓ+1 to happen is if the “if” d ℓ ) > 2α2 θℓ /(1 + α). We will statement on line 10 evaluates to true, which occurs when Cost(x d ℓ ) is the average of Nℓ independent show that this happens with small probability. Since Cost(x samples each with mean Cost(xℓ ), by the first part of Lemma 3.2 and the discussion above, we have 2α2 d Pr[Bℓ+1 | ¬Cℓ ∧ Eℓ,1 ] ≤ Pr Cost(xℓ ) > θℓ ≤ M −1 T −4 ≤ T −4 , (2) 1+α completing the argument for this case. Case 2: αθℓ ≤ Cost(xℓ ) ≤ θℓ . For this case, we want Algorithm 3 to be called with high probability and that it succeeds with high probability. Denote the event that αθℓ ≤ Cost(xℓ ) ≤ θℓ by Eℓ,2 . In this case, there are two ways that we could fail to satisfy Cost(xℓ+1 ) ≤ θℓ+1 . The first is by skipping the step which explores the neighborhood and moving to the next phase with xℓ+1 = xℓ . This occurs when the “if” statement in line 10 of Algorithm 2 evaluates to False, which happens with probability at most M −1 T −4 by part (b) of Lemma 3.2. Assuming Algorithm 3 is called, the second way that we could fail to satisfy Cost(xℓ+1 ) ≤ θℓ+1 is if Algorithm 3 returns a bad neighboring solution. Lemma 3.10 shows that this occurs with 13
probability at most (ℓ + 1)T −4 ≤ T −3 . Combining the bounds completes the analysis of this case. Case 3: α2 θℓ < Cost(xℓ ) < αθℓ . This last case is more flexible; we use Eℓ,3 to denote the event that Cost(xℓ ) ∈ (α2 θℓ , αθℓ ). Since Cost(xℓ ) ≤ αθℓ , we will be safe in either the situation that d ℓ ) > 2α2 θℓ /(1 + α) (and so we set xℓ+1 = xℓ ) or not (and so we use Algorithm 3 to Cost(x determine xℓ+1 ). In the first situation, we clearly have Cost(xℓ ) ≤ αθℓ = θℓ+1 . In the other situation, we use the same argument as in the previous case to argue that the probability of setting xℓ+1 to a bad neighbor is small. Thus we conclude that Pr[Bℓ+1 | ¬Cℓ ∧ Eℓ,3 ] ≤ T −4 Since the three cases above are exhaustive, i.e., Eℓ,1 ∨ Eℓ,2 ∨ Eℓ,1 ≡ True when conditioned on Cℓ , we conclude by the law of total probability that Pr[Bℓ+1 | Cℓ ] =
3 X
Pr[Bℓ+1 | Cℓ ∧ Eℓ,i ] Pr[Eℓ,i | Cℓ ] ≤ T −3
i=1
3 X
Pr[Eℓ,i | Cℓ ] = T −3 ,
i=1
completing the proof of this lemma. 3.1.4
Bounding the Number of Phases
Let L be the index of the last complete phase, i.e., Algorithm 2 either finds a local solution xLast in phase L (which is then played until period T ) or period T is reached in phase L + 1. We will show that L is logarithmic in T , which will be helpful to establish our regret bound later. Lemma 3.11. L ≤ log(T )/ log( α1 ) P Proof. By definition of L we know that L ℓ=1 Nℓ ≤ T , since this is just counting the number of plays due to line 7 in Algorithm 2. From the definition of Nℓ , we have: T ≥
L X
Nℓ
ℓ=1 L X 3Cmax
(4 log T + log M ) δ 2 α 2 θℓ L 12 log T X 1 ℓ−1 ≥ δ 2 α2 α ℓ=1 ! 1 L − 1 12 log T α . = 1 δ 2 α2 α −1 =
ℓ=1
Rearranging this inequality to solve for L and simplifying yields result. 3.1.5
Final Regret Analysis
To complete the analysis, we separately analyze the γ-regret incurred by the algorithm during phases 1 to L and the γ-regret after phase L.
14
Regret from Phases 1 to L: Consider phase ℓ. We incur regret from playing the solution xℓ and also from playing neighboring solutions when Algorithm 3 is called. Let Rℓ,1 and Rℓ,2 represent each of these quantities, respectively. We start by bounding Rℓ,1 . Since OPT ≥ 0, by the law of total expectation we have: E[Rℓ,1 ] = E[Rℓ,1 | ¬Bℓ ] Pr[¬Bℓ ] + E[Rℓ,1 | Bℓ ] Pr[Bℓ ] ≤ θℓ Nℓ + Cmax Nℓ ℓT −3 12Cmax ≤ 2 2 (log T + log M ) + Cmax T −1 . δ α The first inequality follows since Cost(xℓ ) ≤ θℓ under ¬Bℓ (giving the first term) and Lemma 3.5 (which bounds Pr[Bℓ ]). The second inequality follows from the definition of Nℓ and the fact that Nℓ and ℓ are both smaller than T . Bounding Rℓ,2 is similar, but we have to account for each sub-phase. We see that: E[Rℓ,2 ] = E[Rℓ,2 | ¬Bℓ′ ] Pr[¬Bℓ′ ] + E[Rℓ,2 | Bℓ′ ] Pr[Bℓ′ ] ≤M
ℓ X
θℓ′ Nℓ′ + Cmax · T · T −4
ℓ′ =1
12M ℓCmax (log T + log M ) + Cmax T −3 . δ 2 α2 The first term in the first inequality follows since in the worst case we play each neighboring solution in all sub-phases, but under event ¬Bℓ′ we never play a solution with cost more than θℓ′ in each sub-phase ℓ′ . The second term follows since, under Bℓ′ , we can’t play a solution of cost more than Cmax for more than T steps and Pr[Bℓ′ ] ≤ T −4 by Lemma 3.8. ≤
Regret Incurred after Phase L: Let R>L denote the regret incurred after phase L. We need to consider both the case where Algorithm 2 terminated with a solution xLast and when it did not. Denote the former event by L. Then we have E[R>L ] = E[R>L | L] Pr[L] + E[R>L | ¬L] Pr[¬L]. We now focus on each conditional expectation and show that the regret is small in each. Consider the first case where we condition on L, and so we have that Algorithm 2 terminated with some solution xLast which is used for all remaining rounds. This happens when Algorithm 3 is run in phase L and returns the solution xL . We want to show that it is unlikely for xL to satisfy Cost(xL ) > γOPT. Suppose Cost(xL ) > γOPT, then by Lemma 2.2, we have that N (xℓ ) contains a solution x′ with Cost(x′ ) ≤ β Cost(xL ) = α2 Cost(xL ). This means that event Fℓ,2 has occurred, and by Lemma 3.9 the probability of Algorithm 3 yielding xL as output is at most (ℓ + 1)T −4 ≤ T −3 . If, instead, Cost(xL ) ≤ γOPT, we incur zero γ-regret. Together, E[R>L | L] ≤ Cmax T · T −3 . Now suppose L does not occur. In this case, period T was reached before finding an approximate local optimum, midway through executing an incomplete phase L + 1. We can use similar techniques to bound R>L for this incomplete phase as we for Rℓ above, in fact, we can simply consider R>L to be RL+1 . It follows from the same arguments as before that E[R>L | ¬L] = E[RL+1 ] ≤
12(M + 1)(L + 1)Cmax (log T + log M ) + 2Cmax T −1 . δ 2 α2
Putting everything together, E[R>L ] ≤
12(M + 1)(L + 1)Cmax (log T + log M ) + 3Cmax T −1 . δ 2 α2 15
Combining the Bounds: Summing all the terms together, we have: Regretγ (A, D, T ) ≤
L X
(E[Rℓ,1 ] + E[Rℓ,2 ]) + E[R>L ]
ℓ=1
X L M Cmax L M Cmax (log T + log M ) (log T + log M ) ℓ + O δ 2 α2 δ 2 α2 ℓ=1 M Cmax L2 ≤O (log T + log M ) δ 2 α2 ! M Cmax log2 T (log T + log M ) , ≤O δ 2 α2 log2 α1
≤O
where in the last step we used the bound on L from Lemma 3.11. This establishes Lemma 3.1.
4
Applications of Our Framework
4.1
Stochastic Completion Time Scheduling on a Single Machine
We consider the problem of scheduling stochastic jobs to minimize total completion time on a single machine. Let D be a distribution over job sizes which is unknown to the scheduler. There are n jobs with stochastic sizes P = (P1 , P2 , . . . , Pn ) ∼ D. Let µj := E[Pj ] denote the expected size of job j. We only require independence across time periods; a pair of jobs j and j ′ may have correlated size distributions. We also make a standard assumption that the job size distribution is bounded and normalized to be in [0, 1]. A schedule is given by a permutation π : [n] → [n] specifying that job j is scheduled in position π(j). LetP Πn be the permutations on [n], the feasible schedules. Given a schedule π, let Cj (π, P ) := Pj + j ′ :π(j ′ )<π(j) Pj ′ be the completion time of job j under schedule π and sizes P . After reordering the summation, the cost of a schedule π is Cost(π, P ) =
n X
Cj (π, P ) =
j=1
n X
(n − π(j) + 1)Pj .
(3)
j=1
Let OPT := minπ EP ∼D [Cost(π, P )]. We focus on learning from limited feedback using fixed, non-preemptive schedules. In the single machine case full-information case, it is well known that the optimal schedule is given by applying Smith’s rule to the expected job sizes: π ∗ orders the jobs in non-decreasing order of µj , or shortest expected processing time first [44, 46]. When learning to schedule with bandit feedback, the scheduler gains information by interacting with unknown D through the following process which occurs in each of T discrete time periods. In period t ∈ [T ], the scheduler commits to a schedule π t before job sizes are realized according to an independent sample P t ∼ D. Then the scheduler observes Cost(π t , P t ), the realized total completion time of schedule π t , but does not observe the realized job sizes P t . For a schedule π, define error(π) := E[Cost(π, P )] − OPT to measure the expected regret we incur by using π for one step. Recall that in this case an optimal schedule π ∗ must schedule j after j ′ if and only if µj > µj ′ . We say that π inverts a pair of jobs j, j ′ with µj > µj ′ if instead it has π(j) < π(j ′ ). The following proposition shows that we can write error(π) in terms of inversions in π from an optimal schedule.
16
Proposition 4.1 (Lindermayr and Megow [38]). For any schedule π, X error(π) = µj − µj ′ 1{π(j) < π(j ′ )}. j,j ′ :µj >µj ′
Let N (π) = {π ′ ∈ Πn | ∃i = ̸ j, π(i) = π ′ (j), π(j) = π ′ (i), and π(k) = π ′ (k) for all k ̸∈ [n]\{i, j}} be the the neighborhood of schedules that consists of swapping a single pair of jobs. We show this admits (β, γ)-improving moves, with γ = 1 + ϵ for any ϵ > 0 and β = 1 − ϵ/n2 . Lemma 4.2. Let π be any schedule with Cost(π) > (1 + ϵ)OPT with ϵ ∈ (0, 1), then there exists a schedule π ′ obtainable from π by swapping a single pair of jobs such that ϵ Cost(π ′ ) ≤ 1 − 2 Cost(π). n Proof. First we lower bound Cost(π) − OPT by ϵ · Cost(π)/2 since Cost(π) − OPT ≥ Cost(π) −
Cost(π) ϵ · Cost(π) ϵ · Cost(π) = ≥ . 1+ϵ 1+ϵ 2
Next, we upper bound Cost(π) − OPT = error(π) as error(π) =
X j,j ′ :µj >µj ′
n (µj − µj ′ )1{π(j) < π(j )} ≤ · ′max (µj − µj ′ )1{π(j) < π(j ′ )} j,j :µj >µj ′ 2 ′
where we use the fact that there are at most n2 terms in the sum. Combining these bounds, we conclude that there exists a pair j, j ′ with µj > µ′j and π(j) < π(j ′ ) such that µj − µj ′ ≥
ϵ · Cost(π) ϵ · Cost(π) ≥ . n n2 2 2
For the new schedule π ′ created by swapping the positions of j and j ′ in π, we observe that Cost(π) − Cost(π ′ ) = (π(j ′ ) − π(j))(µj − µj ′ ) ≥ (µj − µj ′ ) ≥
ϵ · Cost(π) , n2
which uses the fact that π(j ′ ) − π(j) ≥ 1 by construction. The lemma follows after rearranging. Corollary 4.3. Consider the problem of scheduling to minimize total completion time with stochastic job sizes drawn from distribution D. For any ϵ > 0 there is an algorithm A (Algorithm 2) with 12 n log3 T . Regret1+ϵ (A, D, T ) = O ϵ4 Proof. We apply Lemma 3.1 and simplify with problem-specific parameters. For the swap neighborhood, the maximum neighborhood size is M ≤ n2 . Job sizes are at most 1, so Cmax ≤ n2 . We can bound 1 1 ϵ log(1/α) = − log(1 − ϵ/n2 ) ≥ 2 2 n2 since log(1 − x) ≤ −x for x > −1. We can also bound (1 − ϵ/n2 )(ϵ/n2 )2 p ≥ 16(1 − ϵ/n2 )(ϵ/n2 )2 ≥ 8ϵ2 /n4 (1 + 1 − ϵ/n2 )4 p since 1 − ϵ/n2 < 1, implying (1 + 1 − ϵ/n2 )4 ≤ 16. The result follows after substitution and observing log n ≤ log T . δ2β =
17
4.2
Minimum Cost Base of a Matroid
We now apply our framework to the online stochastic bandit setting for finding a minimum cost base in a matroid. Let M = (S, I) be a matroid on ground set S of cardinality |S| = n with family of independent sets I. Let B be its family of bases, or maximal independent sets, so that each that B ∈ B satisfies B ∈ I and there is no s ∈ S \ B such B ∪ s ∈ I. The rank of set S, denoted r(S), is the cardinality of the largest independent subset of S. The rank of matroid M is the cardinality of a base, so r(M ) = |B|. In the minimum cost base problem, each element s ∈ S is associated a cost and the objective is to find a base of minimum total cost. In the online stochastic bandit setting, the learner acts over a sequence of T time periods, selecting base B t in period t = 1, . . . , T . In each period t, stochastic costs Z t = {Zst }s∈S ∼ D realize for each element s ∈ S, where D is a joint distribution over edge costs. In time step t, given underlying realizations z t , the learner observes only the cost of base B t , P which is Cost(B t , z t ) = s∈B t zst . Let µe = EZ∼D [Ze ] denote the expected cost of edge e, and let B ∗ = arg minB ′ ∈B EZ∼D [Cost(B ′ , Z)] be the base with lowest expected cost. We now define the local search neighborhood which will allow us achieve low regret online. A circuit C is a minimally dependent set: C ̸∈ I but every subset of C is independent. Definition 4.4. Given a base B of matroid M and s ∈ S \ B, there is a unique circuit C(s, B) such that x ∈ C(s, B) ⊆ B ∪ s. Furthermore, for each t ∈ C(s, B), (B ∪ s) \ t is also a base. Definition 4.5. Given matroid M with bases B, let N : B → 2B be the circuit swap neighborhood map. More formally, for each B ∈ B, let N (B) = {B ′ ∈ B | B ′ = (B ∪ s) \ t for some s ∈ S \ B, t ∈ C(s, B)}, so N (B) is the set of bases reachable from B by adding an element s ̸∈ B to B, followed by removing an element t from the resulting circuit C(s, B). We will make use of the following well-known property of matroids. Lemma 4.6 (Frank [25]). If B1 , B2 ∈ B, then there exists a bijection f : (B1 \ B2 ) → (B2 \ B1 ) such that B1 \ {x} ∪ f (x) ∈ B for every x ∈ B1 \ B2 . We can now show that the circuit swap neighborhood admits (β, γ)-improving moves. Lemma 4.7. Given matroid M , the circuit swap neighborhood admits (β, γ)-improving moves with γ = 1 + ϵ for any ϵ > 0 and β = 1 − ϵ/(2r(M )). Proof. Consider B ∈ B satisfying Cost(B) > (1 + ϵ) Cost(B ∗ ) for ϵ ∈ (0, 1). It follows that , ∆ = Cost(B) − Cost(B ∗ ) ≥ Cost(B) −
Cost(B) ϵ · Cost(B) ϵ · Cost(B) = ≥ . 1+ϵ 1+ϵ 2
We want to show there exists B ′ ∈ N (B) satisfying Cost(B ′ ) ≤ β Cost(B). It is easy to see that X X ∆ = Cost(B) − Cost(B ∗ ) = µe − µe . e∈B\B ∗
e∈B ∗ \B
From Lemma 4.6, construct a bijection f : (B \ B ∗ ) → (B ∗ \ B) such that B \ {s} ∪ f (s) is a base for every s ∈ B \ B ∗ . If we start from B, then delete s and add f (s) from B for all s ∈ B \ B ∗ , we transform from base B to B ∗ . Since there are at most |B| = r(M ) items in B \ B ∗ , there 18
must exist s′ ∈ B \ B ∗ , for which B \ s′ ∪ f (s′ ) improves the cost by at least ∆/ρ(M ). Let T ′ = B \ s′ ∪ f (s′ ) ∈ N (B). Then Cost(B) − Cost(B ′ ) ≥
∆ ϵ · Cost(B) ≥ . ρ(M ) 2r(M )
Corollary 4.8. Consider the problem of finding a minimum cost base in a matroid M = (S, I) with |S| = n and rank r(M ) = r when element costs are stochastically drawn from D. For any ϵ > 0, there is an algorithm A (Algorithm 2) with 6 6 nr log2 T nr log3 T . Regret1+ϵ (A, D, T ) = O (log T + log n) = O ϵ4 ϵ4 Proof. We apply Lemma 4.7 and Lemma 3.1 with (β, γ) = (1 − ϵ/2r, 1 + ϵ) for ϵ > 0. Thus we just need to bound M , Cmax , α12 , δ12 , and log α1 . It is easy to see that M ≤ nr and that Cmax ≤ r. Next, we can see that α12 = O(1) for ϵ ≤ r since α2 = 1 − ϵ/2r ≥ 1/2. For δ12 , we have: δ=
1 − α2 ϵ/2r ϵ 1−α = = ≥ . 2 2 1+α (1 + α) 1 + 2α + α 8r
Finally, for log(1/α) we have: 1 log = log α
1 1 − ϵ/2r
1/2
1 1 ϵ = − log (1 − ϵ/2r) ≥ − log exp (−ϵ/2r) = . 2 2 4r
Combining in Lemma 3.1 yields the bound.
4.3
Uncertain k-Median Clustering
Our final application concerns k-median clustering where the set of points to be clustered are drawn at random from an unknown distribution. The following setup was studied by Cormode and McGregor [17] and Guha and Munagala [28] for a several of k-clustering objectives in the offline setting. An instance consists of n points arriving from a metric space (M, d) of diameter 1. The location of the i’th point is uncertain and the objective is to choose k cluster centers which minimize the total expected distance between each arriving point and its closest cluster center. We let Zi ∈ M denote the random realization of the i’th point. For a fixed location z ∈ M and a fixed set C of cluster centers, let d(z, C) = minc∈C d(z, c) denote the distance of z to its nearest cluster center in C. Then the cost of a solution C on points Z = (Z1 , Z2 , . . . , Zn ) is X Cost(C, Z) = 1{Zi = z} · d(z, C). i∈[n],z∈Z
Thus, the expected cost of solution C is given by X E[Cost(C, Z)] =
Pr[Zi = z] · d(z, C),
i∈[n],z∈Z
and OPT denotes the expected cost of a set of cluster centers which minimizes this expected cost. In the bandit setting, we do not observe the realizations of the point locations. In each round t a set of cluster center locations Ct is submitted, after which the learner only observes Cost(Ct , Z). 19
Let N (C) = {C ′ ∈ X | C ∪ {b} \ {a}, a ∈ C, b ∈ X \ C} be the swap-neighborhood of cluster centers C. Arya et. al. [3] propose a local search algorithm for the k-medians problem which starts from an arbitrary set of k cluster centers C and repeatedly moves to neighboring C ′ ∈ N (C) satisfying Cost(C ′ ) ≤ (1 − ϵ) Cost(C) until no local improvement is found. Cormode and McGregor [17] shows that this is equally effective for the uncertain k-medians problem. Lemma 4.9 (Arya et al. [3] and Cormode and McGregor [17]). For the uncertain k-median clustering problem, local search with ϵ-improvements terminates in C ∈ X satisfying Cost(C) ≤ (5/(1 − nϵ)) Cost(C ∗ ). We can leverage this to show that uncertain k-median clustering permits (β, γ)-improving moves. Lemma 4.10. The Minimum Cost K-Median problem with n input points admits (β, γ)-improving moves where γ = 5/(1 − n1 ) and β = (1 − 1/n2 ). Proof. We prove this lemma by contradiction. Suppose that the local search algorithm does not admit (β, γ)-improving moves where γ = 5/(1 − n1 ) and β = (1 − 1/n2 ). This implies that there exists C ∈ X with Cost(C) > γ Cost(C ∗ ) and that Cost(C ′ ) > β Cost(C) for all C ′ ∈ N (C). It follows that the local search algorithm of [17] may terminate with C as a local optimum. However, setting ϵ = 1/n2 in Lemma 4.9 gives a 5/(1 − 1/n)-factor approximation algorithm. This implies that Cost(C) ≤ 1−5 1 Cost(C ∗ ), a contradiction. n
Corollary 4.11. Consider the uncertain k-median clustering with candidate set of m potential cluster centers where the locations of n points in a metric space of diameter 1 are drawn from distribution D. There exists algorithm A (Algorithm 2) achieving Regret5n/(n−1) (A, D, T ) = O n9 m2 log3 T , when m2 ≤ T . Proof. We apply Lemma 3.1 and simplify with problem-specific parameters. For the swap neighborhood, the maximum neighborhood size is M ≤ |X |2 = m2 . The metric space has diameter 1, so Cmax ≤ n. As in the proof of Lemma 4.3, We can bound log(1/α) ≥ 1/2n2 and δ 2 β ≥ 8/n4 . The result follows after substitution and observing log n ≤ log T .
5
Discussion
We conclude by discussing a couple of relevant issues not raised elsewhere. For ease of exposition we assumed the algorithm knows T , and that there is an upper bound Cmax on costs. It is straightforward but tedious to modify the algorithms and analysis to not require explicit knowledge of T . Similarly, we can replace the assumption of bounded costs with suitable distributional assumptions about the cost. For example, we could require a sub-gaussian like condition on the tails of the distribution or even just finite variance. In the latter case, we could make use of tools for handling heavy-tailed distributions in the bandit setting [11]. It remains to computationally demonstrate the benefits of our algorithm. All three applications are instances of linear bandits[10, 19, 37], so a natural starting point may be to compare the regret of our algorithm with that of a linear bandit style algorithm which, in each step, uses the bandit feedback to estimate problem parameters (eg. mean job sizes for completion time scheduling), then computes the solution to an offline instance of the problem with those parameters to submit in 20
the next time step. For the scheduling and matroid applications the offline instances can be solved efficiently, for clustering we have to resort to an approximate solution due to NP-hardness. An exciting direction for future work is exploring further applications for our framework where local search is effective offline. Some applications may require generalizing our current approach, for example, the local search guarantees for set cover [29] rely on finding neighboring solution which improves a specialized potential function, and not the objective function directly. It is an open question whether a version of (β, γ)-improving moves defined on such potential functions can provide guarantees in the bandit online setting.
References [1] Arpit Agarwal, Rohan Ghuge, and Viswanath Nagarajan. Semi-bandit learning for monotone stochastic optimization. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 1260–1274. IEEE, 2024. doi: 10.1109/FOCS61266.2024.00083. URL https://doi.org/10.1109/FOCS61266.2024.00083. [2] Sara Ahmadian, Zachary Friggstad, and Chaitanya Swamy. Local-search based approximation algorithms for mobile facility location problems. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1607–1621. SIAM, 2013. doi: 10.1137/1. 9781611973105.115. URL https://doi.org/10.1137/1.9781611973105.115. [3] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristic for k-median and facility location problems. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 21–29, 2001. [4] Jean-Yves Audibert, Sébastien Bubeck, and Gábor Lugosi. Regret in online combinatorial optimization. Math. Oper. Res., 39(1):31–45, 2014. doi: 10.1287/MOOR.2013.0598. URL https://doi.org/10.1287/moor.2013.0598. [5] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 47(2-3):235–256, 2002. doi: 10.1023/A:1013689704352. URL https://doi.org/10.1023/A:1013689704352. [6] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32(1):48–77, 2002. doi: 10.1137/S0097539701398375. URL https://doi.org/10.1137/S0097539701398375. [7] Gerdus Benadè, Rathish Das, and Thomas Lavastida. Brief announcement: Stochastic parallel scheduling with bandit feedback. In Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2025, Portland, OR, USA, 28 July 2025 - 1 August 2025, pages 618–622. ACM, 2025. doi: 10.1145/3694906.3743344. URL https://doi.org/10.1145/ 3694906.3743344. [8] Thierry Benoist, Frédéric Gardi, Antoine Jeanjean, and Bertrand Estellon. Randomized local search for real-life inventory routing. Transportation Science, 45(3):381–398, 2011. [9] Paul Bogdan, Thomas Sauerwald, Alexandre Stauffer, and He Sun. Balls into bins via local search. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 21
2013, pages 16–34. SIAM, 2013. doi: 10.1137/1.9781611973105.2. URL https://doi.org/10. 1137/1.9781611973105.2. [10] Sébastien Bubeck, Nicolò Cesa-Bianchi, and Sham M. Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings, pages 41.1–41.14. JMLR.org, 2012. URL http://proceedings.mlr.press/v23/bubeck12a/bubeck12a.pdf. [11] Sébastien Bubeck, Nicolò Cesa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IEEE Trans. Inf. Theory, 59(11):7711–7717, 2013. doi: 10.1109/TIT.2013.2277869. URL https: //doi.org/10.1109/TIT.2013.2277869. [12] Sara Ceschia and Andrea Schaerf. Local search for a multi-drop multi-container loading problem. Journal of Heuristics, 19(2):275–294, 2013. [13] Ke Chen. A constant factor approximation algorithm for k -median clustering with outliers. In Shang-Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 826–835. SIAM, 2008. URL http://dl.acm.org/citation.cfm?id=1347082.1347173. [14] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, volume 28 of JMLR Workshop and Conference Proceedings, pages 151–159. JMLR.org, 2013. URL http://proceedings.mlr.press/v28/ chen13a.html. [15] Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, and David Saulpic. An improved local search algorithm for k-median. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1556–1612. SIAM, 2022. doi: 10.1137/1.9781611977073.65. URL https://doi.org/10.1137/1.9781611977073.65. [16] Richard Combes, Mohammad Sadegh Talebi, Alexandre Proutière, and Marc Lelarge. Combinatorial bandits revisited. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 2116–2124, 2015. URL https://proceedings.neurips.cc/ paper/2015/hash/0ce2ffd21fc958d9ef0ee9ba5336e357-Abstract.html. [17] Graham Cormode and Andrew McGregor. Approximation algorithms for clustering uncertain data. In Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 191–200, 2008. [18] Thibaut Cuvelier, Richard Combes, and Eric Gourdin. Statistically efficient, polynomialtime algorithms for combinatorial semi-bandits. Proc. ACM Meas. Anal. Comput. Syst., 5(1): 09:1–09:31, 2021. doi: 10.1145/3447387. URL https://doi.org/10.1145/3447387. [19] Varsha Dani, Sham M Kakade, and Thomas Hayes. The price of bandit information for online optimization. In Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007. URL https://proceedings.neurips.cc/paper_files/paper/2007/ file/bf62768ca46b6c3b5bea9515d1a1fc45-Paper.pdf. 22
[20] Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. [21] Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis, and Jennifer Wortman Vaughan. Oracle-efficient online learning and auction design. J. ACM, 67(5): 26:1–26:57, 2020. doi: 10.1145/3402203. URL https://doi.org/10.1145/3402203. [22] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. PAC bounds for multi-armed bandit and markov decision processes. In Jyrki Kivinen and Robert H. Sloan, editors, Computational Learning Theory, 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, 2002, Proceedings, volume 2375 of Lecture Notes in Computer Science, pages 255–270. Springer, 2002. doi: 10.1007/3-540-45435-7\_18. URL https://doi. org/10.1007/3-540-45435-7_18. [23] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. J. Mach. Learn. Res., 7: 1079–1105, 2006. URL https://jmlr.org/papers/v7/evendar06a.html. [24] Fares Fourati, Christopher John Quinn, Mohamed-Slim Alouini, and Vaneet Aggarwal. Combinatorial stochastic-greedy bandit. In Michael J. Wooldridge, Jennifer G. Dy, and Sriraam Natarajan, editors, Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence, IAAI 2024, Fourteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2014, February 20-27, 2024, Vancouver, Canada, pages 12052–12060. AAAI Press, 2024. doi: 10.1609/AAAI.V38I11.29093. URL https://doi.org/10.1609/aaai.v38i11.29093. [25] András Frank. Connections in combinatorial optimization, volume 38. Oxford University Press Oxford, 2011. [26] Shayan Oveis Gharan and Luca Trevisan. Partitioning into expanders. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1256–1266. SIAM, 2014. doi: 10.1137/1.9781611973402.93. URL https://doi.org/10.1137/1.9781611973402.93. [27] Margalit Glasgow and Alexander Rakhlin. Tight bounds for γ-regret via the decision-estimation coefficient, 2023. [28] Sudipto Guha and Kamesh Munagala. Exceeding expectations and clustering uncertain data. In Jan Paredaens and Jianwen Su, editors, Proceedings of the Twenty-Eigth ACM SIGMODSIGACT-SIGART Symposium on Principles of Database Systems, PODS 2009, June 19 - July 1, 2009, Providence, Rhode Island, USA, pages 269–278. ACM, 2009. doi: 10.1145/1559795.1559836. URL https://doi.org/10.1145/1559795.1559836. [29] Anupam Gupta, Euiwoong Lee, and Jason Li. A local search-based approach for set covering. In Telikepalli Kavitha and Kurt Mehlhorn, editors, 2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023, pages 1–11. SIAM, 2023. doi: 10.1137/1. 9781611977585.CH1. URL https://doi.org/10.1137/1.9781611977585.ch1. [30] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Mach. Learn., 69(2-3):169–192, 2007. doi: 10.1007/S10994-007-5016-8. URL https://doi.org/10.1007/s10994-007-5016-8. 23
[31] Kazuo Iwama, Shuichi Miyazaki, and Naoya Yamauchi. A 1.875: approximation algorithm for the stable marriage problem. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 288–297. SIAM, 2007. URL http://dl.acm.org/citation.cfm?id=1283383.1283414. [32] Sham M. Kakade, Adam Tauman Kalai, and Katrina Ligett. Playing games with approximation algorithms. SIAM J. Comput., 39(3):1088–1106, 2009. doi: 10.1137/070701704. URL https: //doi.org/10.1137/070701704. [33] Adam Tauman Kalai and Santosh S. Vempala. Efficient algorithms for online decision problems. J. Comput. Syst. Sci., 71(3):291–307, 2005. doi: 10.1016/J.JCSS.2004.10.016. URL https: //doi.org/10.1016/j.jcss.2004.10.016. [34] Felipe Lagos and Jordi Pereira. Multi-armed bandit-based hyper-heuristics for combinatorial optimization problems. Eur. J. Oper. Res., 312(1):70–91, 2024. doi: 10.1016/J.EJOR.2023.06.016. URL https://doi.org/10.1016/j.ejor.2023.06.016. [35] T.L Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Adv. Appl. Math., 6(1):4–22, March 1985. ISSN 0196-8858. doi: 10.1016/0196-8858(85)90002-8. URL https://doi.org/10.1016/0196-8858(85)90002-8. [36] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. [37] Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bandit approach to personalized news article recommendation. In Michael Rappa, Paul Jones, Juliana Freire, and Soumen Chakrabarti, editors, Proceedings of the 19th International Conference on World Wide Web, WWW 2010, Raleigh, North Carolina, USA, April 26-30, 2010, pages 661–670. ACM, 2010. doi: 10.1145/1772690.1772758. URL https://doi.org/10.1145/1772690.1772758. [38] Alexander Lindermayr and Nicole Megow. Permutation predictions for non-clairvoyant scheduling. In Kunal Agrawal and I-Ting Angelina Lee, editors, SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022, pages 357–368. ACM, 2022. doi: 10.1145/3490148.3538579. URL https: //doi.org/10.1145/3490148.3538579. [39] Ole Jakob Mengshoel, Tong Yu, and Ming Zeng. Stochastic local search and machine learning: From theory to applications and vice versa. In Giuseppe De Giacomo, Alejandro Catalá, Bistra Dilkina, Michela Milano, Senén Barro, Alberto Bugarín, and Jérôme Lang, editors, ECAI 2020 - 24th European Conference on Artificial Intelligence, 29 August-8 September 2020, Santiago de Compostela, Spain, August 29 - September 8, 2020 - Including 10th Conference on Prestigious Applications of Artificial Intelligence (PAIS 2020), volume 325 of Frontiers in Artificial Intelligence and Applications, pages 2919–2920. IOS Press, 2020. doi: 10.3233/ FAIA200453. URL https://doi.org/10.3233/FAIA200453. [40] Nysret Musliu, Andrea Schaerf, and Wolfgang Slany. Local search for shift design. European journal of operational research, 153(1):51–64, 2004. [41] Gergely Neu and Gábor Bartók. Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits. J. Mach. Learn. Res., 17:154:1–154:21, 2016. URL https://jmlr.org/papers/v17/15-091.html. 24
[42] Rad Niazadeh, Negin Golrezaei, Joshua R. Wang, Fransisca Susan, and Ashwinkumar Badanidiyuru. Online learning via offline greedy algorithms: Applications in market design and optimization. Manag. Sci., 69(7):3797–3817, 2023. doi: 10.1287/MNSC.2022.4558. URL https://doi.org/10.1287/mnsc.2022.4558. [43] Pierre Perrault, Vianney Perchet, and Michal Valko. Exploiting structure of uncertainty for efficient matroid semi-bandits. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 5123–5132. PMLR, 2019. URL http://proceedings.mlr.press/v97/perrault19a.html. [44] Michael H. Rothkopf. Scheduling with random service times. Management Science, 12(9): 707–713, 1966. ISSN 00251909, 15265501. URL http://www.jstor.org/stable/2627947. [45] Shai Shalev-Shwartz and Sham M. Kakade. Mind the duality gap: Logarithmic regret algorithms for online optimization. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Léon Bottou, editors, Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8-11, 2008, pages 1457–1464. Curran Associates, Inc., 2008. URL https://proceedings.neurips.cc/paper/2008/hash/ bd686fd640be98efaae0091fa301e613-Abstract.html. [46] Wayne E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1-2):59–66, 1956. doi: https://doi.org/10.1002/nav.3800030106. URL https: //onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800030106. [47] Alberto Vera, Siddhartha Banerjee, and Itai Gurvich. Online allocation and pricing: Constant regret via bellman inequalities. Oper. Res., 69(3):821–840, 2021. doi: 10.1287/OPRE.2020.2061. URL https://doi.org/10.1287/opre.2020.2061. [48] Zheng Wen, Branislav Kveton, and Azin Ashkan. Efficient learning in large-scale combinatorial semi-bandits. In Francis R. Bach and David M. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 1113–1122. JMLR.org, 2015. URL http://proceedings.mlr.press/v37/wen15.html. [49] Jianyu Xu and Yu-Xiang Wang. Logarithmic regret in feature-based dynamic pricing. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 13898–13910, 2021. URL https://proceedings.neurips.cc/paper/2021/hash/ 742141ceda6b8f6786609d31c8ef129f-Abstract.html. [50] Shuo Yang, Tongzheng Ren, Sanjay Shakkottai, Eric Price, Inderjit S. Dhillon, and Sujay Sanghavi. Linear bandit algorithms with sublinear time complexity. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 25241–25260. PMLR, 2022. URL https://proceedings.mlr.press/v162/yang22m.html. [51] Tong Yu, Branislav Kveton, and Ole J. Mengshoel. Thompson sampling for optimizing stochastic local search. In Michelangelo Ceci, Jaakko Hollmén, Ljupco Todorovski, Celine Vens, and 25
Saso Dzeroski, editors, Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2017, Skopje, Macedonia, September 18-22, 2017, Proceedings, Part I, volume 10534 of Lecture Notes in Computer Science, pages 493–510. Springer, 2017. doi: 10.1007/978-3-319-71249-9\_30. URL https://doi.org/10.1007/978-3-319-71249-9_30. [52] Jiongzhi Zheng, Kun He, Jianrong Zhou, Yan Jin, Chu-Min Li, and Felip Manyà. Bandmaxsat: A local search maxsat solver with multi-armed bandit. In Luc De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 1901–1907. ijcai.org, 2022. doi: 10.24963/IJCAI.2022/264. URL https://doi.org/10.24963/ijcai.2022/264.
26