{"id":"49f4e4a1-1e7c-4ee4-9c55-2279002df513","arxiv_id":"2607.23772","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Adding a fairness-deficit virtual-queue term to the Whittle index improves long-run completion rates for disadvantaged classes in deadline RMAB scheduling, at a profit cost that shrinks with more servers.","lead":"The paper adds fairness-deficit virtual queues to Whittle indices so deadline schedulers complete more jobs from disadvantaged demographic groups. The idea targets EV charging, cloud jobs, and similar systems where pure profit maximization starves some classes.","discovery_kind":"extension","skeptic_critique":{"model":"moonshotai/kimi-k3","headline":"The claimed completion-rate guarantee (9) rests on a Lyapunov drift argument that does not transfer: the fair index weights jobs by λ_k·δ_i (feasibility), but the virtual queue drains only on completions, and multi-slot workloads break the one-step service→debt coupling Hou–Kumar [15, Thm. 2] assume","rationale":"The reader already identified the correct soft spot — citation-plus-heuristic in place of a stability/indexability proof — and conditioned the verdict on supplying proofs or relabeling the policy as heuristic, plus code and error bars. My analysis sharpens the same concern to a specific technical gap: even granting [15, Thm. 2], its hypotheses (per-slot debt decrement upon service, greedy maximization of the debt-weighted delivery sum) do not hold for the composite index (11), because (a) the queue drains on completions while the index weights feasibility, and (b) multi-unit workloads decouple service from completion across many slots. This does not move the verdict below CONDITIONAL: the paper's simulations are internally consistent, the virtual-queue construction is standard in spirit, and the mismatch may well be repairable with a frame-based drift argument or a modified index that weights by imminent completion. It also does not rise to REJECT because the contribution is honestly presented as an algorithm with numerical evidence, and the abstract's empirical claims (better fairness, profit trade-off shrinking with M) are plausibly supported by the figures as described. The one rhetorical overreach worth flagging is the word \"guarantees\" for (9), which currently has only simulation support. Hence: agree with the reader's weakest_assumption, UNCHANGED verdict (CONDITIONAL, MODERATE confidence), with the single concrete check being a long-horizon λ_B stability test against an oracle/fluid achievability bound.","tokens_in":12293,"tokens_out":2327,"duration_ms":107720,"concrete_test":"In the Fig. 2 regime (N=50, two classes as specified, c0=0.2, η_B=0.5, α=5e-5), run the outcome-fair policy for 10^6 slots at M=10 and M=15 and record the trajectory of λ_B[t]. Independently compute an upper bound on class B's achievable completion rate via a fluid/LP relaxation (or an oracle debt policy that each slot maximizes Σ_k λ_k·1{serving i completes job i}). If λ_B[t] grows approximately linearly while the oracle bound meets η_B, the δ-weighted greedy rule does not stabilize the deficit queue and the guarantee claim fails; if λ_B stays bounded and tracks the target across α values, the heuristic is validated at least in this regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central engineering claim is that update (10) \"dynamically enforces long-term completion rate guarantees\" (9). The standard route to such a guarantee: show λ_k[t] is mean-rate stable, since λ stable implies limsup (η_k A_k − C_k) ≤ 0, i.e., (9). Stability proofs of the Hou–Kumar type the paper cites require the policy to greedily maximize, each slot, a weighted sum whose weights are exactly the debts and whose increments directly reduce those debts — i.e., serving a class-k job decrements λ_k by a coupled amount in the same slot. Here the coupling is broken in two places. First, the greedy rule (11) maximizes Σ_i a_i (ν_i + λ_{k_i}δ_i), i.e., a λ-weighted sum of feasibility indicators, not of completions C_k[t]; the drift-minimizing action for (10) would weight jobs by expected immediate completion credit (roughly λ_k·1{B_i=1}), which is not what δ_i = 1{B_i≤T_i} measures. Second, with workloads B_i up to 13–15 units (§V), service and completion are separated by many slots, so no per-slot drift inequality of the cited form holds without a new multi-slot (e.g., frame-based) argument, which is not given. A further unaddressed failure mode: targets {η_k} are asserted feasible by citation, but if η_B exceeds the capacity-feasible completion rate for tight-deadline class B, λ_B diverges linearly and the policy degenerates toward serving only class B — the paper neither states a feasibility condition nor checks one for its chosen η_B = 0.5. None of this shows the simulations are wrong; it shows the word \"guarantees\" is unsupported beyond the simulated regimes, and the α = 5e-5 step size enters with no convergence analysis. Lemmas 1–3 and indexability are also only sketched/cited, so even the baseline index term rests partly on [6]'s constant-cost result while the fair composite index is never shown to be an index of any well-posed subsidized MDP.","agreement_with_reader":"agree"},"referee_report":{"model":"moonshotai/kimi-k3","summary":"The paper studies a stochastic deadline scheduling problem (motivated by EV charging) modeled as a restless multi-armed bandit with two demographic classes. Building on the closed-form constant-cost Whittle index of Wang et al. [6], the authors define outcome fairness as a long-run per-class completion-rate target (Def. 4, Eq. (9)) and propose an \"outcome-fair Whittle index\" (Def. 6, Eq. (11)) that adds to the baseline index a class-dependent fairness-deficit virtual queue λ_k[t] (Eq. (10)) multiplied by a feasibility indicator δ_i[t]. Simulations with two classes and varying server capacity M (§V, Figs. 2–3) show the proposed policy raises the disadvantaged class's completion rate relative to standard and input-fair Whittle policies, at a profit cost that shrinks as M grows. Lemmas 1–3 and the indexability claim are stated without proof, with citations to [6], [15], [18].","tokens_in":12721,"tokens_out":2786,"duration_ms":43357,"significance":"If the construction is sound, the paper makes a useful and modestly novel contribution: combining RMAB deadline scheduling with hard outcome-fairness (completion-rate) guarantees via an O(N log N) index policy is, to my knowledge, not in the literature, and the simulation evidence that a simple additive virtual-queue correction can lift a structurally disadvantaged class's completion rate is of practical interest for EV charging and similar systems. The baseline closed-form index is inherited from [6], which keeps the proposal cheap to implement, and the fairness–profit trade-off curves as a function of capacity M are a genuinely informative empirical observation. However, the paper's strengths are currently empirical rather than established: the claimed guarantee \"dynamically enforces long-term completion rate guarantees\" (Abstract) is asserted, not proved, and the simulations are too thin (two setups, no error bars) to carry the claim alone.","major_comments":[{"comment":"The central claim — that the virtual queue (10) 'dynamically enforces long-term completion rate guaranties' (Abstract) — is supported only by the sentence 'The sufficient conditions ... is analyzed using the Lyapunov drift criteria, see [15, Theorem 2]' (§IV). This citation does not obviously transfer. The Hou–Kumar-style drift argument that would yield (9) via mean-rate stability of λ_k requires the greedy rule to maximize, each slot, a weighted sum whose per-slot increments directly reduce the corresponding debt. Here the greedy rule maximizes Σ_i a_i(ν_i + λ_{k_i}δ_i), where δ_i = 1{B_i ≤ T_i} is a feasibility indicator, not a completion credit; and the queue (10) drains only on completions C_k[t]. With workloads B up to 13–15 (§V), service and completion are separated by many slots, so no per-slot drift inequality of the cited form holds. The paper needs either (a) a proof (e.g., a f","section":"§IV, Eq. (10)–(11); claim in Abstract and §IV"},{"comment":"No feasibility condition on the targets {η_k} is stated or checked. If η_B exceeds the capacity-feasible completion rate for the tight-deadline class (B ~ U(6,13), T = B + U(1,5), 30% of arrivals, M as low as 5 with N = 50), then λ_B[t] grows linearly and the policy degenerates toward serving only class B. The simulations use η_B = 0.5 (§V) without verifying it is inside the feasible region, and Definition 4 / Eq. (9) is silent on feasibility. At minimum the paper should state the feasibility requirement (in the spirit of [14]'s feasibility-region characterization) and verify it for the chosen parameters; ideally, comment on policy behavior when targets are infeasible.","section":"§III, Def. 4 / Eq. (9); §IV; §V parameter choice η_B = 0.5"},{"comment":"The 'outcome-fair Whittle index' (11) is never shown to be the Whittle index of any well-posed subsidized MDP, and the indexability analysis (Lemma 3, §II-E) applies only to the baseline arm without the λ term. Since λ_{k_i}[t] is time-varying and coupled across arms through the shared queue update, the composite policy is not a Whittle index policy in the technical sense. This may be fine — the policy can stand as a virtual-queue-augmented index heuristic — but the paper should say so explicitly (as it commendably does for the appendix heuristic W in §A-4) rather than calling (11) a Whittle index and citing skipped indexability proofs as support.","section":"§IV, Def. 6; §II-E, Lemma 3"},{"comment":"The empirical support for the central comparative claim is thin: two experimental setups, 5000 slots each, with no error bars, confidence intervals, seed counts, or sensitivity to the step size α = 5×10⁻⁵. The fairness–profit trade-off (Fig. 3b) and the claim that the gap 'decreases as the server capacity increases' (Abstract) rest on single traces. Moreover, Example 2's baseline is the admittedly 'Whittle-inspired heuristic' fW (Appendix, §A-4), not an exact Whittle index, so the profit-loss attribution in Fig. 3b is relative to a heuristic baseline whose suboptimality gap is unknown. At least 10–20 seeds with reported variability, and a brief sensitivity study in α, are needed before the trade-off claim can be stated quantitatively.","section":"§V, Figs. 2–3; Appendix §A-5"}],"minor_comments":[{"comment":"Lemma 1 lists 'Q^ν_i(s,0), Q^ν_i(s,0), and V^ν_i(s)' — the second entry should be Q^ν_i(s,1).","section":"§II-D, Lemma 1"},{"comment":"Notation collision: A_k[t] and C_k[t] denote cumulative counts in Definition 4 but per-slot counts in Eq. (10). Use distinct symbols (e.g., a_k[t], c_k[t] for per-slot increments).","section":"§III Def. 4 vs. §IV Eq. (10)"},{"comment":"The skipped proofs of Lemmas 1–3 are justified 'due to space constraint,' yet the manuscript includes a full appendix on Example 2. Given that these lemmas underpin the indexability claim, a short proof or a precise pointer (theorem numbers, not just '[18, Appendix B]') would fit the available space.","section":"§II-D,E"},{"comment":"References [15] and [22] are the same Hou–Kumar INFOCOM paper listed twice with different years (2010 and 2014); please deduplicate and correct. Reference [20] (2026) and [4]–[5] years should be double-checked.","section":"References"},{"comment":"Repeated sentence in §II-C: 'Let S̃_i[t] = (S_i[t], c[t]) denote the extended state of arm i' appears twice; also 'R^{a_i}(S̃) == 0' has a double equals sign. Numerous grammar issues throughout ('guaranties', 'is defines the Whittle indexability', 'compare to other schemes'). A careful proofreading pass is needed.","section":"§II-C and passim"},{"comment":"Figures 1–3: legends, axis labels, and line-style assignments are described only in text ('solid lines for class A and dotted lines for class B'); please add proper legends and state units. Fig. 1's caption should state what the y-axis measures.","section":"Figs. 1–3"},{"comment":"In the baseline index formula (§II-E), for the case T ≤ B the term β^{T−1}[F(B−T+1) − F(B−T)] is positive for increasing F, giving infeasible jobs a higher index than feasible ones; a one-line remark on why this is the correct subsidy-derived priority (penalty avoidance) would help readers, and clarify whether δ_i in (11) is redundant given this term.","section":"§II-E, index formula"}],"recommendation":"major_revision","confidential_remarks":"The paper sits at the intersection of RMAB scheduling and fairness and would fit a systems/control venue, but in its current form the Abstract's guarantee language outruns what is proved — all structural lemmas are unproven and the one stability claim is a bare citation that does not obviously apply to multi-slot workloads. The writing quality is below the journal's bar and will need substantial copyediting. If the authors either supply a real stability/feasibility argument or reframe the contribution honestly as a well-motivated heuristic with strengthened experiments (multiple seeds, α sensitivity), the paper could become acceptable; I would not reject outright because the empirical observation is plausible and the setting is of interest, but the gap between claim and support is currently too large for minor revision."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The one thing to know: this is a clean systems extension, not a new theory result. They take the constant-cost deadline Whittle index from Wang–Xu–Tong, add a Hou–Kumar-style fairness-deficit virtual queue, and schedule on ν + λ_k δ_i. That concrete policy and the two-class EV-style comparison (plain Whittle vs input-fair vs outcome-fair) are what is actually new; the related-work claim that the joint package had not been done looks fair.\n\nWhat they do well is the motivation and the numerics. The bias figure for standard Whittle under heterogeneous laxity is clear, the completion-rate plots show the disadvantaged class improving under the fair index, and the profit gap shrinking with M is the right trade-off to report. Complexity stays O(N log N). The appendix heuristic for richer rewards (bonuses, waste penalties) is honest about not being an exact index.\n\nSoft spots, in proportion. Lemmas 1–3 and indexability are sketched or cited to [6] with proofs skipped; fine for a short paper if they label it, but the composite fair index is never shown to be the Whittle index of a subsidized fair MDP—it is an additive heuristic. The stronger claim that the virtual queue “enforces” long-run completion targets (9) leans on a Lyapunov citation that does not transfer cleanly: the greedy weight is λ·δ (feasibility), not immediate completion credit, and multi-unit workloads break the one-step service–debt coupling those theorems assume. So “guarantees” is too strong; the sims support the claim inside the plotted regimes, nothing more. No error bars, no seed reporting, free parameters (η, α, class distributions) are tuned without sensitivity. None of that sinks the engineering point.\n\nWho it is for: people doing deadline RMAB, EV charging, or fair real-time scheduling who want a drop-in index tweak and a documented profit–fairness curve. A serious editor should send it to referees; expect revision to tone down guarantee language, supply or clearly defer the proofs, and add basic statistical rigor. I would skim the camera-ready if I were working in the area; I would not rearrange my own agenda around it.","headline":"Useful engineering combo of deadline Whittle and outcome virtual queues; the “guarantee” language outruns the proof, but the sims and trade-off story are real and worth a referee.","tokens_in":14090,"tokens_out":572,"would_cite":false,"duration_ms":23815,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"An outcome-fair Whittle index raises long-run completion rates for disadvantaged job classes in deadline scheduling, at a profit cost that shrinks as server capacity grows.","keywords":["restless multi-armed bandits","Whittle index","stochastic deadline scheduling","outcome fairness","virtual queues","demographic fairness","EV charging"],"falsifier":"Re-run the paper’s two-class simulations (N=50 or 80, stated workload/deadline distributions, η_B=0.5, varying M): if the disadvantaged class’s empirical completion rate under the outcome-fair index stays below target while input-fair or plain Whittle matches or exceeds it, or if the profit gap versus plain Whittle does not fall toward zero as M grows, the central claim fails.","tokens_in":13619,"feed_emoji":"⚖️","tokens_out":901,"duration_ms":31337,"temperature":0.7,"pith_summary":"Standard Whittle-index scheduling for stochastic deadline jobs maximizes discounted reward but systematically starves demographic classes whose jobs have heavier workloads or tighter deadlines. This paper formulates outcome fairness—minimum long-run completion-rate targets per class—inside the restless bandit model and builds an outcome-fair Whittle index by adding a fairness-deficit virtual-queue term only to feasible jobs. Simulations against plain Whittle and input-fair (quota) Whittle show higher completion rates for the disadvantaged class and a fairness–profit trade-off that narrows once more servers are available. A sympathetic reader cares because the same capacity-constrained deadline setting appears in EV charging, cloud jobs, and real-time wireless, where pure reward maximization can lock out whole user groups.","feed_headline":"Fair Whittle index lifts disadvantaged completion rates","feed_subtitle":"Virtual queues hit long-run targets; profit loss shrinks as servers grow","key_machinery":"The outcome-fair Whittle index ν_fair_i[t] = ν_i(B_i[t], T_i[t], c[t]) + λ_{k_i}[t] δ_i[t], where λ_k is a virtual queue that grows when class k’s completions fall short of its target rate η_k and δ_i marks remaining feasibility; the M highest-index arms are activated each slot.","core_discovery":"Grafting a Lyapunov fairness-deficit virtual queue onto the ordinary Whittle index yields an outcome-fair index policy that, in the paper’s two-class deadline simulations, meets prescribed long-run completion-rate targets for the structurally disadvantaged class better than either unconstrained Whittle or fixed per-class server quotas, while the associated profit loss relative to unconstrained Whittle decreases as the number of servers increases.","pith_inferences":["If arrivals or costs become non-stationary, the fixed step-size α in the virtual queue may need online tuning or a diminishing schedule to keep completion rates on target.","The method should transfer to multi-class AoI or timely-throughput bandits where “completion” is replaced by a freshness or delivery-debt metric.","Closed-form indexability of the fair subsidized MDP remains open; a counter-example with heavy-tailed deadlines would force a fully numerical or rollout fair policy."],"forward_implications":["Deadline schedulers can enforce designer-chosen completion-rate floors per demographic class by a simple additive virtual-queue priority.","Input fairness (fixed server shares) does not guarantee outcome fairness when classes differ in workload and laxity.","The profit penalty of fairness is largest at tight capacity and becomes negligible once servers are plentiful.","The same virtual-queue-augmented index applies to any indexable deadline RMAB whose baseline index is already computable."],"fun_headline_variants":["Virtual queues make Whittle index outcome-fair for deadlines","Outcome-fair Whittle beats quotas on disadvantaged completion rates","Lyapunov deficit queues enforce long-run class completion targets","Fair Whittle index meets group rates; profit gap falls with servers","Outcome-fair index tops unconstrained and input-fair Whittle"],"cache_read_input_tokens":128,"weakest_assumption_plain":"That simply adding the virtual-queue bonus to the known constant-cost Whittle index, and citing an existing Lyapunov drift result, is enough to guarantee the long-run completion-rate targets without a fresh proof that the coupled fair policy remains indexable or feasible.","fun_headline_variants_meta":{"raw":{"variants":["Virtual queues make Whittle index outcome-fair for deadlines","Outcome-fair Whittle beats quotas on disadvantaged completion rates","Lyapunov deficit queues enforce long-run class completion targets","Fair Whittle index meets group rates; profit gap falls with servers","Outcome-fair index tops unconstrained and input-fair Whittle"]},"model":"grok-4.5","effort":"low","cost_usd":0.00361,"raw_usage":{"total_tokens":1142,"prompt_tokens":756,"num_sources_used":0,"completion_tokens":67,"cost_in_usd_ticks":36104000,"prompt_tokens_details":{"text_tokens":756,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":319,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":756,"tokens_out":67,"duration_ms":6307,"temperature":1.0,"reasoning_tokens":319,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-30T13:01:00.878983+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Re-run the paper’s two-class simulations (N=50 or 80, stated workload/deadline distributions, η_B=0.5, varying M): if the disadvantaged class’s empirical completion rate under the outcome-fair index stays below target while input-fair or plain Whittle matches or exceeds it, or if the profit gap versus plain Whittle does not fall toward zero as M grows, the central claim fails.","supporting_citations":[],"review_version":1}