{'fraction_non_alphanumeric': 0.043374608596641044, 'fraction_numerical': 0.006386991175633362, 'mean_word_length': 3.9848350478893226, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Safe Learning for Near Optimal Scheduling

In this paper, we investigate the combination of synthesis, model-based learning, and online sampling techniques to obtain safe and near-optimal schedulers for a preemptible task scheduling problem. Our algorithms can handle Markov decision processes (MDPs) that have 1020 states and beyond which cannot be handled with state-of-the art probabilistic model-checkers. We provide probably approximately correct (PAC) guarantees for learning the model. Additionally, we extend Monte-Carlo tree search with advice, computed using safety games or obtained using the earliest-deadline-first scheduler, to safely explore the learned model online. Finally, we implemented and compared our algorithms empirically against shielded deep Q-learning on large task systems.


Introduction
In this paper, we show how to combine synthesis, model-based learning, and online sampling techniques to solve a scheduling problem featuring both hard and soft constraints. We investigate solutions to this problem both from a theoretical and from a more pragmatic point of view. On the theoretical side, we show how safety guarantees (as understood in formal verification) can be combined with guarantees offered by the probably approximately correct (PAC) learning framework [24]. On the pragmatic side, we show how safety guarantees obtained from automatic synthesis can be combined with Monte-Carlo tree search (MCTS) [21] to offer a scalable and practical solution to solve the scheduling problem at hand.
The scheduling problem that we consider is defined as follows. A task system is composed of a set of n preemptible tasks (τ i ) i∈[n] partitioned into a set F of soft tasks and a set H of hard tasks. Time is assumed to be discrete and measured e.g. in CPU ticks. Each task τ i generates an infinite number of instances τ i,j , called jobs, with j = 1, 2, . . . Jobs generated by both hard and soft tasks are equipped with deadlines, which are relative to the respective arrival times of the jobs in the system. The computation time requirements of the jobs follow a discrete probability distribution, and are unknown to the scheduler but upper bounded by their relative deadline. Jobs generated by hard tasks must complete before their respective deadlines. For jobs generated by soft tasks, deadline misses result in a penalty/cost. The tasks are assumed to be independent and generated stochastically: the occurrence of a new job of one task does not depend on the occurrences of jobs of other tasks, and both the inter-arrival and computation times of jobs are independent random variables. The scheduling problem consists in finding a scheduler, i.e. a function that associates, to all CPU ticks, a task that must run at that moment; in order to: (i) avoid deadline misses by hard tasks; and (ii) minimise the mean cost of deadline misses by soft tasks.
In [14], we modelled the semantics of the task system using a Markov decision process (MDP) and posed the problem of computing an optimal and safe scheduler. However, that work assumes that the distribution of all tasks is known a priori which may be unrealistic. Here, we investigate learning techniques to build algorithms that can schedule safely and optimally a set of hard and soft tasks if only the deadlines and the domains of the distributions describing the tasks of the system are known a priori and not the exact distributions. This is a more realistic assumption. Our motivation was also to investigate the joint application of both synthesis techniques coming from the field of formal verification and learning techniques on an understandable yet challenging setting.
Contributions. First, we show the distributions underlying a task system with only soft tasks are efficiently PAC learnable: by executing the task system for a polynomial number of steps, enough samples can be collected to infer ε-accurate approximations of the distributions with high probability (Thm. 1).
Then, we consider the general case of systems with both hard and soft tasks. Here, safe PAC learning is not always possible, and we identify two algorithmically-checkable sufficient conditions for task systems to be safely learnable (Thms. 2 and 3). These crucially depend on the underlying MDP being a single maximal end-component, as is the case in our setting (Lem. 2). Subsequently, we can use robustness results on MDPs to compute or learn near-optimal safe strategies from the learnt models (Thm. 4).
Third, in order to evaluate the relevance of our algorithms, we present experiments of a prototype implementation. These empirically validate the efficient PAC guarantees. Unfortunately, the learnt models are often too large for the probabilistic model-checking tools. In contrast, the MCTS-based algorithm scales to larger examples: e.g. we learn safe scheduling strategies for systems with more than 10 20 states. Our experiments also show that a strategy obtained using deep Q-learning [2,19] by assigning high costs to missing deadlines of hard tasks does not respect safety, even if one learns for a long period of time and the deadline-miss costs of hard tasks are very high (cf. [1]). Related works In [14], we introduced the scheduling problem considered here but made the assumption that the underlying distributions of the tasks are known. We drop this assumption here and provide learning algorithms. In [1], the framework to combine safety via shielding and model-free reinforcement learning is introduced and applied to several examples using table-based Q-learning as well as deep RL. In [3], shield synthesis is studied for long-run objective guarantees instead of safety requirements. Unlike our work, the transition probabilities on MDPs in both [1] and [3] are assumed to be known. We observe that [1] and [3] do not provide model-based learning and PAC guarantees. While some pre-shielding literature does consider unknown MDPs (see, e.g. [13]), we are not aware of PAC-learning works that focus on scheduling problems.
In [17], we studied a framework to mix reactive synthesis and model-based reinforcement learning for mean-payoff with PAC guarantees. There, the learning algorithm estimates the probabilities on the transitions of the MDP. In our approach, we do not estimate these probabilities directly from the MDP, but learn probabilities for the individual tasks in the task system. The efficient PAC guarantees that we have obtained for the model-based part cannot be obtained from that framework. Finally, in [8] we introduced a first combination of shielding with model-predictive control using MCTS, but did not consider learning.

Preliminaries
We denote by N the set of natural numbers; by Q, the set of rational numbers; and by Q ≥0 the set {q ∈ Q | q ≥ 0} of all non-negative rational numbers. Given n ∈ N, we denote by [n] the set {1, . . . , n}. Given a finite set A, a (rational) probability distribution over A is a function p : A → [0, 1] ∩ Q such that a∈A p(a) = 1. We call A the domain of p, and denote it by Dom(p). We denote the set of probability distributions on A by D(A). The support of the probability distribution p on A is Supp(p) = {a ∈ A | p(a) > 0}. A distribution is called Dirac if |Supp(p)| = 1. For a probability distribution p, the minimum probability assigned by p to the elements in Supp(p) is π p min = min a∈Supp(p) (p(a)). We say two distributions p and p are structurally identical if Supp(p) = Supp(p ). Given two structurally identical distributions p and p , for 0 < ε < 1, we say that p is ε-close to p , denoted p ∼ ε p , if Supp(p) = Supp(p ), and for all a ∈ Supp(p), we have that |p(a)−p (a)| ≤ ε.
Scheduling problem An instance of the scheduling problem studied in [14] consists of a task system Υ = ((τ i ) i∈[n] , F, H), where (τ i ) i∈[n] are n preemptible tasks partitioned into hard and soft tasks H and F respectively. The latter need to be scheduled on a single processor. Formally, the work of [14] relies on a probabilistic model for the computation times of the jobs and for the delay between the arrival of two successive jobs of the same task. For all i ∈ [n], task τ i is defined as a tuple C i , D i , A i , where: (i) C i is a discrete probability distribution on the (finitely many) possible computation times of the jobs generated by τ i ; (ii) D i ∈ IN is the deadline of all jobs generated by τ i which is relative to their arrival time; and (iii) A i is a discrete probability distribution on the (finitely many) possible inter-arrival times of the jobs generated by τ i . We denote by π Υ max the maximum probability appearing in the definition of Υ , that is, across all the distributions C i and A i , for all i ∈ [n]. It is assumed that max(Dom(C i )) ≤ D i ≤ min(Dom(A i )) for all i ∈ [n]; hence, at any point in time, there is at most one job per task in the system. Also note that when a new job of some task arrives at the system, the deadline for the previous job of this task is already over. Finally, we assume that the task system is schedulable for the hard tasks, meaning that it is possible to guarantee that jobs associated to hard tasks never miss their deadlines. On the other hand, the full set of tasks may not be schedulable, so that jobs associated with soft tasks may be allowed to miss their deadlines. The potential degradation in the quality when a soft task misses its deadline is modelled by a cost function cost : F → Q ≥0 that associates to each soft task τ j a cost c(j) that is incurred every time a job of τ j misses its deadline. As a final observation, we recall the earliest deadline first (EDF) algorithm that always gives execution time to the job closest to its deadline. EDF is an optimal scheduling algorithm in the following sense: if a task system is schedulable (without any misses at all) then EDF will yield such a feasible schedule [6]. In general, applying EDF on both the hard and soft tasks may cause hard tasks to miss deadlines, as the entire task system may not be schedulable. However, one may apply EDF on hard tasks only, and allow for soft tasks whenever no hard task is available. This version of EDF ensures that all jobs of hard tasks are scheduled in time, but does not guarantee optimality with respect to cost. Given a task system Υ = ((τ i ) i∈[n] , F, H) with n tasks, the structure of Υ is ((struct(τ i )) i∈[n] , F, H) where struct( C, D, A ) = ( Dom(C), D, Dom(A) ). We denote by C max and A max resp. the maximum computation time, and the maximum inter-arrival time of a task in Υ . Formally, C max = max( i∈[n] Dom(C i )), and A max = max( i∈[n] Dom(A i )). Note that A max ≥ C max . We also let D = max i∈[n] (|Dom(A i )|). We denote by |Υ | the number of tasks in the task system Υ . Consider two task systems Υ 1 = ((τ 1 i ) i∈[n] , F, H), and Υ 2 = ((τ 2 i ) i∈[n] , F, H), with and j ∈ [2]. The two task systems Υ 1 and Υ 2 are said to be ε-close, denoted

Markov decision processes
Let us now introduce Markov Decision Process (MDP) as they form the basis of the formal model of [14], which we recall later. A finite Markov decision process is a tuple Γ = V, E, L, (V , V ), A, δ, cost , where: (i) A is a finite set of actions; (ii) V, E is a finite directed graph and L is an edge-labelling function (we denote by E(v) the set of outgoing edges from vertex v); (iii) the set of vertices V is partitioned into V and V ; (iv) the graph is bipartite i.e. E ⊆ (V × V ) ∪ (V × V ), and the labelling function . For all edges e, we let cost(e) = L(e) if L(e) ∈ Q, and cost(e) = 0 otherwise. We further assume that, for all v ∈ V , for all e, e in E(v): L(e) = L(e ) implies e = e , i.e. an action identifies uniquely an outgoing edge. Given v ∈ V , and a ∈ A, we define we have that Supp(δ(v)) = Supp(δ (v)). For two structurally identical MDPs Γ and Γ with distribution assignment functions δ and δ respectively, we say that An MDP Γ can be interpreted as a game G Γ between two players: and , who own the vertices in V and V respectively. A play in an MDP is a path in its underlying graph V, E, A ∪ Q . We say that a prefix π(n) of a play π belongs to player i ∈ { , }, iff its last vertex Last(π(n)) is in V i . The set of prefixes that belong to player i is denoted by Prefs i (G Γ ). A play is obtained by the interaction of the players: if the current play prefix π(n) belongs to , she plays by picking an edge e ∈ E(Last(π(n))) (or, equivalently, an action that labels a necessarily unique edge from Last(π(n))). Otherwise, when π(n) belongs to , the next edge e ∈ E(Last(π(n))) is chosen randomly according to δ(Last(π(n))). In both cases, the plays prefix is extended by e and the game goes ad infinitum.
A (deterministic) strategy of is a function σ : Prefs (G) → E, such that σ (ρ) ∈ E(Last(ρ)) for all prefixes. A strategy σ is memoryless if for all finite prefixes ρ 1 and ρ 2 ∈ Prefs(G): Last(ρ 1 ) = Last(ρ 2 ) implies σ (ρ 1 ) = σ (ρ 2 ). For memoryless strategies, we will abuse notations and assume that such strategies σ are of the form σ : V → E (i.e., the strategy associates the edge to play to the current vertex and not to the full prefix played so far). From now on, we will consider memoryless deterministic strategies unless otherwise stated. Let Γ = V, E, L, (V , V ), A, δ, cost be an MDP, and let σ be a memoryless strategy. Then, assuming that plays according to σ , we can express the behaviour of Γ as a Markov chain Γ [σ ], where the probability distributions reflect the stochastic choices of (see [14] for the details). is an EC that is not included in any other EC. MDP for the scheduling problem Given a system Υ = {τ 1 , τ 2 , . . . , τ n } of tasks, we describe below the modelling of the scheduling problem by an MDP Γ Υ = V, E, L, (V , V ), A, δ, cost as it appears in [14]. The two players and correspond respectively to the Scheduler and the task generator (TaskGen) respectively. Since there is at most one job per task that is active at all times, vertices encode the following information about each task τ i : (i) a distribution c i over the job's possible remaining computation times (rct); (ii) the time d i up to its deadline; and (iii) a distribution a i over the possible times up to the next arrival of a new job. We also tag vertices with either or to remember their respective owners and we have a vertex ⊥ that is reached when a hard task misses a deadline. For a vertex v = (c 1 , d 1 , a 1 ) . . . (c n , d n , a n ), ∆ , for ∆ ∈ { , }, let active(v) = {i | c i (0) = 1 and d i > 0} be the tasks that have an active job in v; dlmiss(v) = {i | c i (0) = 0 and d i = 0}, those that have missed a deadline in v. Possible moves The possible actions of Scheduler are to schedule an active task or to idle the CPU. We model this by having, from all vertices v ∈ V one transition labelled by some element from active(v), or by ε. The moves of TaskGen consist in selecting, for each task one possible action out of four: either (i) nothing (ε); or (ii) to finish the current job without submitting a new one (f in); or (iii) to submit a new job while the previous one is already finished (sub); or (iv) to submit a new job and kill the previous one, in the case of a soft task (killAN Dsub), which will incur a cost.
We consider the following example from [14].
When p is s.t. p(x) = 1 for some x, we simply denote p by x. Vertices from V and V are depicted by rectangles and rounded rectangles respectively. Each vertex is labelled by (c h , d h , a h ) on the top, and (c s , d s , a s ) below. A strategy to avoid missing a deadline of τ h consists in first scheduling τ s , then τ h . One then reaches the left-hand part of the graph from which can avoid ⊥ whatever does. Other safe strategies are possible: the first step of the algorithm in [14] is to compute all the safe nodes (i.e. those from which can ensure to avoid ⊥), and then find an optimal one w.r.t to missed-deadline costs.
There are two optimal memoryless strategies, one in which Scheduler first chooses to execute τ h , then τ s ; and another where τ s is scheduled for 1 time unit, and then preempted to let τ h execute. Since the time difference between the arrival of two consecutive jobs of the soft task τ s is 3 and the cost of missing a deadline is 10, for both of these optimal strategies, the soft task's deadline is missed with probability 0.6 over this time duration of 3, and hence the mean-cost is 2. There is another safe schedule that is not optimal which only grants τ h is CPU access, and never schedules τ s , thus giving a mean-cost of 10 3 . Expected mean-cost Let us first associate a value, called the mean-cost MC(π) to all plays π in an MDP Γ cost(e i ) (recall that cost(e) = 0 when L(e) is an action). Then, for a play π = e 0 e 1 . . ., we have MC(π) = lim sup n→∞ MC(π(n)). Observe that MC is a measurable function. A strategy σ is optimal for the mean-cost from some initial v init (MC). Such optimal strategy always exists, and it is well-known that there is always one which is memoryless. Moreover, this problem can be solved in polynomial time through linear programming [12] or in practice using value iteration (as implemented, for example, in the tool Storm [10]). We denote by Given Γ with vertices V , initial vertex v init ∈ V , and a set V bad ⊆ V of bad vertices, the safety synthesis problem is to decide whether has a strategy σ ensuring to visit the safe vertices only, i.e.: If this is the case, we call such a strategy safe. The safety synthesis problem is decidable in polynomial time for MDPs (see, e.g., safety games in [23]). Moreover, if a safe strategy exists, then there is a memoryless safe strategy. Henceforth, we will consider safe strategies that are memoryless only. We say that a vertex v is safe iff has a safe strategy from v, and that an edge So, the safe edges safe(v) from some node v correspond to the choices that can safely make from v. The set of safe edges exactly correspond to the set of safe actions that can make from v. Then, we let the safe region of Γ be the MDP Γ safe obtained from Γ by applying the following transformations: (i) remove from Γ all unsafe edges; (ii) remove from Γ all vertices and edges that are not reachable from v init . Most general safe scheduler Consider a task system Υ that is schedulable for the hard tasks. Then, Scheduler has a winning strategy to avoid ⊥ in Γ Υ . We say a non-deterministic strategy in Γ Υ is the most general safe scheduler (MGS) for the hard tasks if from any vertex of Scheduler it allows all safe edges 4 .

Model-Based Learning
We now investigate the case of model-based learning of task systems. First, we consider the simpler case of task systems with only soft tasks. We show that those systems are always efficiently PAC learnable. Second, we consider learning task systems with both hard and soft tasks. In that case, we study two conditions for learnability. The first condition allows us to identify task systems that are safely PAC learnable, i.e. learnable while enforcing safety for the hard tasks. The second condition is stronger and allows us to identify task systems that are safely and efficiently PAC learnable. Learning setting We consider a setting in which we are given the structure of a task system Υ = ((τ i ) i∈I , F, H) to schedule. While the structure is known, the actual distributions that describe the behaviour of the tasks are unknown and need to be learnt to behave optimally or near optimally. The learning must be done only by observing the jobs that arrive along time. When the task system contains some hard tasks (H = ∅), all deadlines of such tasks must be enforced.
For learning the inter-arrival time distribution of a task, a sample corresponds to observing the time difference between the arrivals of two consecutive jobs of that task. For learning the computation time distribution, a sample corresponds to observing the CPU time a job of the task has been assigned up to completion. Thus if a job does not finish execution before its deadline, we do not obtain a valid sample for the computation time. Given a class of task systems, we say: the class is probably approximately correct (PAC) learnable if there is an algorithm L such that for all task systems Υ in this class, for all ε, γ ∈ (0, 1): given struct(Υ ), the algorithm L can execute the task system Υ , and can compute Υ M such that Υ ≈ ε Υ M , with probability at least 1 − γ. the class is safely PAC learnable if it is PAC learnable, and L can ensure safety for the hard tasks while computing Υ M . the class is (safely) efficiently PAC learnable if it is (safely) PAC learnable, and there is a polynomial q in the size of the task system, in 1 /ε, and in 1 /γ, s.t. L obtains enough samples to compute Υ M in a time bounded by q.
Note that our notion of efficient PAC learning is stronger than the definition used in classical PAC learning terminology [24] since we take into account the time that is needed to get samples and not only the number of samples needed. Learning discrete finite distributions To learn an unknown discrete distribution p defined on a finite domain Dom(p), we collect i.i.d. samples from that distribution and infer a model of it. Formally, given a sequence S = (s j ) j∈J of samples drawn i.i.d. from the distribution p, we denote by p(S) : Dom(p) → [0, 1], the function that maps every element a ∈ Dom(p) to its relative frequency in S. The following lemma tells us that if the size of S is large enough then the model p(S) is close to the actual p with high probability.
Proof. For a distribution p, and an element e in Dom(p), let X pe 1 , . . . , X pe m be independent and identically distributed Bernoulli random variables with E X pe j = µ for j ∈ [m]. Recall that a Bernoulli random variable takes two values, 1 and 0.
In our case, the value 1 denotes witnessing the element e in the domain of the distribution p.
Here m is the number of samples required to learn the probability of occurrence of the element e of the support of the distribution. By Hoeffding's two sided inequality, for the special case of Bernoulli random variables, we have, Now we want that the probability of |X pe m − µ| ≥ ε for all e ∈ Dom(p) is at most γ r , so that the probability of |X pe m − µ| ≥ ε for some element e in the domain of the distribution p is at most γ.
Thus we have 2 exp(−2mε 2 ) ≤ γ r leading to m ≥ 1 2ε 2 (ln 2r − ln γ) . Since there are r elements in the domain, we need a total of at least f(r, ε, γ) = m · r samples, and hence the result.
We say that we "PAC learn" a distribution p if for all ε, γ ∈ (0, 1) such that π p min > ε, by drawing a sequence S of i.i.d. samples from p, we have p ∼ ε p(S) with probability at least 1 − γ. Given a task system Υ , if we can learn the distributions corresponding to all the tasks in Υ , and hence a model Υ M , such that each learnt distribution in Υ M is structurally identical to its corresponding distribution in Υ , the corresponding MDP are structurally identical. Efficient PAC learning Let Υ = ((τ i ) i∈I , F, ∅) be a task system with soft tasks only, and let ε, γ ∈ (0, 1). We assume that for all distributions p occurring in the models of the tasks in Υ : π p min > ε. To learn a model Υ M which is ε-close to Υ with probability at least 1 − γ, we apply Lemma 1 in the following algorithm: 1. for all tasks i = 1, 2, · · · ∈ F , repeat the following learning phase: Always schedule task τ i when a job of this task is active. Collect the samples S(A i ) of A i and S(C i ) of C i as observed. Collect enough samples to apply Lemma 1 and obtain the desired accuracy as fixed by ε and γ. 2. the models of inter-arrival time distribution and computation time distribution for task τ i are p(S(A i )) and p(S(C i )) respectively.
It follows that task systems with only soft tasks are efficiently PAC learnable: There is a learning algorithm such that for all task systems Υ = ((τ i ) i∈I , F, H) with H = ∅, for all ε, γ ∈ (0, 1), the algorithm learns a model Υ M such that Υ M ≈ ε Υ with probability at least 1 − γ after executing Υ for |F | · A max · D · 1 2ε 2 (ln 4D|F | − ln γ) steps.
Since samples for computation time distribution and inter-arrival time distribution for each soft task can be collected simultaneously, and observing each sample takes a maximum of A max time steps, and we collect samples for each soft task by scheduling one soft task after another, the result follows.
Safe learning with hard tasks We turn to task systems Υ = ((τ i ) i∈I , F, H) with both hard and soft tasks. The learning algorithm must ensure that all the jobs of hard tasks meet their deadlines while learning the task distributions. The soft-task-only algorithm is clearly not valid for that more general case. Recall we have assumed schedulability of the task system for the hard tasks 5 . This is a necessary condition for safe learning but it is not a sufficient condition. Indeed, to apply Lemma 1, we need enough samples for all tasks i ∈ H ∪ F .
First, we note that when executing any safe schedule for the hard tasks, we will observe enough samples for the hard tasks. Indeed, under a safe schedule for the hard tasks, any job of a hard task that enters the system will be executed to completion before its deadline. We then observe the value of the inter-arrival and computation times for all the jobs of hard tasks that enter the system. Unfortunately, this is not necessarily the case for soft tasks when they execute in the presence of hard tasks. Indeed, it is in general not possible to schedule all the jobs of soft tasks up to completion. We thus need stronger conditions in order to be able to learn the distributions of the soft tasks while ensuring safety. PAC guarantees for safe learning Our condition to ensure safe PAC learnability relies on properties of the safe region Γ safe Υ in the MDP Γ Υ associated to the task system Υ . First, note that Γ safe Υ is guaranteed to be non-empty as the task system Υ is guaranteed to be schedulable for its hard tasks by hypothesis. Our condition will exploit the following property of its structure: Lemma 2. Let Υ = ((τ i ) i∈I , F, H) be a task system and let Γ safe Υ be the safe region of its MDP. Then Γ safe Υ is a single maximal end-component (MEC).
Proof. We first assume that the task system Υ = ((τ i ) i∈I , F, H) is schedulable. Otherwise, Γ safe Υ is empty and the Lemma is trivially true. Let V and E be the set of vertices and the set of edges of Γ safe Υ respectively. First, observe that, since we want to prove that the whole MDP Γ safe Υ corresponds to an MEC, we only need to show that its underlying graph (V, E) is strongly connected. Indeed, since (V, E) contains all vertices and edges from Γ safe Υ , it is necessarily maximal, and all choices of actions from any vertex will always lead to a vertex in V .
In order to show the strongly connected property, we fix a vertex v ∈ V , and show that there exists a path in Γ safe Υ from v to v init . Since all vertices in V are, by construction of Γ safe Υ , reachable from the initial vertex v init , this entails that all vertices v are also reachable from v, hence, the graph is strongly connected.
Let us first assume that v ∈ V , i.e., v is a vertex where Scheduler has to take a decision.
to v, where all vertices v j belong to Scheduler, and all v j are are vertices that belong to TaskGen.
Then, from path π, we extract, for all tasks τ i the sequence of actual interarrival times σ i = t i (1), t i (2), . . . , t i (k i ) defined as follows: for all 1 ≤ j ≤ k i , t i (j) ∈ Supp(A i ) is the time elapsed (in CPU ticks) between the arrival of the j − 1th job the jth job of task i along π (assuming the initial release occurring in the initial state v init is the 0-th release). In other words, letting T i (j) = j k=1 t i (k), the jth job of τ i is released along π on the transition between v T i (j−1) and v T i (j) . Observe thus that all tasks i ∈ [n] are in the same state in vertex v init and in vertex v T i (j) , i.e. the time to the deadline, and the probability distributions on the next arrival and computation times are the same in v init and v T i (j) . However, the vertices v T i (j) can be different for all the different tasks, since they depend on the sequence of job releases of τ i along π. Nevertheless, we claim that π can be extended, by repeating the sequence of arrivals of all the tasks along π, in order to reach a vertex where all tasks have just submitted a job (i.e. v init ). To this aim, we first extend, for all tasks i ∈ For all i ∈ [n], let ∆ i denote ki+1 j=1 t i (j), i.e. ∆ i is the total number of CPU ticks needed to reach the first state after v where task i has just submitted a job (following the sequence of arrival σ i defined above). Further, let ∆ = lcm(∆ i ) i∈ [n] . Now, let π be a path in Γ safe Υ that respects the following properties: 1. π is a prefix of π ; 2. π has a length of ∆ CPU ticks; 3. π ends in a vertex v ; and 4. for all tasks i ∈ [n]: τ i submits a job at time t along π iff it submits a job at time t mod ∆ i along π.
Observe that, in the definition of π , we do not constrain the decisions of Scheduler after the prefix π. First, let us explain why such a path exists. Observe that the sequence of task arrival times is legal, since it consists, for all tasks i, in repeating ∆/∆ i times the sequence σ i of inter-arrival times which is legal since it is extracted from path π (remember that nothing that Scheduler player does can restrict the times at which TaskGen introduces new jobs in the system). Then, since Υ is schedulable, we have the guarantee that all vertices in Γ safe Υ have at least one outgoing edge. This is sufficient to ensure that π indeed exists. Finally, we observe π visits v (since π is a prefix of π ), and that the last vertex v of π is a vertex obtained just after all tasks have submitted a job, by construction. Thus v = v init , and we conclude that, from all v ∈ V which is reachable from v init , one can find a path in Γ safe Υ that leads back to v init . This reasoning can be extended to account for the nodes v ∈ V : one can simply select any successor v ∈ V of v, and apply the above reasoning from v to find a path going back to v init .
Good for sampling The safe region Γ safe Υ of the task system Υ = ((τ i ) i∈I , F, H) is good for sampling if for all soft tasks i ∈ F , there exists a vertex v i ∈ Γ safe Υ such that: (i) a new job of task i enters the system in v i ; and (ii) there exists a strategy σ i of Scheduler that is compatible with the set of safe schedules for the hard tasks so that from v i , under schedule σ i , the new job associated to task τ i is guaranteed to reach completion before its deadline.
There is an algorithm that executes in polynomial time in the size of Γ safe Υ and which decides if Γ safe Υ is good for sampling. Also, remember that only the knowledge of the structure of the task system is needed to compute Γ safe Υ . Given a task system Γ safe Υ that is good for sampling, given any ε, γ ∈ (0, 1), we safely learn a model Υ M which is ε-close to Υ with probability at least 1 − γ (PAC guarantees) by applying the following algorithm: 1. Choose any safe strategy σ H for the hard tasks, and apply it until enough samples (S(A i ), S(C i )) for each i ∈ H have been collected according to Lemma 1. The models for tasks i ∈ H are p(S(A i )) and p(S(C i )). 2. Then for each i ∈ F , apply the following phases: (a) from the current vertex v, schedule some task uniformly at random among the set of tasks that correspond to the safe edges in safe(v) up to reaching some v i (while choosing tasks that do not violate safety uniformly at random, we reach some v i with probability 1. 6 The existence of a v i is guaranteed by the hypothesis that Γ safe Υ is good for sampling). (b) from v i , apply the schedule σ i as defined by the second condition in the good for sampling condition. This way we are guaranteed to observe the computation time requested by the new job of task i that entered the system in vertex v i , no matter how TaskGen behaves. At the completion of this job of task i, we have collected a valid sample of task i. (c) go back to (a) until enough samples (S(A i ), S(C i )) have been collected for soft task i according to Lemma 1.
The properties of the learning algorithm above are used to prove that: There is a learning algorithm such that for all task systems Υ = ((τ i ) i∈I , F, H) with a safe region Γ safe Υ that is good for sampling, for all ε, γ ∈ (0, 1), the algorithm learns a model Υ M such that Υ M ≈ ε Υ with probability at least 1 − γ.
Proof. For the hard tasks, as mentioned above, we can learn the distributions by applying the safe strategy σ H to collect enough samples (S(A i ), S(C i )) for each i ∈ H.
We assume an order on the set of soft tasks. First for all τ i for i ∈ F , since Γ safe Υ is good for sampling, we note that the set V i of vertices v i (as defined in the definition of good for sampling condition) is non-empty. Recall from Lemma 2 that Γ safe Υ has a single MEC. Thus from every vertex of Γ safe Υ , Scheduler by playing uniformly at random reaches some v i ∈ V i with probability 1, and hence can visit the vertices of V i infinitely often with probability 1. Now given ε and γ, using Theorem 1, we can compute an m, the number of samples corresponding to each distribution required for safe PAC learning of the task system. Since by playing uniformly at random, Scheduler has a strategy to visit the vertices of V i infinitely often with probability 1, it is thus possible to visit these vertices at least m times with arbitrarily high probability.
Also after we safely PAC learn the distributions for task τ i , since there is a single MEC in Γ safe Υ , there exists a uniform memoryless strategy to visit a vertex v i+1 corresponding to task τ i+1 with probability 1. Hence the result.
In the algorithm above, to obtain one sample of a soft task, we need to reach a particular vertex v i from which we can safely schedule a new job for the task i up to completion. As the underlying MDP Γ safe Υ can be large (exponential in the description of the task system), we cannot bound by a polynomial the time needed to get the next sample in the learning algorithm. So, this algorithm does not guarantee efficient PAC learning. We develop in the next paragraph a stronger condition to guarantee efficient PAC learning. Good for efficient sampling The safe region Γ safe Υ of the task system Υ = ((τ i ) i∈I , F, H) is good for efficient sampling if there exists K ∈ N which is bounded polynomially in the size of Υ = ((τ i ) i∈I , F, H), and if, for all soft tasks i ∈ F the two following conditions hold: 1. let V safe be the set of Scheduler vertices in Γ safe Υ . There is a non-empty subset Safe i ⊆ V safe of vertices from which there is a strategy σ i for Scheduler to schedule safely the tasks H ∪ {i} (i.e. all hard tasks and the task i); and 2. for all v ∈ V safe , i ∈ F , there is a uniform memoryless strategy σ Safei s.t.: (a) σ Safei is compatible with the safe strategies (for the hard tasks) of Γ safe Υ ; (b) when σ Safei is executed from any v ∈ V safe , then the set Safe i is reached within K steps. By Lemma 2, since Γ safe Υ has a single MEC, we have that Safe i is reachable from every v ∈ V safe .
Here again, the condition can be efficiently decided: there is a polynomial-time algorithm in the size of Γ safe Υ that decides if Γ safe Υ is good for efficient sampling. Given a task system Γ safe Υ that is good for efficient sampling, given ε, γ ∈ (0, 1), we safely and efficiently learn a model Υ M which is ε-close of Υ with probability at least than 1 − γ (efficient PAC guarantees) by applying: 1. Choose any safe strategy σ H for the hard tasks, and apply this strategy until enough samples (S(A i ), S(C i )) for each i ∈ H have been collected according to Lemma 1. The models for tasks i ∈ H are p(S(A i )) and p(S(C i )). 2. Then for each i ∈ F , apply the following phase: (a) from the current vertex v, play σ Safei to reach the set Safe i . (b) from the current vertex in Safe i , apply the schedule σ i as defined above. This way we are guaranteed to observe the computation time requested by all the jobs of task i that enter the system. (c) go to (b) until enough samples (S(A i ), S(C i )) are collected for task i as per Lem. 1. The models for task i are given by p(S(A i )) and p(S(C i )). For a task system Υ , let T = A max · D · 1 2ε 2 (ln 4D|Υ | − ln γ) . The properties of the learning algorithm above are used to prove the following theorem: Theorem 3. There exists a learning algorithm such that for all task systems Υ = ((τ i ) i∈I , F, H) with a safe region Γ safe Υ that is good for efficient sampling, for all ε, γ ∈ (0, 1), the algorithm learns a model Υ M such that Υ M ≈ ε Υ with probability at least 1 − γ after scheduling Υ for T + |F | · (T + K) steps.
Proof. Consider the algorithm described above. Since σ H is a safe schedule for the hard tasks, we can observe the samples corresponding to the computation time distribution and the inter-arrival time distribution for all the hard tasks simultaneously while scheduling the system. Following the proof of Theorem 1, the samples required to learn the distributions of the hard tasks can be observed in time T . Now consider an order on the set of tasks. Under the good for efficient sampling condition, again from the proof of Theorem 1, we need to execute the system for |F |T time steps for collecting samples to PAC learn the computation time distributions and the inter-arrival time distributions for all soft tasks in F . Further, for every soft task τ i with i ∈ F , from a vertex in V safe , by using the strategy σ Safei , we reach Safe i in at most K steps. Hence the result.
We note that there indeed exist task systems that satisfy the good for sampling condition, but not the stronger good for efficient sampling condition.
Example 2. Consider the following task system with one hard and one soft task that we want to learn. More specifically, we want to learn the distributions associated to the tasks in the system. For the hard task, the computation time distribution is Dirac with support {2}, the relative deadline is 2, and the interarrival time distribution is also Dirac with support {4}. For the soft task, the computation time distribution has the support {1, 2}, the relative deadline is 2, and the inter-arrival time distribution is also Dirac and has the support {3}. We assume that the domain of each distribution is the same as its support.
We can see that during the execution of the task system, for every time t, Scheduler does not have a safe schedule from t that also ensures that the soft task will never miss a deadline. This implies that considering the good for efficient sampling condition, we have Safe i = ∅ for i ∈ F , and hence the good for efficient sampling condition is not satisfied by this task system. Thus we cannot ensure safe and efficient PAC learning for this task system.
On the other hand, there exists a schedule such that for all the jobs of the soft task that arrive at time lcm(4, 3) · n + 6 = 12n + 6 (assuming that the system starts executing at time 0) for n ≥ 0 can be scheduled to completion, and thus by Theorem 2, there exists an algorithm to safely PAC learn the task system. Using the learnt model Given a system Υ of tasks, and parameters ε, γ ∈ (0, 1), once we have learnt a model Υ M such that Υ M ≈ ε Υ , we construct the MDP Γ safe Υ M . From Γ safe Υ M , we can compute an optimal scheduling strategy that minimises the expected mean-cost of missing deadlines of soft tasks. Such an algorithm is given in [14]. Then, we execute the actual task system Υ under schedule σ. However, since σ has been computed using the model Υ M , it might not be optimal in the original, unknown taks system Υ . Nevertheless, we can bound the difference between the optimal values obtained in Γ safe Υ M and Γ safe Υ .
Proof. Since we have that Υ M ≈ ε Υ with probability at least 1−γ, by definition, we have that the probability that all the distributions of Υ M are ε-close to their corresponding distributions in Υ is at least 1−γ. Let |Υ | = n, and there are a total of 2n distributions. Let δ and δ M be the distribution assignment functions of Γ and Γ M respectively. Thus corresponding to δ in M, if an edge has probability p = p 1 p 2 · · · p 2n , and for δ M we have the corresponding probability as p M , then where p i is the estimation of p i in δ M , and is such that p i ≤ min{1, p i + ε}, since each estimated probability in the distribution δ M is also bounded above by 1. Now p i ≤ s for all i ∈ [2n], and we have that (MC). The following Lemma captures the idea that some expectation-optimal strategies for MDPs whose transition functions have the same support as that of Γ are 'robust'.
Lemma 4 (Adapted from [7,Theorem 5]). Consider β ∈ (0, 1), and MDPs Γ and Γ such that Γ ≈ η β Γ with η β ≤ β·πmin 8|V | , where π min is the minimum probability appearing in Γ . For all memoryless deterministic expectation-optimal strategies σ in Γ , for all v ∈ V , it holds that E Proof. Recall that in our case, we have that the cost of missing the deadlines of the soft tasks are known, and thus we have the same cost function cost in both Γ and Γ . The bounds for η β is obtained directly from Solan's inequality [22,Theorem 6] as adapted by Chatterjee [7, Proposition 1]: In the proof of [7, Theorem 5]), it has been shown that if the optimal expected values of two structurally identical MDPs differ by at most λ, then a memoryless expectation-optimal strategy for one MDP is 2λ-expectation-optimal for the other one. Thus The result thus follows.
One of the results we cite, i.e. [7,Theorem 5], focuses on stochastic parity games with the same support, i.e., for structurally identical MDPs. There, they derive robustness bounds for MDPs with the discounted-sum function and use them to obtain robustness bounds for MDPs with a parity objective. We are, however, extending those results to MDPs with the mean-cost function (cf. [9]) making use of an observation by Solan [22]: robustness bounds for discountedsum MDPs extend directly to mean-cost MDPs if they do not depend on the discount factor.
Finally, using both Lemma 3 and Lemma 4, we obtain the following guarantees on the quality of the scheduler that our model-based learning algorithm outputs: Theorem 4. Suppose we are given a task system Υ (with min probability π min ) and a robustness precision β ∈ (0, 1). Let γ, ε ∈ (0, 1) be s.t. ε ≤ βπmin 8|V |+βπmin . Let Υ M be the model that is learnt using the above algorithms s.t. Υ M ≈ ε Υ with probability at least 1 − γ, and let σ be a memoryless deterministic expectationoptimal strategy of Γ Υ M . Then, with probability at least 1 − γ, the expected mean-cost of playing σ in Γ Υ (i.e. in the task system Υ ) is s.t. for all v ∈ V :

Monte Carlo Tree Search with Advice
When the model of the task system is known, or once it has been learned using techniques developed in Section 3, our goal is to compute a (near) optimal strategy while ensuring safe scheduling of hard-tasks with certainty.
The challenge is the sizes of the MDPs that are too large for exact modelchecking techniques (see Sect. 5). To overcome this problem, we resort to a receding horizon framework [15], that bases its decisions on a finite-depth unfolding of the MDP from the current state. In particular, we advocate the use of Monte Carlo Tree Search (MCTS) algorithms [4], that are a popular method for sampling the finite-depth unfolding while avoiding an exponential dependency on the horizon. MCTS algorithms aim at discovering and exploring the "most relevant" parts of the unfolding, and they approximate the value of actions in intermediary nodes using a fixed number of trajectories obtained by simulations. The MCTS algorithm builds an exploration tree incrementally. At every step of the algorithm, the selection phase selects a path in the current tree, possibly extending it by adding a new node. It is followed by a simulation phase, that extends this trajectory further, until the fixed horizon is reached. Finally, a backpropagation phase updates the exploration tree based on this new trajectory. A reader looking for a more detailed introduction to MCTS is referred to [5].
MCTS has been successfully applied to large state-spaces. For example, it is an important building block of the AlphaGo algorithm [21] that has obtained super-human performances in the game of Go. Such level of performances cannot be obtained with the plain MCTS algorithm. In Go, the simulation and selection Value from Storm on actual task system: 0.0678526 Fig. 3. Model-based learning for 1 hard, 2 soft tasks phases are guided by a board scoring function that has been learned using neuralnetworks techniques and self-play. For our scheduling problem, we also need a solution to this guidance problem and, equally importantly, we must augment the MCTS algorithm in a way that ensures safe scheduling of hard tasks. Symbolic advice In a recent previous work [5], we have introduced the notion of (symbolic) advice that provides a generic and formal solution to systematically incorporate domain knowledge in the MCTS algorithm. For our scheduling problem, we use selection advice that prunes parts of the MDP on-the-fly in order to ensure that only safe schedulers are explored. We have considered two possibilities. First, we consider the most general safe scheduler (MGS scheduler) as defined in page 7 to restrict the selection phase to safe scheduling decisions only. Second, we consider the earliest deadline first (EDF) scheduling strategy for hard tasks defined in page 4, that only allows soft tasks when there are no available hard tasks, and restricts to the hard tasks with the earliest deadline otherwise. EDF is guaranteed safe as the set of hard tasks is assumed schedulable. The MGS advice allows for maximal exploration as it leaves open all possible safe scheduling solutions, while the EDF advice can be applied on larger task systems as it does not require any precomputations. These advice are also applicable during the simulation phases.

Experimental Results
In this section, we first report experimental results on model-based learning and observe that the models are learnt efficiently with only a small number of samples. Our MCTS based algorithms can then be applied on the learnt models that are very close to the original ones. 7 We compare the performance of our MCTS-based algorithms with a state-of-the-art deep Q-learning implementation from OpenAI [11] on a set of benchmarks of task systems of various sizes. The experimental results show that our MCTS-based algorithms perform better in practice than safe reinforcement learning (RL) [3].
Models with only soft tasks In Figure 2, we show that the distributions of a task system with soft tasks can be learnt efficiently with a small number of samples, corroborating our theory in Section 3. This is not the case in general for arbitrary MDPs where in order to collect samples, one may need to reach some specific states of the MDP, and it may take a considerable amount of time to reach such states. However, in this case of systems with only soft tasks, the number of samples increases linearly with time. As a representative task system, we display the learning curve for a system with six soft tasks in Figure 2. Here "exe" and "arr" refer to the distributions of the computation times and the inter-arrival times respectively. The left y-axis is the max-norm distance between the probabilities in the actual distributions and the learnt distributions across all soft tasks. The x-axis is the number of time steps over which the system is executed. For learning the computation time distribution, the soft tasks are scheduled in a round robin manner. Once a job of a soft task is scheduled, it is executed until completion without being preempted. A sample for learning the computation time distribution of a soft task thus corresponds to a job of the task that is scheduled to execute until completion. Since the system has only soft tasks, a job can always be executed to finish its execution without safety being violated. On the other hand, the samples for learning the inter-arrival time distribution for each task correspond to all the jobs of the task that arrive in the system. Thus over a time duration, for each task, the number of samples collected for learning the inter-arrival time distribution is larger than the number of samples collected for learning the computation time distribution. The number of samples of both kinds increases linearly with time. The y-axis on the right corresponds to the number of samples collected over a duration of time when the system executes. The plot "Exe samples" corresponds to the number of samples collected per task for learning the computation time distributions. Since the tasks are executed in a round robin manner, the tasks have an equal number of samples for learning their computation time distributions. On the other hand, for learning inter-arrival time distributions, a task with larger inter-arrival time produces fewer samples than a task with smaller inter-arrival time. The plot "Arr samples" corresponds to the minimum of the number of jobs, over all the tasks, that arrived in the system. Each point in the graphs is obtained as a result of averaging over 50 simulations.
Safe model-based learning For safe model-based learning of systems with both hard and soft tasks, first, we verify that the task system satisfies the good for efficient sampling condition, and hence admits safe efficient PAC learning. We consider a small representative task system, and report the value of the optimal expected mean-cost strategy as computed by Storm on the learnt model as a function of the number of steps for which the system is executed (training steps). This converges quickly to the optimal expected value of the actual task system, roughly equal to 0.06 (see Fig 3). We also note that the expected value computed by Storm is not necessarily monotonic as it is computed on the learnt model and this model changes over time with the samples that it receives, and the expected value may also sometimes be smaller than the value on the actual model. The results show that this approach is effective in terms of the quality of learning and the number of samples required. MCTS In the above approach, the main bottleneck towards scalability is the extraction of an optimal strategy from the learnt model using probabilistic modelcheckers like Storm. This is because the underlying MDP grows exponentially with the number of tasks. Therefore we advocate the use of receding horizon techniques instead, that optimize the cost based on the next h steps for some horizon h. In our examples, the unfoldings have approximately 2 h states, so we use MCTS to explore them in a scalable way. Deep Q-learning One of the most successful model-free learning algorithm is the Q-learning algorithm, due to Watkins and Dayan [25]. It aims at learning (near) optimal strategies in a (partially unknown) MDP for the discounted sum objective. In our scheduling problem, we search for (near) optimal strategies for the mean-cost and not for the discounted sum, as we want to minimise the limit average of the cost of missing deadlines of soft tasks. However, if the discount factor is close to 1, both values coincide [22,18]. In our experiments, we use an implementation of deep Q-learning available in the OpenAI repository [11]. We make use of shielding [8,1,3], a technique that restricts actions in the learning process so that only those actions that are safe for the hard tasks can be used. Experimental setup for MCTS and deep Q-learning We compare some variants of model-based learning augmented with MCTS and some variants of deep Q-learning in the context of scheduling. The first option is to set a very high penalty on missing the deadline of a hard task, and then to apply either MCTS or deep Q-learning. However, safety is not guaranteed in this case, and we report on whether a violation was observed or not. We call this variant unsafe MCTS and unsafe deep Q-learning respectively as a consequence. The second option is to enforce safety in MCTS and deep Q-learning by computing the most general safe scheduler for hard tasks, and then using the MGS advice for MCTS or the MGS shield for deep Q-learning. The third option is to use the earliestdeadline-first (EDF) scheme on hard tasks instead of MGS as an advice or a shield. Note that the second and the third options are required to ensure safety, and thus are applicable to systems that have at least one hard task, and hence are not applicable (NA) to systems with only soft tasks. Experimental Results In the first column of Table 1, we describe the task systems that we consider. A description 2H, 5S refers to a task system with two hard tasks and five soft tasks, while 4S refers to a task system with four soft tasks and no hard tasks. The simple system refers to a 1H, 2S task system where all the arrival time distributions are Dirac. The output of Storm for the smaller task systems is given in the third column. We report sizes of the MDPs, computed with Storm whenever possible. Otherwise we report an approximation of the size of the state space obtained by taking the product of (c i + 1)(a i + 1) over the set of tasks, where c i and a i are the greatest elements in the support of the distributions C i and A i . Recall that the size of the state space is exponential in the number of tasks in the system. In the columns where safety is not guaranteed, ∞ denotes an observed violation (a missed deadline for a hard task). For MCTS, at every step we explore 500 nodes of the unfolding of horizon 30, and the value of each node is initialized using 100 uniform simulations. This computation takes 1-4 minutes in our Python implementation for different benchmarks, running on a standard laptop. It is reasonable to believe that a substantial speedup could be obtained with well-optimised code and parallelism. For deep Q-learning, we train each task system for 10000 steps. The implementation of deep-Q learning in the OepnAI respository uses the Adam optimizer [16]. The size of the replay buffer is set to 2000. The learning rate used is 10 −3 . The probability ε of taking a random action is initially set to 1. This parameter reduces over the training steps, and becomes equal to 0.02 at the end of the training. The network used is a multi-layer perceptron which, by default, uses two fully connected hidden layers, each with 64 nodes. Since we are interested in mean-cost objective, the discount factor γ is set to 1. We observed that reducing the value of γ leads to poorer results. The values reported for both MCTS and deep Q-learning are obtained as an average cost over 600 steps. Conclusions While deep Q-learning provides good results for small task systems with 3-4 tasks with several thousands of states, this method does not perform well for the benchmarks with large number of tasks. We trained the task system with 10 soft tasks with deep Q-learning for several million steps, but the state space was found to be too large to learn a good strategy, and the resulting output produced a cost that is much higher than that observed with MCTS.
Overall, our experimental results show that MCTS consistently provides better results, in particular when the task systems are large, with huge state spaces. This can be explained by the fact that MCTS optimizes locally using information about multiple possible "futures" while deep Q-learning rather optimizes globally using information about the uniquely observed trace. We observe that the performance of MCTS with EDF advice is only slightly worse than MCTS with MGS advice. EDF guarantees safety and does not require computing the most general safe strategy, therefore it forms a good heuristic for systems with many hard tasks, where MGS computation becomes too expensive.
In future work, we consider using Deep-Q learning in either a selection advice for MCTS or as a complement to simulations when evaluating new states.