Paper deep dive
Outcome-Fair Restless Multi-Armed Bandits for Stochastic Deadline Scheduling
Shakti Sharma, Rahul Meshram
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study a restless multi-armed bandit (RMAB) problem for a stochastic deadline scheduling application. RMAB problems are solved using the Whittle index policy. The goal in RMAB is to maximize the expected cumulative discounted reward maximization. The Whittle index policy maximizes reward, but is not fair among two classes. In this paper, we introduce fairness criteria and study an outcome-fair model for RMAB which allows fairness for jobs and users structurally disadvantaged demographic classes. We formulate an outcome fair stochastic deadline scheduling problem as RMAB, and we develop the outcome fair Whittle index policy. We define a virtual queue mechanism that dynamically enforces long-term completion rate guaranties across demographic groups. We analyze a standard Whittle index policy and the outcome-fair index policy. We demonstrate the performance of our algorithms with numerical examples. We compare policies---Whittle index policy (no fairness), input-fairness Whittle index policy, outcome fair Whittle index policy. We observe that the outcome-fair Whittle index policy provides better fairness among classes compared to other policies. We demonstrate a trade off between fairness and profit. This decreases as the server capacity increases.
Tags
Links
- Source: https://arxiv.org/abs/2607.23772v1
- Canonical: https://arxiv.org/abs/2607.23772v1
Trouble viewing inline? Open PDF directly →
Full Text
44,636 characters extracted from source content.
Expand or collapse full text
Outcome-Fair Restless Multi-Armed Bandits for Stochastic Deadline Scheduling Shakti Sharma Rahul Meshram Dept. of Physics, Dept. of Electrical Engineering, IIT Madras, Chennai, India. IIT Madras, Chennai, India. Abstract We study a restless multi-armed bandit (RMAB) problem for a stochastic deadline scheduling application. RMAB problems are solved using the Whittle index policy. The goal in RMAB is to maximize the expected cumulative discounted reward maximization. The Whittle index policy maximizes reward, but is not fair among two classes. In this paper, we introduce fairness criteria and study an outcome-fair model for RMAB which allows fairness for jobs and users structurally disadvantaged demographic classes. We formulate an outcome fair stochastic deadline scheduling problem as RMAB, and we develop the outcome fair Whittle index policy. We define a virtual queue mechanism that dynamically enforces long-term completion rate guaranties across demographic groups. We analyze a standard Whittle index policy and the outcome-fair index policy. We demonstrate the performance of our algorithms with numerical examples. We compare policies—Whittle index policy (no fairness), input-fairness Whittle index policy, outcome fair Whittle index policy. We observe that the outcome-fair Whittle index policy provides better fairness among classes compared to other policies. We demonstrate a trade off between fairness and profit. This decreases as the server capacity increases. I Introduction Restless Multi-Armed Bandit (RMAB) problem is a classical framework in sequential decision-making and planning. At each discrete time step, a decision-maker (the ‘agent’) must choose one of the N available actions (the ‘arms’) to activate. Each arm, when pulled, yields a reward based on state. The state of all arms evolve at each time step and this evolution is dependent on action like activation or non-activation (passive). The goal in RMAB is the selection of arms subject to budget constraint in each time step to maximize the long term reward function when the state of each arm is evolving according to Markov process. RMAB problems are known to be PSPACE-hard. A heuristic index based policy that assigns a scalar priority score (the index) to each arm at each time step, then activates the M arms with the highest indices. The Whittle index is a popular policy for RMAB problems [1] and it shown to be near optimal for many resource allocation problems [2]. We consider stochastic deadline scheduling problem and it has applications to many class of real-world systems, an example electric vehicle (EV) charging station where EVs arrive randomly, each vehicle with a stochastic charging demand (workload) and a hard departure deadline. The station operates M charging ports subject to real-time electricity pricing. When a vehicle departs with an incompletely charged battery, the operator incurs a penalty proportional to the unmet demand. The operator’s objective is to maximise total long term infinite horizon discounted profit, combining service revenue, electricity costs, and non-completion penalties. Other applications of this model include cloud computing (finite-sized jobs with deadlines), patient scheduling and public healthcare intervention, packet scheduling in real-time wireless networks, and data centre workload management. In this paper, we introduce deadline scheduling problem with fairness constraints. We propose outcome-fair Whittle index policy. This has advantage in many applications where fairness is essential social welfare criteria. Without fairness, a scheduler (decision maker) repeatedly serves the highest-value jobs using Whittle index policy. For example, jobs with long deadlines may never be processed, low-priority users may receive almost no service and some queues may remain permanently backlogged. In a capacity-constrained system, the scheduler will preferentially activate high-index arms, but these may systematically belong to one demographic group, starving the other. Fairness constraints ensure that every job or user eventually receives attention. I-A Related Work Restless bandit problem is first introduced by Whittle in [1] and studied the Whittle index policy. RMAB studied for applications in scheduling problems in wireless networks, 5G networks [3], age of information [4] and online caching problem, [5]. In [6], authors modeled stochastic deadline scheduling as an RMAB, proved indexability, and derived a closed-form Whittle index for the constant-cost case. In [7], authors demonstrated the Whittle index policy for real-time multicast scheduling in wireless broadcast systems and studied as RMAB, and derived closed form expression for index. Recently, RMAB framework is applied for minimizing age of information (AoI) problem, [8]. Fairness in RMAB problems is another direction of work,[9, 10, 11, 12] there are no hard deadlines assumed, instead additional fairness constraints introduced and modified version of index policies are developed. In [13], authors examined fair scheduling with deadline guaranties in single-hop networks but did not employ the RMAB framework. In wireless networks, a packet scheduling problem with hard deadlines has been studied in a work of [14], where authors characterized the feasibility region for timely throughput in single-hop networks and proved the optimality of debt-based policies (Largest debt first policy). Later, this model is extended for heterogeneous real-time traffic over fading wireless channels in [15]. The problem of jointly enforcing demographic fairness and hard deadline constraints within an RMAB framework has not been addressed in previous work. In [16] studied multicast deadline scheduling in wireless networks and discussed per-class delivery trade-offs, but did not model demographic groups or enforce long-turn completion-rate targets. A work of [17] highlighted the need for a fairness-aware management of EV charging infrastructure as a key challenge in future electric energy systems. I-B Our Contributions We study stochastic deadline scheduling problem and this is a class of RMAB problem where queue position is represented as an arm, each queue position is independent of others. The state of each queue position is described using remaining load and time to deadline. The state of each arm evolves independent of other positions, and it changes at each time step. There is capacity constraints. Thus it is RMAB. We study Whittle index policy. For a simplified model Whittle index formula can be derived. In this policy, the arms with highest indices are scheduled, but these may belong to one class, other class may be starving because arms in these classes are not scheduled. We demonstrated this using a simple example. Our model is extension of [6] with fairness constraints. We introduce outcome fairness constraints with stochastic deadline scheduling problem. This outcome fairness constraint measures the rate of completion from different classes and maintains the fairness while scheduling. We combine both Whittle index policy and fairness in the index and we propose outcome fairness base Whittle index algorithm. Next we provide computational complexity of this algorithm where we have introduced fairness deficit virtual queue. Finally, we provide numerical examples and compare policies—standard Whittle index, input fair index policy and outcome fair index policy, round robin policy. We observe that outcome fair policy have better fairness compare to other schemes. Our paper is organized as follows. In Section I, we present system model and preliminary studied on Whittle index policy. We introduce fairness model in Section I and present outcome fair Whittle index policy algorithm and its properties in Section IV. Simulation examples are discussed in Section V and concluding remarks in Section VI. I System Model We consider a discrete-time stochastic scheduling system with M homogeneous servers and a queue consisting of N job positions, where N>MN>M. Time is slotted and indexed by t∈0,1,2,….t∈\0,1,2,…\. The system is modeled as a Markov Decision Process (MDP). At the beginning of each time slot, the scheduler observes the complete system state and allocates at most M servers to the waiting jobs. Each queue position i∈1,…,Ni∈\1,…,N\ is modeled as an independent restless multi-armed bandit (RMAB) arm. The state of arm i at time t is given by Si[t]=(Bi[t],Ti[t],ki),S_i[t]= (B_i[t],\,T_i[t],\,k_i ), (1) which consists of the following components: • Bi[t]∈ℤ+B_i[t] _+ denotes the remaining workload of job i, such as the remaining charging time of an EV or the remaining computational workload of a task. Whenever a server is assigned to arm i, the workload decreases by one unit during that time slot. • Ti[t]∈ℤ+T_i[t] _+ denotes the remaining time until the job’s hard deadline. This quantity decreases by one at every time slot irrespective of the scheduling decision, and the job expires when Ti[t]=0T_i[t]=0. • ki∈k_i denotes the demographic or application class associated with job i, where K is a finite set of user groups (e.g., =A,BK=\A,B\). Different classes may exhibit heterogeneous workload characteristics, deadline distributions, or fairness requirements. Thus, the state of each arm is characterized by three attributes: the remaining workload, the remaining time until deadline, and the associated user class. In addition to the arm states, the scheduler observes a global exogenous process c[t]∈c[t] representing the processing cost at time t. This cost may capture, for example, the real-time electricity price in an EV charging system or the operating cost of computational resources in a data center, and evolves according to an underlying stochastic process. A useful state variable is the laxity of job i at time t, defined as Li[t]=Ti[t]−Bi[t].L_i[t]=T_i[t]-B_i[t]. Laxity quantifies the scheduling flexibility of a job. A job with Li[t]=0L_i[t]=0 must receive service in every remaining time slot to meet its deadline, whereas larger values of Li[t]L_i[t] indicate greater scheduling flexibility. A job is feasible if and only if Li[t]≥0L_i[t]≥ 0; when Li[t]<0L_i[t]<0 (equivalently, Bi[t]>Ti[t]B_i[t]>T_i[t]), it is impossible to complete the job before its deadline under any scheduling policy. I-A Action Space and Capacity Constraint At each time slot t, the scheduler selects a binary action ai[t]∈0,1a_i[t]∈\0,1\ for each arm i, where ai[t]=1a_i[t]=1 indicates that a server is assigned to job i (active), and ai[t]=0a_i[t]=0 indicates that the job is not served (passive). Since only M servers are available, the scheduling decisions satisfy ∑i=1Nai[t]≤M, _i=1^Na_i[t]≤ M, ∀t.∀ t. To cast the problem into the standard RMAB framework, which requires exactly M active arms at every time slot, we augment the system with M dummy arms. Each dummy arm has a fixed state (0,0)(0,0), yields zero reward, incurs no cost, and remains unaffected by the chosen action. Consequently, the augmented system consists of N+MN+M arms, of which exactly M are activated at every time slot. The original jobs correspond to arms 1,…,N\1,…,N\, while the dummy arms are indexed by N+1,…,N+M\N+1,…,N+M\. I-B State Transition Dynamics Given the scheduling action ai[t]a_i[t], the workload evolves according to Bi[t+1]=max0,Bi[t]−ai[t],B_i[t+1]= \0,\,B_i[t]-a_i[t]\, while the remaining time to deadline decreases deterministically as Ti[t+1]=max0,Ti[t]−1.T_i[t+1]= \0,\,T_i[t]-1\. A job departs the system when either it is completed or its deadline expires. Specifically, if Bi[t+1]=0B_i[t+1]=0, the job is successfully completed and leaves the system without penalty. If Ti[t+1]=0T_i[t+1]=0 and Bi[t+1]>0B_i[t+1]>0, the job departs unfinished and incurs a penalty F(Bi[t+1]),F\! (B_i[t+1] ), where F:ℤ+→ℝ+F:Z_+ _+ is an increasing convex function satisfying F(0)=0F(0)=0. The convexity of F assigns a larger penalty to jobs with greater unfinished workload. Whenever a job departs, the corresponding queue position is immediately refreshed according to the arrival distribution Q. A new job with workload B and deadline T arrives with probability Q(T,B)Q(T,B), while the position remains empty with probability Q(0,0)Q(0,0). I-C Reward Structure and Objective The processing cost is determined by a global stochastic environment state c[t]∈c[t] , which evolves according to a finite-state Markov chain. In contrast, the local state of each arm evolves deterministically given the scheduling action, while job arrivals into vacant queue positions follow the stochastic arrival distribution described earlier. Thus, the overall system dynamics consist of deterministic arm evolution coupled with a stochastic global environment and stochastic job arrivals. Whenever a server is allocated to job i (i.e., ai[t]=1a_i[t]=1), the scheduler earns one unit of service reward while incurring a processing cost c[t]c[t], resulting in a net reward of 1−c[t]1-c[t]. Thus, if Bi[t]>0B_i[t]>0 and Ti[t]>1T_i[t]>1, the one-step reward is (1−c[t])ai[t](1-c[t])a_i[t], and zero otherwise. If the job reaches its final time slot before the deadline, i.e., Ti[t]=1T_i[t]=1, an additional penalty F(Bi[t]−ai[t])F(B_i[t]-a_i[t]) is imposed whenever unfinished workload remains after the scheduling decision. Here, F:ℤ+→ℝ+F:Z_+ _+ is an increasing convex function satisfying F(0)=0F(0)=0, so that larger residual workloads incur a higher penalty. Let S~i[t]=(Si[t],c[t]) S_i[t]=(S_i[t],c[t]) denote the extended state of arm i, and let Rai[t](S~i[t])R_a_i[t]( S_i[t]) denote the corresponding one-step reward. Let S~i[t]=(Si[t],c[t]) S_i[t]=(S_i[t],c[t]) denote the extended state of arm i. The one-step reward is given by Rai[t](S~i[t])=(1−c[t])ai[t]R_a_i[t]( S_i[t])=(1-c[t])\,a_i[t] if Bi[t]>0,Ti[t]>1,B_i[t]>0,\;T_i[t]>1, Rai[t](S~i[t])=(1−c[t])ai[t]−F(Bi[t]−ai[t]),R_a_i[t]( S_i[t])=(1-c[t])\,a_i[t]-F(B_i[t]-a_i[t]), if Bi[t]>0,Ti[t]=1,B_i[t]>0,\;T_i[t]=1, and Rai[t](S~i[t])==0R_a_i[t]( S_i[t])==0 otherwise. The objective is to determine a scheduling policy π that maximizes the expected discounted cumulative reward: VN(s)=supπ:∑i=1Nai[t]≤M,∀tπ[∑t=0∞βt∑i=1NRai[t](S~i[t]) V^N(s)= _π:\, _i=1^Na_i[t]≤ M,\;∀ tE_π [ _t=0^∞β^t _i=1^NR_a_i[t]( S_i[t]) |S[0]=s]. |\,S[0]=s ]. (2) where β∈(0,1)β∈(0,1) is the discount factor. We study deterministic stationary policies. I-D Whittle Index Policy Whittle’s key idea is to relax the instantaneous resource constraint ∑i=1Nai[t]≤M, _i=1^Na_i[t]≤ M, for all t by replacing it with a discounted activation constraint and then a Lagrangian relaxation. Introducing a Lagrange multiplier (or subsidy) ν≥0ν≥ 0 for the passive action decouples the original N-arm optimization problem into N independent single-arm Markov decision processes. The parameter ν can be interpreted as a subsidy received whenever an arm is left passive. For a fixed subsidy ν, the value function of arm i is Viν(s)=supπ[∑t=0∞βtRai[t]ν(S~i[t])|S~i[0]=s],V_i^ν(s)= _πE_π [ _t=0^∞β^tR_a_i[t]^ν( S_i[t])\, |\, S_i[0]=s ], (3) where the subsidized one-step reward is Rai[t]ν(S~i[t])=Rai[t](S~i[t])+ν 1ai[t]=0.R_a_i[t]^ν( S_i[t])=R_a_i[t]( S_i[t])+ν\,1\a_i[t]=0\. (4) The subsidy increases the attractiveness of the passive action. Consequently, as ν increases, the set of states in which passivity is optimal expands monotonically. This monotonicity is defines the Whittle indexability. The optimal value function are as follows. Viν(s)=maxQiν(s,0),Qiν(s,1),V_i^ν(s)= \Q_i^ν(s,0),\;Q_i^ν(s,1) \, (5) where Qiν(s,0) Q_i^ν(s,0) =R0(s)+ν+β∑s′P(s′|s,0)Viν(s′), =R_0(s)+ν+β _s P(s |s,0)V_i^ν(s ), (6) Qiν(s,1) Q_i^ν(s,1) =R1(s)+β∑s′P(s′|s,1)Viν(s′). =R_1(s)+β _s P(s |s,1)V_i^ν(s ). (7) The optimal action in state s is therefore a∗(s)=argmaxa∈0,1Qiν(s,a).a^*(s)= _a∈\0,1\Q_i^ν(s,a). Lemma 1 Qiν(s,0),Q_i^ν(s,0), Qiν(s,0),Q_i^ν(s,0), and Viν(s)V_i^ν(s) are non-decreasing piecewise linear and convex in ν for fixed s and each i.i. The Proof of this lemma is using the mathematical induction technique. We skip the details of the proof due to space constraint. The similar technique is used in [18, Proof of Lemma 1,1, Appendix A]. Remark 1 Note that Rai[t](S~i[t])R_a_i[t]( S_i[t]) is non-decreasing in ai[t]a_i[t] and it is independent of state if Bi[t]>0B_i[t]>0 and Ti[t]>1.T_i[t]>1. Reward Rai[t](S~i[t])R_a_i[t]( S_i[t]) is dependent on state only through penalty for not meeting deadline, i.e.,Bi[t]>0B_i[t]>0 and Ti[t]=1.T_i[t]=1. Moreover, jobs arrival is dependent current state Si[t].S_i[t]. Then we have the following lemma. Lemma 2 For fixed λ,λ, the optimal policy for each arm i,i, πiν(s) _i^ν(s) is non-decreasing in s.s. That is, the optimal policy is a single threshold type in state s.s. Proof of lemma is skipped due space constraint, The proof is analogous to proof of Theorem 11 in [18, Appendix B]. I-E Indexability and the Whittle Index Definition 1 (Indexability) Let Pi(ν)=s∈Si:a=0 is optimal under subsidy νP_i(ν)=\s∈ S_i:a=0 is optimal under subsidy ν\ denote the passive set of arm i. Arm i is indexable if Pi(ν)P_i(ν) expands monotonically from ∅ to the entire state space SiS_i as ν increases from −∞-∞ to +∞+∞. An RMAB is said to be indexable if every arm is indexable. Lemma 3 Each arm is indexable. Further, RMAB is indexable. We sketch idea of the proof. Let Δiν(s)=Qiν(s,0)−Qiν(s,1). _i^ν(s)=Q_i^ν(s,0)-Q_i^ν(s,1). For indexability, we need to show that Δiν(s) _i^ν(s) is monotone non-decreasing in ν for each s.s. This implies that there is there exists a threshold type policy in ν∗(s)ν^*(s) such that the optimal action 0 for ν≥ν∗(s)ν≥ν^*(s) and the optimal action 1.1. for ν<ν∗(s).ν<ν^*(s). Define g(ν)=Viν(s′)−Viν(s)g(ν)=V_i^ν(s )-V_i^ν(s) where s=(B,T)s=(B,T) and s′=(B+1,T),s =(B+1,T), observe that g(ν)g(ν) is difference of value functions, it is continuous and piecewise linear. Then there exists ν¯ ν and ν¯ ν such that ∂g(ν)∂ν≥−1 ∂ g(ν)∂ν≥-1 for ν∈[ν¯,ν¯]ν∈[ ν, ν] and ∂g(ν)∂ν=0 ∂ g(ν)∂ν=0 outside this region. Using this, indexability is proved in [6, Theorem 11, Appendix A]. Definition 2 (Whittle Index) For an indexable arm i, the Whittle index at state s is the smallest subsidy that makes the active and passive actions equally desirable: νi(s)=infν:Qiν(s,0)≥Qiν(s,1), _i(s)= \ν:Q_i^ν(s,0)≥ Q_i^ν(s,1) \, For the Whittle index formula, we solve the following equation for ν:ν: Qiν(s,0)−Qiν(s,1)=0,Q_i^ν(s,0)-Q_i^ν(s,1)=0, and index formula is derived. Since the immediate reward structure is simple for our problem, we can explicitly compute the index formula. However,if reward structure is complex, then the closed form expression may not be possible. We need to compute the index numerical using value iteration algorithm. The analysis of algorithm of numerical computation of index follows from two-timescale stochastic approximation algorithm. Numerical computation method of index is given in [19, 20]. With complex transition dynamics and reward structure, it is difficult to show indexability, in that we can employ heuristic policy like online rollout policy, [21]. In [6], the indexability is proved and the Whittle index formula for constant processing cost, i.e., c[t]=c0c[t]=c_0 is obtained. It is as follows: νi(B,T)=0 _i(B,T)=0 if B=0.B=0. νi(B,T)=1−c0 _i(B,T)=1-c_0 if 1≤B≤T−1.1≤ B≤ T-1. νi(B,T)=1−c0+βT−1[F(B−T+1)−F(B−T)] _i(B,T)=1-c_0+β^T-1 [F(B-T+1)-F(B-T) ] if T≤B.T≤ B. The Whittle index of each dummy arm is νi(0,0,c0)=0 _i(0,0,c_0)=0. When B=0B=0, the job has already been completed and therefore has zero priority. If 1≤B≤T−11≤ B≤ T-1, the job is feasible and can be completed before its deadline, so its index equals the net processing reward 1−c01-c_0. Definition 3 (Whittle Index Policy) At each decision epoch, compute the Whittle index νi(S~i[t]) _i( S_i[t]) for every arm i=1,…,Ni=1,…,N, and activate the M arms with the largest indices. Ties, if any, they are broken uniformly at random. The Whittle index policy is computationally efficient, requiring (NlogN)O(N N) operations to compute the indices. I Fairness in RMAB: The Demographic Fairness In Figure 1, we illustrates the demographic bias induced by the standard Whittle index policy. We consider two demographic classes with heterogeneous job characteristics in a queue of size N=50N=50. Jobs from the advantaged class (Class A) are generated with workload B∼U(2,6)B U(2,6) and deadline T∼U(3,15)T U(3,15), resulting in relatively high-laxity jobs. In contrast, jobs from the disadvantaged class (Class B) are generated with workload B∼U(7,12)B U(7,12) and deadline T∼U(1,5)T U(1,5), yielding predominantly low-laxity jobs. This example highlights how heterogeneity in job characteristics can lead to systematic differences in scheduling priority under the standard Whittle index policy. Hence unequal service allocation across the two demographic groups. As number of server increases, this bias reduces. Figure 1: Exp 1: Standard Whittle Inherent Bias. Assuming the probability of arrival of class A user as 70 percent and class B user as 30 percent, we varied the capacity from 20-40 for N=50. This motivates fairness models which can ensure fairness to different groups. We study two fairness models. I-A Input Fairness and Outcome Fairness models Input Fairness Input fairness requires that each demographic class receives a minimum long-run fraction of the available service opportunities. Let ℐk=i:ki=k.I_k=\i:k_i=k\. denote the set of jobs belonging to class k. The input fairness constraint is lim infT→∞1T[∑t=0T−1∑i∈ℐkai[t]]≥ηk,∀k∈, _T→∞ 1TE [ _t=0^T-1 _i _ka_i[t] ]≥ _k, ∀ k , (8) where ηk _k is the minimum service allocation rate for class k. This notion guarantees that each class receives a prescribed share of server capacity. However, it does not ensure that the allocated service is sufficient to complete jobs before their deadlines. Consequently, a class may satisfy (8) while still experiencing a high deadline miss rate. Outcome Fairness It requires that each demographic class achieves a prescribed minimum long-run completion rate, thereby accounting for differences in workloads, deadlines, and scheduling decisions. Consequently, outcome fairness provides a stronger notion of equity in deadline-constrained systems. Motivated by these considerations, we adopt outcome fairness as the fairness criterion throughout this paper. Definition 4 (Outcome Fairness) Let Ak[t]A_k[t] and Ck[t]C_k[t] denote the cumulative numbers of arriving and successfully completed jobs, respectively, for demographic class k up to time t. For a prescribed target completion rate ηk∈[0,1] _k∈[0,1], the scheduling policy satisfies outcome fairness if lim infT→∞Ck[T]Ak[T]≥ηk,∀k∈, _T→∞ C_k[T]A_k[T]≥ _k, ∀ k , (9) provided Ak[T]>0A_k[T]>0. Constraint (9) guarantees that, in the long run, at least an ηk _k fraction of jobs from demographic class k are completed before their deadlines. The parameters ηkk∈\ _k\_k are specified by the system designer and may differ across demographic groups to account for heterogeneous workloads or to mitigate structural disadvantages. IV The Outcome-Fair Whittle Index Policy To enforce the long-run outcome fairness constraint in Eqn. (9), we adopt the Lyapunov virtual queue framework, following the delivery debt approach of [22] for deadline-constrained wireless scheduling. The idea is to associate a virtual queue with each demographic class, whose backlog represents the accumulated fairness deficit. Classes that fall below their target completion rates accumulate larger virtual queues and are consequently assigned higher scheduling priority. Definition 5 (Fairness Deficit Virtual Queue) For each demographic class k∈k , let λk[t]≥0 _k[t]≥ 0 denote the fairness deficit virtual queue, initialized as λk[0]=0 _k[0]=0. The queue evolves according to λk[t+1]=[λk[t]+α(ηkAk[t]−Ck[t])]+, _k[t+1]= [ _k[t]+α ( _kA_k[t]-C_k[t] ) ]^+, (10) where [x]+=maxx,0[x]^+= \x,0\, α>0α>0 is a step-size parameter, Ak[t]A_k[t] and Ck[t]C_k[t] denote the numbers of arrivals and successful completions, respectively, for class k during time slot t, and ηk _k is the target completion rate. The virtual queue λk[t] _k[t] measures the cumulative fairness deficit of demographic class k. Whenever the observed completion rate falls below the prescribed target, i.e., Ck[t]<ηkAk[t]C_k[t]< _kA_k[t], the queue increases, thereby assigning higher priority to jobs from class k in future scheduling decisions. Conversely, when the target is exceeded, the queue decreases, reducing the additional priority assigned to that class. Feasibility Indicator: The feasibility of job i at time t is defined by δi[t]=Bi[t]≤Ti[t], _i[t]=1_\B_i[t]≤ T_i[t]\, where δi[t]=1 _i[t]=1 indicates that the job can still be completed before its deadline, while δi[t]=0 _i[t]=0 indicates that completion is impossible under any future scheduling policy. Definition 6 (Outcome-Fair Whittle Index) The Outcome-Fair Whittle Index of arm i at time t is defined as νifair[t]=νi(Bi[t],Ti[t],c[t])+λki[t]δi[t], _i^fair[t]= _i(B_i[t],T_i[t],c[t])+ _k_i[t] _i[t], (11) where νi(⋅) _i(·) is the baseline Whittle index, λki[t] _k_i[t] is the virtual queue associated with the demographic class of job i, and δi[t] _i[t] is the feasibility indicator. The first term represents the economic priority of the job under the standard Whittle policy, while the second term provides an adaptive fairness incentive. Consequently, jobs belonging to demographic classes with larger accumulated fairness deficits receive higher scheduling priority, but only if they remain feasible. At each time slot, the scheduler computes the outcome-Fair Whittle index for every active job, activates the M jobs with the largest indices, and updates the fairness virtual queues using the observed arrivals and completions. The sufficient conditions on fairness-deficit virtual queue in Eqn (10) for feasibility optimality is analyzed using the Lyapunov drift criteria, see [15, Theorem 22]. Outcome fair Whittle index policy schedules M arms with highest indices νifair,\ _i^fair\, and this ensures that each class is scheduled and fairness criteria with completion rate is maintained. If it is not maintained for arm i in class k, then λki[t] _k_i[t] increases for arm i,i, it increases fair index for arm i and it is scheduled to the server. The fair index policy balances the tradeoff between total expected reward and fairness. The computational complexity of outcome fair Whittle index policy at each decision epoch is O(NlogN).O(N N). V Simulation Results We present numerical experiments comparing three scheduling policies: the standard Whittle index policy, the Input-Fair Whittle index policy, and Outcome-Fair Whittle index policy. The standard Whittle index policy schedules jobs solely according to their Whittle indices, computed using the closed-form index expression. The Input-Fair Whittle policy enforces a fixed per-class server quota but does not adapt to differences in workload or deadline characteristics across classes. In contrast, the proposed Outcome-Fair Whittle policy dynamically adjusts scheduling decisions through a virtual queue to achieve desired long-term completion-rate targets. Figure 2: Completion rates vs Server capacity for a simple two class case, illustrating fair completion rates for outcome-fair whittle policy. In the simulation example 1 (Figure 2), we consider N=50N=50 parking spots and cost of fixed c0=0.2.c_0=0.2. discount factor β=0.99β=0.99, and terminal penalty F(B)=1.5BF(B)=1.5B. Class A users (70%70\% of arrivals) generate low-demand, relaxed-deadline jobs with B∼U(2,6)B U(2,6) and T=B+U(3,12)T=B+U(3,12), while Class B users (30%30\% of arrivals) generate high-demand, tight-deadline jobs with B∼U(6,13)B U(6,13) and T=B+U(1,5)T=B+U(1,5). Each vacant parking spot receives a new arrival with probability 0.9.0.9. The number of available servers is varied over M∈5,10,15,20,25,30M∈5,10,15,20,25,30, while all other parameters remain fixed. Each policy is simulated over 5000 time slots. The Input-Fair Whittle policy reserves 30%30\% of the available servers for Class B users. The proposed Outcome-Fair Whittle policy instead employs a virtual queue with target completion rate ηB=0.5 _B=0.5 and step size α=5×10−5.α=5× 10^-5. Figure 2 present the completion rates of Classes A and B as functions of server capacity. Figure illustrate that outcome-fair Whittle index policy consistently achieves a higher completion rate for the disadvantaged Class B users than the input-fair Whittle policy. Observe that in the figure solid lines for class A and dotted lines for class B. As server capacity increase, the completion rate increases for both classes. In example 2 (Figure 3(a)), we illustrate the completion rate vs server capacity, outcome fair policy increases the fairness. However, there is decrease in the total profit. There is trade-off between fairness and profit. In example 2, Figure 3(b), we compare difference of profit from 1) standard whittle index policy and input fair policy, it is denoted a blue line. 2) Standard whittle index policy and outcome fair policy, it is denoted by an orange line. As the number of servers increases, this loss in profit difference decreases. More details on simulations of example 2 are given in Appendix. (a) N=80N=80 Completion rate vs server capacity (b) N=80N=80 Differences in profit Figure 3: Comparison of scheduling policies as the number of servers increases. Figure shows the completion rates for the two user classes and difference in profit. VI Concluding Remarks We studied outcome fairness for restless multi-armed bandits for deadline scheduling problem, where we proposed the outcome fair Whittle index policy. We presented analysis on the Whittle index policy and it extension to outcome fair index policy. We illustrated numerical examples and it demonstrate performance of outcome fair Whittle index policy and it is compared with standard Whittle index policy and input fair index policy. We observed that there is a trade-off between profit and fairness. The completion rate is improved in outcome-fair index policy while profit difference between standard Whittle index and outcome fair index policy is high. In the future we plan to investigate further on fairness vs profit trade-off for deadline scheduling problems with varying immediate reward structures. References [1] P. Whittle, “Restless bandits: Activity allocation in a changing world,” Journal of Applied Probability, vol. 25, no. A, p. 287–298, 1988. [2] R. R. Weber and G. Weiss, “On an index policy for restless bandits,” Journal of applied probability, vol. 27, no. 3, p. 637–648, 1990. [3] V. Mehta, R. Meshram, K. Kaza, S. N. Merchant, and U. B. Desai, “Rested and restless bandits with constrained arms and hidden states: Applications in social networks and 5g networks,” IEEE Access, vol. 6, p. 56782–56799, 2018. [4] Y. Hsu, E. Modiano, and L. Duan, “Scheduling algorithms for minimizing age of information in wireless broadcast networks with random arrivals,” IEEE Transactions on Mobile Computing, vol. 19, no. 12, p. 2903–2915, 2019. [5] A. Koley and C. Singh, “Fresh caching of dynamic contents using restless multi-armed bandits over wireless access,” IEEE Transactions on Networking, 2025. [6] W. Wang, J. Xu, and L. Tong, “Deadline scheduling as restless bandits,” IEEE Transactions on Automatic Control, vol. 63, no. 8, p. 2343–2358, 2018. [7] V. Raghunathan, V. Borkar, M. Cao, and P. R. Kumar, “Index policies for real-time multicast scheduling for wireless broadcast systems,” in Proceedings of IEEE INFOCOM, 2008, p. 1–9. [8] I. Kadota, A. Sinha, E. Uysal-Biyikoglu, R. Singh, and E. Modiano, “Scheduling policies for minimizing age of information in broadcast wireless networks,” IEEE/ACM Transactions on Networking, vol. 26, no. 6, p. 2637–2650, 2018. [9] D. Li and P. Varakantham, “Towards soft fairness in restless multi-armed bandits,” arXiv preprint arXiv:2207.13343, 2022. [10] A. Biswas, J. A. Killian, P. R. Diaz, S. Ghosh, and M. Tambe, “Fairness for workers who pull the arms: An index based policy for allocation of restless bandit tasks,” arXiv preprint arXiv:2303.00799, 2023. [11] S. Wang, G. Xiong, and J. Li, “Online restless multi-armed bandits with long-term fairness constraints,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2024, p. 15616–15624. [12] Y. Mao and A. Perrault, “Time-constrained restless multi-armed bandits with applications to city service scheduling.,” in AAMAS, 2024, p. 2375–2377. [13] K. J. H. Ahmed and S. Bhashyam, “Fair scheduling with deadline guarantees in single-hop networks,” in Sixth International Conference on Communication Systems and Networks (COMSNETS), 2014, p. 1–7. [14] I-Hong Hou, Vivek Borkar, and P. R. Kumar, “A theory of QoS for wireless,” in Proceedings of IEEE INFOCOM, 2009, p. 486–494. [15] I-Hong Hou and P. R. Kumar, “Scheduling heterogeneous real-time traffic over fading wireless channels,” in Proceedings of IEEE INFOCOM, 2010, p. 1–9. [16] Kyu S. K., C. Li, and E. Modiano, “Scheduling multicast traffic with deadlines in wireless networks,” in Proceedings of IEEE INFOCOM, 2014, p. 2193–2201. [17] Le X., Tong H., P. R. Kumar, A. A. Thatte, and S. K. Mitter, “On an information and control architecture for future electric energy systems,” IEEE Transactions on Power Systems, vol. 38, no. 1, p. 10–31, 2022. [18] V. Mittal, R. Meshram, D. Dev, and S. Prakash, “Indexability of finite state restless multi-armed bandit and rollout policy,” arXiv preprint arXiv:2305.00410, 2023. [19] K. Kaza, R. Meshram, V. Mehta, and S. N. Merchant, “Constrained restless bandits for dynamic scheduling in cyber-physical systems,” IEEE Access, vol. 12, p. 182274–182295, 2024. [20] K. Avrachenkov, V. S. Borkar, and P. Shah, “Lagrangian index policy for restless bandits with average reward,” Queueing Systems, vol. 110, no. 1, p. 21, 2026. [21] R. Meshram and K. Kaza, “Simulation based algorithms for Markov decision processes and multi-action restless bandits,” Arxiv, 2020. [22] I-Hong Hou and P. R. Kumar, “Scheduling heterogeneous real-time traffic over fading wireless channels,” in IEEE INFOCOM, 2014. -A Study of Example 2: General Model for Deadline Scheduling At each time step, the scheduler selects at most M jobs to receive one unit of service. The objective is to maximize the cumulative discounted reward over the infinite horizon. We now modify the reward structure and include immediate service reward, completion bonus, deadline failure penalty, and wasted service penalty. Suppose • ai[t]∈0,1a_i[t]∈\0,1\ denote whether job j is served at time t, • ki∈A,Bk_i∈\A,B\ denote the class of job j, • ctc_t denote the electricity price at time t, • vkv_k denote the service value of class k, • GkG_k denote the completion bonus, • FkF_k denote the deadline penalty coefficient, • wkw_k denote the wasted-service penalty coefficient. Whenever a selected job receives one unit of processing, its remaining workload decreases by one unit, Bi[t+1]=Bi[t]−1,B_i[t+1]=B_i[t]-1, and the scheduler earns the immediate reward rservice(i)[t]=vki−ct.r_service^(i)[t]=v_k_i-c_t. Here, vkiv_k_i represents the economic value of serving one unit of workload, while ctc_t denotes the electricity price during slot t. Consequently, serving jobs during periods of low electricity prices yields higher profit. The total immediate reward collected at time t is Rservice[t]=∑i∈[t]ai[t](vki−ct),R_service[t]= _i [t]a_i[t] (v_k_i-c_t ), where [t]Q[t] denotes the set of jobs currently present in the system. A job is successfully completed whenever Bi[t]=0.B_i[t]=0. Successful completion yields an additional terminal reward rcompletion(i)=Gki,r_completion^(i)=G_k_i, where GkiG_k_i depends on the job class. The total completion reward at slot t is Rcompletion[t]=∑i∈[t]Gki,R_completion[t]= _i [t]G_k_i, where [t]C[t] denotes the set of jobs completing during slot t.t. -A1 Deadline Failure Penalty If the job reaches its final time slot before the deadline, i.e., Ti[t]=1T_i[t]=1, an additional penalty F(Bi[t]−ai[t])F(B_i[t]-a_i[t]) is imposed whenever unfinished workload remains after the scheduling decision. Here, F:ℤ+→ℝ+F:Z_+ _+ is an increasing function satisfying F(0)=0.F(0)=0. For simplicity, we assume that F(Bi[t])=PiBi[t],F(B_i[t])=P_iB_i[t], where PiP_i is penalty and Bi[t]>0.B_i[t]>0. Thus, reward to the scheduler for the remaining unfinished workload is rremaining(i)[t]=−PkiBi[t].r_remaining^(i)[t]=-P_k_iB_i[t]. The corresponding total penalty is Rremaining[t]=−∑i∈ℱ[t]PkiBi[t],R_remaining[t]=- _i [t]P_k_iB_i[t], where ℱ[t]F[t] denotes the set of jobs leaving unsuccessfully. -A2 Wasted Service Penalty Suppose an unfinished job has already received Ei[t]E_i[t] units of service before missing its deadline. Since these resources do not produce a completed job, the scheduler incurs the additional penalty rwaste(i)=−zkiEi[t].r_waste^(i)=-z_k_iE_i[t]. The total wasted-service penalty equals Rwaste[t]=−∑i∈ℱ[t]qkiEi[t].R_waste[t]=- _i [t]q_k_iE_i[t]. This term discourages allocating resources to jobs that are unlikely to finish before their deadlines. Combining all four components, the one-step reward is R[t]= R[t]= ∑i∈[t]ai[t](vki−ct)+∑i∈[t]Gki _i [t]a_i[t] (v_k_i-c_t )+ _i [t]G_k_i −∑i∈ℱ[t](PkiBi[t]+zkiEi[t]). - _i [t] (P_k_iB_i[t]+z_k_iE_i[t] ). The reward structure simultaneously captures the economic value of service, the cost of electricity, the incentive to complete jobs, and the opportunity cost of wasting limited charging or processing resources on jobs that eventually miss their deadlines. We have the heuristic index Wi(B,T,k).W_i(B,T,k). W~k(B,T)= W_k(B,T)= vki−c \;v_k_i-c +B=1Gki +1_\B=1\G_k_i +B≥TβT−1(Pki+zkiEi), +1_\B≥ T\β^T-1 (P_k_i+z_k_iE_i ), The first term vki−cv_k_i-c represents the net profit obtained by serving the job during the current time slot. Jobs with larger service value or lower electricity prices receive higher priority. The second term B=1Gki1_\B=1\G_k_i is completion incentive, it is activated whenever one additional unit of service completes the job. The final term B≥TβT−1(Pki+zkiEi)1_\B≥ T\β^T-1(P_k_i+z_k_iE_i) is active only for critical jobs, i.e., jobs whose remaining workload is at least as large as the remaining time before departure. This term estimates the discounted future loss that can be avoided by serving the job immediately. The quantity Pki+qkiEiP_k_i+q_k_iE_i represents the total expected terminal loss. -A3 Scheduling Policy At every decision epoch, the heuristic index is computed for every job in the queue. The scheduler then selects the M jobs with the largest values. (t)=argmax||=M∑j∈W~j(B,T),A(t)= _|S|=M _j W_j(B,T), This policy preserves the computational efficiency of Whittle-index scheduling while incorporating the richer economic reward structure of the proposed charging model. -A4 Discussion The proposed score should be viewed as a Whittle-inspired heuristic rather than an exact Whittle index. An exact Whittle index would require solving the single-job subsidized dynamic programming problem and determining the subsidy for which the active and passive actions are equally valuable, Qν(B,T,1)=Qν(B,T,0).Q^ν(B,T,1)=Q^ν(B,T,0). The resulting index generally does not admit a closed-form expression under the proposed reward model because of the interaction between completion bonuses, heterogeneous service values, and class-dependent terminal penalties. Nevertheless, the heuristic captures the dominant economic trade-offs while maintaining the low computational complexity characteristic of index policies. -A5 Details on Simulation In this example, we demonstrate with this general reward, the completion rate vs number of servers capacity. There are two classes are considered. The outcome fair algorithm improves the completion rate for class B compared to a heuristic Whittle index policy. This is illustrated in the Figure 3(a). As number of server increases, the completion rate improves. The completion rate of outcome fair index policy and Whittle index policy matches when the server capacity reaches to 45.45. We also plot the profit difference between Whittle index policy and outcome fair index policy, profit difference Whittle index policy and input fair index policy. It illustrates the trade-off between fairness and profit. It is given in Figure 3(b). Interestingly, the profit difference is high when server capacity at 20-25, while profit difference is minimum, reaches to 0 when server capacity increases 50.50. The following parameters are used in simulations. N=80N=80 parking spots and cost is 0.2,0.2, β=0.99β=0.99 Class A users (70%70\% of arrivals) generate low-demand, relaxed-deadline jobs with B∼U(2,6)B U(2,6) and T=B+U(3,8)T=B+U(3,8), while Class B users (30%30\% of arrivals) generate high-demand, tight-deadline jobs with B∼U(8,15)B U(8,15) and T=B+U(1,4)T=B+U(1,4). Service value for class A vA=2.2v_A=2.2 and for class B vB=0.9.v_B=0.9. The completion bonus GA=7G_A=7 for class A and GB=1.5G_B=1.5 for class B. Failure penalty PA=1.5P_A=1.5 and PB=0.6P_B=0.6 for class A and class B. Waste cost for class A and class B is EA=0.2E_A=0.2 and EB=0.6.E_B=0.6. Each vacant parking spot receives a new arrival with probability 0.55.0.55. The number of available servers is varied over M∈5,10,15,20,25,30,35,40,45,50M∈5,10,15,20,25,30,35,40,45,50, while all other parameters remain fixed. Each policy is simulated over 50005000 time slots. The Input-Fair Whittle policy reserves 30%30\% of the available servers for Class B users.