Many scheduling and routing problems come with hard time windows: a customer must be visited between 9:00 and 9:30, or a job must finish before its due date. These windows have a useful property that classical planners have exploited for decades. When one step makes a later window impossible to meet, every continuation of that plan is already doomed. Reinforcement learning (RL) agents for these problems mostly ignore this. They add a clock to the state, see the penalty only when the deadline actually passes, and must learn from scratch which earlier decision caused the failure. The clock also multiplies the state space, because the same configuration reached at 9:05 and at 9:12 becomes two different states.
We propose to change what the value-estimating half of an actor-critic agent sees during training. Such an agent has two parts: the policy (the "actor"), which picks actions, and the "critic", which estimates how good the current situation is and is used only during training. In an asymmetric actor-critic, the critic receives privileged simulator information that the deployed actor never gets. Our critic receives something more specific: a temporal constraint network, meaning the earliest and latest feasible times of every remaining task, propagated with shortest-path algorithms using the simulator's true, already-sampled durations and travel times. Two consequences follow. The critic can mark a decision as fatal at the moment it makes a future deadline unreachable, not when the deadline passes. And states that differ only in clock values but have the same feasible future map to the same critic input. This is a learned analogue of the "metastates" used in temporal planning.
Core Claim
In stochastic routing and scheduling with tight time windows, an asymmetric critic conditioned on the privileged, propagated temporal network will learn faster and yield better policies than one conditioned on the same privileged information in raw form. Here "raw form" means clocks, windows, and realized durations fed in directly. The two inputs are deterministic functions of the same simulator state, so any gain comes from representation and from credit arriving at the right step, not from extra information.
We also make a falsifiable prediction. The advantage should grow with window tightness and with the number of remaining tasks, and it should vanish when windows are loose. Loose windows are exactly the regime where classical propagation stops pruning anything.
Why this is not already done
The closest work is Learning to Optimize Job Shop Scheduling Under Structural Uncertainty, which introduces UP-AAC. After an episode ends, UP-AAC replays the realized trajectory as a fixed, deterministic job-shop instance and has the critic evaluate that instance. Its uncertainty is discrete branching of job routes, not metric time windows. Its critic sees the hindsight instance rather than a propagated feasibility structure, and nothing in it tells the critic when infeasibility became inevitable. It therefore motivates our proposal rather than covering it.
On the other side, three planning and scheduling methods supply the propagation machinery, all without learning:
- Generating Feasible Schedules under Complex Metric Constraints (SP-PCP) runs all-pairs shortest paths over a temporal constraint network to detect forced orderings.
- Temporal Scope of Assertions and Window Cutoff aborts orderings whose windows cannot be met.
- Efficient Temporal Planning Using Metastates merges states with identical logical content and handles differing arrival times lazily.
Two RL papers constrain our design. Informed Asymmetric Actor-Critic shows that giving the critic the full state can hurt, because uninformative privileged features act as structured noise. That paper selects a fixed feature subset before training. We instead apply a state-dependent transformation that discards temporal slack irrelevant to feasibility. A Theoretical Justification for Asymmetric Actor-Critic Algorithms proves that a state-conditioned critic removes aliasing error but faces a harder approximation problem. Our input is designed to lower that approximation cost without giving back the aliasing benefit.
Research Program
The environment is a simulator of stochastic vehicle routing with time windows, extended with stochastic job-shop scheduling under release and due windows. At episode start the simulator pre-samples every random duration and travel time, collectively $\xi$.
The actor sees only deployable information: current time, windows, and nominal duration estimates. It also receives an action mask computed by propagating the network with pessimistic duration bounds. This mask is identical across all compared methods, so the comparison isolates the critic.
The critic receives $G_t(\xi)$, the temporal network at step $t$ tightened by incremental shortest-path propagation under the true $\xi$. It carries three things: per-task earliest and latest start times, flags for tasks whose windows have become infeasible, and the dominance edges that propagation forces. A graph attention encoder turns $G_t(\xi)$ into a value $V_\phi(G_t(\xi))$, where $\phi$ are the critic's weights.
Propagation is incremental. Committing one task adds a few edges, and re-tightening costs about $O(n^2)$ for $n$ remaining tasks, avoiding a full Floyd-Warshall pass at each step. We will report this overhead in wall-clock time.
Conditioning a baseline on $\xi$ does not bias the policy gradient, provided the actor's action distribution does not depend on $\xi$ given its observation $o_t$. That condition holds because the actor never sees $\xi$:
$$ \mathbb{E}_{\xi,\,a_t\sim\pi_\theta(\cdot\mid o_t)}\big[\nabla_\theta \log \pi_\theta(a_t\mid o_t)\, V_\phi(G_t(\xi))\big] = \mathbb{E}_{\xi}\Big[V_\phi(G_t(\xi))\,\nabla_\theta \textstyle\sum_{a}\pi_\theta(a\mid o_t)\Big] = 0, $$
where $\pi_\theta$ is the actor with weights $\theta$ and $a_t$ is its action. There is one caveat. Durations that depend on the chosen schedule, for example machine-dependent processing times, are not exogenous. For those settings we will test whether revealing only already-committed durations preserves the gains.
The analysis side has three parts. First, we measure how many distinct critic inputs occur per episode under raw versus propagated encodings, as a direct count of state collapse. Second, we measure "credit latency": the number of steps between the decision that made a deadline unreachable (identified offline by exact propagation) and the step at which the critic's value drops sharply. Third, we measure policy-gradient variance and the critic's explained variance.
Baselines
The naive reference point is a symmetric proximal policy optimization agent. Its critic sees only the actor's observation, and it shares the propagation-based action mask. It shows what masking alone achieves. We also run REINFORCE with a rollout baseline, following Reinforcement Learning for Solving Stochastic Vehicle Routing Problem with Time Windows. That paper reports a 1.73% reduction in travel cost relative to ant colony optimization and about 0.416 seconds per 100-node instance versus 123 seconds for ant colony optimization. We rerun it in our simulator with the shared mask rather than quoting its numbers, since our window tightness differs.
The strongest learned competitor is the UP-AAC hindsight critic (Learning to Optimize Job Shop Scheduling Under Structural Uncertainty). We reimplement its critic as an encoder over the fully realized deterministic instance. On its own job-shop setting it reports a 1.94% gap to optimal on small and medium Taillard instances and stays within 0.18% of best-found solutions on larger ones. We use those figures only to check that our reimplementation is sane on its original task.
The ablation that isolates our key ingredient is a full-state asymmetric critic. It sees exactly the same privileged quantities as ours (clocks, windows, all of $\xi$) as raw features, with the same encoder size. We also run the same raw input filtered by residual-informativeness feature selection from Informed Asymmetric Actor-Critic.
All learned methods get the same environment steps, the same encoder parameter budget, and the same hyperparameter search of 20 trials each. Results are reported over 5 seeds.
On the classical side we run the rolling-horizon integer program from Rolling Horizon Based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows with a per-decision time limit. It serves as a quality ceiling, and we report its latency alongside.
Beating the full-state critic means two things. The first is statistically lower cost at equal feasibility on tight-window instances at 50 and 100 nodes. The second is reaching the full-state critic's final return in no more than about 60% of its environment steps.
Why not just…?
Why not just use action masking with an ordinary critic? The mask handles a problem we do not target. It keeps the actor from choosing an action that is infeasible now. It does not tell the learner which earlier feasible action made a later deadline impossible. We keep the mask in every arm, so the symmetric baseline measures masking alone. UP-AAC's reported advantage over symmetric critics under uncertainty suggests masking will not close the gap.
Why not just give the critic the full privileged state and let a big network learn propagation itself? This is the real threat. Propagation is a deterministic function of the raw state, and a large enough graph network could learn it. The full-state ablation with matched capacity settles the question. If raw and propagated critics tie across all tightness levels and instance sizes, the proposal fails. We predict they diverge as tasks and tightness grow, because the approximation cost identified in A Theoretical Justification for Asymmetric Actor-Critic Algorithms rises with the size of the state the critic must handle.
Why not just use the UP-AAC hindsight critic? Its input contains everything that happened after step $t$, but it never marks the step at which infeasibility became locked in. It must learn that implicitly, like the raw critic. Our credit-latency measurement directly tests whether that distinction matters.
Why not skip learning and use a classical solver? For offline instances a solver may win on quality. The rolling-horizon integer program raised the CARTA paratransit service rate from 77.7% to 85.6%. The case for learning is dispatch latency under stochastic durations, and we report both quality and latency so the reader can see the trade-off.
Proposed Experiments
The primary benchmark is the stochastic VRP-TW simulator of Reinforcement Learning for Solving Stochastic Vehicle Routing Problem with Time Windows, at 10, 20, 50, and 100 nodes. We add a time-window tightness knob adapted from Rethinking_Constraint_Tightness.
The secondary benchmark is Taillard job-shop instances with stochastic processing times and release and due windows, built on L2S. CARTA paratransit data serves as a real-data check against the rolling-horizon solver.
Metrics are travel cost or makespan, the fraction of tasks served within their windows, environment steps to reach a fixed return, critic explained variance, gradient variance, credit latency, distinct critic inputs per episode, and wall-clock propagation overhead.
The decisive check is the tightness sweep. The prediction is a gain over the full-state critic that grows monotonically as windows tighten and disappears at loose windows. The second check is credit latency: the propagated critic should drop in value within one step of the fatal decision, while the raw and hindsight critics should lag. If both checks come out flat, the representation offers nothing a large critic cannot learn on its own, and we will say so.
References
- Learning to Optimize Job Shop Scheduling Under Structural Uncertainty
- Generating Feasible Schedules under Complex Metric Constraints
- Temporal Scope of Assertions and Window Cutoff
- Efficient Temporal Planning Using Metastates
- Informed Asymmetric Actor-Critic: Leveraging Privileged Signals Beyond Full-State Access
- A Theoretical Justification for Asymmetric Actor-Critic Algorithms
- Reinforcement Learning for Solving Stochastic Vehicle Routing Problem with Time Windows
- Rolling Horizon Based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows