PaperlayerView exact revision on arXiv

Source-linked AI summary

From Prior-Guided Heuristics to Deployable Agents: Accelerating Demonstration-Driven Reinforcement Learning for Deadline-Constrained Network Control

Vincenzo Norman Vitale, Mohammad Solki, Antonia Maria Tulino, Andreas F. Molisch, Jaime Llorca

arXiv:2609.03590v1cs.NIcs.AI

TL;DR

Deadline-constrained network control needs urgency-aware congestion metrics and more sample-efficient learning than from-scratch DRL provides. The paper combines Effective Congestion, UPG, MADRL EC (p∗), and demonstration-driven MGA-RL. EC-based routing improves reliability by up to 40%, while MGA-RL cuts online interaction cost sevenfold versus from-scratch training.

  • Problem

    Volume-based congestion metrics overlook packet expiration and lifetime-dependent competition, while from-scratch MADRL has low sample efficiency and costly exploration for deadline-constrained control.

  • Method

    The framework combines urgency-aware EC metrics, UPG load balancing, MADRL EC (p∗), and GPR-derived MGA-RL initialized from an analytical prior policy.

  • Results

    Reliability gains reach 40% over traditional volume-based routing, while MGA-RL reduces online interaction cost by a factor of seven versus from-scratch training.

  • Takeaways & Limitations

    The framework provides an extensible, deployment-focused basis for deadline-aware routing with lower online interaction requirements.

  • Takeaways & Limitations

    The framework’s scalability on substantially larger, highly dynamic network instances remains open, and validating the p∗ complexity advantage at that scale is future work.

Abstract

from arXiv · show

Timely delivery of delay-sensitive information over dynamic, heterogeneous networks is essential for NextG interactive applications, yet providing strict End-to-End (E2E) peak latency guarantees remains an open challenge. Two obstacles limit the adoption of learning-based network control in this setting: traditional volume-based routing metrics, while highly effective for general traffic management, are not designed to capture traffic urgency; and Deep Reinforcement Learning (DRL) controllers trained from scratch suffer from sample inefficiency, long training times, and early-stage exploration volatility. This paper introduces a deployment-focused network control framework that addresses both obstacles. First, we present Effective Congestion (EC), a deadline-aware metric family that quantifies interface congestion by packet urgency and proactively filters non-viable traffic, coupled with a Uniform Path Grouping (UPG) distribution heuristic promoting robust load-balancing; the resulting policies are embedded into Multi-Agent Deep Reinforcement Learning Effective Congestion ($p^*$) (MADRL EC ($p^*$)), a hybrid architecture combining a distributed scheduler with a centralized RL-based router. Second, we introduce a unified training objective that generalizes existing policy-learning paradigms---behavioral cloning, offline Reinforcement Learning (RL), online RL, and offline-to-online schemes---as special cases, combining a live-reward term, a pre-collected-reward term, and a policy-imitation term. From this objective, we derive the Model-Guided Annealed Reinforcement Learning (MGA-RL) protocol, instantiated on a Deep Deterministic Policy Gradient (DDPG) backbone: a deployment-oriented, demonstration-driven training approach that generalizes conventional Offline-to-Online (O2O) schemes, in which trajectories from a lightweight [...]

1. Introduction

