Source-linked AI summary
Factorized Scheduling Principle: Learning Interpretable and Transferable Policies via Structured Additive Functions
Hong Je-Gal, Hyun-Suk Lee
TL;DR
Scheduling requires repeatedly choosing among candidates, yet learned policies can be entangled with a particular joint state and candidate set. FSP learns a structured, feature-based scheduling principle; experiments report strong performance, interpretability, and generalization beyond the training system.
Problem
Learning-based schedulers can entangle item features in joint-state policies, making their decisions difficult to interpret and their strategies difficult to transfer across candidate sets.
Source: §1 · p. 1, §2.2 · p. 3Method
FSP learns a global priority principle over item-level features, representing system conditions as a feature distribution and using a structured additive representation with identifiability constraints.
Source: §1 · pp. 1–2, §3.1 · p. 3Results
Takeaways & Limitations
FSP provides a practical approach for learning scheduling rules that are interpretable and transferable across systems.
Source: §7 · p. 9Pairwise interaction components grow quadratically with feature count, potentially increasing computational cost and reducing interpretability in high-dimensional systems.
Source: §6 · p. 9
Abstract
from arXiv · showhide
Scheduling problems arise from repeatedly selecting one item from a set of candidates based on their states. These problems often reduce to assigning priority scores and choosing the highest-ranked item. In this work, we propose a factorized scheduling principle (FSP) framework to learn interpretable and transferable scheduling rules. The FSP framework represents system states as condition distributions and decomposes a global scheduling principle into additive univariate and pairwise components with identifiability constraints. The scheduling principle enables the framework to maintain a simple priority-based structure during deployment. This principle is learned by using a policy-based objective combined with a temporal-difference signal defined on the condition distribution. Experiments on synthetic and realistic scheduling tasks demonstrate the FSP framework's strong performance, interpretability, and zero-shot generalization across different system scales.
1. Introduction
Classical priority rules are transparent but often depend on restrictive assumptions, while learned schedulers can be difficult to interpret and transfer when candidate populations change. The paper proposes FSP, which learns an interpretable, reusable scheduling principle from experience and reports strong performance and zero-shot generalization.
1. Introduction
- Classical indices offer transparent, reusable priorities but rely on restrictive assumptions, while learned policies can entangle item features and struggle to transfer across candidate populations.The gap motivates learning scheduling principles from experience while preserving interpretability and reuse.Source: §1 · p. 1
- FSP learns a global scheduling principle over item-level features, so priorities need not depend on item identities, indices, or the number of candidates.The principle is defined over feature conditions rather than a joint state representation.Source: §1 · pp. 1–2
- The framework uses a structured additive representation of feature contributions and interactions, with centering constraints for identifiability.Its learning formulation combines complementary local and temporal signals.Source: §1 · p. 2
- Experiments on synthetic and realistic scheduling tasks report strong performance, interpretability, and zero-shot generalization across candidate populations.The paper also lists theoretical results on identifiability, approximation guarantees, ranking consistency, and transfer properties.Source: §1 · p. 2
2. Background and Motivation
The background contrasts transparent but inflexible hand-crafted rules with flexible learned schedulers whose decision logic can be hard to interpret and sensitive to system changes. FSP instead seeks explicit feature-based priority principles that can be applied across candidate sets.
2.1. Motivation for Learning Scheduling Principles
- Hand-crafted heuristics and analytical priority rules can be effective and transparent in intended settings, but their logic may require re-engineering to transfer across systems.RL offers a flexible alternative, yet its decision logic can be difficult to interpret and sensitive to configuration or candidate-population changes.Source: §2.1 · p. 2
- FSP represents priorities as a structured additive function over descriptive features, making feature and interaction contributions explicit across candidate-set sizes and compositions.This is intended to combine learning-based adaptability with the interpretability and transferability associated with classical heuristics.Source: §2.1 · p. 2
2.2. Standard Scheduling Problem
- The standard scheduling formulation selects an indexed candidate at each step, receives a reward, transitions to a next state, and seeks a policy maximizing expected discounted return.The state is typically represented by concatenating candidate features, which ties it to candidate count and ordering.Source: §2.2 · p. 2
- Joint-state value functions or policies obscure shared item-level priorities, hinder feature-level interpretation, and couple learned strategies to candidate-set size, ordering, or feature distribution.FSP instead learns a feature-space priority rule that can be evaluated on arbitrary candidate sets.Source: §2.2 · p. 3
3. Proposed Framework: Factorized Scheduling Principle
FSP learns a global item-priority principle from feature conditions, retaining a priority-based decision structure while targeting interpretability and transfer across candidate sets. It represents system states as condition distributions, models priorities additively, and learns the principle from complementary local and temporal signals.
3.1. Condition Distribution as State Representation
- Condition distributions represent the population of item features independently of item identities and candidate-set size.The distribution places point masses at item feature locations; smooth kernel bumps can be used in practice.Source: §3.1 · p. 3
3. Proposed Framework: Factorized Scheduling Principle
- FSP defines item priority as a global function of feature conditions, intended to apply across candidate sets and environments.The principle is designed to explain why feature conditions receive particular priorities and to generalize across systems with different numbers or identities of items.Source: §3.2 · p. 3, §3 · p. 3
3.2. Global Scheduling Principle
- The scheduling principle uses one-dimensional feature effects and selected pairwise interactions, with centering constraints separating marginal and interaction contributions.Smooth spline or lattice bases provide a concrete parameterization that supports visualization and approximation guarantees.Source: §3.2 · p. 4
3.3. Scheduling Scoring and Selection Rule
- Each candidate is scored by the global principle, and a softmax policy selects among item scores, becoming greedy as its temperature approaches zero.Because scores decompose into feature effects and interactions, the chosen item's priority can be inspected through those components.Source: §3.3 · pp. 4–5
3.4. Learning the Global Scheduling Principle
- Learning combines a policy-likelihood signal for rewarded actions with value regression against temporal-difference targets, plus structural regularization.The likelihood signal shapes local item rankings, while value regression enforces temporal consistency; using either alone misses one of these signals.Source: §3.4 · p. 5
3.5. Theoretical Analysis
- Centering constraints make the additive decomposition identifiable, so marginal and interaction effects can be inspected as distinct components.The theoretical analysis establishes identifiability under the stated constraints.Source: §3.2 · p. 4, §3.5 · p. 5
- For sufficiently smooth ground-truth principles, spline and lattice parameterizations achieve approximation error O(R^-2), and score error at most ϵ bounds instantaneous regret by 2ϵ.The ranking is preserved whenever the ground-truth score gap exceeds 2ϵ.Source: §3.5 · p. 5
- A shared conditional supervision mechanism yields the same unique population-risk minimizer across systems with different characteristics, assuming a strictly convex loss.The minimizer depends only on the conditional law of supervision given features.Source: §3.5 · p. 6
4. Related Work
Prior scheduling work offers either interpretable index rules or flexible learning-based policies, while structured additive approaches improve transparency. The related-work section positions FSP as explicitly learning a transferable scheduling principle rather than using learned structure only as a value or policy proxy.
4. Related Work
- Index-based methods assign item-level priorities, but learned or approximated indices still rely on indexability assumptions or proxy an explicit index.The Gittins index is optimal for rested bandits; the Whittle index is a heuristic for restless bandits without general optimality guarantees.Source: §4 · p. 6
- RL schedulers can perform well across domains, but joint-state representations and black-box policies make decision logic difficult to interpret and sensitive to candidate-set changes.The cited applications include recommender systems, wireless scheduling, and job-shop environments.Source: §4 · p. 6
- Structured additive models improve transparency, yet prior approaches generally use learned structure as a value-estimation proxy or embed it in policy optimization rather than learn an independent transferable priority principle.FSP instead learns a global priority principle and enforces temporal properties.Source: §4 · p. 6
5. Experiments
The experiments test whether FSP recovers a known scheduling principle and transfers to realistic tasks across system sizes and feature distributions. Results show accurate synthetic recovery and competitive realistic performance, including robust transfer in the warehouse task.
5.1. Synthetic Experiment
- The synthetic experiment tests recovery of a known principle using eight candidates, four features, nonlinear marginal effects, and an interaction between the first two features.Rewards are generated from the true principle with added noise.Source: §5.1 · p. 6
- Across candidate counts N, learned policy average reward gaps versus oracle are on the order of 10^-4, with ranking accuracy around 99.4%; over a dense grid in [0,1]^4, distance between learned and true functions is 0.013.Table 2 reports transfer performance varying N, with the learned function trained at N = 8.Source: §5.1 · p. 7, Table 2 · p. 7
5.2. Realistic Scheduling Experiment
- Across three realistic tasks, FSP is competitive on the training system and transfers without retraining across system sizes and populations.FSP and the Whittle-index are learned or estimated on N = 10; other learning baselines are trained separately for each N.Source: §5.2 · p. 8, Table 3 · p. 8
- In wireless scheduling, FSP overtakes Whittle at N = 15 and N = 20, though Whittle performs better at N = 5 and N = 10.The passage suggests item-wise index approximations become less effective as system-level coupling strengthens.Source: §5.2 · p. 8
- In inventory replenishment, FSP is best at N = 20 after training only on the 10ID system, while several per-size DRL policies win at N = 5 and N = 15.Whittle slightly outperforms FSP at the training size N = 10 and falls behind at the other tested sizes.Source: §5.2 · pp. 8–9
- In warehouse clearance, FSP achieves the highest reward at every tested system size, despite training only on the 10ID system.The task includes distribution shifts where ranking errors can cause severe overflow penalties.Source: §5.2 · p. 9
- In wireless scheduling, the learned channel-condition score rises with channel quality while the uninformative noise-feature score remains nearly flat.These component functions illustrate meaningful prioritization and suppression of a spurious feature.Source: §5.2 · p. 9, Figure 3 · p. 9
6. Discussions
FSP is designed to extend beyond item selection while retaining interpretability, but its pairwise structure creates a feature-dimensionality scalability constraint. Its theoretical guarantees also assume a global scheduling principle, which may not hold exactly in every setting.
6. Discussions
- FSP can incorporate system factors and item-system interactions additively, and extend to sub-decisions and multi-item selection through structured residuals and reusable scores.These extensions are proposed as ways to address more complex scheduling scenarios without sacrificing interpretability.Source: §6 · p. 9
- Pairwise interaction components grow quadratically with feature count, potentially increasing computational cost and reducing interpretability in high-dimensional systems.The experiments show scalability with candidate count N; larger feature spaces may require sparse, low-rank, or domain-restricted interactions.Source: §6 · p. 9
- The theoretical analysis assumes a global scheduling principle; without exact additive structure, FSP is an approximate interpretable surrogate, though realistic experiments find it informative and robust.The assumed global principle enables identifiability and regret guarantees.Source: §6 · p. 9
7. Conclusion
FSP learns an interpretable, priority-based scheduling rule from experience and is reported to perform robustly and transfer across system scales and feature distributions. Experiments show generalization beyond the training system, including when an exact global principle is not guaranteed.
7. Conclusion
- Experiments on synthetic and realistic tasks show FSP learns reusable, interpretable scheduling principles that generalize beyond the training system, even without a guaranteed exact global principle.The framework preserves a simple priority-based factorized structure while achieving robust performance and transferability across system scales and feature distributions.Source: §7 · p. 9
Impact Statement
This appendix states the paper's impact, provides the learning and deployment procedures, lists assumptions for theoretical results, and gives proof details for identifiability and approximation error.
Impact Statement
- The work aims to advance interpretable and transferable scheduling principles and reports no anticipated near-term negative societal impacts beyond typical learning-based optimization risks.The framework is intended to improve transparency and robustness of decision-making systems.Source: Impact Statement · p. 10
A. Algorithmic Details
- Training updates the univariate and pairwise additive model using likelihood and value-regression losses, regularization, and identifiability constraints; deployment scores candidates and selects the highest-scoring item.The learning algorithm combines a policy-based likelihood loss with a TD-target value loss, while inference applies the learned principle to score items.Source: A. Algorithmic Details · p. 12
B.1. Assumptions
- The theoretical results assume an existing global principle that determines expected reward, single-item selection with weak interactions, stationary i.i.d. feature sampling, and smooth components.The principle is assumed Lipschitz, with bounded second mixed derivatives for its univariate and bivariate components.Source: §B.1 · pp. 12–13
B.2. Proof of Theorem 3.1 (Identifiability)
- Centering constraints make the additive decomposition identifiable: the proof establishes uniqueness of the univariate and pairwise components almost everywhere.The argument applies marginal projections to isolate the components.Source: §B.2 · p. 13
B.3. Proof of Theorem 3.2 (Approximation Error)
- Under the stated smoothness assumptions, cubic univariate and tensor-product bivariate spline approximations each achieve uniform error O(h^2), with h = 1/R.Combining the component-wise bounds yields the stated approximation result.Source: §B.3 · p. 13
B.4. Proof of Theorem 3.3 (Ranking Consistency & Greedy regret)
The proof bounds greedy regret when the learned principle uniformly approximates the global one. It also shows that the optimal principle is invariant across systems sharing the same conditional outcome law.
B.4. Proof of Theorem 3.3 (Ranking Consistency & Greedy regret)
- If the learned principle approximates the global principle uniformly within ϵ, any ranking gap greater than 2ϵ is preserved and greedy regret is at most 2ϵ.The ranking guarantee applies when the true score difference exceeds 2ϵ.Source: §B.4 · p. 13
B.5. Proof of Theorem 3.4 (Principle invariance)
- When systems share the same conditional law Y | X, they share the same optimal scheduling principle, independently of their marginal feature distributions.Identifiability constraints ensure uniqueness of the decomposition into univariate and pairwise components.Source: §B.5 · p. 14
C. Additional Results for Synthetic Experiments
The synthetic visualizations show close recovery of the true univariate and pairwise scheduling components. The realistic environments vary in coupling and economic structure, from wireless penalties to inventory trade-offs and overflow-sensitive clearance.
C. Additional Results for Synthetic Experiments
- The learned univariate curves closely overlap the ground truth, while pairwise slices and surfaces recover the interaction structure with uniformly small discrepancies.Together, the visualizations provide qualitative evidence that FSP recovers both component types in the synthetic environment.Source: C. Additional Results for Synthetic… · pp. 14–15
D.1. Wireless User Scheduling
- Wireless scheduling combines nonlinear throughput constraints with system-wide age penalties and bursty traffic, making user priorities sensitive to other users’ states.The resulting task requires balancing spectral efficiency with long-term stability.Source: §D.1 · p. 16
D.2. Inventory Replenishment
- Inventory replenishment has conflicting economic incentives and shared constraints, but partial replenishment of unselected items gives its dynamics a quasi-additive, relatively localized structure.That structure can make item priorities more stable across feature-distribution changes at a fixed system size.Source: §D.2 · p. 17
D.3. Warehouse Clearance
- Warehouse clearance couples item features to global overflow dynamics, so changing item counts or ordering can expose policies that overfit system-specific overflow patterns.Unselected items accumulate inventory and may incur large negative rewards after crossing capacity thresholds.Source: §D.3 · p. 17
D.4. Experimental Settings
The experiments use a shared training setup and task-specific parameters to represent each scheduling environment’s dynamics and reward trade-offs.
Common Settings
- FSP uses additive item-level components and pairwise interactions; DQN-based baselines take concatenated item features, while Whittle uses an item-wise index estimated from the training system.The NAM baseline replaces DQN’s Q-network with a neural additive model.Source: §D.4 · p. 18
- Unless otherwise specified, policies are trained with N = 10 items and evaluated in both in-distribution and out-of-distribution settings.FSP is optimized with stochastic gradient descent using a fixed learning rate.Source: §D.4 · p. 18
Wireless User Scheduling System Parameters
- Wireless task parameters control stochastic arrivals, service capacity, throughput weight, and queue-overflow and delay penalties.Together, they set the efficiency and delay-related trade-off.Source: §D.4 · pp. 18–19, Table 5 · p. 19
Inventory Replenishment System Parameters
- Inventory parameters govern replenishment quantity, demand granularity and drift, item economics, overflow penalties, and reward weights.These controls represent trade-offs among revenue, ordering, holding, stock-out, and overflow costs.Source: §D.4 · p. 19, Table 6 · p. 19
Warehouse Clearance System Parameters
- Warehouse parameters govern global sales capacity, inflow and margin variation, revenue scaling, holding costs, and overflow thresholds and penalties.Together, they balance immediate clearance revenue against inventory congestion.Source: §D.4 · p. 19
E. Additional Results for Realistic Experiments
The appendix details realistic-task transfer comparisons, distinguishing FSP’s single training system from DQN’s size-specific policies.
E. Additional Results for Realistic Experiments
- FSP is trained once on the N = 10 system, whereas DQN policies are trained separately for each system size and cannot be applied to other sizes.The appendix reports detailed FSP–DQN in-distribution and out-of-distribution breakdowns.Source: E. Additional Results for Realistic… · pp. 19–20
- A DQN variant without the uninformative random feature is included to separate feature-noise effects from transfer behavior.The appendix’s detailed breakdown includes this variant.Source: E. Additional Results for Realistic… · p. 20
- The expanded comparison with Whittle, NAM, A2C, PPO, TRPO, and QR-DQN is summarized in the main text’s Table 3.The appendix tables focus on the FSP–DQN transfer breakdown.Source: E. Additional Results for Realistic… · p. 20
E.1. Wireless User Scheduling
Across the realistic tasks, FSP transfers across system sizes, while the size-specific DQN policies show distinct out-of-distribution weaknesses. The learned components also reveal interpretable task-specific priorities and interactions.
E.1. Wireless User Scheduling
- In wireless scheduling, FSP stays stable across system sizes and consistently outperforms DQN OOD, with the gap growing as system size increases.Removing DQN’s random feature does not resolve its OOD generalization failure.Source: §E.1 · p. 20, Table 8 · p. 20
- Wireless components assign strong increasing priority to channel quality, smaller effects to age and buffer state, and nearly flat effects to noise; interactions further condition priority on channel, age, and backlog.Users with nearly empty buffers remain low priority regardless of channel condition.Source: §E.1 · p. 21
E.2. Inventory Replenishment
- In inventory replenishment, FSP transfers across system sizes, while FSP and DQN both generalize across populations at a fixed size; DQN remains size-specific.The reported pattern is consistent with the task’s quasi-additive structure.Source: §E.2 · p. 22, Table 9 · p. 22
- Inventory components prioritize higher demand and margins, while inventory level has an increasing-then-decreasing effect; interactions amplify demand priority when stock is scarce.The learned interaction also discourages replenishment when inventory is abundant and demand is low.Source: §E.2 · p. 23
E.3. Warehouse Clearance
- FSP maintains stable, positive performance and significantly outperforms DQN across warehouse-clearance OOD settings, despite training only on the 10-item system.DQN performance deteriorates dramatically on unseen populations, with overflow penalties amplifying poor-prioritization costs.Source: §E.3 · p. 23, Table 10 · p. 24
- In warehouse clearance, moderate-inventory items gain priority conditionally on margin, while low-inventory items remain low priority even at high margins.The inflow interactions are weak, and the random-feature component is nearly flat.Source: §E.3 · pp. 24–25, Figure 12 · p. 25