PREPRINT — SUBMITTED FOR PEER REVIEW
1
Learning Selective Merge Policies for Deadline-Constrained Coded Caching via Deep Reinforcement Learning
arXiv:2605.15236v1 [cs.IT] 13 May 2026
Amirhossein Yousefiramandi
Abstract—With the coded caching, the server can use the information the users have cached to serve multiple users at a time by sending a single coded multi-casting message, i.e., the merged message, thereby relieving the peak network loads. However, for the delay-sensitive applications of the users, like the video streaming services, it becomes essential to choose which messages to merge online, considering the strict deadlines for each request. The problem, however, is that while the merge is helpful for the formation of the current coded multi-casting message, it can be harmful for the subsequent ones. We proposed a DRL-based solution that formulates the deadline-constrained coded delivery as a masked discrete-action queue-state control problem, while we trained a graph-attention policy network via proximal policy optimization. The policy network reduces the broadcast-packet expiration ratio ρ by 40.9% (0.208 vs. 0.352) with respect to the best coded multi-casting baseline (SACM++) on the uniform-demand benchmark, while also attaining the best broadcast-efficiency score σ across the Track A battery among the coded multi-casting methods. The interesting fact we observed is that for the applications of the users with tight deadlines, the method of selective merging is better than the method of aggressive merging, i.e., the policy network learns to merge at only ≈ 31.8% rate, even though the same observation holds across the variations within the same simulator family. Index Terms—Coded caching, deadline-constrained scheduling, deep reinforcement learning, graph attention networks, action masking.
N OTATION TABLE I N OTATION USED THROUGHOUT THE PAPER . Symbol System Parameters K B pc Q H
Description
Symbol
Description
Number of edge caches (users) Subfiles per file Cache fraction (M =⌊pc F ⌋ packets per cache; pc F is integer in all evaluated regimes) Pending-queue depth Episode horizon (steps)
N F =N B Ck D Pmax
Number of files in library Total packets Cached packets at user k Maximum deadline (slots) Max candidate merge pairs = Q 2
Control Model & Actions r=(kr , fr , dr , Sr ) Request tuple kr Dest. of fresh r; for aggregates, the representative kmg (Eq. (6)) dr Remaining deadline of r κ Keep-side decision γ Discount factor Evaluation Metrics (Sec. V-D; auxiliary bookkeeping in Sec. III-C0f) Ut XOR degree at slot t (packet-set count) ρ Broadcast-packet expiration ratio (Eq. (27)) σ Broadcast-efficiency score (Eq. (29)) ε Expirations per episode (Eq. (32)) A(r) Per-arrival ID annotation (evaluator bookkeeping; Sec. III-C0f) Ct , M t Per-step completed / missed request IDs (Eqs. (11), (12)) ηreq Request timely-throughput (per-step; Eq. (34)) σreq Request selection score (per-step; Eq. (36))
Mt fr Sr mt
Feasible merge set at step t Packet set of r: singleton at arrival, union fmg after merges Side-info providers of r Action mask vector
Et δ µ Xt ϕ
Expired packet-set mass at slot t Distinct file-identity coverage (Eq. (28)) Served packet-set / tx (Eq. (30)) Expiration-event set at t (Eq. (18)) Packet→file projection (Eq. (7))
mreq λ
Request miss rate (per-step; Eq. (35)) Miss-penalty weight in σ/σreq
Note. σ (broadcast-efficiency score) and σreq (request selection score) are distinct metrics computed at different aggregation levels (broadcast/packet-set vs. per-arrival); the req subscript is load-bearing.
I. I NTRODUCTION LOBAL mobile data traffic continues to grow at a compound annual rate of approximately 20% [1], thereby placing severe pressure on the last-mile link between the edge nodes and the users, while the edge caching alleviates this bottleneck [2], considering that the conventional schemes exploit only the local cache contents. With the coded caching [3], [4], the server can use the information the users have cached to serve multiple users at a time by sending a single coded multicasting message, i.e., the merged message, thereby relieving
G
the peak network loads while satisfying multiple users at a time by a single coded broadcast. The coded-caching framework of Maddah-Ali and Niesen [3] and its decentralized extension [4] formalize this XOR-multicasting principle, i.e., the formation of the coded multi-casting message from the cached side information, while Section II provides a detailed review. The classical coded-caching schemes were designed for a synchronous, batch-delivery model in which all requests are collected before any transmission begins, an assumption that is incompatible with the delay-sensitive streaming applications of the users, like the video on demand, the interactive augmented reality, and the cloud gaming, where each user request carries a hard deadline by which it must be delivered or it becomes worthless. Niesen and Maddah-Ali quantified the gain–delay tradeoff, showing that the larger coding gains require aggregating more requests over longer time horizons, at the cost of higher per-request delivery delay [5]. In an online delivery setting with hard per-request expiration deadlines, this tradeoff becomes a sequential decision at every time step, considering that the server must either merge a feasible pair of pending requests into a coded XOR packet, thereby yielding an immediate bandwidth reduction while consuming the shared side information and shrinking the intersection available for future merges, or fall back to the unicast, i.e., serving the earliest-deadline request to protect against the expiration while forgoing the multicast gain. The problem, however, is that while the merge is helpful for the formation of the coded multi-casting message, it can be harmful for the subsequent ones: the best action depends on the entire queue state, i.e., the remaining deadlines of all the pending requests, their file identities, which of the users have cached which of the files, and how merging now will reshape the feasibility of the future merges, and no closed-form policy captures this dependence in general. The existing algorithms do not address this deadline-aware online setting, considering that the greedy and the size-aware coded multi-casting heuristics (GCM [3], SACM [6]) always merge whenever any feasible pair exists, irrespective of the deadline urgency of the users (see Section II for a detailed review), while the graph-coloring approaches [7], [8] are likewise stateless with respect to the deadlines, and even the fixedthreshold policies (τ -Fit), which merge only when both of the remaining deadlines exceed a parameter τ , require oracle tuning, cannot adapt to the current queue state, and saturate in performance (as we show in Section VI). What is needed is a state-dependent merge-or-defer policy, i.e., the policy network, that learns when to exploit a coding opportunity and when to fall back to the unicast, thereby balancing throughput and
PREPRINT — SUBMITTED FOR PEER REVIEW
deadline compliance from experience. The reinforcement learning (RL) is a natural framework for learning such a state-dependent policy from the interaction, considering that the prior RL work on caching has focused on placement and replacement, i.e., deciding what content to pre-fetch or evict under time-varying demand [9]– [11]. The most closely related work is Naderializadeh and Asghari [12], who train a deep actor–critic agent for codedcaching delivery and demonstrate that the learned policies can match the SACM-family heuristics while reducing the online inference cost. However, that work does not model the hard expiration deadlines, uses a flat multilayer-perceptron (MLP) policy that ignores the graph structure of the mergeability relation, omits the invalid-action masking, and evaluates a single configuration without out-of-distribution (OOD) generalization analysis, while our work directly and systematically addresses all four of the gaps. Effective learning here requires three ingredients: (i) invalid-action masking [13], [14] to restrict policy-gradient updates to feasible XOR merges; (ii) a graph attention network [15] that exploits the variable-cardinality merge-graph structure with parameter-sharing across pairs and a relational inductive bias, avoiding a flat monolithic parameterization of all pairwise relations (although the worstcase O(Pmax ) = O(Q2 ) pair-construction and edge-MLP cost still applies; see Sec. IV-A, Appendix K); and (iii) behaviorcloning warm start and Expert Iteration [16], [17] to bootstrap from heuristic demonstrators and then exceed them. In this paper, we proposed a deep RL framework for the deadline-constrained coded caching delivery in a decentralized random-prefetching model, while providing an empirical evaluation across multiple baselines, holdout seeds, and nonID regimes (curriculum-seen and unseen-parameter; detailed in Section V, where “OOD-” is used in the narrow withinfamily sense of unseen parameter values, i.e., the parameter values never seen during the training of the policy network). In the uniform-demand benchmark, our σ-selected checkpoint, i.e., the policy network picked by the robust-advantage rule on BE-score σ at the validation (see Sec. IV-F), achieves the lowest broadcast-packet expiration ratio ρ among all of the coded multi-casting methods, reducing ρ by 40.9% (0.208 vs. 0.352) with respect to SACM++ (the paired-bootstrap effect sizes in Table VIII; the uncoded ED-Unicast baseline still attains a lower ρ of 0.134 by forfeiting all coding gain, so the “lowest ρ” headline is explicitly scoped to the coded multi-casting methods), while also attaining the best broadcastefficiency score σ among the coded multi-casting methods across the full Track A battery (and the best overall σ in 7 of 8 Track A regimes; ED-Unicast leads on σ at OOD-delay10), along with a substantially lower per-step request miss rate mreq than the SACM++ comparator (the only baseline in the main-text request-level table) on Track A, even though EDUnicast remains the best deadline-protection baseline on mreq in the paired-bootstrap analysis (Table VIII: ∆mreq = +0.074 for PPO minus ED-Unicast at ID-default, i.e., PPO is worse than ED-Unicast on this metric), so the broader “lower than all coded baselines” statement is confined to the SACM++ comparison while the GCM, SACM, SACM+, and τ -Fit extension is left as future work. The cross-track BE-score
2
picture is more nuanced and is reported separately for the Zipf benchmark in Section VII. The policy network also exhibits a selective merge strategy, i.e., the method of selective merging, a qualitative behavior not reproducible by any fixed-threshold heuristic. a) Modeling abstraction for unicast slot cost.: We adopted a one-slot-per-record service model, i.e., each transmission consumes exactly one slot, whether it is a coded XOR broadcast over a packet union fmg or a unicast of a codingstate record, so that a unicast that resolves an aggregate record (built up from multiple merges) costs the same slot budget as a unicast of a singleton, while the XOR pathway uses an equal-length packet model and the one-gap invariant of Appendix H for the decodability, and the unicast pathway uses the record-level cost abstraction. We document this choice considering that it determines the throughput–deadline tradeoff the policy network optimizes, i.e., a packet-level unicast cost scaling with |fr | would change both the simulator and the reported gains. The abstraction is reflected in the broadcastlevel metrics (Ut = 1 for any unicast, regardless of |fr |), while the request-level metrics (ηreq , mreq , σreq ) provide a complementary view that credits each original arrival exactly once. We evaluate the learned policy along four metric families that use three different notions of demand: (i) broadcast-level deadline compliance (ρ: the fraction of broadcast-level packetset mass that expires before delivery, measuring channeluse waste); (ii) distinct file-identity coverage (δ: distinct fileidentity coverage among the resolved (served or expired) identities under the H=50 in-episode horizon (Eq. (28)), which conflates all packet arrivals for the same file into a single coverage event, not a measure of multi-packet demand completion, and subject to episode-end right-censoring of identities still pending at step H); (iii) request-level accounting (ηreq , mreq , σreq , computed from per-arrival identifiers stamped at arrival time), which tracks each original arrival through queue aggregation and credits completion or miss exactly once per request identifier; and (iv) broadcast efficiency (σ), a per-slot composite that rewards XOR degree and penalizes expirations. We anchor our central claims on the primary demand-centric metrics (ρ at the broadcast-packet level and δ at the fileidentity level; both are formally defined in Sec. V-D, while “demand-centric” is a name-only umbrella, i.e., not a perarrival semantic claim), considering σ as a broadcast-efficiency diagnostic and the request-level family (ηreq , mreq , σreq ) as supplementary metrics whose full-baseline coverage we leave as future work. The main contributions of this paper are: 1) C1: Deadline-sensitive queue-state control with masked combinatorial actions. We proposed a Gymnasium-compatible masked discrete-action queuestate control formulation for the deadline-constrained coded caching, trained as a stationary policy under a discounted truncated continuing-control surrogate (Sec. III-F5), while the formal model is a contextual POMDP (Definition 1), i.e., the “masked-MDP” language used elsewhere is shorthand for this surrogate. The state encodes a finite pending queue of Q requests,
PREPRINT — SUBMITTED FOR PEER REVIEW
each annotated with target-cache identity (one-hot), sideinformation provider flags, normalized remaining deadline, packet-set size, and merge degree. The discrete ac tion space tracks up to Pmax = Q 2 = 45 feasible merge pairs, while each pair admits two keep-side choices, thereby yielding up to 2Pmax coded actions (where the keep-side decision controls which queue slot is freed for replenishment by a fresh arrival), plus a deterministic unicast fallback that always serves the earliest-deadline request (2Pmax + 1 = 91 actions total), so that the policy network learns which merge pair to execute and which side to keep, or whether to defer to the earliestdeadline unicast, considering that it does not select individual unicast targets, while the dynamic feasibility masking enforces hard constraints at every step. The reward combines a system-aligned Ut − Et base term, a quality bonus on coded merges (intersection-size reward minus union-size penalty), and a merge-potential shaping term [18] based on the fraction of currently feasible queue pairs Φ(s) = |M(s)|/ Q 2 , inspired by potential-based shaping [18]; the formal invariance theorem applies to an idealized fully observed continuing-state MDP, while in our implemented contextual-POMDP surrogate (truncated at H=50, hidden episode cache placement, aliased aggregate observations) the shaping term is best read as heuristic credit-assignment guidance rather than as a guarantee of optimal-policy preservation. This formulation jointly captures the decentralized cache diversity, the multiple concurrent outstanding requests, the hard perrequest expiration deadlines, the keep-side control, and the dynamic invalid-action masking, while to the best of our knowledge (after the literature sweep summarized in Section II and Table II), this specific combination has not previously been integrated in a single RL delivery formulation, even though closely related ingredients exist in adjacent settings, i.e., the claim should be read as a positioning statement rather than as a definitive nonexistence result. 2) C2: Graph-attentive MaskablePPO policy network. We proposed a graph-structured policy network, i.e., the policy network, a structured actor–critic architecture that treats the pending request queue as a node-attributed graph and the candidate merges as the edges, while a twolayer, four-head graph self-attention module [15] builds contextual node and edge representations, considering that the shared edge MLPs then score all (pair, keep-side) actions jointly. This design captures the combinatorial interaction among merge candidates through message passing with shared per-pair parameters, replacing a flat monolithic parameterization of all pairwise relations by a relational encoder (without eliminating the worst-case O(Pmax ) = O(Q2 ) pair processing intrinsic to scoring all candidate merges; see Sec. IV-A, Appendix K). The policy is trained via Maskable Proximal Policy Optimization (MaskablePPO) [14], [19] with Generalized Advantage Estimation [20], and feasibility is enforced at every policy-gradient step through the action mask. 3) C3: Rollout-improved behavior cloning and ExIt-style
3
online distillation. To handle the sparse rewards and the hard exploration in the early training stages, we adopted a three-phase pipeline, i.e., (i) a behavior-cloning warm start from a rollout-improved heuristic teacher, (ii) valuenetwork pre-training to calibrate the critic before the policy updates, and (iii) MaskablePPO fine-tuning with ExIt/DAgger-style online dataset aggregation [16], [17] and a progressive curriculum that increases the task difficulty [21], while the full training details are provided in Sections IV and V, considering that this pipeline lets the policy network first replicate, and then exceed, its heuristic teachers. 4) C4: Comprehensive evaluation and out-of-distribution generalization. We evaluated the policy network against the baselines covering three strategy families, i.e., the conservative uncoded unicast, the aggressive coded multicasting, and the oracle-tuned threshold policies, under the holdout evaluation (Section V). In the uniform-demand benchmark (Track A), under the simulator conventions of Sec. III-F (notably the one-slot-per-record unicast cost abstraction (A2) and the uniform representative-destination convention kmg ∼ Unif{ki , kj } of Eq. (6), both flagged as first-order limitations in Sec. IX), our σ-selected checkpoint reduces the broadcast-packet expiration ratio ρ by 40.9% (0.208 vs. 0.352) and expired-record count per episode (ε) by 50.7% relative to SACM++, the highestthroughput coded-multicast baseline (and the heuristic teacher used in BC/ExIt training); on Track A it also achieves the highest σ among coded-multicast methods across all 8 Track A regimes (and the highest overall σ in 7 of 8 Track A regimes; ED-Unicast leads on σ at OOD-delay10 at 0.019 vs. PPO’s −0.002). Full metrics are in Section VI; on the ID-default uniform table at ρ = 0.345, GCM and SACM tie for the lowest broadcast-packet expiration ratio among coded baselines, and both are reported alongside SACM++ in the permetric ranking tables. On the Zipf-demand benchmark (Track B) the cross-method BE-score lead does not transfer: ED-Unicast tops σ overall, and SACM, SACM+, GCM also exceed PPO on σ at Zipf ID-default; see Section VII. The policy network learns a qualitatively different policy, i.e., a selective merge strategy, that defers to the earliest-deadline unicast to protect the deadlines while reserving the coded transmissions for the merge opportunities where the side-information intersection is genuinely beneficial. The interesting fact we observed is that these gains transfer across the full Track A nonID battery (2 curriculum-seen and 5 unseen-parameter regimes covering the unseen cache fractions and the deadline budgets, along with the parameter-invariance sweeps over the file count under fixed per-packet caching probability pc , all within the same simulator family), with the advantages often growing under the high-stress conditions, even though all transfer experiments keep K, Q, the action dimensionality, and the placement family fixed, so these results demonstrate the withinfamily parameter generalization rather than the broad architectural out-of-distribution robustness. In an extension
PREPRINT — SUBMITTED FOR PEER REVIEW
study (Section VII), a separately trained popularity-aware variant remains competitive with the coded multi-casting baselines across 11 additional Zipf-demand regimes. The remainder of the paper is organized as follows. Section II reviews related work. Section III presents the system model. Sections III-F–IV detail the contextual-POMDP formulation and the training pipeline. Sections V–VI report the experimental setup and the uniform-demand results. Section VII presents the Zipf-demand extension. Section VIII reports the full ablation analysis. Section IX concludes. II. R ELATED W ORK A. Coded Caching: Foundations and Decentralized Placement The coded-caching framework of Maddah-Ali and Niesen [3] showed that the server can achieve a global caching gain scaling with the number of users K by exploiting the cached side information for the XOR multicasting, while the decentralized extension [4] removed the need for the coordinated prefetching, i.e., each cache independently stores the subfiles i.i.d. at rate pc , and the server uses the resulting random overlaps for the coded transmissions, thereby achieving an order-optimal memory– rate tradeoff. The mechanism is the XOR multi-casting, i.e., if user 1 requests file A and user 2 requests file B, and each has pre-cached the other’s file, the server broadcasts A ⊕ B, thereby letting each user cancel its cached file to recover the requested one, while this gain generalizes to larger cliques of the users with overlapping side information. The decentralized random-prefetching model is the placement strategy we adopt, while Pedarsani et al. [22] extended the framework to the sequential demand arrivals, characterizing the achievable rate regions when the server dynamically decides how to group the requests, i.e., a step toward the streaming delivery setting we consider. Our work builds directly on this decentralized model, but departs from it in two ways, i.e., (i) we introduce the hard per-request expiration deadlines absent from [4], [22], and (ii) we made the keep-side decision an explicit learned action dimension controlling the queue composition across the time slots, rather than the hand-designed endpoint-retention rule that the earlier coded-caching heuristics use, like the degreeaware endpoint retention of SACM+/SACM++ (the ablation in Appendix R). To our knowledge, the prior coded-caching work treats the keep-side as a fixed heuristic rather than as an action exposed to a deadline-aware RL scheduler with the invalid-action masking, while we read this as a positioning statement rather than as a definitive non-existence result. B. Coded Delivery Algorithms and Complexity With arbitrary cache contents, the optimal coded delivery reduces to an NP-hard clique-cover problem on the sideinformation graph [6], while the polynomial-time approaches include the graph-coloring-based schemes for specific graph structures (GCLC [7]) and the heterogeneous-link extensions (HgLC [8]), both reporting substantial coding gains in the deadline-free settings.
4
For the general decentralized case, Asghari et al. [6] provided an O(log K)-approximation polynomial-time algorithm under their model assumptions, i.e., the Size-Aware Coded Multicast (SACM) family, including the enhanced SACM+ and SACM++ variants with the degree-aware keep-side selection. We adopted SACM++ as the principal heuristic teacher for the BC and ExIt training considering that it achieves the best served-per-transmission throughput in our deadlineconstrained simulator, while we do not claim SACM++ is the best per-metric across all evaluated criteria, and indeed SACM has a lower miss ratio than SACM++ on the ID-default uniform table (Sec. VI). All of the SACM variants and GCM maintain a 100% merge rate, i.e., whenever any feasible merge exists, they execute it. Despite the strong coding-gain guarantees, all of these algorithms are stateless greedy rules, i.e., they do not account for the remaining deadlines, the effect of the current merge on the future queue composition, or the long-horizon consequences of consuming the shared side information prematurely, while the policy network, i.e., a learned policy that internalizes these future-state effects, could in principle select high-quality pairs selectively rather than merging every feasible candidate, and we test this hypothesis in Sections VI–VIII. C. Delay-Sensitive and Online Coded Caching Niesen and Maddah-Ali [5] characterized the gain–delay tradeoff, i.e., achieving the large coding gains requires aggregating many of the requests, which is in tension with the hard per-request deadlines, while Pedarsani et al. [22] extended this analysis to the online settings with the sequential arrivals and the rate-delay tradeoff regions, even though both of the works operate at the information-theoretic level and do not produce concrete scheduling policies for the streaming queues with the hard deadlines. Several recent works have addressed the asynchronous and the time-varying aspects of the coded caching, considering that Jiang et al. [23] proposed a decentralized asynchronous coded caching scheme for fog radio access networks, providing both synchronous and asynchronous transmission methods for different delay requirements with closed-form fronthaulload expressions, while Zhang and Tao [24] applied deep learning to the wireless coded caching under the unknown and time-variant content popularity, thereby optimizing the cache placement via LSTM-based popularity prediction and a supervised deep deterministic policy gradient. Like our method, this work uses neural networks in the coded-caching pipeline, even though it targets the placement rather than the delivery phase. Amir et al. [25] studied the coded caching with the time-varying file popularities and the asynchronous delivery, designing schemes that exploit the delivery messages to proactively update the user caches, while Yang et al. [26] formulated the optimal scheduling for the asynchronous coded caching, thereby deriving the rate-optimal delivery schedules when the user requests arrive at different times with prescribed deadlines. These works advance the understanding of the asynchronous and non-stationary coded caching, even though none of them formulates an RL-based delivery scheduler that
PREPRINT — SUBMITTED FOR PEER REVIEW
jointly handles the hard per-request expirations, the keepside control, and the dynamic invalid-action masking, i.e., the specific gap our work addresses. A remaining gap is the absence of an operational scheduling policy that can be deployed online under the hard deadline constraints, considering that to the best of our knowledge, no prior RL delivery formulation models the following combination as a single integrated learned scheduler, i.e., (i) a finite queue of pending requests each with a different remaining deadline, (ii) the XOR feasibility that depends on the current cache state, (iii) a keep-side decision exposed as a learned action (rather than a hand-designed endpoint rule as in SACM+/SACM++) that dynamically reshapes the queue composition, and (iv) the immediate replacement of the expired requests by the fresh arrivals, while our contextual-POMDP formulation in Section III-F addresses this gap, thereby enabling deep RL training at scale. D. Reinforcement Learning for Caching Systems The reinforcement learning has been extensively applied to the cache placement and eviction, i.e., deciding what content to store, rather than to the delivery scheduling, while the representative examples include the PPO-based cache replacement under the dynamic pricing [9], the Q-learning for the proactive caching in the wireless networks [10], the deep RL for the joint caching and user scheduling [11], and the survey by Liu et al. [2] covering 30+ RL-based caching approaches. A shared limitation of these placement-focused works is that they treat the coded delivery as a black box, i.e., the delivery phase is assumed to be simple unicasting, with no scheduling decisions over the structured XOR merge candidates, while our work is entirely in the delivery track, taking the decentralized random placement as given, i.e., a complementary contribution to the placement-focused RL literature, considering that the joint placement–delivery optimization is identified as a future direction in Section IX. E. RL for Coded Delivery, Graph-Attentive Scheduling, and Training Techniques RL for coded delivery. The most directly related prior work is Naderializadeh and Asghari [12], who trained a deep RL agent for the coded caching delivery under arbitrary decentralized cache contents, considering that their actor-critic policy (flat MLP) scores the candidate merge pairs at each step and learns to form the coded transmissions that match or slightly outperform SACM while reducing the online inference complexity, i.e., this work shows that the RL is a viable approach for the coded delivery problem. Our work differs from [12] in four respects, i.e., (i) Hard per-request deadlines. [12] uses a soft delay penalty but does not model the hard expiration deadlines, even though in our setting, an expired slot is refilled immediately, thereby producing the non-stationary feasibility dynamics. (ii) Graph-attentive policy architecture. Their flat MLP encodes all of the pair features into a fixed-length vector,
5
thereby losing the relational structure, while our graphstructured policy network, i.e., the policy network, treats each request as a graph node and each feasible merge as an edge, applying two-layer graph self-attention before scoring the actions. (iii) Invalid-action masking. [12] does not employ the action masking, so the policy gradient wastes capacity on the infeasible actions, while our MaskablePPO formulation masks the infeasible actions at both the sampling and the gradient computation. (iv) Evaluation scale. [12] evaluates a single configuration against few of the baselines without OOD analysis [27], [28], while we evaluate against 9 Track A baselines + PPO (10 unique methods) across 50 holdout seeds × 200 episodes and 7 non-ID conditions, plus a mainbody Zipf-demand extension study (Section VII) covering 11 additional regimes. Architectural and training building blocks. Our method draws on several established techniques, each adapted to the coded-caching setting, considering that the graph attention networks [15] provide the inductive bias for the variablesize, relationally structured inputs, i.e., here, the pendingrequest queue is a node set with the XOR-feasibility edges, while the invalid-action masking [13] is theoretically justified and empirically necessary when up to 90 of 91 actions may be infeasible at a given step (i.e., only the unicast fallback is valid), so our MaskablePPO formulation [14], [29] applies dynamic masks at both the sampling and the gradient computation. The behavior cloning and DAgger [17] address the distributional shift in the imitation learning, while the Expert Iteration [16] extends this to a self-improvement loop where the policy network’s own rollout planner generates improved labels for the online distillation, and the curriculum learning [21] over the progressive task difficulty shapes the policy network toward a deadline-conscious selective merge strategy, i.e., the method of selective merging, rather than the aggressive-merge policy that the direct training converges to (see the ablation in Section VIII). The PPO with GAE [19], [20] provides the policy-gradient backbone, implemented via Stable-Baselines3 [30]. Each of these components exists independently in the literature, even though we are not aware of prior work that integrates them into a single coded-caching delivery agent with the hard deadline constraints, considering that beyond stacking, the integration required two non-obvious couplings, i.e., (i) the dynamic action mask must be wired through the graphattention edge scorer so that the infeasible pairs are filtered before the message passing (rather than zeroed out posthoc), thereby avoiding the gradient-flow pathology of masking after the softmax (Sec. IV-A), and (ii) the BC/ExIt teacher’s pair pre-filter must be coupled to the same per-pair edge scorer used at the inference (top-Kpair candidate pruning), so that the imitation distribution sits on the same support the policy network can express (Sec. IV-B). We summarize what distinguishes our approach: • Hard-deadline contextual-POMDP surrogate. We jointly model the per-request expiration deadlines, the keep-side decisions, and the masked combinatorial actions, i.e., a
PREPRINT — SUBMITTED FOR PEER REVIEW
TABLE II G AP – CONTRIBUTION MAPPING . E ACH ROW IDENTIFIES A GAP IN THE PRIOR LITERATURE AND THE CORRESPONDING CONTRIBUTION THAT ADDRESSES IT.
Gap in Prior Work
Our Contribution
The combination of hard deadlines, masked combinatorial actions, and keep-side decisions does not, to our knowledge, appear together in any prior RL delivery formulation (§II-C). We frame this as a positioning statement based on the literature sweep documented in this section, not as a definitive nonexistence claim, and welcome pointers to closely related prior work Flat MLP policies ignore the graph structure of the mergeability relation (§II-E) Pure RL exploration is slow; we are not aware of a coded-caching agent that uses teacher distillation or selfimprovement (§II-E) Prior evaluations use a single configuration with few baselines and no OOD analysis (§II-E)
C1: Deadline-sensitive masked queue-state control (stationarypolicy / truncated continuing-control surrogate) with dynamic feasibility masking (§III-F)
C2: Graph-attentive MaskablePPO policy network (§IV-A) C3: Rollout-improved BC warm start and ExIt online distillation (§IV-B– IV-E) C4: 9 Track A baselines + PPO = 10 unique methods (12 table rows with two literature-compatible aliases), 50 holdout seeds × 200 episodes, 7 nonID evaluation conditions (uniform demand); main-body Zipf-demand extension study adds 11 additional regimes with 6 baselines + PPO-Zipf = 7 unique methods (§VII)
combination not present in the prior RL-based delivery formulations (§II-C). • Graph-attentive policy. Unlike the flat MLP of [12], our graph-structured policy network, i.e., the policy network, applies two-layer self-attention over the merge graph, thereby capturing the relational structure among the pending requests (§IV-A). • Behavior-cloning warm start and self-improving distillation. We combined the rollout-improved BC with the Expert Iteration online distillation, which lets the policy network exceed its heuristic teacher, i.e., a self-improvement loop absent from the prior coded-caching RL work (§IV-B–IV-E). • Large-scale OOD evaluation. We evaluate across 7 nonID regimes (2 curriculum-seen + 5 OOD) in the main uniform-demand evaluation, along with a main-body Zipfdemand extension study with 11 additional regimes (§VII), 50 holdout seeds, and 9 Track A baselines + PPO (10 unique methods) spanning three policy families, while the evaluation scale is qualitatively different from the prior work (§VI). The integration and its effect on policy quality are validated by the ablation study in Section VIII. Summary of gaps and our contributions. Table II maps the four gaps identified above to the contributions of this paper. III. P ROBLEM F ORMULATION We consider a content delivery network consisting of one central server connected to K edge caches, i.e., the users, through a shared broadcast bottleneck link, while the notation is summarized in Table I preceding the Introduction.
6
A. Network Model and Decentralized Cache Placement The server holds a library of N files, and following the standard coded-caching practice [3], [4], each file is divided into B equal-sized subfiles, i.e., the packets, thereby yielding a total library of F = N B packets. All packets are assumed to be equal-length, while the XOR operations are bitwise over GF(2), so that a single coded packet X = p1 ⊕ p2 has the same length as each constituent packet. In our setting we use N = 100, B = 10, and thus F = 1,000 packets, while the evaluation also covers N ∈ {60, 120, 150} to test the generalization. We adopt the decentralized fixed-size random placement inspired by [4], while at the episode reset, each cache k independently samples exactly M = ⌊pc F ⌋ distinct packet IDs uniformly without replacement from the F -packet library, without any coordination with the other caches.1 Let Ck ⊆ {0, 1, . . . , F −1} denote the resulting content of cache k, with |Ck | = M . Any single packet is present in a given cache with the marginal probability M/F = pc ; however, because each cache draws a fixed-size subset, the placements of different packets within the same cache are not independent, while the placements across different caches are mutually independent. We use pc = 0.30 (30%) as the default training configuration and evaluate the generalization to pc ∈ {0.20, 0.40} outof-distribution. The cache placement is independent of the file-request distribution, i.e., each packet is cached with the marginal probability pc regardless of the file popularity. This separation means that changing the demand model (e.g., from uniform to Zipf) alters the request queue statistics without affecting the cached content, thereby allowing us to isolate the effect of demand skew on the scheduling performance. However, as described in Section VII-A, the Zipf-demand agent uses an extended observation space with popularityaware features and is trained separately from the uniformdemand agent. The server transmits over a shared broadcast link, i.e., every packet sent by the server is received by all K caches simultaneously. This broadcast nature enables the XOR-coded transmissions that can carry useful information for multiple users in a single slot, while this is the property that the coded caching exploits to achieve the multicast gain. Fig. 1 illustrates the network topology and the one-step transition timeline. B. Online Request Arrival and Queue Dynamics The users issue subfile, i.e., the packet, requests continuously over time. We model the set of outstanding requests as a finite queue of depth Q that is maintained at full occupancy throughout an episode, i.e., whenever a slot is vacated by the delivery or expiration, a new request arrives immediately, thereby modeling the steady-state operation of the delaysensitive streaming system. 1 The standard theoretical model uses i.i.d. Bernoulli(p ) placement [4], c yielding a random cache size with mean pc F . Our implementation fixes the cache size at M = pc F for reproducibility (each cache holds exactly M packets, so side-information statistics do not fluctuate across episodes). For F =1000 and pc =0.30 the two placement models were empirically similar in pilot tests on the ID-default regime; we did not run a full sensitivity comparison across all reported regimes and adopt fixed-size sampling as a reproducibility-friendly substitute rather than as a proven equivalence.
PREPRINT — SUBMITTED FOR PEER REVIEW
7
One environment step (st → st+1 )
System model
Central server
Queue state (Q = 10)
library: 100 files × 10 packets = 1000 packet IDs
r0 = (k0 , f0 , d0 , S0 ) r1 = (k1 , f1 , d1 , S1 )
C0
C1
C2
C3
C4
r2 = (k2 , f2 , d2 , S2 )
Observe ot = {xt , pt } and mask mt
at
at ∈ {2k, 2k + 1, 90} 2k/2k+1: merge pair Mt [k] = (i, j); keep-side bit κ=0 keeps i, κ=1 keeps j 90=2Pmax : unicast earliest deadline
r3 = (k3 , f3 , d3 , S3 )
each cache stores |Ck | = pc F = 0.3 · 1000 = 300 packet IDs sampled uniformly without replacement fj : requested packet-set Sj : caches that store fj . . . 10 queue slots
Merge semantics
ri = (ki , fi , di , Si )
⊕
Deadline tick d ← d − 1 for all queue entries
Transmit / queue update
merge: kept slot ← aggregate; dropped slot ← fresh request; packet-set XOR degree Ut = |fi ∪ fj |
unicast: earliest-deadline record served in one slot (Ut = 1, one-slot-per-record); served slot ← fresh request
rj = (kj , fj , dj , Sj )
Reward + next state feasible iff fi ⊆ Ck
and fj ⊆ Ck j i merged state: (kmg , fi ∪ fj , min(di , dj ), Si ∩ Sj ) kmg ∼ Unif{ki , kj } independently of the keep-side κ
Expire / refill if d ≤ 0 Rt = 1 · Ut − 1 · Et + ⊮[coded merge] 0.75 |Si ∩ Sj | − 0.15 max(0, |fi ∪ fj | − 2) Q + 0.20 [γΦ Φ(st+1 ) − Φ(st )], Φ(s) = |M(s)|/ , γΦ = 0.995 2 episode ends when t = H = 50; metrics are reported in the final info dict
Fig. 1. System model and one-step timeline for deadline-constrained coded caching. Left: A central server broadcasts over a shared link to K=5 edge caches, each storing exactly M =pc F =300 library packets sampled uniformly without replacement. A queue of Q=10 outstanding requests (each with a per-request deadline) drives the scheduling decisions. An XOR-coded merge combines two requests ri , rj into a single broadcast X whenever the feasibility condition is met. Right: At each step the agent observes the queue state and feasible merge set Mt , selects either a coded merge (with keep-side choice κ) or an earliest-deadline unicast, after which all deadlines decrement and expired requests are refilled.
a) Request Representation: Each active request r in the queue is a four-tuple r = kr , f r , d r , S r , (1) where • kr ∈ {0, . . . , K − 1} is the destination cache when r is a fresh singleton request (the user making the request). When r is an aggregate coding-state record produced by a chained merge, the same field carries the representative destination kmg sampled independently of κ via Eq. (6), a bookkeeping representative rather than residual user demand. A single record is in exactly one of these two states at any time, so the symbol kr is unambiguous in context; for clarity we write kmg explicitly whenever the record in question is an aggregate (e.g., in unicast bookkeeping for aggregates, in the chained-merge proof of Appendix H, and in the observation feature tables of Appendix F); • fr ⊆ {0, . . . , F − 1} is the packet set to be delivered (a single subfile at request creation; may grow to a union after an XOR merge, as detailed in Section III-C); • dr ∈ {1, . . . , D} is the remaining deadline in integer time slots; and • Sr ⊆ {0, . . . , K − 1} is the side-information set, i.e., the subset of caches that currently hold all packets in fr and can therefore cancel them from any XOR-coded packet. b) Request Generation: A fresh request rnew is generated by: (i) rejection-sampling a candidate file/packet pair (n, b) ∼ Uniform{0, . . . , N − 1} × Uniform{0, . . . , B − 1} until the resulting packet fr = {nB + b} is not held by every cache simultaneously, i.e., until {k : fr ⊆ Ck } ̸= {0, . . . , K − 1}; under independent placement with marginal probability pc , the per-draw rejection probability is pK c , which is about 0.305 ≈ 0.24% at the default pc = 0.30 and about 0.405 ≈ 1.0% at pc = 0.40, so the expected number of resamples is essentially 1; (ii) sampling the destination cache kr uniformly from the admissible set {0, . . . , K − 1} \ {k : fr ⊆ Ck }, which guarantees fr ̸⊆ Ckr (no unsolicited delivery); (iii) computing Sr = {k : fr ⊆ Ck } (the set of caches that can
provide side information); and (iv) drawing the initial deadline uniformly, dr ∼ Uniform{1, . . . , D}. A request is generated whenever the destination cache kr does not already hold fr (no unsolicited delivery), while we explicitly allow Sr = ∅, in which case no XOR partner can cancel the request and the only feasible delivery action is the unicast. The contextual-POMDP surrogate therefore covers both the codable arrivals (Sr ̸= ∅) and the unicast-only arrivals (Sr = ∅), while the latter must still be served before their deadline, thereby contributing to the deadline misses on equal footing with the codable arrivals. Each arrival therefore corresponds to a single packet, i.e., the subfile, request, while a full-file retrieval can be modelled as a stream of B individual packet requests, each carrying its own deadline. c) Modeling Assumptions: We state five assumptions before introducing the transmission model and the reward, considering that they determine the slot-cost and deadlinebookkeeping semantics of the contextual-POMDP surrogate: (A1) Equal-length packets. All packets have the same length, so one XOR broadcast carries one packet’s worth of data and feasibility is governed by the side-information set Sr rather than packet size. (A2) One-slot-per-record service. Each environment step delivers exactly one record: either a coded XOR over a feasible pair (one slot, Ut = |fmg | as a packet-set cardinality, see Sec. V-D) or a unicast of one coding-state record (one slot, Ut = 1, regardless of |fr |). The unicast pathway is therefore a record-level service abstraction, not a packet-level model: a physical packet-level model would charge |fr | slots for the unicast of an aggregate. We adopt the record-level abstraction so that the mergeor-defer decision faces a uniform slot cost across its two branches; we revisit its broadcast-efficiency implications in Sec. V-D. (A3) Static random cache placement. Caches are populated once at episode start by uniform random sampling without replacement (cache fraction pc ) and held fixed for the episode; placement updates are out of scope.
PREPRINT — SUBMITTED FOR PEER REVIEW
(A4) EDF unicast. The unicast action is bound to the earliestdeadline record; per-request unicast targeting is not part of the action space, isolating the merge-or-defer decision from unicast scheduling. (A5) Refill-timing convention. A queue slot vacated by a Phase-1 transmission is refilled before the Phase-2 deadline decrement, so a fresh request sampled with dr ∼ Uniform{1, . . . , D} enters the next decision step with effective remaining deadline in {0, . . . , D − 1}. A slot vacated by a Phase-3 expiration is refilled after the decrement and therefore retains its sampled deadline in {1, . . . , D}. As a consequence, a Phase-1 fresh request that draws dr = 1 joins the same step’s expiration set Xt (Eq. (18)) and is reported under the standard expiration counters. This induces a small policy-independent floor in Et and the related metrics (ρ, σ, ε, Etuniq , mreq ): under dr ∼ Uniform{1, . . . , D} the per-Phase-1-arrival samestep-expiration probability is exactly 1/D, which upperbounds the contribution at 1/D ≈ 5% for the default D=20, ≤ 10% for the tight-deadline regime D=10, and ≤ 3.3% for D=30. All inter-method comparisons in Sec. VI share the same episode seeds and the same initial cache placements, so this floor is shared in expectation up to the first-divergent-action RNG drift. The simulator does not implement a strict common-randomnumbers (CRN) scheme across methods (RNG draws within an episode are sequential, and policy-dependent refill timings cause the realized arrival sequences to diverge across methods after the first divergent action), so the floor does not cancel pathwise. The paired-bootstrap comparisons of Table VIII therefore inherit sharedcontext pairing rather than the stronger same-arrivals pairing. Absolute interpretations of ρ, ε, mreq , and δ are benchmark-specific to this refill convention and should be qualified accordingly when compared across simulators or papers using a different (e.g., symmetric) refill rule. We adopt this asymmetric convention deliberately, since it is the actual simulator behavior, and a faithful reimplementation must place the Phase-1 refill before the Phase-2 decrement and the Phase-3 refill after, exactly as in Algorithm 1. C. Coded Transmission Model At each time slot the server performs exactly one of the two transmission types. a) Unicast Transmission: The server transmits the packet set fr of a single coding-state record r to its representative destination kr in one slot, while in our formulation, the unicast action always selects the record with the shortest remaining deadline, r∗ = arg minr dr , so that the unicast is a deterministic earliest-deadline-first (EDF) fallback rather than a free scheduling choice. Because the deadlines are integervalued in {1, . . . , D} and the queue depth is Q, ties on dr occur regularly, and we resolve them deterministically in favor of the smallest queue index r among the tied records, where the queue index is the FIFO insertion order maintained by the simulator (the reference implementation realizes this via
8
an insertion-ordered map keyed by queue index, even though the rule itself is language-independent, i.e., the tied records are served in arrival order). The same tie-break rule is applied consistently to the ED-Unicast, the PPO unicast fallback, and every lookahead teacher used in BC and ExIt. Upon reception, kr obtains all packets in fr (which is a singleton at arrival and may be a union after one or more merges). We adopt this oneslot-per-record convention as a transmission-cost abstraction, i.e., the broadcast-level packet-set XOR degree is fixed to Ut = 1 for any unicast action, regardless of |fr |. Bookkeeping for aggregate-record unicasts. When r is an aggregate (built up from n ≥ 2 prior merges), the underlying n original arrivals were already decoded at their respective merge broadcasts (Sec. III-C, “Broadcast Semantics of Aggregation”), and the surviving r is a residual coding-state record that tracks the union fmg for the future XOR-feasibility checks rather than the unserved demand. A later unicast on r therefore physically clears that residual record, even though the requestlevel newly-completed set Ct = A(txt ) \ (Dt−1 ∪ Lt−1 ) defined in Sec. III-C0f excludes any arrival identifier already credited in Dt−1 , so no original arrival is counted twice. The two readings of an aggregate-record unicast are therefore consistent: at the broadcast level it is a single record-clearing slot (Ut = 1, |Xt | unaffected if the deadline has not expired), while at the request level it adds at most the not-yet-credited subset of A(r) to Ct . The one-gap invariant proved in Appendix H is a decodability property for the XOR pathway and does not constrain the unicast slot-cost model. The unicast target selection is fixed to the earliest-deadlinefirst rather than learned, thereby isolating the merge-or-defer decision and controlling the action-space growth, while learning per-request unicast targets is left as future work. b) XOR-Coded Multicast: Given two distinct requests ri and rj in the queue,L the server may broadcast a single XORcoded packet X = p∈fi ∪fj p if and only if the following XOR feasibility condition holds: fi ⊆ Ckj
and
fj ⊆ Cki .
(2)
Condition (2) ensures that the cache kj already holds all packets in fi and can therefore cancel them from X to recover fj , and symmetrically for the cache ki . A single broadcast thus simultaneously serves two users, thereby yielding Ut = 2 in the simplest case (or Ut = |fi ∪ fj | after chained merges). c) Post-Merge Queue Update and Keep-Side Decision: An XOR merge is a compound action, i.e., beyond deciding which pair (ri , rj ) to merge, the agent also selects a binary keep-side bit κ ∈ {0, 1}, where κ = 0 retains slot i and κ = 1 retains slot j. We use κ exclusively for this binary indicator throughout the paper, while the semantic “which slot is kept” is recovered by the deterministic decode i if κ=0 else j, and is never re-introduced as a separate symbol. The merge produces a new aggregate request fmg = fi ∪ fj ,
(3)
dmg = min(di , dj ),
(4)
Smg = Si ∩ Sj ,
(5)
kmg ∼ Unif{ki , kj } independently of κ.
(6)
PREPRINT — SUBMITTED FOR PEER REVIEW
Status of the representative-destination rule (6). Both original arrivals are already decoded at the merge broadcast (Sec. “Broadcast Semantics of Aggregation”), so the residual record’s destination kmg is a bookkeeping representative rather than a remaining physical demand: a future broadcast that includes the residual record is feasible iff partner caches hold fmg , and the representative only enters through the symmetric one-gap invariant of Appendix H. We separate two distinct claims about (6): (a) Correctness requirement. The chainedmerge state sufficiency proof (Proposition 1, Appendix H) only requires kmg ∈ {ki , kj }; uniformity and independence from κ are not used in the proof, so a deterministic keepside-tied or earliest-deadline-tied rule would also satisfy the one-gap invariant. (b) Chosen simulator convention. On top of the correctness requirement, we adopt the uniform sampling independent of κ as a deliberate design choice, so that the keep-side bit κ is free to encode the queue-evolution control without also overloading the residual destination identity, while alternatives such as the keep-side-tied kmg = kκ or higher-degree / earliest-deadline representatives are plausible and would change the transition kernel, even though a focused sensitivity analysis is left for future work considering that every method we report here is evaluated under the same convention, so the paired comparisons are not biased by (6). The queue slot selected by the keep-side bit κ (slot i if κ = 0; slot j if κ = 1) is updated to hold the aggregate request, while the other slot is immediately replaced by a fresh request rnew . Considering that dmg and Smg are fully determined by (4)–(5), the keep-side choice κ cannot alter the merged request’s deadline, the side-information set, or the destination cache. What κ does control is the queue evolution, i.e., it selects which slot is freed and immediately replenished by a fresh arrival rnew . The identity of rnew , i.e., its file, deadline, and side-information providers, is drawn stochastically, thereby giving the agent indirect influence over the queue’s future composition and mergeability. Appendix R provides an empirical ablation confirming that the learned keep-side decision contributes measurably to the performance beyond the pair selection alone. d) Broadcast Semantics of Aggregation: Each XOR mergeL constitutes an actual broadcast, i.e., the server transmits X = p∈fi ∪fj p in one channel use, while every user whose individual request was folded into the merge decodes its requested packet immediately via its cached side information. The metric Ut = |fmg | therefore records the packet-setcardinality XOR degree of the coded packet, i.e., the number of distinct packet identities carried in the broadcast at that step (Section V-D). It is not the number of original singleton requests folded into the aggregate: under the request generator (Sec. III-B) two pending records can share packet identities without contradicting XOR feasibility, so |fmg | can equal the number of folded original arrivals only when no such overlaps occur (see the non-gap-overlap remark in Appendix I). Whenever original-arrival semantics are intended we use the request-level metrics ηreq , mreq , σreq of Section V-D instead. The aggregate request rmg that remains in the queue after the broadcast is not unserved demand; it is a coding-state record that (i) tracks the growing packet union fmg for future
9
XOR feasibility checks via (2), and (ii) carries the tightened side-information set Smg = Si ∩ Sj . A chained merge of ′ (r Lmg , rz ) is a second channel use: the server broadcasts X = p∈fmg ∪fz p. The two active participants (kmg and kz ) can always decode X ′ (Proposition 1, Theorem 1; Appendix H); previously served users in the chain may or may not be able to decode X ′ , but need not do so as they were already served at their respective merge steps (Remark 7). Because each chained broadcast is a separate transmission, a user that participates in multiple links of the chain contributes to Ut at every link, while this reflects the per-broadcast XOR degree, not the redundant delivery. If the coding-state record expires before a subsequent merge or unicast resolves it, the expiration penalty Et = |fmg | captures the wasted time slot and the side-information investment, not the undelivered data (Section III-D). Considering that Smg = Si ∩ Sj , each successive merge demands that a prospective partner cache holds all packets in the growing set fmg , which is a typically harder condition, with strict worsening exactly when the next merge contributes a packet identity not already in fmg (Appendix I). The method of aggressive merging therefore narrows the pool of future merge partners, thereby producing a throughput–flexibility trade-off that the scheduling agent must learn to manage. This construction is analogous to incrementally growing a clique in the sideinformation conflict graph, i.e., each new edge corresponds to one additional coded broadcast exploiting the enlarged cache overlap [6]. Two supplementary remarks on chained-merge scope and per-broadcast accounting are provided in Appendix I. A worked three-request merge example appears in Appendix E. e) Unique-Demand Accounting: A separate evaluation concern is whether the scheduler covers the distinct file identities at least once during the episode, independent of which cache requested the packet. We define a unique-demand, i.e., the file-identity-coverage, accounting at the granularity of the file identities. Each packet ID p ∈ {0, . . . , F − 1} projects onto a file identity via the deterministic map ϕ(p) = p/B ∈ {0, . . . , N − 1}, (7) so the file identity carried by a packet set fr is ϕ(fr ) = {ϕ(p) : (t−1) p ∈ fr } ⊆ {0, . . . , N − 1}. Let Fserved ⊆ {0, . . . , N − 1} be the set of file identities that have been delivered by any transmission strictly before step t (initialized to ∅ at episode start). Define (t−1)
Utuniq = ϕ(ftxt ) \ Fserved , [ (H) uniq Et = ϕ(fr ) \ Fserved ,
(8) (9)
r∈Xt
where ftxt is the packet set delivered at step t (either fmg for a coded merge or fr for a unicast on record r), Xt is the (H) expiration-event set of Eq. (18), and Fserved is the cumulative served-file-identity set at episode end (so an expired record contributes only those file identities never delivered during the episode). Under this accounting, each distinct file identity is credited exactly once per episode, i.e., a coding-state record that expires after its constituent file identities were already delivered earlier in the episode incurs Etuniq = 0.
PREPRINT — SUBMITTED FOR PEER REVIEW
10
The broadcast-efficiency view (Ut , Et ) and the unique-demand view (Utuniq , Etuniq ) are complementary, i.e., the former quantifies how effectively each channel use exploits the codedmulticast gain at the granularity of the broadcast-level packetset XOR degree, while the latter isolates how many distinct file identities, under the projection ϕ, are delivered before their deadlines. Section V-D formalizes all three metric families, and all results tables report all three views (Sections VI–VIII). The distinct file-identity coverage δ becomes a co-primary evaluation criterion alongside the broadcast-packet expiration ratio ρ in Section VI (formal definitions in Section V-D); “co-primary” here means jointly headline within the symbolretention convention of Sec. V-D, not a claim of per-arrival miss-probability or per-user completion semantics. f) Request-Level Accounting: The unique-demand view tracks the file identities, i.e., two requests targeting the same file from different caches are conflated as a single demand. To distinguish the individual arrivals through the queue aggregation, we introduce a finer-grained request-level accounting. Status of A(r). The annotation set A(r) introduced below is auxiliary evaluator bookkeeping maintained alongside the latent simulator state for the sole purpose of computing the request-level metrics M8–M10 of Sec. V-D; it is not part of the control-relevant queue record r = (kr , fr , dr , Sr ) used by the contextual-POMDP transition kernel of Sec. III-F, and it is never observed by the policy πθ (a | o). The controlrelevant record remains the four-tuple stated above; A(r) is carried through merges (Eq. (10) below) and refills only so that completion and miss can be credited per original request identifier at episode end. Each new arrival r is assigned a unique request identifier u and carries the singleton annotation set A(r) = {u}, while when two queue entries merge (Section III-C), the resulting record inherits the union of both annotation sets: A(rmg ) = A(ri ) ∪ A(rj ).
(10)
At each step t, let A(txt ) denote the annotation set of the transmitted entry (or the union for coded transmissions involving both endpoints), and let A(expt ) denote the union of annotation sets over all entries that expire at step t. We define the newly completed and newly missed request sets as Ct = A(txt ) \ Dt−1 ∪ Lt−1 , (11) Mt = A(expt ) \ Dt ∪ Lt−1 , (12) with cumulative sets Dt = Dt−1 ∪ Ct and Lt = Lt−1 ∪ Mt (D0 = L0 = ∅). By construction, each request identifier is credited exactly once as completed, missed, or still pending at episode end, while Section V-D defines the derived metrics, considering that the λ-sensitivity of the composite requestlevel score is analyzed in Appendix P. g) Feasible Merge Set: The complete set of feasible pairs at time t is Mt = (i, j) 0 ≤ i < j < Q, fi ⊆ Ckj , fj ⊆ Cki , (13) with cardinality |Mt | ≤ Pmax = Q 2 = 45. Setting Pmax = Q 2 ensures that no feasible pair is ever discarded; the merge set Mt is therefore exact. We index Mt in lexicographic
order on queue indices with i < j: the same enumeration rule is applied identically by the environment, the pair-feature tensor (whose rows correspond to the listed pairs in this order, then zero-padded to Pmax ), and the action decoder (ik , jk ) = Mt [k] (Sec. III-E). This rule is the order produced by itertools.combinations(range(Q), 2) in our reference implementation and guarantees that policy logits, action masks, and pair features remain aligned across processes. This set changes at every step as the deadlines decrement, new requests arrive, and the side-information sets evolve through the merges. Constructing Mt from scratch requires O(Q2 ) pairwise feasibility checks, each verifying the two subsetinclusion conditions on the cache contents. In practice, the environment maintains Mt incrementally, i.e., only the pairs involving a newly arrived or recently merged request are reevaluated, thereby reducing the per-step cost to O(Q) checks plus O(|Mt |) bookkeeping. The feasibility predicate (13) has no size cap on |fi ∪ fj |, while the constant Umax = 6 used in the observation feature tables of Appendix F is purely an observation clip on the size feature, not a merge-feasibility cap. h) Impact on Future Mergeability: A direct consequence of (5) is that the merging shrinks the side-information set, i.e., Smg ⊆ Si and Smg ⊆ Sj , while the subsequent merges involving rmg require a cache to hold all packets in the now-larger set fmg , which is less likely than holding fi or fj individually. The method of aggressive merging therefore progressively reduces the pool of future merge partners, which is a structural reason why the classical “always merge” strategy is suboptimal under deadlines. D. Deadline Dynamics and Expiration The time is slotted, and after every transmission, whether unicast or coded, all deadlines in the queue are decremented by one: dr ← dr − 1, ∀ r ∈ queue. (14) A request r expires if dr ≤ 0 before it is served, while the expiration is a hard constraint, i.e., an expired request yields zero throughput benefit to any user. Upon expiration, the slot is immediately refilled by a fresh request rnew so that the queue remains at depth Q. An aggregate request, formed by merging ri and rj , that expires wastes the side-information investment of the prior merge, thereby making the method of overly aggressive merging more costly under tight deadlines. The aggregate-expiration accounting is detailed in the transition dynamics of Section III-F4. The performance metrics for evaluating the scheduling policies are formally defined alongside the experimental protocol in Section V-D, while the opportunity rate orate = {t : |Mt | > 0} /H measures the fraction of steps at which at least one feasible merge pair exists and is used to contextualize the merge-rate values across the scenarios. E. Problem Statement We state the scheduling problem studied in this paper below.
PREPRINT — SUBMITTED FOR PEER REVIEW
11
Definition 1 (Deadline-Constrained Coded Caching Scheduling). Given a network with K edge caches, a library of N files (B subfiles each), decentralized random-prefetching placement with cache probability pc , a queue of Q outstanding requests each with a per-request hard deadline dr ≤ D, and an episode horizon of H slots, the reference scheduling problem of interest is to find an online scheduling policy π : S → A that maximizes the expected broadcast-efficiency score: π σ = arg max Eπ [σ] , π
(15)
subject to the constraint that any request still unserved after D time slots expires and yields zero throughput. The action space studied in this paper is the restricted merge-or-defer with EDF unicast fallback class formalized in (A4) of Sec. III-B0c and parameterized in Sec. III-F3, i.e., the policy π chooses among the coded-merge actions, with a binary keep-side bit, and a deterministic earliest-deadline-first unicast, rather than over the arbitrary per-request transmission targets. The optimization of (15) is therefore over this restricted policy class, not over the unrestricted online scheduling problem. We do not optimize (15) directly, i.e., the agent is trained on a shaped surrogate Rt = Rbase + Rquality + Rshape (Sec. III-F5) chosen to improve the sample efficiency and the deadline-aware behavior, while the trained policy πθsurr is then evaluated on the demand-centric and request-level metrics of Sec. V-D. Among the three reward components, the potentialbased shaping Rshape is inspired by the policy-invariance theorem of Ng et al. [18], while that theorem holds exactly only for an idealized, fully observed, continuing-state MDP with terminal Φ(sH ) = 0 and time-to-go information. The implemented training environment is the contextual-POMDP surrogate of Definition 1 (truncated at H=50, hidden episode cache placement, aliased aggregate observations, no time-togo feature), so we do not claim a formal invariance guarantee for the implemented setup, even though in this paper Rshape should be read as the heuristic credit-assignment shaping that empirically improves the sample efficiency without distorting the empirical headline rankings in our ablation. The mergequality bonus Rquality does change the optimized objective with respect to σ, so π σ in (15) is a reference target rather than the exact attractor of training. We report this distinction here so that the empirical claims in Sec. VI are read as those of πθsurr on the demand-centric and request-level metrics, not as those of an exact maximizer of σ. Formal status: contextual POMDP, not a strict MDP. We treat the agent as a stationary policy for a discounted continuing-control POMDP truncated at the horizon H = 50 (with the discount γ = 0.995 in PPO/GAE), rather than as the optimal non-stationary policy of a strict finite-horizon MDP, while the “masked-MDP” language used elsewhere in the paper is shorthand for this contextual-POMDP surrogate, considering that the queue-only observation ot is not a strict Markov state for at least three reasons. (i) Hidden episode context. The cache placement {Ck }K−1 k=0 is sampled once at the episode start (A3) and remains hidden in the sense that it is not directly fed to the policy, while the future arrival distributions depend on it via the rejection-sampling rule of
Sec. III-B, so two episodes with the same observed queue features can induce different refill distributions even though the latent placements differ. This makes the formal model a contextual MDP / POMDP with the hidden episode context. (ii) Aggregate-state partial observability. For an aggregate record produced by the chained merges, Appendix H proves the sufficiency of (kmg , fmg , Smg ) for the future feasibility and decodability, while the policy observation retains kmg and Smg explicitly even though it exposes fmg only through its size min(|fmg |, Umax )/Umax , so two observation-equivalent queue states can yield different merge union sizes |fi ∪ fj | when the records share non-gap packets, thereby resulting in different immediate Ut rewards and next aggregate sizes (Appendix I). The packet identities are deliberately discarded for the scalability of the graph-attention encoder, not because they are theoretically redundant, while reducing the remaining bias is an open question we leave to future work. (iii) Time-togo. st omits a remaining-horizon feature, so the finite-horizonoptimal policy can in principle differ from the stationary fixed point the agent learns, while the chosen γ = 0.995 has effective discount horizon 1/(1 − γ) = 200 > H, thereby making the surrogate closer to a continuing averagereturn objective than to a finite-horizon objective. All empirical comparisons in Sec. VI are paired across the methods at fixed H on shared seeds and shared cache placements, so (i)–(iii) are absorbed into the within-benchmark comparison, while the paper’s claims should be read as conclusions about the learned stationary policy under this contextual-POMDP surrogate, not as the optimality claims for a strict finitehorizon MDP. Exposing the remaining-horizon and packetidentity features, or reframing the agent input to include a sufficient summary of the cache placement, would close (i)– (iii) at the cost of a wider observation, and we flag this as future work in Sec. IX. Remark 1 (Training objective vs. evaluation metrics). The optimization in (15) maximizes the expected broadcast-efficiency score σ, which matches the base training reward Rbase = Ut − Et . However, because Ut is the packet-set-cardinality XOR degree of the broadcast, and grows with each chained merge, σ is best interpreted as a broadcast-efficiency metric measuring the per-slot packet utilization rather than the distinct file-identity coverage. The demand-centric evaluation metrics, i.e., the broadcast-packet expiration ratio ρ and the distinct file-identity coverage δ, are computed post-hoc from the same trajectories, even though they are not directly optimized. We anchor our main empirical claims on these demand-centric metrics (Sections VI–VIII). Several features of Problem 1 make it challenging: Combinatorial action space. The feasible merge set Mt changes at every step, while the agent must select a pair and a keep side, thereby inducing up to 2Pmax + 1 = 91 discrete actions of which only a state-dependent subset is valid at any given step. • Long-horizon mergeability consequences. Each merge action simultaneously (i) delivers one coded packet, (ii) shrinks the side-information set for the aggregate request via Smg = Si ∩ Sj , and (iii) changes the future feasibility •
PREPRINT — SUBMITTED FOR PEER REVIEW
structure of the queue, while evaluating these cascading effects requires look-ahead beyond the next step. • Hard deadline and expiration dynamics. The penalty for the expiration is discontinuous, i.e., a request delivers the full value if served one slot before its deadline and zero value if served one slot after, while the policies that optimize only the immediate throughput tend to defer the urgent requests in favor of the coding opportunities, thereby producing large expiration penalties. • Stochastic request arrivals. New requests arrive with random file identities, deadlines, and side-information sets, so the future queue state is unknown at the decision time, while a useful policy must generalize across the distribution of the arriving requests. These properties make the problem intractable for the exact dynamic programming at realistic scales and motivate the reinforcement learning formulation developed in the following sections. Specifically, we model Problem 1 as a masked discrete-action Markov Decision Process (Section III-F), in which the state encodes the full queue configuration, while the action space is dynamically masked to the feasible set Mt ∪ {unicast}, and the reward is shaped to match (15). a) Assumptions and Scope.: To aid the reproducibility we summarize the modelling boundaries. Fixed within each episode: the network topology (one server, K edge caches, shared broadcast link), the cache contents (drawn once via the uniform-without-replacement placement with fraction pc ), the file library (N files, B equal-length subfiles each), and the file-popularity distribution (uniform for Track A, while a separately trained agent handles the Zipf demand in Track B, Section VII-A). Stochastic: the request arrivals are drawn each time a queue slot is filled or refilled by (i) sampling the file index from the within-track popularity law (i.e., uniform on Track A, while Zipf with α=0.8 or Mandelbrot– Zipf on Track B), (ii) sampling the packet index uniformly within the file, (iii) rejecting any sampled (file, packet) that is held by every cache, (iv) drawing the destination cache uniformly from the admissible subset of caches that do not already store the sampled packet, and (v) drawing the deadline dr ∼ Uniform{1, . . . , D}, while “Request Generation” above provides the full conditional procedure. Not modelled: the physical-layer errors (i.e., the error-free broadcast is assumed), the time-varying link rates (i.e., all packets are equal-length), the queueing or propagation delay beyond the discrete deadline mechanism, the cache-size heterogeneity, and the wireless fading. F. Contextual-POMDP Formulation We cast the deadline-constrained coded caching scheduling problem (Definition 1) as a masked discrete-action contextual POMDP that can be optimized by a deep RL agent, while we use “masked discrete-action MDP” interchangeably below as a shorthand for this contextual-POMDP surrogate, considering that the formal-status caveats of Definition 1, i.e., the hidden episode cache context, the aggregate-state partial observability, and the no time-to-go feature, apply throughout. The environment is implemented as a Gymnasium-compatible class [31] and is trained using 32 parallel environment workers.
12
TABLE III O BSERVATION S PACE C OMPONENTS (K = 5, Q = 10, Pmax = 45). T RACK B ADDS POPULARITY- AWARE FEATURES (S ECTION VII-A). Component Per-request feature vector Pairwise feature tensor
— —
Track A
Track B
(130, ) (45, 8)
(140, ) (45, 11)
1) Contextual-POMDP Surrogate: The implemented training environment is the contextual-POMDP surrogate of Definition 1, with latent-state space S, observation space O, and observation map ot ∈ O defined in Sec. III-F2. We summarize it by the tuple M = S, O, A, R, P, γ , (16) where A is the discrete action space, R : S × A × S → R is the latent-state reward kernel R(st , at , st+1 ) used by the simulator (it depends on the realized expiration-event set Xt and the merged-record union |fmg |, which are functions of the latent queue and not of the aliased observation alone; see Sec. III-F5), P is the latent-state transition kernel, and γ = 0.995 is the discount factor. The agent receives the scalar reward Rt alongside the observation stream during the training, i.e., its policy πθ (a | o) conditions on the observation only, while Rt is computed from the latent state by the environment and delivered as part of the standard Gymnasium step tuple. We do not treat R as a function of the observation, considering that the observation-equivalent aggregate states can yield different immediate Ut rewards and different next aggregate sizes (Definition 1, point (ii); also discussed in Appendix I). Whenever the “masked-MDP” shorthand is used elsewhere in the paper, it refers to this contextual-POMDP surrogate, not to a strict fully observed MDP. Each episode runs for a fixed horizon of H = 50 transmission steps, and no early termination is applied. 2) State Space and Observation Encoding: The latent state st at step t is the complete queue configuration {r0 , r1 , . . . , rQ−1 } together with the fixed cache assignment {C0 , . . . , CK−1 } for the current episode, while the agent’s observation ot encodes only the queue, thereby projecting the cache assignment through the per-request side-information sets Sr and through the aggregate side-information set Smg for any chained-merge record. This projection is lossy in two ways that are spelled out in the formal-status block of Definition 1, i.e., the placement is treated as hidden episode context (the policy sees only its Sr summaries, not the cache contents themselves), while the aggregate packet set fmg is summarized only by its size feature min(|fmg |, Umax )/Umax rather than by the explicit packet identities. We discard the packet identities deliberately for the scalability of the graphattention encoder, not because they are theoretically redundant, and consequently the model is best read as a contextual POMDP whose observation is a sufficient statistic for the feasibility but not in general for the immediate Ut reward when the records share non-gap packets. The observation ot is a structured dictionary with two components whose dimensions are summarized in Table III.
PREPRINT — SUBMITTED FOR PEER REVIEW
The per-request feature vector ϕi ∈ [0, 1]dreq encodes the target cache identity (one-hot), the side-information providers, the normalized deadline, the file-set size, and the merge degree (dreq =13 for Track A, 14 for Track B with an additional popularity-mass feature), while the per-pair feature vector ψij encodes the intersection size, the partner degrees, the combined urgency, and the aggregate sizes (dpair =8 for Track A, 11 for Track B). All features are bounded in [0, 1], while the full feature definitions are provided in Appendix F. 3) Action Space and Keep-Side Parameterization: The action space is A = {0, 1, . . . , 2Pmax }, i.e., a discrete set of 2Pmax + 1 = 91 actions, while each action encodes both the pair index and the keep-side decision via the bijection a 7−→ k, κ = ⌊a/2⌋, a mod 2 , (17) where k ∈ {0, . . . , Pmax −1} indexes the candidate pair (ik , jk ) = Mt [k] and κ ∈ {0, 1} selects the kept slot (κ = 0 retains slot ik ; κ = 1 retains slot jk ). The special action a = 2Pmax = 90 triggers a unicast transmission. The three action categories are summarized below: • a ∈ {0, 2, 4, . . . , 2Pmax −2} (even): coded merge, keep slot ik . • a ∈ {1, 3, 5, . . . , 2Pmax −1} (odd): coded merge, keep slot jk . • a = 2Pmax : unicast, serve earliest-deadline request. The role of the keep-side parameter in governing the queue evolution, exposed here as a learned action dimension rather than as the hand-designed endpoint-retention rules used by SACM+/SACM++, is discussed in Appendix I. 4) Transition Dynamics: Given the state st and action at , the transition to st+1 proceeds in three sequential phases. One-step timeline. At step t the agent observes the queue and the feasible merge set Mt , selects an action, i.e., the coded merge or the unicast, while the environment executes the transmission and updates the affected queue slots (Phase 1), decrements all remaining deadlines by one (Phase 2), then expires and refills any request whose deadline has reached zero (Phase 3), thereby yielding the latent state st+1 . The observation ot does not carry a time-to-go feature, and consistent with the truncated continuing-control framing in Definition 1, the agent is trained as a stationary policy on the contextualPOMDP observation defined there. Expiration event set. Let q^ ueuet denote the queue after the Phase-1 transmission update and the Phase-2 deadline decrement, even though before any Phase-3 refill, while the expiration-event set at step t is Xt = r ∈ q^ ueuet : dr ≤ 0 , (18) i.e., the records whose deadline reached or fell below zero during this step. All expiration-derived counters in this paper, i.e., Et , the request-level miss set Mt , and the file-identity expiration set Etuniq , are defined in terms of Xt , never in terms of the post-refill queue st+1 in which the corresponding slots have already been replaced by fresh arrivals. Refill timing convention (cross-reference to A5). The asymmetric refill ordering (Phase-1 refills before the Phase2 decrement, Phase-3 refills after) is recorded as modeling
13
assumption (A5) above (Sec. III-B0c). The two refill paths occupy different positions in the one-step timeline, and we adopt this asymmetry deliberately rather than patching it: a slot vacated by the Phase-1 transmission is refilled before the Phase-2 global decrement, so the fresh request sampled with dr ∼ Uniform{1, . . . , D} is decremented on this step and enters the next decision step with effective remaining deadline in {0, . . . , D − 1}; a slot vacated by Phase-3 expiration is refilled after the Phase-2 decrement and so retains its sampled remaining deadline in {1, . . . , D}. As a consequence, a Phase1 fresh request that draws dr = 1 joins Xt and expires in the same step without ever being selectable; we treat this as the model’s representation of an arrival whose initial slack already fits inside one transmission slot, and report it under the standard expiration counters. Any reader re-implementing the simulator must place the Phase-1 refill before the Phase-2 decrement and the Phase-3 refill after, exactly as in Algorithm 1. The three phases are formalized in Algorithm 1. Algorithm 1 One-Step Environment Transition Require: State st = {r0 , . . . , rQ−1 }, action at , mask mt // Phase 1 — Transmission (Phase-1 refills happen before the Phase-2 decrement, so a fresh request sampled with dr = 1 here will expire in Phase 3 of the same step; see “Refill timing convention” above.) 1: if at ̸= 2Pmax and ⌊at /2⌋ < |Mt | then 2: Decode (k, κ) ← (⌊at /2⌋, at mod 2) 3: (ik , jk ) ← Mt [k]; compute (fmg , dmg , Smg ) via Eqs. (3)–(5) 4: Sample kmg ∼ Unif{kik , kjk } independently of κ ▷ Eq. (6); correctness requires only kmg ∈ {kik , kjk } for Prop. 1, uniformity is a chosen simulator convention 5: Form aggregate queue record rmg ← (kmg , fmg , dmg , Smg ) ▷ four-tuple, matches the canonical control-relevant record 6: Set A(rmg ) ← A(rik ) ∪ A(rjk ) ▷ auxiliary evaluator bookkeeping (Sec. III-C0f); not part of the queue tuple 7: if κ = 0 then slot ik ← rmg ; refill slot jk with rnew 8: else slot jk ← rmg ; refill slot ik with rnew ▷ κ is the keep-side bit, not a slot index 9: else ▷ unicast 10: Serve r∗ = arg minr dr , queue-index(r) ; refill its slot with rnew ▷ ties on dr broken by smallest queue index, matching the reference simulator 11: end if // Phase 2 — Deadline Decrement 12: dr ← dr − 1 for all r in queue // Phase 3 — Expiration Handling 13: Xt ← {r ∈ q ueuet : dr ≤ 0} ▷ event set, Eq. (18) P ^ 14: Et ← |f | ▷ expired packet-identity count r∈Xt r 15: for each r ∈ Xt do 16: Refill slot with rnew 17: end for 18: Compute mt+1 , observation ot+1 , reward Rt 19: return (ot+1 , mt+1 , Rt )
PREPRINT — SUBMITTED FOR PEER REVIEW
14
5) Reward Function: The per-step reward R(st , at ) decomposes additively into the three components: R(st , at ) = Rbase + Rquality + Rshape .
(19)
a) R1: System-Aligned Base Reward: Rbase = wserved · Ut − wexp · Et ,
(20)
with wserved = 1.0 and wexp = 1.0, while Ut = |fmg | is the XOR degree of a coded P merge (or Ut = 1 for a unicast transmission), and Et = r∈Xt |fr | is the total expired packet-set mass at step t, computed over the expiration-event set Xt defined in Eq. (18) (i.e., the records whose deadline reached zero after the Phase-2 decrement, evaluated before the Phase-3 refill replaces those slots with fresh arrivals). The perbroadcast packet-set formulation matches the training reward P with the broadcast-efficiency score σ = H −1 t (Ut − λEt ) (Section V-D), so that the higher reward correlates with the higher broadcast-level packet utilization, while Remark 1 discusses the distinction between this training-aligned broadcastlevel metric and the file-identity / request-level evaluation metrics. b) R2: Quality Bonus (Coded Merge Only): coded merge, winter · |Smg | Rquality = − wunion · max 0, |fmg | − 2 0 unicast, (21) with winter = 0.75 and wunion = 0.15, while the intersection bonus winter · |Smg | rewards the pairs whose merged sideinformation set is large, considering that a larger Smg means the aggregate request can participate in future XOR merges with more potential partners. The union penalty wunion · max(0, |fmg |−2) discourages repeatedly merging the alreadymerged aggregates, i.e., as |fmg | grows, the XOR feasibility condition (2) becomes harder to satisfy (a partner must cache the entire union), thereby making the deeply chained aggregates increasingly difficult to serve before their deadline. c) R3: Potential-Based Shaping: Rshape = wΦ · γΦ · Φ(st+1 ) − Φ(st ) , (22) where the potential function is Φ(s) =
|M(s)| , Q
(23)
2
i.e., the fraction of all Q possible queue pairs that are 2 currently the feasible merges, while we use wΦ = 0.20 and γΦ = 0.995. This shaping is inspired by the potential-based shaping [18], whose formal invariance theorem holds for an idealized fully observed continuing-state MDP, while in the implemented contextual-POMDP surrogate of Definition 1 (truncated at H=50, hidden episode cache placement, aliased aggregate observations, no time-to-go feature), the theorem does not apply directly, and we therefore present Rshape as the heuristic credit-assignment guidance and do not claim that it leaves the optimal policy of the surrogate exactly unchanged. The empirical effect of Rshape is examined in the reward ablation
in Sec. VIII, while an exact finite-horizon-MDP invariance result would additionally require a terminal Φ(sH ) = 0, a time-to-go feature, and an observation exposing the hidden episode context and the packet identities. Remark 2 (Reward design and selective merging). The potential-based term Rshape is inspired by [18], even though the formal invariance theorem applies only to an idealized fully observed continuing-state MDP, and we therefore treat Rshape as the heuristic shaping for the implemented contextualPOMDP and make no formal optimal-policy preservation claim. The quality bonus Rquality , specifically the intersection bonus and the union penalty, is the heuristic shaping that explicitly incentivizes the high-overlap merges and discourages the deep chaining, thereby giving rise to the selective merge behavior reported in Section VI, which is learned under this specific reward design, not in a reward-free setting. Remark 3 (Training reward vs. evaluation metrics). The shaped reward R(st , at ) defined above is used exclusively during training to guide the policy optimization, while all performance comparisons in Sections VI–VIII are based on the communications-system metrics defined in Section V-D, i.e., the broadcast-efficiency score, the broadcast-packet expiration ratio ρ, the distinct file-identity coverage δ, the served/tx, the coding gain, and the expirations, and the per-step reward is reported only as a training diagnostic and is never used for the policy ranking. 6) Dynamic Action Masking: At every step t, a boolean mask mt ∈ {0, 1}2Pmax +1 is computed alongside the observation as follows: 1 if ⌊a/2⌋ < |Mt | (pair ⌊a/2⌋ exists), mt (a) = 1 if a = 2Pmax (unicast, always valid), (24) 0 otherwise. The mask is exposed to the learning algorithm via the Gymnasium action_masks() interface, while MaskablePPO [14], [19] applies it at the two points as follows: 1) Sampling: the infeasible actions are assigned zero probability by replacing their logits with −∞ before the softmax, so they are never selected during the rollout collection. 2) Gradient update: the infeasible actions are excluded from the policy-gradient loss computation, thereby preventing the optimizer from assigning the probability mass to them. Huang and Ontañón [13] show that this masking introduces no gradient bias, while the details are provided in Appendix J. 7) Episode Termination: An episode terminates deterministically after H = 50 transmission steps, and no early termination is applied. At termination, the environment returns the episode-level aggregate counters from which the evaluation metrics of Section V-D are derived, while the full evaluation protocol, i.e., the holdout seeds, the episode seeding, and the confidence intervals, is described in Section V-A. IV. L EARNING F RAMEWORK This section describes the learning system we developed for the deadline-constrained coded caching delivery, i.e., the delivery of the coded multi-casting messages under the strict
PREPRINT — SUBMITTED FOR PEER REVIEW
deadlines of the users. The system has three components, while each of them addresses a distinct aspect of the problem: a structured policy network that uses the graph topology of the pending request queue (Section IV-A), a three-phase training pipeline that bootstraps from the heuristics and then refines through the self-improved online experience (Sections IV-B–IV-E), and a conservative model-selection criterion that reduces the sensitivity to the training-seed variance [27] (Section IV-F), thereby giving us a more reliable final policy.
15
TABLE IV P OLICY NETWORK ARCHITECTURE . Q=10 REQUESTS , K=5 CACHES , Pmax =45 CANDIDATE PAIRS . Component
Architecture
Node MLP Graph Self-Attention Context MLP Edge MLP
13 → 256 → 128 (ReLU) L=2 layers, h=4 heads, d=128 128 → 256 → 128 (ReLU) 518 → 256 → 64 (ReLU)
36.5K 198K 66K 149K
Actor (pairwise action head) Critic graph-pair encoder Critic value MLP
per-pair: 192 → 128 → 2 (same architecture, separate weights) 3008 → 256 → 128 → 1
25K 449.5K 803K
Total
Params
∼1.73M
A. Policy Architecture The policy must map a variable-cardinality request queue (whose merge structure changes at every step) to a probability distribution over the 91 discrete actions, while at the same time respecting the feasibility constraints of the merge graph. A flat multilayer perceptron (MLP) would require padding to a worst-case size and could not share the computation across the merge candidates, even though the merge candidates share most of the structural information. We therefore use a graphstructured policy network, i.e., a two-stage architecture that treats the queue as a node-attributed graph and each candidate merge as an attributed edge. We chose the graph attention [15] over a flat MLP for two reasons: (i) the merge topology Mt changes at every step, so we need a variable-structure encoder; and (ii) the merge decisions are coupled across the pairs, since the value of merging (ri , rj ) depends on its effect on the other pairs’ feasibility. The ablation in Section VIII confirms that replacing the graph attention with a flat MLP degrades the miss ratio across all the eight evaluation regimes, i.e., the regimes used in our evaluation. Stage 1: Graph-Pair Encoder: The extractor receives the structured observation from Section III-F2, i.e., a per-request feature matrix X ∈ RQ×dreq (dreq = 13 for Track A; 14 for Track B) and a per-pair feature matrix E ∈ RPmax ×dpair (dpair = 8 for Track A; 11 for Track B; zero-padded to Pmax = 45). The extractor processes the observation in four stages: (i) a NodeMLP (dreq → 256 → 128) lifts each per-request vector to a 128-d embedding; (ii) two GraphAttentionBlocks [15] with four heads and dmodel =128 propagate information along feasible merge edges to produce contextual node embeddings; (iii) a ContextNet mean-pools all node embeddings through an MLP (128 → 256 → 128) to produce a global queue context vector c; and (iv) an EdgeNet forms each pair embedding eij ∈ R64 by concatenating the two node embeddings, their element-wise product, the absolute pairwise difference |hi − hj |, and the base pair features (the first dpair − 2 entries; the last two pair features encode normalized queue indices and are used only to build the merge-graph adjacency, not as EdgeNet inputs), then maps through an MLP ((4×128 + dpair − 2) → 256 → 64, i.e., input width 518 for Track A and 521 for Track B). Full equations and inference cost analysis are in Appendix K. Stage 2: Pairwise Action Head: Given the context vector c and all pair embeddings {eij }, the action head scores the 91-dimensional action space. For each of the (up to) 45 candidate pairs, two logits are produced by a shared MLP
([c∥eij ] → 128 → 2), corresponding to keep-side i and keepside j, respectively. The unicast action receives a separate logit from an MLP (c → 64 → 1). The 91 raw logits are concatenated, the infeasible entries are set to −∞ via the dynamic action mask (Section III-F6), and a softmax produces the action distribution πθ (a | s) (here and below, s is the shorthand for the agent observation ot of Definition 1; the underlying environment is a contextual POMDP and we never condition the policy on the latent state directly), thereby producing a feasible action distribution at every step. The value head uses a separate encoder from the actor, i.e., it runs an independent graph-pair encoder of identical architecture (with its own weights), concatenates the global queue context vector c ∈ R128 with the Pmax = 45 per-pair embeddings eij ∈ R64 to form the 128 + 45·64 = 3008dimensional value latent zv = [c ∥ e1 ∥ · · · ∥ e45 ], and maps it through a critic MLP (3008 → 256 → 128 → 1), exactly matching Table IV and Fig. 2. This separation lets the critic learn its own task-relevant features, independent of the actor’s action-scoring head, thereby reducing the interference between the actor and the critic. Table IV and Fig. 2 summarize the parameter count and the dataflow by module. The total is ≈1.73M parameters for the Track A (uniform) agent and ≈1.75M for the Track B (Zipf) agent (i.e., the larger input feature dimensions account for the difference), thereby giving enough representational capacity without overfitting on the 104 -episode evaluation regime. The Track B (Zipf) agent uses slightly larger input dimensions (dreq =14, dpair =11), thereby yielding ≈1.75M parameters, while all the other architectural choices are identical (Appendix K).
PREPRINT — SUBMITTED FOR PEER REVIEW
16
Stage 1: Graph-pair encoder (actor branch shown) R128
Observation dict
Mean pool
Context MLP 128 → 256 → 128
c
Stage 2: Pairwise action head + critic ×45 candidate pairs
ReLU
Per-request features X ∈ R10×13
Node MLP (0) 13 → 256 → 128 h Masked self-attention ×2 blocks heads= 4, d = 128 Build adjacency from (inorm , jnorm ) + valid-pair mask
Pair features P ∈ R45×8
[c∥eij ]
Pair scorer 192 → 128 → 2
90
91 logits Gather (hi , hj ) and concat [hi , hj , hi ⊙ hj , |hi −hj |, ψij ]
Edge MLP 518 → 256 → 64
eij
Send scorer 128 → 64 → 1
invalid 7→ −∞ Apply action Softmax mask mt
πθ (a | s)
1
R64 , padded to 45 pairs
A ∈ {0, 1}10×10 with self-loops ψij uses only the first 6 pair features: inter, degi , degj , min-deadline, sizei , sizej . The last 2 entries (inorm , jnorm ) are used to build A.
Value head 3008 → 256 → 128 → 1 Critic: a separate graph-pair encoder with the same architecture but independent weights, followed by a value MLP 3008 → 256 → 128 → 1.
Vϕ (s)
Actor latent: zπ = [c∥e1 ∥ · · · ∥e45 ] ∈ R128+45·64 = R3008 .
Fig. 2. Architecture of the graph-structured policy network. Stage 1 (graph-pair encoder): Per-request features are lifted by a node MLP and refined by two graph-attention blocks (h=4 heads, d=128). A context network mean-pools all node embeddings to a global context vector c ∈ R128 . An edge network combines node embeddings, element-wise interactions, and raw pair features into per-pair embeddings eij ∈ R64 . Stage 2 (pairwise action head): Each pair embedding is concatenated with c and mapped to two keep-side logits; a separate unicast MLP produces one additional logit. Dynamic action masking zeroes infeasible entries before softmax produces πθ (a | s). The value head uses a separate graph-pair encoder (not shown).
B. Phase 1: Rollout-Improved Behavior Cloning A randomly initialized policy almost never discovers the selective merging from the exploration alone, considering that the reward signal is sparse while the consequences of the premature merging (i.e., fewer future coding opportunities and more expirations) are delayed across many steps. We therefore start with a supervised warm-up using the behavior cloning (BC) from a rollout-improved teacher [17], thereby giving the policy a useful initial starting point. Teacher construction: For each encountered state s, the teacher constructs a candidate action set as follows. We rank all currently feasible merge pairs (i, j) ∈ Mt by the lexicographic key rank(i, j) =
|Si ∩ Sj |, − min(di , dj ), deg(ri ) + deg(rj ), −k(i, j) ,
sorted in descending order, where the primary key is the side-information intersection size, the secondary key prefers more urgent (smaller minimum-deadline) pairs, the tertiary key prefers larger combined degree, and the final key −k(i, j) negates the pair’s position under the lexicographic queue-index enumeration (i < j) used to build the action mask, so that on full ties the earliest lexicographic position wins (i.e., descending sort on the negated key implements ascending lexicographic candidate-enumeration order on ties). We collectively call this the raw merge score; the same key is implemented in the reference simulator’s candidate_actions_topk routine. We retain the top Kpair = 16 pairs under this ranking; both keep-side variants κ ∈ {0, 1} are expanded for each selected pair, yielding up to 2Kpair = 32 coded candidates. The deterministic EDF unicast action is always included as an additional candidate (so the planner can always choose to defer to unicast on urgent states), giving a candidate set of size at most 2Kpair + 1 = 33, further restricted to mask-feasible actions. Each candidate a is then evaluated by a short-horizon simulation: i. Clone the environment in state s. Cloning copies the queue, the per-episode cache placement, and the RNG bit-generator state, so the cloned environment carries the same hidden episode context as the original.
ii. Execute candidate action a. iii. Run SACM++ for d = 4 lookahead steps; the per-step return accumulated along the rollout is the full shaped reward Rtotal = Rbase + Rquality + Rshape used in PPO training (Sec. III-F5), discounted with γ = 0.995. iv. Repeat for M = 4 independent Monte Carlo seeds. For each candidate, every seed re-clones the original environment and re-seeds its RNG with a fixed per-seed value before applying a, so all candidates are scored against the same common-random-numbers stream per seed and the candidate-vs-candidate comparison is paired across rollouts. The discounted returns are averaged across the M seeds. The action with the highest average discounted return is selected as the teacher label a∗ = arg maxa V̂ (s, a), while the ties on V̂ (s, a) are broken by the candidate-enumeration order above (i.e., lexicographic (i, j, κ) for the coded actions, with the unicast action ranked last). Because the lookahead uses the rollouts rather than a learned value function, this teacher is model-free and approximately rollout-improved over the SACM++ heuristic on the retained candidate set, i.e., each retained candidate is scored by its average d=4 Monte-Carlo discounted return under the SACM++ continuation, thereby allowing the teacher to outperform the SACM++ action under its own finite-horizon, pruning-restricted estimate V̂ (s, a). We do not claim a strict per-step improvement guarantee, even though the rollout-improved teacher is empirically stronger than SACM++, since V̂ is finite-horizon, stochastic, and sensitive to the top-Kpair pre-filter (see the pruning-sensitivity caveat below). Pruning-sensitivity caveat. The candidate-set pre-filter keeps only the top Kpair feasible pairs, so the supervisory signal is restricted to the actions that survive a heuristic pre-filter closely related to the SACM++ ranking, i.e., the same ranking that we used for the teacher construction. We do not report the binding rate of this filter or a full-enumeration-vs-pruned teacher comparison on a small instance in this version; that sensitivity sweep would isolate how much of the BC/ExIt advantage comes from the rollout-improved planner with respect to the pre-filter itself, and we leave it for future work.
PREPRINT — SUBMITTED FOR PEER REVIEW
Dataset and training: We collected a dataset of NBC = 150,000 state–action pairs (s, a∗ ) by rolling out the teacher across the randomized episodes. We then trained the policy network by minimizing the cross-entropy loss LBC = −E(s,a∗ ) [log πθ (a∗ | s)] using Adam with the learning rate ηBC = 3 × 10−4 , for 6 epochs with minibatch size 2,048 and gradient clipping at 1.0. After the BC, the policy already reproduces the selective merge behavior, i.e., it unicasts the urgent requests and prefers the pairs with large cached side-information intersections, thereby shortening the self-improvement phase that follows. C. Phase 2: Value Network Warm-Up The policy gradient methods need a well-calibrated value function to produce useful advantage estimates, considering that the advantage estimates drive the policy updates. Right after the BC, the critic’s parameters are still random and produce inaccurate baselines, which gives high-variance gradients that can destabilize the BC-warmed policy. To address this, we froze the action-scoring layer and ran 50,000 MaskablePPO steps with 32 parallel environments, while only the value network (and the shared lower-layer graph-pair encoder of the critic) receives the gradient updates. The critic thus learns to predict the returns under the fixed BC policy before the policy optimization begins, thereby giving the subsequent PPO phase a calibrated advantage estimator. Once the 50,000 steps are complete, we unfroze the actionscoring layer and Phase 3 begins with an already-calibrated advantage estimator. D. Phase 3: MaskablePPO with Curriculum Learning Phase 3 runs Maskable Proximal Policy Optimization [14], [19] with Generalized Advantage Estimation (GAE, λ = 0.95) [20] for 6,000,000 Phase-3 environment steps per training seed. Combined with the 50,000-step Phase-2 warm-up (Sec. IV-C), this gives 6,050,000 total RL environment steps per seed; the training-curve x-axes in Fig. 3 (and its Zipf counterpart in Fig. 11) include the warm-up offset, so the curriculum boundaries plotted there are at T = 50K+500K = 550K and T = 50K + 1M = 1.05M. Training is distributed across 32 parallel environment instances. Curriculum: Training directly on the target domain (N = 100 files, pc = 0.30) is challenging, considering that with more files the side-information intersection of any two random requests is small, so the feasible merge pairs are rare while the reward is sparse. Following the curriculum learning [21], we increase the task difficulty across the three stages: I. Stage I (500,000 steps): N = 60 files, pc = 0.50, dense merge opportunities, strong shaping signal. II. Stage II (500,000 steps): N = 80 files, pc = 0.40, intermediate difficulty. III. Stage III (500,000+ steps): N = 100 files, pc = 0.30, target evaluation domain. Each stage is initialized from the final checkpoint of the previous stage. The policy thus encounters the monotonically increasing task difficulty, while the learned selective merge behaviors transfer from the easier to the harder domains, thereby producing a more generalization-capable final policy.
17
PPO hyperparameters: The main hyperparameters are as follows: the learning rate 5×10−4 → 1×10−4 (linear decay), the entropy coefficient 0.010 → 0.001, 32 parallel environments, 6M Phase-3 environment steps per seed (plus the 50K warm-up of Phase 2, for 6.05M total RL steps). The training runs in 250,000-step chunks, thereby letting us interleave the ExIt distillation between the chunks (Section IV-E). The full hyperparameter set is in the Appendix Table XXXIII. E. Expert Iteration with Online Distillation Even with a BC warm start, pure PPO can plateau if the policy’s value function under-estimates the benefit of the rare but highly rewarding selective merge decisions, i.e., the decisions that matter most for the final policy. We address this through the Expert Iteration (ExIt) [16] with the Dataset Aggregation (DAgger) [17], interleaved with PPO between the training chunks, thereby periodically re-injecting a planner-based supervisory signal into the policy. The trigger is implemented as follows: PPO runs in 250,000-step chunks and a distillation iteration fires at the end of any chunk for which a 300,000step interval threshold has been crossed (the next-fire counter advances by 300,000 each time). Concretely, the first fire occurs at T = 500,000 Phase-3 steps (the first chunk boundary at or after the start threshold of 300,000), and subsequent fires snap to the chunk boundary at or after each +300,000 increment of the threshold. Because a +300,000 threshold advance lands between chunk boundaries every fourth chunk (the chunks at T ∈ {1.75M, 3.25M, 4.75M} fall below the threshold and skip), this realizes 20 distillation iterations over the 24 Phase-3 chunks, with an average inter-fire interval of ≈ 300,000 Phase-3 steps that matches the threshold parameter. Distillation procedure: Each ExIt iteration proceeds as follows: i. Roll-in. Collect 8,192 states by executing the current policy with probability 1 − pexpert = 0.80 and the heuristic expert (SACM++) with probability pexpert = 0.20. The mixed roll-in gives sufficient coverage of high-value state regions that the current policy may still visit infrequently. ii. Critic-bootstrapped labeling. For each collected state s, the candidate set is constructed by the same raw merge score key as Section IV-B (intersection size, then − min(di , dj ), then combined degree, then queue-index position), retaining the top Kpair = 12 pairs, expanding both keep-side variants, and always including the EDF unicast action, giving up to 2Kpair +1 = 25 mask-feasible candidates. For each candidate a, clone the environment (queue, hidden cache placement, and RNG bit-generator state) and execute the action; run SACM++ for d = 5 lookahead steps using the full shaped reward Rtotal at γ = 0.995, and bootstrap with the critic’s value estimate V̂θ (s′ ) at the terminal state. Average over M = 3 Monte Carlo seeds with common random numbers across candidates per seed, and select â = arg maxa Q̂(s, a), with the same candidate-enumeration tie-break as in BC. The pruning-sensitivity caveat from BC carries over verbatim. iii. Buffer aggregation. Append the (s, â) pairs to a DAgger replay buffer capped at 80,000 entries (uniform random eviction when full).