NextG interactive applications require deadline-aware network control because information loses value after application-imposed deadlines, while learning-based controllers face costly, unstable from-scratch exploration. The paper combines Effective Congestion and Uniform Path Grouping with a hybrid MADRL architecture and demonstration-driven MGA-RL training.

  • Motivation: RTI applications make strict E2E latency guarantees and urgent-traffic management central network-control requirements.Throughput maximization alone is insufficient when information loses value after application-imposed deadlines.
  • Motivation: From-scratch MADRL typically requires many interactions, causing low sample efficiency, long training times, and poor initial decisions.These properties hinder practical deployment.
  • Contributions: Effective Congestion filters expired or lower-priority packets under LELF scheduling, producing path- and urgency-aware interface congestion estimates.The approximate p∗ model reduces observation dimensionality to one value per interface with negligible accuracy loss.
  • Contributions: UPG balances traffic across comparable-weight paths, while UPG EC (p∗) achieves near-optimal reliability with lower state-space complexity than exact EC.The heuristic is designed to prevent localized hotspots caused by greedy assignment.
  • Contributions: MADRL EC (p∗) combines a distributed LELF scheduler with a centralized routing agent whose observations explicitly encode EC congestion.This makes urgency-aware congestion an explicit routing observation rather than only a queueing effect.
  • Contributions: GPR unifies behavioral cloning, offline RL, online RL, and offline-to-online learning, yielding MGA-RL with automatically annealed policy imitation.The analytical reference policy remains queryable in online states, while pre-collected rewards support Actor–Critic alignment during transition.
  • Empirical validation: Reliability improves by up to 40% over volume-based routing, while MGA-RL reduces online interaction cost sevenfold versus from-scratch training.The Vectorial EC representation matches or exceeds fully online reliability; Scalar trades some reliability for faster convergence and lower complexity.

2. Reinforcement Learning: Background

The paper frames network control as reinforcement learning in an MDP, where policies select actions from observed states to maximize expected cumulative reward. Because unknown dynamics and continuous high-dimensional spaces make exact value-based optimization impractical, it adopts an actor–critic DDPG backbone.

  • RL formulation: An MDP models an agent observing state s(t), selecting action a(t) under policy π, receiving reward r(t), and transitioning to s(t+1).The transition and reward distribution is represented by P(s(t+1) | s(t), a(t)).
  • RL formulation: The overarching RL objective is to discover a policy π∗ that maximizes expected discounted cumulative reward.Value functions and action-value functions characterize expected returns under a policy.
  • RL formulation: For finite stationary MDPs, an optimal deterministic policy can be obtained from the optimal action-value function Q∗.The policy selects actions by maximizing Q∗ without requiring an explicit policy representation.
  • Practical limitations: Unknown transition dynamics prevent closed-form Bellman backups, requiring learning from sampled transition tuples in the model-free setting.This limitation is relevant to real-world network control.
  • Practical limitations: Continuous, high-dimensional state–action spaces make tabular Q∗ representations and per-step maximization over actions computationally infeasible.These limitations motivate parametric actor–critic architectures.
  • Actor–critic backbone: The adopted DDPG backbone uses a parametric actor to output actions and a parametric critic to estimate their value.Both networks are updated from sampled mini-batches without requiring knowledge of transition dynamics.

3. Reward Estimation and the Actor–Critic Framework

This section replaces unavailable closed-form expectations with sample averages from live and pre-collected transitions, then combines reward maximization with policy imitation in an actor–critic framework. DDPG uses neural-network actor and critic functions to handle continuous, high-dimensional routing decisions without knowing transition dynamics.

  • Reward Estimation: Unknown transition dynamics require reward and Bellman expectations to be estimated from sampled transition tuples rather than evaluated in closed form.The work applies finite-sample averages consistently across reward terms and Bellman backups.
  • Reward Estimation: Live replay data tracks the evolving policy, whereas the fixed pre-collected dataset provides a stationary source of transitions from a reference policy.Mini-batches are sampled from the live buffer D(t) or fixed dataset Doff, with sizes N and M respectively.
  • Reward Estimation: Policy imitation minimizes discrepancy between the learned policy and the reference policy over the fully available pre-collected dataset.The policy-deviation estimator serves as a stable anchor distinct from live and pre-collected reward estimators.
  • Reward Estimation: The unified objective combines live reward, pre-collected reward, and policy imitation, thereby encompassing reward-maximization and imitation-based training paradigms.The three sample-average quantities are combined in the MGA-RL training objective.
  • Actor–Critic Framework: DDPG uses a neural-network actor to output actions and a neural-network critic to estimate value, avoiding tabular Q-functions and explicit maximization over continuous actions.Both networks are updated from sampled transition mini-batches without requiring knowledge of the transition kernel.

