--- title: "Contract Scheduling with Distributional and Multiple Advice" authors: - "Spyros Angelopoulos" - "Marcin Bienkowski" - "Christoph Dürr" - "Bertrand Simon" doi: "10.24963/ijcai.2024/404" url: "https://ijcai.org/proceedings/2024/404" pdf: "https://ijcai.org/proceedings/2024/0404.pdf" venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence" year: 2024 pages: "3652-3660" track: "Main Track" keywords: - "Uncertainty in AI: UAI: Sequential decision making" - "Planning and Scheduling: PS: Scheduling" - "Machine Learning: ML: Optimization" - "Planning and Scheduling: PS: Learning in planning and scheduling" --- # Contract Scheduling with Distributional and Multiple Advice Spyros Angelopoulos, Marcin Bienkowski, Christoph Dürr, Bertrand Simon *Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 3652-3660. DOI: [10.24963/ijcai.2024/404](https://doi.org/10.24963/ijcai.2024/404) ## Abstract Contract scheduling is a widely studied framework for designing real-time systems with interruptible capabilities. Previous work has showed that a prediction on the interruption time can help improve the performance of contract-based systems, however it has relied on a single prediction that is provided by a deterministic oracle. In this work, we introduce and study more general and realistic learning-augmented settings in which the prediction is in the form of a probability distribution, or it is given as a set of multiple possible interruption times. For both prediction settings, we design and analyze schedules which perform optimally if the prediction is accurate, while simultaneously guaranteeing the best worst-case performance if the prediction is adversarial. We also provide evidence that the resulting system is robust to prediction errors in the distributional setting. Last, we present an experimental evaluation that confirms the theoretical findings, and illustrates the performance improvements that can be attained in practice. ## Full text ## 1 Introduction A central requirement in the design of real-time and intelligent systems is the provision for anytime capabilities. Many applications, such as motion-planning and medical diagnosis, require systems that are able to output a reasonably efficient solution even if they are interrupted at arbitrary points in time. This motivates the design and evaluation of anytime systems given, as building component, more rudimentary systems that are not interruptible. Questions related to trade-offs between resources (e.g., computational time) and performance are at the heart of AI applications, and the topic of early influential works on flexible computation, resource-bounded algorithms and time-depending planning [Boddy and Dean, 1994; Horvitz, 1988; Zilberstein and Russell, 1996]. We are interested, in particular, in a paradigm introduced by [Russell and Zilberstein, 1991], in which the building component is a contract algorithm, namely an anytime algorithm that is given the exact amount of allowable computation time as part of its input. A contract algorithm will always output the correct result if it is allowed at least its prescribed computation time (hence its name), otherwise it may very well return a meaningless result if it is queried prior to its promised contract time. Thus, contract algorithms are not interruptible; however [Russell and Zilberstein, 1991] proposed a methodology for obtaining interruptible systems via scheduling consecutive executions of the contract algorithm with increasing computation times. As an example, consider a schedule in which the i-th execution of the contract algorithm is allowed time 2i , for all i ∈ N. This yields a system in which, at any time t, the contract algorithm has completed at least one execution of time t/4. The factor 4 quantifies the performance of the schedule, and is the multiplicative loss due to the repeated executions of the contract component. More generally, given a contract algorithm A, a contract schedule is defined as an increasing sequence X = (xi)i≥0, where xi is the length of the i-th execution of A. To evaluate the performance of a schedule X, we rely on a worst-case measure known as the acceleration ratio [Russell and Zilberstein, 1991]. Let ℓ(X, T) denote the largest contract length completed by time T in X, then the acceleration ratio of X is defined formally as It is easy to show that the optimal acceleration ratio is equal to 4, and that it is obtained by the doubling schedule xi = 2i . However, contract scheduling becomes far more challenging in more complex settings that have been studied in the literature. This includes schedules that are run on multiple processors [Bernstein et al., 2002], on multiple instances [Zilberstein et al., 2003], or combinations of these seeings [Bernstein et al., 2003; L´opez-Ortiz et al., 2014]; soft interruptions where the query time is not a hard deadline [Angelopoulos et al., 2008]; performance measures beyond the acceleration ratio [Angelopoulos and L´opez-Ortiz, 2009]; adaptive schedules [Angelopoulos and Panagiotou, 2023]; schedules with end-guarantees on completion time [Angelopoulos and Jin, 2019]; and learning-augmented schedules [Angelopoulos and Kamali, 2023]. Furthermore, contract scheduling is an abstraction of resource allocation under uncertainty, hence it has connections to other optimization problems under uncertainty, such as searching for a hidden target in a known environment under the competitive ratio, as shown in [Bernstein et al., 2003; Angelopoulos, 2015]. ## 1.1 Contract Scheduling with Predictions The standard formulation of contract scheduling assumes that the scheduler has no prior information on the interruption time, hence the acceleration ratio evaluates the system performance at worst-case interruptions. In practice, however, one expects that the scheduler should be able to benefit from a prediction on the interruption, that may be available via a ML oracle. This motivated the recent study [Angelopoulos and Kamali, 2023] of the problem, in a setting in which an imperfect oracle provides the system with a single, deterministic prediction (advice) τ concerning the interruption time T . [Angelopoulos and Kamali, 2023] showed that there exists a schedule with acceleration ratio equal to 4 even if the prediction is adversarial, and which also yields a much improved ratio equal to 2 if the prediction is correct (i.e., error-free). Moreover, they showed that this result is optimal. Using the terminology of learning-augmented online algorithms [Lykouris and Vassilvitskii, 2021; Purohit et al., 2018], we say that there exist schedules of consistency equal to 2, and robustness equal to 4, whereas no 4-robust schedule can be better than 2consistent 1 . We emphasize that the prediction is assumed to be single, i.e., it consists of a unique predicted interruption time, and deterministic, in that the oracle does not incorporate any stochastic aspects. In practice, however, the above model may not adequately capture the information content of the anticipated prediction. For instance, in motion-planning algorithms, the systemmay operate under a certain probabilistic knowledge of the terrain, hence specific actions may have to be triggered according to a (stochastic) belief about the environment [Zilberstein and Russell, 1993]. For a different example, a medical diagnostic system may have to be queried at multiple anticipated times (e.g., depending on the availability of various facilities and specialists). Note that such settings are not captured by the model of [Angelopoulos and Kamali, 2023], in which the schedule is fine-tuned according to a single prediction, and may have consistency as high as 4 if the prediction includes as few as two possible interruption times. ## 1.2 Contribution Motivated by the above applications, and the limitations of single/deterministic prediction oracles, we study contract scheduling under more general models that incorporate distributional and multiple advice. As in [Im et al., 2023], which studied the learning-augmented dynamic acknowledgment problem, we aim to simultaneously optimize the consistency and the robustness of the system. For both settings, we show that the results we obtain are tight. We begin with the distributional setting, in which the advice oracle provides the scheduler with a distribution on the anticipated prediction. Here, the consistency is evaluated, in expectation, relative to the distributional advice (see Section 2 for the formal definition). We show how to construct a collection of n schedules for any given n ∈ N∗ , such that each schedule in the collection is 4-robust, and the best schedule has consistency at most 4n(2 1n - 1). In particular, we show that as n grows, the consistency of the system is arbitrarily close to 4 ln 2 ≈ 2.77, and that the best schedule can be computed in time polynomial in n. We show that this bound is optimal, in that there exists a distributional prediction for which the consistency of any 4-robust schedule is at least 4 ln2. Furthermore, we demonstrate an interesting disconnect between deterministic and distributional predictions. Namely, we prove that, given the distributional prediction that maximizes the consistency, the performance of the optimal schedule deteriorates smoothly as function of the prediction error, measured by the Earth Mover's Distance, or EMD [Rubner et al., 1998]. In contrast, no consistency-optimal 4-robust schedule can exhibit smoothness against deterministic predictions. This disconnect shows that distributional predictions can help mitigate pathological situations, which can be of interest in other learning-augmented optimization problems. 1 [Angelopoulos and Kamali, 2023] also studied a query-based setting in which the prediction is elicited via responses to binary queries, however, this query model is not relevant to our work. In the second part of this work, we study the model in which the advice oracle provides the scheduler a set P of k potential interruption times (e.g., provided by k experts). Here, the consistency is measured as the worst-case performance ratio among interruptions in P, and we refer to Section 2 for the formal definition. We show how to derive a 4-robust schedule of optimal consistency 22- 1k in time O(k log k). We conclude with an experimental evaluation of our schedules, in both the distributional and multiple advice settings, that demonstrates the performance improvements that can be attained in practice. Due to space limitations, we omit or sketch certain proofs. ## 1.3 Other RelatedWork Motivated by the capacity of ML predictions to improve algorithmic performance, the field of learning-augmented algorithms has been growing rapidly in the recent years. We refer to the survey [Mitzenmacher and Vassilvitskii, 2020] and the online repository [Lindermayr and Megow, 2023] that lists several works over the last five years. The vast majority of works have focused on single, deterministic predictions. Multi-prediction oracles were first studied in the context of ski rental [Gollapudi and Panigrahi, 2019], followed by works on multi-shop ski rental [Wang et al., 2020], facility location [Almanza et al., 2021], matching and scheduling [Dinitz et al., 2022], online covering [Anand et al., 2022] and kserver [Antoniadis et al., 2023]. Distributional predictions were first studied in [Diakonikolas et al., 2021] in problems such as ski rental and prophet inequalities. Contract scheduling is related to the online bidding problem [Chrobak and Kenyon-Mathieu, 2006], and a reduction between the two problems for the single prediction setting was shown in [Angelopoulos and Kamali, 2023]. Consistency/robustness tradeoffs for online bidding with a single prediction were shown in [Anand et al., 2021; Angelopoulos et al., 2020]. ## 2 Preliminaries A contract schedule is defined as a sequence of the form X = (xi)i∈N, where xi is the length of the i-th contract, and recall that the acceleration ratio of X is given by (1). In a learningaugmented setting, the acceleration ratio of X is equivalently called the robustness of X, and we say that X is r-robust if it has robustness at most r. From [Russell and Zilberstein, 1991] we thus know that r ≥ 4, and that for X = (2i )i∈N, we have that r(X) = 4. The consistency of X is defined according to the specifics of the prediction oracle, hence we make a distinction between the two learning-augmented settings we study. In the distributional setting, the advice consists of a distribution µ on the anticipated interruption time, and the consistency of a schedule X with advice µ is defined as and recall that the random variable ℓ(X, z) denotes the largest contract completed in X by time z. We will call ℓ(X, z) the profit of X, where z is drawn from distribution µ. In the multiple-advice setting, the prediction consists of a set P = {τ1, . . . , τk} of k possible interruption times (e.g., provided by k experts). Here, we measure the consistency c(X, P) of a schedule X with prediction set P as its worstcase performance relative to the prediction in P, i.e., we define Note that without any assumptions, no schedule can have bounded robustness, if the interruption time is allowed to be arbitrarily small. There are two types of assumptions that can be applied to circumvent this technical issue. The first is to assume that the interruption can only occur after the first contract has completed its execution. The second is to assume that the schedule is bi-infinite, in that it starts with an infinite number of infinitesimally small contracts. For instance, the doubling schedule can be described as (2i )i∈Z, and the completion time of contract i ≥ 0 is defined as ∑ij=-∞ 2j = 2i+1 . We choose the second assumption since it simplifies the calculations, but we note that the two assumptions can be used interchangeably; see, e.g., the discussion in [Demaine et al., 2006]. For a given λ ∈ [0, 1), define the schedule X(λ) ≜ (2i-λ )i∈Z. The following proposition shows that it suffices to focus on the set of schedules ∪λ∈[0,1){X(λ))}. Proposition 1. For any λ ∈ [0, 1), X(λ) is 4-robust. Conversely, every 4-robust schedule must belong in the class ∪λ∈[0,1){X(λ)}. ## 3 Distributional Advice We begin with the setting in which the advice is in the form of a given distribution µ. We first define an appropriate collection Sn of n schedules which will be instrumental towards finding an optimal schedule. Definition 2. For any n, let Sn denote the following collection of n schedules X0 . . . ,Xn-1, defined as Xj = X(j/n) = (2i-j/n )i∈Z. Theorem 3. For any n ∈ N+, there exists a 4-robust schedule in Sn that has consistency at most 4n · (21/n - 1). Figure 1: Illustration of the computation of ℓ(Xj, z) for n = 3 and j = 1. Note that the time scale is logarithmic. Fix an interruption point z ∈ [22 , 23 ). Then z is contained in I k 2 for some value of k ∈ {0, . . . , n - 1}. If k ≥ n - j = 2, then the largest completed contract is c2 (of length 22-1/3 ), and otherwise, the largest completed contract is c1 (of length 21-1/3 ). ![Image](https://ijcai.org/proceedings/2024/fulltext/404/image_000000_53ded2ac8ed8e01f8393534e4920891353acc520df47db5fd71cdcaa4d0fc008.png) Proof. First, observe that any scheduleXj satisfies the conditions of Proposition 1, and hence is 4-robust. Thus, it remains to show that for any distribution µ over (0, +∞), there exists a schedule in Sn with the desirable consistency. We define the intervals I k i for i ∈ Z and k ∈ {0, . . . , n - 1} as I k i = [2i+k/n , 2i+(k+1)/n ). Note that the intervals I k i are disjoint and their union is equal to the support of µ, i.e., ⊎i∈Z ⊎0≤k≤n-1 I k i = (0,+∞). If the interruption time z is drawn from distribution µ, then its expected value is We now estimate the expected value of ℓ(Xj, z) for each schedule Xj with j ∈ {0, . . . , n - 1}. To this end, we consider a fixed value of interruption time z and let I k i be the interval containing z. We note that if k ≥ n - j, then 2i+1-j/n ≤ z < 2i+2-j/n , and thus ℓ(Xj, z) = 2i-j/n . Otherwise, i.e., if k < n - j, we have ℓ(Xj, z) = 2i-1-j/n . See Figure 1 for a pictorial description of this computation. Hence, Next, we compute the sum of the largest contracts over all schedules Xj , as follows: We can now use an averaging argument, and deduce that there exists a schedule Xj ∗ in Sn such that Hence, the consistency of the schedule Xj ∗ is c(Xj ∗, µ) = Ez∼µ[z]/Ez∼µ[ℓ(Xj ∗ , z)] ≤ 4n(21/n - 1). We observe that 4n(21/n - 1) is decreasing and tends to 4 ln2 as n → ∞. Indeed, 4n(21/n - 1) = 4n(eln2·(1/n) - 1) = 4n(ln 2 · (1/n) + O(1/n2 )) = 4 ln 2 + O(1/n). This means that for any ϵ > 0, there exists an integer n = O(1/ϵ) such that 4n(21/n - 1) ≤ 4 ln 2 + ϵ. Assuming that we can evaluate the probability associated with an interval in constant time, for any schedule Xj ∈ Sn, we can compute the quantity Ez∼µ[ℓ(Xj , z)] and select the schedule maximizing this value (i.e., of largest expected completed contract length). We thus obtain the following corollary. Corollary 4. For any arbitrarily small ϵ > 0, there is an algorithm with runtime polynomial in O(1/ϵ) for devising a 4robust schedule that has consistency at most 4 · ln 2 + ϵ. We now show that the upper bound of Theorem 3 is tight. Theorem 5. For any n ∈ N, there exists a distributional prediction for which every collection Cn that consists of n 4-robust schedules cannot contain a schedule of consistency smaller than 4n · (21/n - 1). Proof. Using Proposition 1, let us denote, without loss of generality, the 4-robust schedules in Cn by X(λk) = (2i-λk )∞i=-∞ for k ∈ [0, n - 1] and 0 ≤ λk < λk+1 < 1. We have that Ez∼µ[ℓ(X(λ0), z)] = 2-λ0 as the support of µ is in the interval [21-λ0 , 22-λ0 ]. Therefore, if an interruption occurs at any point in the support of µ, the last completed contract of X(λ0) is of length 2-λ0 . We will define a distribution µ that has an n-point support, and where the k-th point occurs at time 22-λk-ε with probability pk, for ε > 0 arbitrarily small. For k < n-1, we define pk = 2λk+1-λ0 - 2λk-λ0 , and define pn-1 = 2 - 2λn-1-λ0 . Let Pk = ∑j≤k pj , so Pk = 2λk+1-λ0 - 1. Similarly, for any k > 0, we have: The expected value of µ is (defining λn = λ0 + 1): From (4) and (5), the consistency of any X(λk) is: c(X(λk), µ) is minimized when the λj are chosen so as to minimize the sum term, while respecting the constraint that the sum of all the exponents equals λn - λ0 = 1 and each exponent belongs to [0, 1). By the convexity of the function x ↦→ 2x , this occurs when all terms are equal to 21/n , hence By allowing n → ∞, Theorem 5 shows that no 4-robust schedule can have consistency better than 4 ln2. Note that the theorem relies on a probability distribution with n mass points. However, we can obtain the same lower bound by relying to a prediction given as a continuous distribution. Theorem 6. For any D > 0, there is a continuous distribution µD over the interval [D, 2D] such that, for every 4-robust schedule X, c(X, µD) ≥ 4 ln 2. Proof. From Proposition 7, let X(λ) denote the 4-robust schedule, for some λ ∈ [0, 1). Consider any value D > 1. We will define a distribution function µD over [D, 2D] such that c(X(λ), µD) ≥ 4 ln 2. Specifically, let the density function of µD equal fD(x) = 2D/x2 on [D, 2D] and 0 elsewhere. Note that ∫ fD = 1, so µD is indeed a distribution. We have Let k be such that 2k-λ ∈ [D, 2D). The last completed contract of X(λ) is of length 2k-λ-2 if an interruption occurs between D and 2k-λ , and of length 2k-λ-1 if an interruption occurs between 2k-λ and 2D. So Therefore, we have c(X(λ), µD) = 4 ln 2. ## 3.1 Smoothness with Rrediction Errors We will now discuss an interesting disconnect between deterministic and distributional predictions that arises in contract scheduling. Consider first the setting of a single, deterministic prediction, for which we know that there exist 4-robust, 2-consistent schedules [Angelopoulos and Kamali, 2023]. Given such prediction, say τ, let η = |T - τ| denote the prediction error associated with τ, where T denotes the actual interruption. Proposition 7. For any arbitrarily small ϵ > 0, and any schedule X with prediction τ that is 4-robust and 2consistent, there exists T such that η = |T - τ| = ϵ and ℓ(X, T) ≤ 14 T + ϵ4 . Proposition 7 shows that, in the single prediction setting, any schedule that simultaneously optimizes the consistency and the robustness is extremely fragile with respect to prediction errors. Informally, in the presence of a tiny prediction error, the proposition shows that the consistency of the schedule becomes as large as the robustness, namely arbitrarily close to 4, hence the single prediction leads to no improvement in any practical situation. In contrast, we will show that this is not the case for the worst-case distributional prediction of Theorem 6. Specifically, in Theorem 8, we will show that the performance of the schedule degrades smoothly as a function of the prediction error. For some intuition behind the proof, we will use the fact that worst-case distributional predictions require that a large time interval contributes to the schedule's expected profit, and that the distribution is rather "balanced" over that interval. Therefore, if an adversary were to change substantially the performance of the schedule, by altering the predicted distribution, it would have to shift a large amount of probability mass over a long time span. This motivates the choice of the well-known Earth Mover's Distance (EMD) as a metric of the prediction error. We will show that a small EMD error has a likewise small effect on the performance. Given two probability distributions µ and µ′ over R+, the Earth Mover's Distance (EMD) [Rubner et al., 1998] intuitively represents the minimum cost incurred in order to obtain µ′ from µ, where moving an infinitesimal probability mass costs its amount multiplied by the distance moved. Formally, let Ψ(µ, µ′ ) ⊂ (R+ × R+) → R+ be the set of functions ψ such that ∀x ∈ R+, ∫R+ ψ(x, y)dy = µ(x) and ∀y ∈ R+, ∫R+ ψ(x, y)dx = µ′ (y). Here, ψ(x, y) describes the amount of mass that is moved from point x in µ to point y in µ′ . The distance EMD(µ, µ′ ) is then defined as Theorem 8. Given D ∈ R+, let µD be the probability distribution of Theorem 6. Then, for, any probability distribution µ′ such that EMD(µD, µ′ ) ≤ η, for sufficiently small η, any 4-robust schedule X with prediction µD satisfies Proof. We give the main elements of the proof, but omit some technical details due to space limitations. Recall that the distribution µ = µD is defined over [D, 2D] by the density function x ↦→ 2D/x2 . This density function takes values in the interval [1/(2D), 2/D]. From Proposition 1, we know that any 4-robust schedule X is of the form X(λ) = 2i-λ , for some λ ∈ [0, 1). For given η > 0, let µ′ be any probability distribution such that EMD(µ, µ′ ) ≤ η. By the definition of EMD, let ψ ∈ Ψ(µ, µ′ ) be a function such that We decompose ψ in two functions ψ+ and ψ- satisfying the following conditions. For x < y, ψ+(x, y) = ψ(x, y) and ψ-(x, y) = 0. For x > y, ψ-(x, y) = ψ(x, y) and ψ+(x, y) = 0. Last, we require that ψ+(x, x) = ∫z≤x ψ(x, z)dz, and ψ-(x, x) = ∫z≥x ψ(x, z)dz. Intuitively, ψ+ denotes the probability mass moved towards higher values, and, likewise, ψ- denotes the probability mass moved towards lower values. Let µ+ be the probability obtained after applying ψ+; namely, we define µ+(y) = ∫R+ ψ+(x, y)dx. Note that In the first part of the proof, we focus on the effect of ψ+ and bound the expected profit of X(λ) under the distribution µ+, as well as the expectation of the distribution µ+. The intuition here is that the expected profit of X(λ) cannot decrease, and that the growth of the expected value of the distribution is bounded by the EMD. We can show that In the next part of the proof, we focus on the effect of ψ-. Here, the expected value of the distribution cannot increase, and the expected profit of X(λ) decreases by an amount which can be bounded using η and D. This last bound is the most technical step of the proof and uses the fact that minx∈[D,2D] µ(x) ≤ 4 · maxx∈[D,2D] µ(x). We can show that To conclude the proof, note that Ez∼µ[z] = 2D ln2 and Ez∼µ[ℓ(X(λ), z)] = D/2, from the proof of Theorem 6. Combing Equations (6), (7), (8) and (9), we arrive at the desired result, for η < D/512 (to ensure there is no division by zero). ## 4 Multiple Advice In this section, we study the setting in which the prediction oracle provides a set P that consists of k (potential interruption) times, denoted by τ0, . . . , τk-1. Recall that the consistency of a schedule is given by (3). For every j ∈ [0, k - 1], we denote by δj ∈ [0, 1), and by ij ∈ N the unique values such that τi = 2ij+δj . We assume, without loss of generality that 0 ≤ δ0 ≤ δ1 . . . ≤ δk-1 < 1. Figure 2: Illustration of the definitions of δj and Dj. ![Image](https://ijcai.org/proceedings/2024/fulltext/404/image_000001_5db71a971b2761ec7e3a92ecd85665f606a7ede3b269f9f78009f5efc5fa889e.png) We first show that we can find, in time polynomial in k, a schedule that simultaneously minimizes the consistency and the robustness. Theorem 9. Given a prediction set P of size k, we can find a 4-robust schedule of optimal consistency in time O(k2 ). Proof. We first argue that there exists a 4-robust schedule of optimal consistency X∗ = (x∗i )i∈Z, such that X∗ contains at least one contract whose execution is completed at time τj, for some τj ∈ P. By way of contradiction, suppose this is not the case. From Proposition 1, the last contract completed by X∗ by time t finishes at time 2ℓ(X∗ , t). Define a = minj∈[0,k-1] τj 2ℓ(X∗ ,τj) , and consider the schedule X′ = (2log2 a · x∗i )i∈Z. From Proposition 1, X′ is also 4robust. Moreover, we have that ℓ(X′ , τj) ≥ ℓ(X∗ , τ), therefore X′ is also optimal, a contradiction. The above observation leads to the following algorithm for finding an optimal schedule. For every j ∈ [0, k - 1], define the schedule Xj = (2i+δj )i∈Z, and note that, by definition, Xj has a contract that terminates at time τj. Thus, among schedules in the collection {Xj}k-1 j=0 , the schedule Xl∗ with best consistency is such that From Proposition 1, it follows that the above algorithm yields a 4-robust schedule of optimal consistency. The complexity of this algorithm is O(k2 ), since each αj can be computed in time O(k). However, we can reduce the complexity to O(k log k), using an argument that will also be useful in the proof of Corollary 11, and which is illustrated in Figure 2. Consider the circle of unit perimeter, with an arbitrary point O fixed, and let p0, . . . , pk-1 be points in the circle, such that the clockwise (arc-length) distance between O and pj is dc(O, pj) = δj. Given i ∈ [0, k - 1], define Di as the clockwise distance between the consecutive points p(i-1) mod k and pi in the circle. We show the following: Lemma 10. For j ∈ [0, k - 1], let Xj denote the schedule (2i+δj )i∈Z. Then Xj has consistency at most 22-Dj . Lemma 10 implies that we can improve the complexity of the algorithm of Theorem 9, by finding the index j for which Dj is minimized. This can be accomplished in time O(k log k) by sorting. An interesting question is finding the exact value of the worst-case consistency of optimal schedules. The following corollary answers this question. Corollary 11. The schedule of Theorem 9 has consistency at most 22- 1k , where k is the size of P . Furthermore, this bound is tight, in that there exists a prediction P such that every 4-robust schedule has consistency at least 22- 1k . Note that Corollary 11 subsumes the known results for the extreme cases k = 1 (for which the consistency is equal to 2 [Angelopoulos and Kamali, 2023]), and k → ∞ (for which the consistency reduces to the worst-case acceleration ratio [Russell and Zilberstein, 1991]). ## 5 Experimental Evaluation ## 5.1 Distributional Advice We evaluate our algorithm of Theorem 3, to which we refer as SELn, and recall that this algorithm selects the best schedule in class Sn, for some given n ∈ N. We first consider, as distributional advice µ, a normal distribution that is truncated at zero, with mean m, and standard deviation σ. Figure 3 depicts the experimental performance of SELn, as function of m, for n ∈ [1, 4], σ = 0.05m and m ∈ [1, 1024]. Note that for all sufficiently large m, e.g., m≥ 100, the expected interruption time is extremely close to m. We observe that the consistency of SELn improves as n increases, by design of the algorithm. In particular, for n = 4, the empirical consistency is 2.51. This value is, as expected, below the anticipated worst-case bound of Theorem 3 (namely, 16(20.25 -1) ≈ 3.03) and above the lower bound of 2, which applies to single, deterministic predictions. The shape of the consistency is a saw-like function of the mean, which is explained by the fact that the consistency (as the acceleration ratio) has transitions at "critical" times, i.e., right after the completion of a contract. As n increases, we note that the transitions become more smooth. This is because the number of candidate schedules in Sn becomes larger, hence the probability that the interruption is critical for some schedule in Sn decreases. This also explains why the number of peaks increases as function of n. We also report results for a uniform distributional advice. Specifically, Figure 4 depicts the consistency of SELn with advice chosen according to U[0.95t, 1.05t], as function of t. For n = 4, we observe a similar empirical consistency value as in the case of the normal distribution, namely 2.44. The shape of the plot has sharper transitions, relatively to the normal distribution, which can be explained by the fact that the latter spreads the random interruption over a larger interval than the uniform one, in this experimental setup. This also explains why the difference between the peaks and valleys is more pronounced in Figure 4 than in Figure 3. ## 5.2 Multiple Advice We evaluate our algorithm from Section 4, to which we refer as MULTk, where k is the cardinality of the prediction set P. Specifically, for every k ∈ [1, 10], we generate P as k Figure 3: Plot of the consistency of SELn with advice a truncated normal distribution as function of the mean m. ![Image](https://ijcai.org/proceedings/2024/fulltext/404/image_000002_0c9cc8ffad03e0815e5137528adc4236e68413862c86276f89963af935fcbde3.png) ![Image](https://ijcai.org/proceedings/2024/fulltext/404/image_000003_6e13ba051a32de418ad2219aba1056004e364a9fd0e46a3ba25b19e940e01d28.png) t Figure 4: Plot of the consistency of SELn with advice a uniform distribution in [0.95t, 1.05t], as function of t. ![Image](https://ijcai.org/proceedings/2024/fulltext/404/image_000004_7cdf0d3690db07578cec76dfba7205767e7d4f0ce1c357f1aced29a4d55f7d6b.png) Figure 5: Experimental evaluation of MULTk. values chosen independently and uniformly at random in the interval [1, 1024]. For each such prediction set, we compute the worst-case consistency, as evaluated by (3). We compute, in addition, the average-case consistency, namely the average of the ratios τ/ℓ(MULTk, τ), where τ is chosen uniformly at random from P. The latter is a much more relaxed performance measure that treats each of the k predictions in P as equally likely. We repeat this experiment 1000 times, and we report the average of the corresponding ratios. We observe that for all values of k, both the worst-case and the average consistency are below the upper bound of 22- 1k , which confirms the result of Corollary 11. The ratios, as expected, are increasing functions of k, since the larger the size of P , the more noisy the quality of the prediction. ## 6 Conclusion We studied a classic optimization problem related to bounded-resource reasoning, namely contract scheduling, in novel learning-augmented settings that capture distributional and multiple predictions. In both settings, we gave analytically optimal schedules that simultaneously optimize the consistency and the robustness. As discussed in Section 1, contract scheduling has been studied in a variety of settings, including multiple instances that must be solved concurrently, in a single or multiple processors. Future work will address these more complex variants under similar learning-enhanced models, as well as the full Pareto frontier for all values r > 4, which is a challenging problem. It will be also interesting to perform a multi-objective analysis, in the multiple-advice model, that addresses the average expected consistency or trade-offs between the worst-case and the average-case metrics. The techniques of Section 4 can be applicable, by showing first tradeoffs between average and worst-case distances between points on the unit circle. Another direction for future work is searching for a hidden target, with distributional or multiple predictions about its position. This setting has applications in robotic search and exploration, and has been studied with single, or no prediction e.g., [Eberle et al., 2022; Sung and Tokekar, 2019]. In particular, the techniques we developed in this work will be very useful in the context of the line and star search environments [Jaillet and Stafford, 1993], given the connections between contract scheduling and competitive search [Bernstein et al., 2003; Angelopoulos, 2015]. Last, our work is the first to bring attention to the fact that single predictions may be fragile for certain problems, a finding that can have implications in other domains and applications such as learningaugmented online conversion problems [Sun et al., 2021]. ## Acknowledgements This work was partially funded by the project PREDICTIONS, grant ANR-23-CE48-0010 and the project ALGORIDAM, grant ANR-19-CE48-0016 from the French National Research Agency (ANR), as well as by Polish National Science Centre grant 2022/45/B/ST6/00559. ## References 1. [Almanza et al., 2021] Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. Online facility location with multiple advice. Advances in Neural Information Processing Systems, 34:4661-4673, 2021. 2. [Anand et al., 2021] Keerti Anand, Rong Ge, Amit Ku- mar, and Debmalya Panigrahi. A regression approach to learning-augmented online algorithms. Advances in Neural Information Processing Systems, 34:30504-30517, 2021. 3. [Anand et al., 2022] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multi- ple predictions. In International Conference on Machine Learning, pages 582-598. PMLR, 2022. 4. [Angelopoulos and Jin, 2019] Spyros Angelopoulos and Shendan Jin. Earliest-completion scheduling of contract algorithms with end guarantees. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, (IJCAI), pages 5493-5499, 2019. 5. [Angelopoulos and Kamali, 2023] Spyros Angelopoulos and Shahin Kamali. Contract scheduling with predictions. J. Artif. Intell. Res., 77:395-426, 2023. 6. [Angelopoulos and López-Ortiz, 2009] Spyros Angelopou- los and Alejandro López-Ortiz. Interruptible algorithms for multi-problem solving. In Proceedings of the 21st In- ternational Joint Conference on Artificial Intelligence (IJ- CAI), pages 380-386, 2009. 7. [Angelopoulos and Panagiotou, 2023] Spyros Angelopoulos and Konstantinos Panagiotou. Weighted online search. J. Comput. Syst. Sci., 138:103457, 2023. 8. [Angelopoulos et al., 2008] Spyros Angelopoulos, Alejan- dro López-Ortiz, and Angele Hamel. Optimal scheduling of contract algorithms with soft deadlines. In Proceed- ings of the 23rd AAAI Conference on Artificial Intelligence (AAAI), pages 868-873, 2008. 9. [Angelopoulos et al., 2020] Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc P. Renault. Online computation with untrusted ad- vice. In Proceedings of the 11th International Conference on Innovations in Theoretical Computer Science (ITCS), pages 52:1-52:15, 2020. 10. [Angelopoulos, 2015] Spyros Angelopoulos. Further con- nections between contract-scheduling and ray-searching problems. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 1516- 1522, 2015. 11. [Antoniadis et al., 2023] Antonios Antoniadis, Christian Co- ester, Marek Elias, Adam Polak, and Bertrand Simon. Mixing predictions for online metric algorithms. In In- ternational Conference on Machine Learning, pages 969- 983. PMLR, 2023. 12. [Bernstein et al., 2002] Daniel S. Bernstein, T. J. Perkins, Shlomo Zilberstein, and Lev Finkelstein. Scheduling con- tract algorithms on multiple processors. In Proceedings of the 18th AAAI Conference on Artificial Intelligence (AAAI), pages 702-706, 2002. 13. [Bernstein et al., 2003] Daniel S. Bernstein, Lev Finkelstein, and Shlomo Zilberstein. Contract algorithms and robots on rays: Unifying two scheduling problems. In Proceedings of the 18th International Joint Conference on Artificial In- telligence (IJCAI), pages 1211-1217, 2003. 14. [Boddy and Dean, 1994] Mark Boddy and Thomas L. Dean. Deliberation scheduling for problem solving in time- constrained environments. Artif. Intell., 67(2):245-285, 1994. 15. [Chrobak and Kenyon-Mathieu, 2006] Marek Chrobak and Claire Kenyon-Mathieu. SIGACT news online algorithms column 10: Competitiveness via doubling. SIGACT News, 37(4):115-126, 2006. 16. [Demaine et al., 2006] E.D. Demaine, S.P. Fekete, and S. Gal. Online searching with turn cost. Theoretical Com- puter Science, 361:342-355, 2006. 17. [Diakonikolas et al., 2021] Ilias Diakonikolas, Vasilis Kon- tonis, Christos Tzamos, Ali Vakilian, and Nikos Zari- fis. Learning online algorithms with distributional advice. In International Conference on Machine Learning, pages 2687-2696. PMLR, 2021. 18. [Dinitz et al., 2022] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Algorithms with prediction portfolios. Advances in neural information processing systems, 35:20273-20286, 2022. 19. [Eberle et al., 2022] Franziska Eberle, Alexander Linder- mayr, Nicole Megow, Lukas Nölke, and Jens Schlöter. Ro- bustification of online graph exploration methods. In Pro- ceedings of the 36th AAAI Conference on Artificial Intelli- gence, AAAI 2022, pages 9732-9740. AAAI Press, 2022. 20. [Gollapudi and Panigrahi, 2019] Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In Proceedings of the 36th Interna- tional Conference on Machine Learning (ICML), pages 2319-2327, 2019. 21. [Horvitz, 1988] Eric Horvitz. Reasoning about beliefs and actions under computational resource constraints. Int. J. Approx. Reasoning, 2(3):337-338, 1988. 22. [Im et al., 2023] Sungjin Im, Benjamin Moseley, Chenyang Xu, and Ruilong Zhang. Online dynamic acknowledge- ment with learned predictions. In INFOCOM, pages 1-10. IEEE, 2023. 23. [Jaillet and Stafford, 1993] P. Jaillet and M. Stafford. Online searching. Operations Research, 49:234-244, 1993. 24. [Lindermayr and Megow, 2023] Alexander Lindermayr and Nicole Megow. Repository of works on algorithms with predictions. https://algorithms-with-predictions.github.io, 2023. Accessed: 2023-12-01. 25. [López-Ortiz et al., 2014] Alejandro López-Ortiz, Spyros Angelopoulos, and Angele Hamel. Optimal scheduling of contract algorithms for anytime problem-solving. J. Artif. Intell. Res., 51:533-554, 2014. 26. [Lykouris and Vassilvitskii, 2021] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM, 68(4):24:1-24:25, 2021. 27. [Mitzenmacher and Vassilvitskii, 2020] Michael Mitzen- macher and Sergei Vassilvitskii. Algorithms with predictions. In Beyond the Worst-Case Analysis of Algorithms, pages 646-662. Cambridge University Press, 2020. 28. [Purohit et al., 2018] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML pre- dictions. In Proceedings of the 31st Annual Conference on Neural Information Processing Systems (NIPS), pages 9661-9670, 2018. 29. [Rubner et al., 1998] Yossi Rubner, Carlo Tomasi, and Leonidas J Guibas. A metric for distributions with ap- plications to image databases. In Sixth international con- ference on computer vision (IEEE Cat. No. 98CH36271), pages 59-66. IEEE, 1998. 30. [Russell and Zilberstein, 1991] Stuart J. Russell and Shlomo Zilberstein. Composing real-time systems. In Proceedings of the 12th International Joint Conference on Artificial In- telligence (IJCAI), pages 212-217, 1991. 31. [Sun et al., 2021] Bo Sun, Russell Lee, Mohammad Ha- jiesmaili, Adam Wierman, and Danny Tsang. Pareto- optimal learning-augmented algorithms for online con- version problems. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 10339-10350, 2021. 32. [Sung and Tokekar, 2019] Yoonchang Sung and Pratap Tokekar. A competitive algorithm for online multi-robot exploration of a translating plume. In 2019 International Conference on Robotics and Automation (ICRA), pages 3391-3397. IEEE, 2019. 33. [Wang et al., 2020] Shufan Wang, Jian Li, and Shiqiang Wang. Online algorithms for multi-shop ski rental with machine learned advice. Advances in Neural Information Processing Systems, 33:8150-8160, 2020. 34. [Zilberstein and Russell, 1993] Shlomo Zilberstein and Stu- art Russell. Anytime sensing planning and action: A prac- tical model for robot control. In IJCAI, pages 1402-1407. 35. Morgan Kaufmann, 1993. 36. [Zilberstein and Russell, 1996] Shlomo Zilberstein and Stu- art J. Russell. Optimal composition of real-time systems. Artif. Intell., 82(1-2):181-213, 1996. 37. [Zilberstein et al., 2003] Shlomo Zilberstein, Francois Charpillet, and Philippe Chassaing. Optimal sequenc- ing of contract algorithms. Ann. Math. Artif. Intell., 39(1-2):1-18, 2003.