4. System Model

The system models a time-slotted directed network carrying latency-sensitive commodities with packet lifetimes, feasible paths, deadline-aware queues, and hybrid centralized routing with distributed scheduling. Effective lifetime tracks whether queued packets can still reach their destinations, while LELF prioritizes the most urgent packets.

  • 4.1. Network and service parameters: The network is a directed graph with time-slotted operation, link capacities, latency-sensitive commodities, and packet-specific maximum lifetimes.Packets with positive lifetime remain effective, while packets reaching zero lifetime are immediately dropped.
  • 4.1. Network and service parameters: Lower initial lifetime indicates greater latency sensitivity, and commodity arrivals are represented by stochastic source-node packet counts.Each commodity has an initial lifetime Lc and an associated arrival process bc(t).
  • 4.2. Network control variables: A centralized routing agent assigns feasible paths using global congestion information while distributed interface schedulers prioritize transmissions using local congestion and packet lifetimes.Candidate paths are feasible source–destination paths whose traversal time does not exceed the commodity’s initial lifetime.
  • 4.2. Network control variables: Flow, queue, and packet-dropping variables encode transmissions, interface backlogs, and intentional packet removal across commodities, lifetimes, links, and time slots.Packets are queued immediately at the outgoing interface associated with their assigned path, while expired packets and destination-reaching packets are removed from queues.
  • 4.3. Deadline-Aware Queueing Model: Effective lifetime measures how long a packet can wait before its assigned path can no longer deliver it, based on remaining lifetime and distance to the destination.It decreases during queueing but remains unchanged during link traversal, and packets are naturally dropped when it reaches zero.
  • 4.5. Lower Effective Lifetime First (LELF) Scheduler: LELF prioritizes packets with the lowest effective lifetime to maximize the total number delivered on time.An EL-driven network avoids retaining packets that no longer have a chance to reach their destinations.

5. Key Concepts for Effective Routing in Deadline-Constrained Systems

The section develops deadline-aware congestion measures that estimate only traffic likely to compete with a packet, while balancing state detail against computational cost. It introduces path-dependent and reference-path formulations for routing decisions.

  • Motivation: Volume-based congestion overlooks packet expiration and urgency, although low-effective-lifetime packets create stronger competition under LELF scheduling.This motivates representing congestion according to packet lifetime rather than queue volume alone.
  • Lifetime-aware representations: Lifetime Aware Congestion represents interface occupancy as a vector whose components count packets at each effective lifetime.The vector preserves urgency information but increases the state-space dimension and policy complexity.
  • Effective Congestion: Effective Congestion filters interface traffic to packets that survive the considered packet’s transit time and retain equal or higher LELF priority.The metric is path-dependent because the filtering range depends on the packet’s reference path.
  • Reference-path approximation: The EC p∗ formulation selects the path with minimum traversal distance to each interface and evaluates that interface once for all paths crossing it.This reduces evaluations from O(|P|) to O(|E|) and yields one congestion component per network interface.
  • State representations: Vectorial congestion preserves lifetime distributions, whereas scalar congestion reduces state complexity but hides whether queued packets are urgent or non-urgent.The scalar EC p∗ example sums [20, 21, 18, 15] to 74 packets, masking the queue composition.

6. Prior-guided Policies

The prior-guided policy family combines deadline-aware congestion metrics with greedy or grouped path assignment. UPG EC (p∗) combines balanced traffic distribution with the lowest state-space complexity among the proposed policies.

  • Policy dimensions: The policy family varies congestion type, assignment strategy, and resulting state-space dimension, progressing from regular congestion toward deadline-aware EC formulations.The five policies combine RC, EC p, and EC p∗ with minimum-weight or uniform-grouped assignment.
  • Minimum-weight policies: MWP RC computes capacity-normalized path weights from regular congestion and assigns packets to the lowest-weight path until capacity is reached.It then proceeds to the next-lowest-weight path when necessary.
  • Path-dependent EC policies: MWP EC (p) replaces volume-based weights with path-specific Effective Congestion over packets expected to compete along each candidate path.Its filtering uses remaining lifetime and transit time rather than total queue occupancy.
  • Uniform Path Grouping: UPG distributes packets uniformly across comparable-weight paths, capping allocations by the group’s minimum bottleneck capacity to reduce single-path over-utilization.The grouping procedure processes the lowest-weight group first and iterates over subsequent groups if packets remain.
  • UPG EC (p∗): UPG EC (p∗) combines UPG load balancing with EC p∗ computational scalability, pairing the lowest state-space complexity with balanced assignment.The policy is selected as the reference demonstrator for MGA-RL because of its reliability–complexity trade-off.

7. Policy Learning Paradigms and MGA-RL Framework

The section unifies behavioral cloning, offline RL, online RL, and offline-to-online learning through a common reward-and-imitation objective. MGA-RL then uses staged data availability and an adaptive imitation anchor to transition from demonstrations toward live experience.

  • Unified objective: The General Policy Reward frames behavioral cloning, offline RL, online RL, and offline-to-online schemes as coefficient-specific cases of one policy-learning objective.The objective combines live reward, pre-collected reward, and policy imitation signals.
  • Objective components: The framework weights live and pre-collected rewards with time-varying coefficients, while a replay-buffer-dependent imitation term anchors the policy to the reference demonstrator.The imitation weight remains important when live experience is sparse and changes as the live buffer grows.
  • MGA-RL protocol: MGA-RL uses a two-stage schedule: pre-collected data are used before live transitions accumulate, followed by mixed training after live interaction begins.The method implements the transition through piecewise-constant batch composition across stages.
  • Relation to prior methods: Unlike fixed-coefficient offline-to-online methods, MGA-RL uses continuous imitation-weight decay to avoid an abrupt phase boundary and adapts the policy anchor during training.The formulation also treats adaptive reward coefficients as a general extension of fixed-coefficient special cases.
  • Adaptive anchoring: MGA-RL decays the imitation weight with live-buffer growth to a positive floor and evaluates policy deviation over both offline and live states.The floor protects against residual out-of-distribution states under finite interaction budgets and incomplete coverage.

8. MGA-RL for Deadline-Constrained Routing

The section instantiates MGA-RL for deadline-constrained routing by combining a UPG EC (p*) demonstrator, centralized routing, distributed LELF scheduling, and an annealed imitation-to-reward objective. Its DDPG implementation stabilizes transfer with scale normalization, SymLog targets, buffer-dependent imitation weighting, and frozen input statistics.

  • System instantiation: MGA-RL uses UPG EC (p*) as its analytical reference policy and applies the protocol to the centralized RL router within MADRL EC (p*).Distributed LELF scheduling remains part of the control structure, while MGA-RL trains only the centralized router.
  • DDPG updates: The DDPG implementation uses mixed batches containing live and offline data, while α(t) and β(t) are determined automatically once the batch-size design parameters are fixed.The TD target uses the raw sampled reward; the generalized reward appears at the aggregated critic-loss level.
  • Unified objective: The unified objective combines live rewards, pre-collected rewards, and a policy-deviation penalty, with additive actor-gradient terms and critic updates based only on the reward component.The imitation anchor is directly differentiable because the reference policy is queryable, whereas live-reward optimization requires critic-based value estimation.
  • Stabilization mechanisms: Q-value normalization makes λ an interpretable relative weight between reward maximization and imitation despite changes in reward magnitude.This avoids the RL gradient overwhelming the bounded behavioral-cloning term and preserves a gradual transition rather than a hard switch.
  • Stabilization mechanisms: The Anchored Transfer Stabilisation Protocol combines a residual imitation floor, SymLog TD targets, and offline-derived frozen state normalization.SymLog compresses sharp deadline-induced reward discontinuities, while frozen statistics avoid input distribution shift during online transfer.
  • Relation to RLfD: MGA-RL integrates a deterministic lightweight demonstrator, grouped-Softmax flow conservation, and deadline-constrained traffic engineering into an RLfD pipeline.The paper positions this combination as distinct from prior RLfD work concentrated largely in robotics.

9. Experimental Setting

The experiments evaluate the methods on hierarchical, asymmetric backbone, and symmetric mesh topologies with progressively different structural complexity. Training and routing configurations are designed to test deadline-aware control across varied loads, path diversity, and flow-conservation constraints.

  • Test topologies: The study compares Hierarchical, Abilene, and Grid 3 × 3 topologies to evaluate routing under progressively increasing structural complexity.The three regimes represent hierarchical concentration, backbone asymmetry, and symmetric path diversity.
  • Hierarchical topology: The Hierarchical topology models edge computing with a Core Cloud destination, Edge Cloud and Far Edge nodes, and peripheral IoT sources.Its tree-like organization has diameter 3 hops and relatively clear routing preferences.
  • Abilene topology: Abilene models a real-world backbone with two sources reaching a shared destination through asymmetric paths, heterogeneous centralities, and bottlenecks.It has 16 paths for one commodity, 12 for the other, graph diameter 5 hops, and clustering coefficient 0.15.
  • Grid 3 × 3 topology: Grid 3 × 3 represents a regular mesh with cross-diagonal traffic, 12 paths per commodity, overlapping central regions, and zero clustering coefficient.Its equivalent routing alternatives create a homogeneous but difficult exploration environment.
  • Experimental parameters: Experiments stress the methods with loads ranging from 30% to 120% of Min-Cut Capacity and Poisson packet arrivals across topology-specific lifetime settings.Table 4 defines interface subsets, path counts, capacities, arrival rates, and suggested packet lifetimes.
  • RL architecture: The grouped-Softmax actor partitions logits by commodity and normalizes each group independently, ensuring routing probabilities sum to 1 for every commodity.The final action vector concatenates the commodity-specific probability subvectors.

10. Numerical Results

Across hierarchical, asymmetric, and grid networks, EC-based and UPG-based policies improve reliability under tight deadlines and heavy load, while MGA-RL reduces the cost and instability of learning from scratch. The results also show that the value of approximation and bootstrapping depends on topology and deadline regime.

  • Topology-specific results: On the Hierarchical topology, UPG-based policies exceed 80% reliability under the tightest deadline, while MWP RC drops by over 40% relative to EC policies at b = 24.The topology’s structure lets Scalar MGA-RL avoid severe aliasing and reach performance comparable to fully online training in less time.
  • Topology-specific results: At Abilene’s Min-Cut Capacity, balanced assignment has an approximately 15% reliability advantage over greedy assignment under L = 5.The asymmetric backbone also shows that a restrictive prior can hinder exploration under the strictest deadlines, although its bootstrap value emerges as deadlines relax.
  • Topology-specific results: Under Grid L = 4, the p* approximation has an approximately 36% reliability gap versus exact path-dependent UPG EC (p), while EC-based routing remains over 20% ahead of MWP RC at L = 7.At L = 10 and b = 27, EC p* and EC p cluster around 85% and 65% reliability, respectively.
  • Cross-topology observations: EC-based routing achieves relative reliability gains from 20% to over 40% over traditional congestion routing near saturation and under tight deadlines.Urgency-aware filtering prevents expiring packets from inflating congestion estimates and reduces localized drops.
  • Cross-topology observations: UPG EC policies consistently provide the highest stressed reliability, with peak gains of up to 40% over the MWP RC baseline.UPG combines EC filtering with distribution across comparable paths, mitigating greedy localized hotspots.
  • MGA-RL results: MGA-RL reduces online interaction cost by a factor of seven relative to from-scratch training while preserving competitive reliability across congestion-state representations.Both Vectorial and Scalar agents improve stability and training time, especially on the exploration-challenging Grid topology.

11. Conclusions and Future Directions

The paper combines deadline-aware congestion metrics, balanced path assignment, and demonstration-driven learning to improve deployable routing for latency-sensitive networks. Results show reduced complexity or interaction cost, while larger-scale validation and component ablations remain open.

  • Conclusions: EC metrics and UPG provide a computationally efficient basis for deadline-aware routing, with reliability gains of 20% to over 40% over volume-based routing.EC filters non-viable packets, while UPG balances spatial loads and mitigates localized hotspots.
  • Conclusions: The decoupled p* approximation reduces per-step evaluation cost from O(|P|) to O(|E|) while preserving the filtering benefits of exact EC p.It matches or exceeds exact-model reliability on Hierarchical and Grid topologies as deadlines relax, but trails by a few percentage points on Abilene.
  • Conclusions: MGA-RL uses UPG EC (p*) demonstrations for offline pre-training and online fine-tuning, matching or exceeding fully Online reliability while reducing online interaction by a factor of seven.A residual behavioral-cloning regularizer and Anchored Transfer Stabilization support the offline-to-online transition.
  • Conclusions: Scalar observations train faster but can suffer state aliasing, whereas Vectorial observations preserve urgency distributions and support the highest reliability among scalable RL configurations.Large state spaces combined with limited training budgets can still cause sporadic Vectorial degradations.
  • Future Directions: Future work includes testing larger, highly dynamic networks, exploring GNN architectures, ablating Anchored Transfer components, and studying sensitivity to the Stage-1/Stage-2 transition point.The transition point can affect Actor-Critic convergence and misalignment during offline training.

Appendix A. Spatial Drop Rate Distribution

The appendix complements macroscopic reliability results with a microscopic analysis of where packet expirations occur across interfaces. It compares spatial distributions under controlled near-capacity settings and uses two complementary visual representations.

  • Analysis Setup: The appendix analyzes packet-expiration locations at an arrival rate equal to 90% of Min-Cut capacity, with lifetimes sufficient to activate all candidate paths.This setup attributes policy differences to routing decisions rather than infeasibility.
  • Analysis Setup: Spatial drop distributions are represented using two complementary views across the evaluated network topologies.

Appendix A.1. Prior-guided Policies

The prior-guided policy analysis shows that volume-based routing concentrates expirations at structural bottlenecks, whereas EC-guided policies distribute drops more evenly across the network.

  • Prior-guided Policies: MWP RC systematically concentrates expirations on shortest-path bottlenecks because its volume-based metric cannot distinguish viable from expiring traffic.Reported bottlenecks include link 4-5 in Hierarchical, link 2-5 in Abilene, and the central Grid crossbar.

Appendix A.2. RL-based Policies

The RL-based spatial analysis contrasts congestion representations and training paradigms, finding that EC p* with Vectorial observations and MGA-RL produces the cleanest and most balanced drop profile.

  • RL-based Policies: RC- and LAC-based agents leave residual scattered drops, while EC p* agents better discriminate packet urgency.
  • RL-based Policies: The appendix provides spatial distributions for prior-guided and DDPG-based approaches across Hierarchical, Abilene, and Grid topologies.
  • RL-based Policies: EC p* + Vectorial + MGA-RL minimizes both peak drop rate and spatial variance, supporting its selection as the recommended framework instantiation.
  • RL-based Policies: MGA-RL Vectorial agents inherit spatially balanced UPG EC (p*) behavior and refine it during expressive online fine-tuning.

Appendix B. Notation Table

Appendix B provides a table of notations.

  • Table B.1 is a table of notations.
  • The appendix identifies Table B.1 as the notation table.
  • The notation reference appears in Appendix B.
Loading 2609.03590v1…