Conceptio › Archive › arXiv CS
arXiv CSopen access

Learning Selective Merge Policies for Deadline-Constrained Coded Caching via Deep Reinforcement Learning

2026 · arxiv_cs
arXiv CS · Papers · License: Open Access · 2026
Open Source ↗Direct PDF ↓
distributed-systemsinternetnetworkingprotocols
networking, internet, protocols, distributed systems

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).

(YDOXDWLRQ5HZDUG

PREPRINT — SUBMITTED FOR PEER REVIEW

,

      

18

D (YDOXDWLRQUHZDUGSHUHSLVRGH

BC–ExIt teacher (SACM++) is

6WDJH,,, N = 100, pc = 0.30

,,

a(m) = σv(m) − σvSACM++ , v

where σv denotes BE-score on seed v. The selection criterion is the robust advantage: Ω(m) = ā(m) − 0.5 σ̂a(m) ,

6$&0

(26) (m)

('8QL5QG *&0

±VWG

0HDQ VHHGV

E 7UDLQLQJORVVHV VPRRWKHGPHDQDFURVVVHHGV 





9DOXH/RVV

3ROLF\*UDGLHQW/RVV

(25)



 



 

 









7UDLQLQJ6WHSV PLOOLRQV 3ROLF\JUDGLHQWORVV





9DOXHORVV

Fig. 3. Training dynamics of the Track A (uniform-demand) agent across 4 seeds. The x-axis shows total RL environment steps (6.05M per seed, including the 50K Phase-2 warm-up); curriculum stage transitions therefore appear at T = 50K + 500K = 550K and T = 50K + 1.0M = 1.05M on this axis (corresponding to TPhase 3 = 500K and 1.0M Phase-3 steps). (a) Evaluation reward (mean ± std across seeds); vertical dashed lines mark curriculum stage transitions at 550K and 1.05M total RL steps. Horizontal dotted lines show baseline policy rewards (SACM++, ED-Unicast/Random, GCM) evaluated under the same training reward configuration. (b) Policygradient loss (left axis, blue) and value loss (right axis, orange), both smoothed and averaged across seeds. Both losses stabilize after ∼2M total RL steps, with periodic perturbations from ExIt distillation events.

iv. Distillation. Train the policy on the buffer for 2 epochs via cross-entropy loss, Adam, η = 1 × 10−4 , batch size 2,048. Because the ExIt teacher bootstraps from the agent’s own improving critic V̂θ , the labels improve as the training progresses, thereby letting the agent surpass its heuristic teachers (Appendix K). Algorithm 2 summarizes the complete three-phase training pipeline. Fig. 3 shows the evolution of evaluation reward and training losses across the three curriculum stages.

with ā(m) the mean per-seed advantage and σ̂a its standard deviation across the 50 validation seeds. The −0.5 σ̂ penalty favors the models with both the high average advantage and the low variance, while it penalizes the models that perform well only on a subset of the validation seeds. We pick the model with the highest Ω(m) and evaluate it once on the holdout seeds, considering that these holdout seeds are never observed during the training or the model selection, thereby giving us an unbiased estimate of the generalization performance. Appendix S reports the holdout performance of all four seed models, confirming the low inter-seed variance. Methodological caveat: σ-based selection vs. the primary demand-centric metrics. The selection criterion is aligned with the broadcast-efficiency score σ, while Sec. V-D declares the broadcast-packet expiration ratio ρ and the distinct file-identity coverage δ as the primary user-facing metrics, i.e., the metrics we report in the headline tables; the request-level family (ηreq , mreq , σreq ) is supplementary in the current version (fullbaseline coverage left as future work). We chose σ as the preregistered selection criterion because it is the only metric that matches the base training reward Rbase = Ut −Et (Sec. III-F5, Remark 1), thereby keeping the validation–training comparison consistent. The extended seed-stability table at Appendix S reports σ, ρ, served/tx, expirations, δ, ηreq , mreq , and σreq across the four seeds and shows narrow inter-seed spread on every column. The selected seed is the per-seed best on both of the primary demand-centric metrics (ρ=0.203 and δ=0.824) as well as on σ, while on the supplementary request-level family it is competitive even though it is not the per-seed leader (i.e., seed 1 reaches σreq =0.853 with respect to the selected seed’s 0.833), which reflects a broadcast-efficiency / requestlevel deadline-compliance trade-off rather than a weakness on the selected seed’s own primary objective. We do not report a focused robustness sweep over alternative selection rules (bestρ, best-mreq , or a Pareto multi-metric rule) in this version; that controlled selection-sensitivity sweep remains future work. V. E XPERIMENTAL P ROTOCOL

F. Model Selection We ran four independent training seeds (each with distinct network initializations and environment seeds), thereby giving us four candidate models. To control for the variance in the training outcomes [27], we selected among the four candidates using a robust advantage criterion evaluated on 50 validation seeds that are entirely separate from the 50 holdout seeds used in the final evaluation reported in Section VI. For each candidate model m and validation seed v, the perseed advantage over the highest-throughput coded baseline /

This section describes the two evaluation tracks, the complete set of methods (Track A: 9 baselines + PPO = 10 unique methods, 12 table rows with the two literature-compatible aliases; Track B: 6 baselines + PPO-Zipf = 7 unique methods), the non-ID generalization regimes (split into the curriculumseen and the unseen-parameter ones; see Sec. V-C for the narrow within-family sense in which we use “OOD-” throughout), and the statistical reporting protocol, i.e., the protocol that we follow for all the comparisons in this paper. The quantitative results are deferred to Section VI.

PREPRINT — SUBMITTED FOR PEER REVIEW

19

TABLE V D EFAULT E NVIRONMENT PARAMETERS (T RAINING D OMAIN ) Symbol N B K Q D H pc Pmax

Description

Value

File catalog size Subfiles per file Edge caches (users) Queue capacity Max deadline (slots) Episode horizon (steps) Decentralized cache fraction  Max candidate merge pairs = Q 2

100 10 5 10 20 50 0.30 45

A. Environment Parameters and Training Configuration All the experiments use the environment described in Section III-F with the default parameters listed in Table V. We trained two agents independently, i.e., the Track A agent on the uniform demand (≈1.73M parameters) with N =100, pc =0.30, D=20; and the Track B agent on the Zipf demand (α=0.8, ≈1.75M parameters, with the additional popularityaware features). Within each track, all the evaluation conditions beyond the training domain are non-ID, while we further split the non-ID into the curriculum-seen regimes (i.e., the parameter values the agent encountered during the curriculum stages of Sec. IV-D) and the out-of-distribution (OOD) regimes (i.e., the parameter values never seen during the training). The exact split is given in Sec. V-C (Track A: 2 curriculum-seen, 5 OOD; Track B: 2 curriculum-seen, 9 OOD). The queue size Q = 10 and the number of caches K = 5 are fixed across all the experiments. Varying K changes the observation dimension (dreq = 2K + 3) and would require retraining, even though the rest of the architecture remains the same; extending to K ∈ {10, 20} is left for the future work (Section IX). We ran four independent training seeds, each for 6,000,000 Phase-3 environment steps (plus a 50,000-step Phase-2 warmup, for 6,050,000 total RL environment steps per seed) using MaskablePPO with 32 parallel environments and the threephase curriculum described in Section IV. The model selection uses the robust advantage criterion Ω = ā − 0.5σ̂a on a validation split of 50 seeds, entirely separate from the holdout set. The selected model is evaluated on 50 holdout seeds (200 episodes/seed), thereby giving 10,000 episodes per method per evaluation condition. All the methods share the identical seed set under each condition, thereby giving a fully paired design. The seed formulas, the wall-clock times, and the inference latency are reported in Appendix N. B. Baseline Implementations We compare against the 9 Track A baselines (ED-Unicast, GCM, SACM, SACM+, SACM++, TauFit-0/1/2/3) and the 6 Track B baselines (i.e., the five Track A coded methods reused under the Zipf demand plus the popularity-aware SACM++Pop). Counting PPO as the trained agent, the Track A evaluation reports 9 + 1 = 10 unique methods, displayed as the 12 table rows once the two literature-compatible aliases (Perfect-Fit ≡ TauFit-0 and First-Fit ≡ TauFit-3) are shown for

the compatibility with the prior literature, while the Track B evaluation reports 6+1 = 7 unique methods. The baselines are organized into the three strategy families. Table VI summarizes all the baselines with their merge rates on the ID-default condition. Family 1 — Conservative Uncoded: ED-Unicast transmits the earliest-deadline pending request as a unicast packet at every step, irrespective of the available merge set. It is the deadline-safe lower bound, i.e., zero expirations from the excessive merging, even though there is no coding gain (merge rate = 0). Family 2 — Aggressive Coded Multicast: All four methods in this family always merge whenever Mt ̸= ∅, giving merge rate = 100%. GCM (Greedy Coded Merge) selects the first element of Mt without further discrimination. SACM selects the pair that maximizes the cached sideinformation intersection |Si ∩ Sj |, consistently keeping endpoint i [6]. SACM+ refines the keep-side decision: after selecting the maximum-intersection pair, it retains the endpoint with the higher merge degree, improving future connectivity. SACM++ applies a lexicographic priority key (|Si ∩ Sj |, − min(di , dj )) that maximizes the side-information overlap and then prioritizes the more time-critical pair, while keeping the degree-aware endpoint retention. SACM++ is the highest-throughput coded-multicast baseline in our reference simulator (i.e., the highest Served/Tx, µ, on the ID-default uniform table) and is the heuristic teacher used for the BC and the ExIt, considering that it maximizes the broadcast-level packet throughput; even though it is the highest-throughput baseline, it is not the per-metric best baseline (e.g., GCM and SACM tie SACM++ on ρ at 0.345 on the ID-default, while SACM has a higher σ than SACM++). Baseline keep-side semantics. For all baseline methods (SACM, SACM+, SACM++, and the SACM++-Pop variant introduced below), the keep-side bit selects only which queue slot is vacated and refilled (Sec. III-C); the representative destination kmg follows Eq. (6) independently of κ, exactly as it does for the learned policy. “Endpoint retention” here is therefore a queue-slot operation, not a destination-identity operation. Family 3 — Oracle-Tuned Threshold Policies (τ -Fit): This family uses the misfit metric [5], while the threshold τ ∈ {0, 1, 2, 3} controls the merge aggressiveness, from the Perfect-Fit (τ =0, merge rate 13.3%) through the TauFit-1/2/3 (33.2%–41.6%) to the First-Fit (τ =K−2, identical to TauFit3). The Perfect-Fit and TauFit-0 are identical (τ =0), while the First-Fit and TauFit-3 (τ =K−2) are likewise identical, i.e., the same policy with two different labels. Both of the alias labels are retained in the tables for the compatibility with the prior literature, thereby giving 12 table rows from the 10 unique methods (i.e., the 9 Track A baselines plus PPO). For each evaluation metric, we select the oracle-optimal τ ∗ by the exhaustive search on the validation split, considering that this oracle is unavailable at the deployment and is the ceiling of any fixed-threshold policy. The full misfit definition and the per-metric oracle selections are in Appendix M.

PREPRINT — SUBMITTED FOR PEER REVIEW

20

TABLE VI BASELINE S UMMARY (M ERGE R ATE ON ID-D EFAULT, U NIFORM D EMAND ) Method

Family

Merge Rate

Key property

ED-Unicast GCM SACM SACM+ SACM++ Perfect-Fit TauFit-1 TauFit-2 TauFit-3 First-Fit

Uncoded Coded (greedy) Coded Coded Coded τ -Fit (τ =0) τ -Fit (τ =1) τ -Fit (τ =2) τ -Fit (τ =3) τ -Fit (τ =3)

0% 100% 100% 100% 100% 13.3% 33.2% 40.6% 41.6% 41.6%

Never codes First feasible pair Max intersection Max inter. + degree keep Lex (inter., −d) + degree Misfit=0 only Misfit≤1 Misfit≤2 Misfit≤3 ≡ TauFit-3

SACM++-Pop

Coded (Track B)

100%

Pop.-weighted inter.

PPO-Agent

Learned

31.8%

Selective (adaptive)

Track B Additional Baseline: For the Zipf-demand track (Section V-C), we add SACM++-Pop: a popularity-aware extension of SACM++ that uses the lexicographic priority key  |Si ∩ Sj |, m̂(fi ∪ fj ), − min(di , dj ) , sorted in descending order, where m̂(·) P is the popularity-mass projection of Appendix F (m̂(f ) = p∈f p̂ϕ(p) under the assumed Zipf file-popularity law). Ties on the full key are broken by the lexicographic queue-index order (i, j) with i < j. The keep-side bit is set to κ=0 when deg(ri )+2m̂(fi ) ≥ deg(rj )+ 2m̂(fj ) and to κ=1 otherwise (popularity-weighted degreeaware endpoint retention); the representative destination still follows Eq. (6) as for every method (Sec. III-C). This baseline tests whether a heuristic that explicitly exploits the Zipf skew can close the gap with respect to the learned policy.

PREPRINT — SUBMITTED FOR PEER REVIEW

Algorithm 2 BC → PPO → ExIt Training Pipeline Input: Environment E, heuristic teacher SACM++, hyperparams (Table XXXIII) Output: Trained policy πθ // Phase 1: Rollout-Improved Behavior Cloning (§IV-B) = 150K state–action pairs (s, a∗ ) using rollout teacher 2: Train πθ via cross-entropy loss for 6 epochs (Adam, η = 3×10−4 )

1: Collect NBC

// Phase 2: Value Network Warm-Up (§IV-C) 3: Freeze pairwise action head of πθ 4: Run MaskablePPO for 50K steps (critic only receives

gradients) 5: Unfreeze pairwise action head

// Phase 3: MaskablePPO + Curriculum + ExIt (§IV-D– IV-E) // Single global Phase-3 step counter T , 250K-step chunks; 6M total Phase-3 steps across all stages (24 chunks). Adding the 50K Phase-2 warm-up gives 6.05M total RL env steps per seed. // Curriculum advance schedule: I → II at T = 500K (after 2 chunks); II → III at T = 1M (after 4 chunks); III runs the remaining 20 chunks (5M steps). 6: T ← 0; Tnext ← 300K; stage ← I with (N =60, pc =0.50) 7: while T < 6M do 8: if T = 500K then stage ← II with (N =80, pc =0.40) 9: end if 10: if T = 1M then stage ← III with (N =100, pc =0.30) 11: end if 12: Run MaskablePPO with GAE (γ=0.995, λ=0.95) for one 250K-step chunk 13: T ← T + 250K 14: if T ≥ Tnext then ▷ ExIt fires only when T has crossed the next +300K threshold 15: // ExIt distillation (§IV-E) 16: Collect 8,192 states via mixed roll-in (pexpert =0.20) 17: Label each state: critic-bootstrapped lookahead planner 18: Append (s, â) to DAgger buffer (cap 80K) 19: Distill: 2 epochs cross-entropy on buffer 20: while Tnext ≤ T do Tnext ← Tnext + 300K 21: end while ▷ advance counter past current T 22: end if 23: end while 24: return πθ ▷ schedule realizes 20 ExIt iterations across the 24 chunks

21

PREPRINT — SUBMITTED FOR PEER REVIEW

22

C. Out-of-Distribution Evaluation Regimes Each track’s trained agent is evaluated zero-shot across multiple non-ID conditions, thereby giving 7 non-ID regimes for the Track A (2 curriculum-seen, 5 OOD) and 11 nonID regimes for the Track B (2 curriculum-seen, 9 OOD). Within each track, the same trained model is applied directly, without the retraining, the fine-tuning, or the parameter updates. The observation and action space shapes are invariant within each track (Q = 10, K = 5, Pmax = 45), while only the environment dynamics change. The two tracks use the different observation spaces (Table III) and independently trained models, so the cross-track comparisons reflect the two distinct policies rather than the zero-shot transfer of a single model. a) Curriculum-seen vs. unseen-parameter conditions.: Two of the non-ID evaluation conditions, N =60 (Stage I of the curriculum) and pc =0.40 (Stage II), were encountered during the training, even though at the earlier curriculum stages rather than at the convergence. We label these as the curriculumseen transfer conditions (prefix Curr-) to distinguish them from the unseen-parameter conditions (prefix OOD-) that were never seen during the training. The OOD- prefix is used throughout this paper in this narrow sense, i.e., the unseen parameter values (the catalog size, the cache fraction, the deadline budget, the Zipf exponent) within the same simulator family (K, Q, the action dimensionality 2Pmax +1, and the placement family are held fixed across all the evaluations), so all the transfer claims should be read as the within-family parameter generalization rather than as a broader distribution shift. The same convention applies to the Zipf track as well. Track A — Uniform Demand (2 Curr + 5 OOD conditions): Starting from the training domain (ID-default: N = 100, pc = 0.30, D = 20, uniform demand), we vary one parameter at a time: • Catalog size (sanity check): N ∈ {60, 120, 150} (Currfile60, OOD-file120, OOD-file150). Under the decentralized placement with fixed pc , the per-packet caching probability is preserved across the catalog sizes, while this axis therefore verifies that the policy’s queue-state features are invariant to the library cardinality rather than testing a true distribution shift (Section VI-C). • Cache density: pc ∈ {0.20, 0.40} (OOD-pcache0.20, Currpcache0.40). The lower density shrinks the feasible merge set, while the higher density makes the aggressive merging likely to cause the expirations through the queue saturation. • Deadline budget: D ∈ {10, 30} (OOD-delay10, OODdelay30). The tighter deadlines stress the expiration avoidance, while the looser deadlines reward the throughput maximization. Track B adds 11 non-ID regimes spanning the Zipf tail weight (α ∈ {0.6, 1.0, 1.2}), an alternative demand law (Mandelbrot-Zipf), and the same cross-axis shifts as the Track A. The full conditions are listed in Table VII, while the detailed descriptions are in Appendix M. Each track uses a separately trained agent, considering that the cross-track results are not aggregated. The Track B results are reported in Section VII.

TABLE VII E VALUATION C ONDITIONS (2 ID + 4 C URR + 14 OOD) Regime

Axis

N

pc

D

Track A — Uniform demand (8 conditions, 9 baselines + PPO = 10 unique methods) ID-default Curr-file60 OOD-file120 OOD-file150 OOD-pcache0.20 Curr-pcache0.40 OOD-delay10 OOD-delay30

— Catalog Catalog Catalog Cache density Cache density Deadline Deadline

100 60 120 150 100 100 100 100

0.30 0.30 0.30 0.30 0.20 0.40 0.30 0.30

20 20 20 20 20 20 10 30

Track B — Zipf demand (α=0.8 base, 1 ID + 2 Curr + 9 OOD, 6 baselines + PPO-Zipf = 7 unique methods, separately trained agent) Zipf-ID OOD-alpha0.6 OOD-alpha1.0 OOD-alpha1.2 OOD-mandelbrot Curr-file60 (Z) OOD-file120 (Z) OOD-file150 (Z) OOD-pcache0.20 (Z) Curr-pcache0.40 (Z) OOD-delay10 (Z) OOD-delay30 (Z)

— Tail weight Tail weight Tail weight Demand law Catalog Catalog Catalog Cache density Cache density Deadline Deadline

100 100 100 100 100 60 120 150 100 100 100 100

0.30 0.30 0.30 0.30 0.30 0.30 0.30 0.30 0.20 0.40 0.30 0.30

20 20 20 20 20 20 20 20 20 20 10 30

D. Performance Metrics We evaluate the scheduling policies on the thirteen metrics over an episode of H steps (ten performance, three diagnostic), organized into the four families (i.e., the broadcast-level, the file-identity, the request-level, and the diagnostic ones) and enumerated in detail below. Throughout this paper we adopt a single descriptor for the broadcast-level demand quantity: Ut is the packet-set-cardinality XOR degree at step t, defined as Ut = |fmg | for a coded transmission (the number of distinct packet identities carried P in the aggregate) and Ut = 1 for a unicast. Similarly, Et = r∈Xt |fr | is the broadcastlevel packet-identity count of expired records at step t. We deliberately avoid attaching “users served”, “user-equivalents”, or “number of original singleton requests” to Ut in the headline metric language: the request generator does not enforce uniqueness of packet identities across active records, so |fr | in general does not equal the number of original singleton arrivals folded into r (see the per-broadcast accounting remark in Appendix I for an explicit counterexample). Whenever original-arrival semantics are intended, we use the requestlevel metrics ηreq , mreq , σreq (M8–M10), which are computed from the per-arrival identifier sets A(r) stamped at arrival time and credit each original arrival exactly once. Because a packet identity folded into a coding-state record may participate in the subsequent broadcasts, Ut measures the per-slot broadcast utilization (i.e., the packet throughput) at the broadcast level, not the unique demand satisfaction. The three families therefore use three different notions of demand, and we use disjoint terminology to refer to them: (a) the broadcast-level family (ρ, σ, µ, g, ε) is computed from (Ut , Et ) and counts the packetset XOR degree per broadcast (i.e., distinct packet identities carried in the aggregate), where a packet identity folded into a chain can be counted at every link; (b) the file-identity family (δ, ρuniq ) is computed from (Utuniq , Etuniq ) and credits each distinct file identity exactly once per episode (this is a coverage indicator, not a multi-packet completion metric); (c) the request-level family (ηreq , mreq , σreq ) is computed from the original arrival identifiers A(r) defined in Sec. III-C0f and credits each individual user arrival exactly once. We therefore report four complementary views: (i) primary metrics (M1–M2): the broadcast-packet expiration ratio ρ (a

PREPRINT — SUBMITTED FOR PEER REVIEW

packet-set waste ratio at the broadcast level) and distinct fileidentity coverage δ (a coverage indicator at the file-identity level), which capture two different facets of timely delivery; (ii) request-level metrics (M8–M10, supplementary in the current version; the displayed request-level tables compare PPO against the SACM++ and ED-Unicast comparators, with full-baseline coverage over GCM, SACM, SACM+, and the τ Fit family left as future work, so this family is not a co-primary headline in the present manuscript): based on per-request ID tracking (Section III-C0f), which follow each original arrival through queue aggregation and credit completion or miss exactly once per request identifier; this is the only family in which the numerator objects are arrival-level identifiers (the equations remain H-normalized rather than total-arrivalsnormalized; see M8–M10); (iii) broadcast-efficiency metrics (M3–M7, secondary): based on Ut and Et as packet-set counts, which measure how well each channel use exploits the coded-multicast gain at the packet-set level; and (iv) diagnostic metrics (M11–M13): merge rate, opportunity rate, and reward per step, which characterize policy behavior rather than performance. Symbol-retention convention. We retain the symbol names ρ and δ for continuity with prior tables, but their semantics throughout this paper are the formal definitions of Eqs. (27)– (28), namely the broadcast-packet expiration ratio (a packetset waste ratio at the broadcast level) and the distinct fileidentity coverage (a once-per-file coverage indicator under the projection ϕ). “Demand-centric” is therefore a shorthand for those formal definitions rather than a claim of per-arrival miss-probability or per-user completion semantics; the requestlevel family ηreq , mreq , σreq (M8–M10) is computed from per-arrival identifiers but normalizes by H rather than by the total number of admitted arrivals, so it provides per-step request-level rates rather than per-arrival probabilities. The compact table-header labels “Miss Ratio” and “Coverage” used in Tables IX, XXI, XV, and elsewhere are the same symbol-retention shorthand: “Miss Ratio” is the broadcastpacket expiration ratio ρ (27) and “Coverage” is the distinct file-identity coverage δ (28); neither implies per-arrival or peruser satisfaction. Right-censoring at episode end. All the headline metrics (ρ, δ, σ, µ, g, ε, and the request-level ηreq , mreq , σreq ) are computed from the H = 50 in-episode steps only. The records still pending at step H are neither served nor expired in the counters, which is consistent with the truncated continuingcontrol framing of Sec. III-E, even though it does produce a policy-dependent right-censoring, i.e., a policy that defers the difficult records past the horizon will look better on ρ and mreq with respect to a tail-resolved evaluation. The intermethod comparisons are paired across the shared episode seeds and the shared initial cache placements, while the simulator does not implement strict common random numbers, i.e., the RNG draws within an episode are sequential, so the policydependent refill events cause the realized arrival sequences to diverge across the methods after the first divergent action. The censoring therefore is shared in expectation up to the firstdivergent-action RNG drift, rather than cancelling pathwise

23

(notably the paired-bootstrap intervals of Table VIII); the absolute values of ρ, mreq , and δ should therefore be read with this caveat. A sensitivity sweep over H ∈ {50, 100, 200} and a tail-flush variant are deferred to a follow-up extension. M1. Broadcast-Packet Expiration Ratio (↓, primary). The fraction of broadcast-level packet-set mass that expires before delivery is H X

ρ=

Et

t=1 H X

Ut +

t=1

H X

.

(27)

Et

t=1

Both the numerator and the denominator are computed from the packet-set counts (Ut , Et ), not from the original arrival identifiers, so ρ is a broadcast-channel waste ratio (i.e., the fraction of the packet-set mass on the channel that is lost to the expiration) rather than a per-arrival miss probability, while the request-level counterpart is mreq (M9), itself a per-step rate rather than a per-arrival probability. We retain the symbol ρ for continuity with prior tables but use the broader name “broadcast-packet expiration ratio” to avoid implying per-user miss-rate semantics. Lower values indicate better timely delivery at the broadcast level. M2. Distinct File-Identity Coverage (↑, primary). Fraction of distinct file identities that appeared in the served set at least once during the episode, under uniquedemand (file-identity) accounting (Section III-C). Under the packet-level request model (each arrival is a singleton packet request), δ is therefore a coverage indicator: a file identity is credited once any of its packets is served, and subsequent packet requests for the same file no longer contribute to Utuniq . We refer to this as “coverage” rather than “demand satisfaction” or “demand completion” because δ does not measure completion of a multi-packet user-file request: H X

δ=

Utuniq

t=1 H X t=1

Utuniq +

H X

.

(28)

Etuniq

t=1

Here Utuniq and Etuniq are file-identity counts defined formally via the packet-to-file projection ϕ(p) = ⌊p/B⌋ in Eqs. (8)–(9): Utuniq counts only file identities not previously delivered in the episode, and Etuniq counts only file identities in an expired record that were never delivered during the episode. A coding-state record whose constituent file identities were already covered earlier in the episode contributes Etuniq = 0 upon expiration. Unlike σ (M3), each distinct file identity is counted exactly once; unlike ηreq /mreq (M8/M9), all packet arrivals targeting the same file are conflated into a single coverage event. This is the primary file-identity coverage metric; for request-level completion accounting

PREPRINT — SUBMITTED FOR PEER REVIEW

24

(computed from per-arrival identifiers, H-normalized) see the request-level metrics M8–M10. M3. Broadcast-Efficiency Score (BE-Score, ↑, secondary). A composite metric that jointly rewards per-broadcast XOR degree and penalizes expirations: σ=

H  1 X Ut − λEt , H t=1

λ = 1,

(29)

We label this “average XOR degree” rather than “coding gain” to match the packet-set semantics of Ut ; tables retain the legacy “Coding Gain” column header for continuity with prior literature. M6. Expirations per Episode (↓). Total count of distinct queue-entrySexpiration events per episode P (the count of records in t Xt , not the packet-set mass t Et ): H X

|Xt |. (32) with higher values preferred. Because Ut is the packett=1 set-cardinality XOR degree of the broadcast at step t (counting distinct packet identities, not original singleton In the tables, “Exp/Episode” always refers to ε. Whenarrivals), σ measures broadcast-slot packet utilization ever the reward-decomposition discussion accompanying rather than unique demand satisfaction. A policy that Fig. 9 or the appendix refers to P “expired packet-set creates the deep merge chains can achieve a high σ, mass,” that is the distinct quantity t Et (the sum of even though some of the underlying demands are served |fr | over expired records), and not ε. redundantly. For this reason, σ is reported as a secondary M7. Unique Miss Ratio (↓). Complement of δ: broadcast-efficiency metric, while the primary evaluation ρuniq = 1 − δ. (33) uses the demand-centric metrics ρ (M1) and δ (M2). The model selection during the training uses σ because it M8. Request Timely-Throughput (↑, supplementary). Avmatches the training reward (Remark 1). We note that erage number of newly completed original request identhe selection on σ is not the same as the selection on the tifiers per step, under request-level accounting (Secprimary metric ρ, i.e., the σ-selected checkpoint is the tion III-C0f; computed from the per-arrival identifier sets model that maximizes the broadcast-efficiency composite A(r) stamped at arrival time): at the validation, while the headline ρ results in Sec. VI H are then read off that checkpoint rather than off a sepa1 X |Ct |, (34) η = rately ρ-selected one. We adopt σ because it (i) coincides req H t=1 with the shaped training surrogate, thereby producing stable validation rankings during the checkpoint sweep, where Ct is the set of request IDs completed at step t and (ii) penalizes the expirations (−Et ) directly, so the that were not previously completed or missed. σ-selection is not blind to the deadline compliance, even M9. Request Miss Rate (↓, supplementary). Average numthough it is not formally identical to the ρ-selection. ber of newly missed original request identifiers per step, A formal per-metric selection-criterion sensitivity sweep computed from the per-arrival identifier sets A(r): remains the future work. H The composite score uses λ=1, while Appendix O re1 X m = |Mt |. (35) req ports a sensitivity sweep over λ ∈ {0.5, 1, 2, 3}. PPO H t=1 retains the rank 1 among all the coded-multicast methods for λ ≥ 1, while it ranks fourth at λ=0.5, where the low This is the finest-grained demand-centric metric: it meaexpiration penalty favors the aggressive always-merge sures the per-step rate at which original user arrivals baselines. miss their deadlines, tracking each arrival through all M4. Served Packet-Set per Transmission (↑). Average merge aggregations (and is therefore distinct from both broadcast-level packet-set cardinality delivered per transthe broadcast-level ρ and the file-identity ρuniq ). mission slot (the “Served/Tx” column in our tables): M10. Request Selection Score (↑). Composite request-level metric analogous to σ (M3): H 1 X H Ut . (30) µ=  1 X H t=1 |Ct | − λ |Mt | , λ = 1. (36) σreq = H t=1 We retain the column header “Served/Tx” for table compactness, but µ is a packet-set count per slot, not The λ-sensitivity of σreq is analyzed in Appendix P. a count of original arrivals served per slot; the request- M11. Merge Rate (diagnostic). Fraction of steps with at least level counterpart is ηreq (M8), itself a per-step requestone feasible merge pair at which the agent elects to level rate. merge: M5. Average XOR Degree (↑). Mean packet-set cardinality {t : at ∈ coded, |Mt | > 0} per coded broadcast, restricted to time steps where a mrate = . (37) {t : |Mt | > 0} coded action is taken: X This metric is neither universally better high nor low, Ut considering that it characterizes the policy’s selectivity t : coded g= . (31) rather than its performance. {t : coded action at t} ε=

PREPRINT — SUBMITTED FOR PEER REVIEW

25

M12. Opportunity Rate (diagnostic). Fraction of steps at which at least one feasible merge pair exists, measured along the queue trajectory visited by the evaluated policy: orate =

{t : |Mt | > 0} . H

(38)

Even though |Mt | is a function of the queue state, the queue trajectory itself is shaped by the policy (i.e., every merge clears one slot and refills the other with a fresh arrival), so orate is a visited-state (i.e., policy-induced) diagnostic, not an exogenous environment constant. It is reported to contextualize the merge-rate values in the same row of each results table. M13. Reward per Step (diagnostic, training only). Mean shaped reward per step; reported as a training diagnostic only and never used for method ranking (definition in Appendix M). For the τ -Fit family, each metric is optimized independently, i.e., the oracle threshold τ ∗ for a given metric is selected by the exhaustive search on the validation split, while the resulting policy is then evaluated on the holdout set. This procedure ensures that each τ -Fit variant is evaluated at its best for that metric, thereby giving each τ -Fit variant its strongest possible appearance in our comparisons. Statistical reporting. All the methods share the same holdout seeds and the same initial cache placements, i.e., a shared-seed paired design at the seed/context level rather than a strict common-random-numbers (CRN) scheme, considering that within an episode the RNG draws are sequential, so the policy-dependent refill timing causes the realized arrival sequences to diverge across the methods after the first divergent action (see the no-CRN caveat in Sec. V-D). Every comparison is therefore computed on the per-seed paired differences, with the understanding that the pairing holds at the seed/context level rather than pathwise. We report the mean ± 95% CI across the seed-level means, while for the main comparisons we report the 95% percentile bootstrap CI of the paired difference (10,000 resamples). The paired-bootstrap procedure is as follows: for each of the 50 evaluation seeds we compute the per-seed mean of each metric under each method (i.e., averaging over the 200 episodes/seed), form the per-seed paired difference ∆s = mPPO − mbaseline , and report s s the 95% percentile-bootstrap CI of the across-seed average ¯ over 10,000 resamples (drawing with replacement from ∆ the {∆s }50 s=1 values). Following the [27], [28], we report the effect sizes with the calibrated uncertainty rather than the binary significance claims. Additional procedural details are in Appendix M. E. Reproducibility The implementation uses PyTorch and the StableBaselines3 [30] with the MaskablePPO [29]. All the random number generators are seeded deterministically, while the evaluation uses the argmax action selection. The full source code will be released upon acceptance. The complete reproducibility details, the hardware specifications, and the computational costs are in Appendix N.

VI. M AIN R ESULTS : U NIFORM -D EMAND B ENCHMARK We report results for the uniform-demand benchmark (Track A). All values are mean ± 95% CI across 50 holdout seeds × 200 episodes per seed (10 000 episodes per cell); for key comparisons we also report bootstrap CIs of the paired difference (see Section V-D). Primary evaluation uses the demand-centric metrics broadcast-packet expiration ratio ρ (M1) and distinct file-identity coverage δ (M2), supplemented by the broadcast-efficiency score σ (M3), served/tx µ, coding gain g, expirations ε, and request-level views (M8–M10); the shaped training reward is excluded from comparison tables and is never used for method ranking. Throughout this section, ρ and δ (the primary demand-centric metrics; mreq is supplementary, see Sec. V-D) are paired within-benchmark quantities at fixed H=50 with episode-end right-censoring; absolute values are simulator-specific (Sec. V-D). All headline numerical results in this section are reported for the σ-selected checkpoint (Sec. IV-F); a primary-metric-aligned selection rule is left as future work. The reported gains are also conditional on the one-slot-per-record unicast cost abstraction (A2), on the uniform representative-destination convention kmg ∼ Unif{ki , kj } (Eq. (6)), and on the aggregate-size observation clip min(|fr |, Umax )/Umax at Umax = 6 (Sec. III-F2); see the first-order limitations paragraph in Sec. IX. a) Summary of findings.: We summarize the main findings and the mechanisms that drive them before presenting the detailed tables: • The method of selective merging achieves the lowest broadcast-packet expiration ratio among the coded multi-casting methods. The results of our experiment show that the policy network outperforms the best baseline of the coded multi-casting method, i.e., SACM++, by 40.9% with respect to the broadcast-packet expiration ratio (ρ = 0.208 vs. 0.352; paired-bootstrap 95% CI on the relative reduction: [40.6%, 41.5%], computed from ∆ρ ∈ [−0.146, −0.143] in Table VIII normalized by ρSACM++ = 0.352), while reducing the expirations by 50.7% (14.17 vs. 28.76 per episode), i.e., the policy network achieves all of this without compromising the satisfaction of the users’ demands. Among all methods, only ED-Unicast (which never codes) achieves a lower broadcast-packet expiration ratio (ρ = 0.134). The distinct file-identity coverage of the policy network is competitive, i.e., δ = 0.824 for the policy network vs. 0.866 for ED-Unicast and 0.797 for SACM++. The policy network also achieves the highest composite broadcast-efficiency score (σ = 0.976), i.e., the method of selective merging lowers the broadcast-packet expiration ratio and improves the composite BE-score even though the raw Served/Tx (µ) of the policy network is lower than that of the always-merge coded baselines (e.g., the policy network at µ = 1.323 vs. SACM++ at µ = 1.590 at ID-default). Why: by restricting the coded transmissions to the high-intersection pairs (avg. 0.589 vs. 0.393 for SACM++), the policy network preserves the bandwidth headroom for unicasting the deadline-critical requests. • The policy network outperforms even the oracletuned thresholds. The τ -Fit family saturates at σ=0.915

PREPRINT — SUBMITTED FOR PEER REVIEW

(broadcast-efficiency score) regardless of the threshold, while the policy network outperforms this ceiling by +6.61% to +11.25% with respect to the oracle’s tuning criterion. Why: a fixed threshold commits to a static throughput–reliability tradeoff, whereas the policy network conditions on the instantaneous queue configuration and adapts the merge decision per step, i.e., it is not bound by the saturation curve. • The advantages of the policy network grow under stress, while the expirations show the largest relative improvement. The broadcast-efficiency advantage of the policy network over SACM++ grows from +34.4% at IDdefault to +79.0% at high cache density (pc =0.40) and an absolute +0.449 BE-score units under tight deadlines (D=10), i.e., the same observation is true for the variations of the cache fraction and deadline budgets as well. Why: the abundant merge opportunities cause the blind-merge policies to flood the channel with low-quality coded packets, thereby producing the deadline cascades that the method of selective merging avoids. The policy network reduces the expirations by 50.7% with respect to SACM++ (14.17 vs. 28.76 per episode), i.e., the single largest per-metric gain, which directly follows from the selective-merge mechanism, i.e., fewer low-overlap merges means fewer wasted transmission slots and more timely deliveries before the deadlines expire. A. In-Distribution Performance (Track A) Table IX reports the six core methods on the ID-default uniform-demand condition, sorted by broadcast-packet expiration ratio (M1) ascending; the full comparison including τ -Fit threshold rules is deferred to Appendix Table XXV; per-metric rankings of all methods are provided in Appendix Table XXVI. The results of our experiment show that the PPO-Agent, i.e., the policy network, achieves the lowest broadcast-packet expiration ratio among all the coded multi-casting methods (ρ = 0.208±0.001), while reducing the deadline misses by 40.9% with respect to the best baseline of the coded multi-casting method, i.e., SACM++ (ρ = 0.352). Only ED-Unicast achieves a lower broadcast-packet expiration ratio (ρ = 0.134), while at the cost of zero coding gain, i.e., the policy network outperforms ED-Unicast by 15.5% on the broadcast-efficiency score (σ = 0.976 vs. 0.845, denominator ED-Unicast). The distinct file-identity coverage of the policy network is δ = 0.824, while below ED-Unicast’s 0.866 (i.e., a structural consequence of unicast serving exactly one unique request per slot with no merge-induced expirations) yet above all of the SACM variants (0.797 for SACM++). No baseline of the coded multi-casting method achieves higher δ than the policy network. The policy network also achieves the highest broadcast-efficiency score on the ID-default Track A regime (σ = 0.976 ± 0.002, i.e., the highest among all evaluated methods) and the highest average XOR degree (g = 2.162). Across the full Track A non-ID battery, the policy network leads on σ among the coded multi-casting methods in all 8 regimes, and among all evaluated methods, the policy network leads in 7 of 8 Track A regimes, while ED-Unicast takes the top σ at OOD-delay10 (Appendix

26

TABLE VIII PAIRED BOOTSTRAP 95% CI OF METRIC DIFFERENCES (PPO-AGENT MINUS BASELINE ) ON 50 SHARED HOLDOUT SEEDS (10 000 RESAMPLES ). N EGATIVE ∆ρ, ∆mreq / POSITIVE ∆δ, ∆ηreq , ∆σ FAVOR PPO-AGENT. Baseline

∆ρ (95% CI)

∆δ (95% CI)

∆mreq (95% CI)

∆ηreq (95% CI)

∆σ (95% CI)

ED-Unicast SACM++

+0.074 [+0.073, +0.075] −0.144 [−0.146, −0.143]

−0.043 [−0.044, −0.042] +0.027 [+0.026, +0.028]

+0.074 [+0.073, +0.076] −0.097 [−0.099, −0.095]

+0.069 [+0.068, +0.069] −0.217 [−0.219, −0.215]

+0.131 [+0.129, +0.133] +0.250 [+0.248, +0.253]

Table XXVIII; ED-Unicast 0.019 vs. the policy network −0.002). The Zipf-track BE-score picture is different and is discussed separately in Section VII. Table VIII reports the paired bootstrap 95% CIs of the metric differences between the policy network (PPO-Agent) and two reference baselines, i.e., ED-Unicast (the conservative miss-ratio leader) and SACM++ (the highest-throughput coded baseline and the BC/ExIt teacher), computed on the 50 shared holdout seeds (10 000 resamples). Against the best baseline of the coded multi-casting method, i.e., SACM++, the policy network achieves a significantly lower broadcast-packet expiration ratio (∆ρ = −0.144 [−0.146, −0.143]), a higher distinct fileidentity coverage (∆δ = +0.027 [+0.026, +0.028]), a 29.8% lower request miss rate (∆mreq = −0.097 [−0.099, −0.095]), and a higher broadcast-efficiency score (∆σ = +0.250 [+0.248, +0.253]). The tradeoff is a lower request throughput (∆ηreq = −0.217 [−0.219, −0.215]), which follows from the always-merge strategy of SACM++. Against ED-Unicast, the policy network trades a moderate increase in the broadcast-packet expiration ratio (∆ρ = +0.074) and a small decrease in the file-identity coverage (∆δ = −0.043) for a substantially higher broadcast efficiency (∆σ = +0.131), i.e., all intervals exclude zero.

PREPRINT — SUBMITTED FOR PEER REVIEW

27

TABLE IX I N - DISTRIBUTION (ID- DEFAULT ), UNIFORM DEMAND . 50 HOLDOUT SEEDS × 200 EPISODES . M EAN ± 95% CI. B OLD = BEST PER COLUMN . U NDERLINING IS USED only on the PPO-Agent row TO MARK CELLS WHERE PPO RANKS SECOND AFTER AN UNCODED ED-U NICAST BEST (M ISS R ATIO , C OVERAGE δ, E XP /E PISODE ); OTHER ROWS DO NOT CARRY SECOND - BEST ANNOTATIONS BECAUSE THE FOCUS OF THE COMPARISON IS PPO’ S PER - METRIC PLACEMENT RELATIVE TO THE COLUMN LEADER . Miss Ratio (↓)

Coverage δ (↑)

BE-Score σ (↑)

Served/Tx (↑)

Coding Gain (↑)

Exp/Episode (↓)

ED-Unicast PPO-Agent GCM SACM SACM+ SACM++

0.134 ± 0.001 0.208 ± 0.001 0.345 ± 0.001 0.345 ± 0.001 0.348 ± 0.001 0.352 ± 0.001

0.866 ± 0.001 0.824 ± 0.001 0.784 ± 0.001 0.782 ± 0.001 0.787 ± 0.001 0.797 ± 0.001

0.845 ± 0.001 0.976 ± 0.002 0.733 ± 0.003 0.745 ± 0.003 0.731 ± 0.003 0.726 ± 0.003

1.000 ± 0.000 1.323 ± 0.002 1.549 ± 0.002 1.575 ± 0.002 1.572 ± 0.002 1.590 ± 0.003

— 2.162 ± 0.002 2.095 ± 0.001 2.131 ± 0.001 2.124 ± 0.001 2.131 ± 0.001

7.74 ± 0.06 14.17 ± 0.07 28.42 ± 0.15 28.64 ± 0.13 28.71 ± 0.14 28.76 ± 0.14

With respect to SACM++, i.e., the highest-throughput heuristic, the policy network reduces the broadcast-packet expiration ratio by 40.9% (0.208 vs. 0.352) and the expiredrecord count per episode (ε) by 50.7% (14.17 vs. 28.76), while also improving the average XOR degree by +1.5% (2.162 vs. 2.131). The single metric where the policy network does not lead is the served packet-set count per transmission (µ = 1.323 vs. 1.590 for SACM++), i.e., the policy network transmits fewer coded packets overall, while those coded packets are of substantially higher quality and impose far fewer broadcastpacket expirations. ED-Unicast achieves the highest distinct file-identity coverage (δ = 0.866 vs. the policy network’s 0.824). This advantage is structural-by-design rather than an artifact of the metric definition, i.e., unicast serves at most one new file identity per transmission and never incurs merge-induced expirations, which empirically yields the highest δ in our evaluation. We avoid claiming that ED-Unicast maximizes δ “by construction” (a unicast can contribute zero to Utuniq when its target file identity has already been covered earlier in the episode), while the absence of merge-induced expirations and the avoidance of multi-file aggregates explain why this empirical advantage persists across the regimes. However, this unicast-only strategy forfeits all coding gain, i.e., the policy network outperforms ED-Unicast by 15.5% on the broadcast-efficiency score (σ = 0.976 vs. 0.845, denominator ED-Unicast). The method of selective merging of the policy network trades a moderate δ reduction (−4.9% with respect to ED-Unicast) for substantially better channel utilization. No baseline of the coded multi-casting method achieves higher δ than the policy network. A useful diagnostic is the merge rate, i.e., the policy network merges only 31.8% of the available opportunities, whereas all of the SACM variants merge 100%. No single coded multi-casting baseline achieves better values than the policy network across the joint objective {ρ, δ, σ, g}, i.e., SACM++ wins on µ while losing on ρ, δ, and σ. The uncoded EDUnicast baseline wins on ρ and δ while losing on σ and g (by definition, i.e., the coding gain g = 0 for any unicastonly scheme). This multi-objective dominance is visualized in Fig. 4, i.e., the policy network (PPO-Agent) occupies the upper-left (most favorable) region of the σ–ρ trade-off space, with a higher broadcast-efficiency score and a lower broadcastpacket expiration ratio than any point on the τ -Fit threshold sweep. Fig. 5 shows the complementary demand-centric view,

%URDGFDVW(IILFLHQF\6FRUH  KLJKHULVEHWWHU

Method



,GHDO

332$JHQW



= 2, 3

 

=1 =0 ('8QLFDVW

   

332$JHQW ('8QLFDVW 6$&0IDPLO\ )LWVZHHS





6$&0







'HDGOLQH0LVV5DWLR  ORZHULVEHWWHU

Fig. 4. Multi-objective trade-off between broadcast-efficiency score σ (↑) and broadcast-packet expiration ratio ρ (↓) on the ID-default uniform benchmark (50 holdout seeds, 10 000 episodes). PPO-Agent (star) achieves both higher σ and lower ρ than any point on the τ -Fit threshold sweep (connected circles), dominating the entire efficiency–compliance frontier. Error bars: 95% CI. The SACM family (triangles) clusters at high ρ / low σ; ED-Unicast (diamond) achieves low ρ but at substantially lower σ.

i.e., the policy network achieves both a higher δ and a lower ρ than all of the SACM-family baselines. B. Oracle-Tuned Threshold Analysis The τ -Fit family saturates at σ=0.915 regardless of the threshold (τ ≥ 2), while the policy network outperforms this ceiling by +6.61% to +11.25% with respect to the oracle’s tuning criterion (full τ -sweep and per-metric oracle analysis in Appendix L). A fixed threshold commits to a static throughput–reliability tradeoff regardless of the queue state, whereas the policy network conditions on the instantaneous configuration and achieves both a higher σ and a lower ρ than any point on the τ -sweep Pareto frontier. C. Transfer and OOD Generalization Table X presents the zero-shot transfer results across all seven non-ID conditions (2 curriculum-seen, 5 OOD) for the uniform-demand track, i.e., the policy network is evaluated even outside the region of the training data, without any retraining, hyperparameter tuning, or environmental adaptation.

PREPRINT — SUBMITTED FOR PEER REVIEW

28

TABLE X U NIFORM DEMAND , OOD GENERALIZATION : PPO-AGENT VS . SACM++. M EAN ± 95% CI. Miss Ratio (↓) PPO SACM++

Regime

8QLTXH'HPDQG6DWLVIDFWLRQ  KLJKHULVEHWWHU

ID-default Curr-file60 OOD-file120 OOD-file150 OOD-pcache0.20 Curr-pcache0.40 OOD-delay10 OOD-delay30

0.208 ± 0.001 0.208 ± 0.001 0.208 ± 0.001 0.209 ± 0.001 0.176 ± 0.001 0.238 ± 0.001 0.500 ± 0.000 0.064 ± 0.001

PPO

0.352 ± 0.001 0.352 ± 0.001 0.353 ± 0.001 0.353 ± 0.001 0.265 ± 0.001 0.412 ± 0.001 0.555 ± 0.000 0.186 ± 0.002

BE-Score σ (↑) SACM++

0.976 ± 0.002 0.976 ± 0.002 0.976 ± 0.002 0.975 ± 0.002 0.919 ± 0.002 1.038 ± 0.002 −0.002 ± 0.002 1.204 ± 0.002

0.726 ± 0.003 0.726 ± 0.002 0.725 ± 0.003 0.725 ± 0.003 0.828 ± 0.002 0.580 ± 0.003 −0.451 ± 0.003 1.141 ± 0.002

PPO

1.323 ± 0.002 1.324 ± 0.002 1.325 ± 0.002 1.324 ± 0.001 1.168 ± 0.001 1.511 ± 0.002 1.465 ± 0.002 1.293 ± 0.002

,GHDO

 

('8QLFDVW= 0

 332$JHQW

 

6$&0

332$JHQW ('8QLFDVW 6$&0IDPLO\ )LWVZHHS

 













'HDGOLQH0LVV5DWLR  ORZHULVEHWWHU

Fig. 5. Demand-centric trade-off between distinct file-identity coverage δ (↑) and broadcast-packet expiration ratio ρ (↓) on the ID-default uniform benchmark. PPO-Agent (star) achieves higher δ and lower ρ than all SACMfamily baselines. ED-Unicast (diamond) is the empirically strongest method on ρ and δ in this benchmark; its structural advantage on δ comes from serving at most one new file identity per transmission and avoiding merge-induced expirations (see body discussion of Sec. VI-A). Error bars: 95% CI.

TABLE XI PPO-AGENT ADVANTAGE OVER SACM++ (U NIFORM DEMAND ). ∆ = PPO − SACM++, ± PAIRED BOOTSTRAP 95% CI HALF - WIDTH (10 000 RESAMPLES , 50 SHARED HOLDOUT SEEDS ). Regime ID-default Curr-file60 OOD-file120 OOD-file150 OOD-pcache0.20 Curr-pcache0.40 OOD-delay10 OOD-delay30

1.590 ± 0.003 1.592 ± 0.003 1.593 ± 0.002 1.592 ± 0.002 1.296 ± 0.002 1.948 ± 0.002 1.833 ± 0.002 1.481 ± 0.002

Coding Gain (↑) PPO SACM++ 2.162 ± 0.002 2.162 ± 0.001 2.163 ± 0.002 2.163 ± 0.002 2.070 ± 0.002 2.266 ± 0.002 2.126 ± 0.001 2.186 ± 0.003

2.131 ± 0.001 2.132 ± 0.001 2.132 ± 0.001 2.131 ± 0.001 2.048 ± 0.001 2.235 ± 0.001 2.110 ± 0.001 2.135 ± 0.001

Exp/Episode (↓) PPO SACM++ 14.17 ± 0.07 14.22 ± 0.09 14.24 ± 0.08 14.28 ± 0.08 11.14 ± 0.08 17.35 ± 0.08 60.22 ± 0.12 3.68 ± 0.05

28.76 ± 0.14 28.76 ± 0.11 28.87 ± 0.13 28.83 ± 0.12 18.25 ± 0.09 39.72 ± 0.12 81.48 ± 0.15 10.93 ± 0.11

TABLE XII D ISTINCT FILE - IDENTITY COVERAGE δ ( UNIFORM DEMAND ). E ACH DISTINCT FILE IDENTITY COUNTED AT MOST ONCE ; CODING - STATE RECORD EXPIRATIONS OF ALREADY- COVERED FILE IDENTITIES uniq CONTRIBUTE Et =0. M EAN ± 95% CI.

= 2, 3 * =3 =1

* =0

Served/Tx (↑) SACM++

∆ BE-Score

∆ Miss Ratio

∆ Served/Tx

∆ Coding Gain

∆ Exp/Episode

+0.250 ± 0.003 +0.249 ± 0.003 +0.251 ± 0.003 +0.250 ± 0.003 +0.091 ± 0.002 +0.458 ± 0.003 +0.449 ± 0.003 +0.062 ± 0.003

−0.144 ± 0.001 −0.144 ± 0.001 −0.144 ± 0.001 −0.144 ± 0.001 −0.089 ± 0.001 −0.174 ± 0.001 −0.054 ± 0.000 −0.122 ± 0.002

−0.267 ± 0.003 −0.268 ± 0.003 −0.268 ± 0.002 −0.268 ± 0.002 −0.127 ± 0.002 −0.436 ± 0.003 −0.368 ± 0.003 −0.189 ± 0.002

+0.031 ± 0.002 +0.030 ± 0.002 +0.031 ± 0.002 +0.032 ± 0.002 +0.022 ± 0.002 +0.031 ± 0.003 +0.016 ± 0.002 +0.052 ± 0.002

−14.59 ± 0.14 −14.54 ± 0.13 −14.62 ± 0.12 −14.55 ± 0.13 −7.11 ± 0.09 −22.37 ± 0.13 −21.26 ± 0.16 −7.25 ± 0.11

Complete per-method breakdowns of broadcast-packet expiration ratio and broadcast-efficiency score across all uniformdemand non-ID regimes are provided in Appendix C (Tables XXVII and XXVIII). The policy network (PPO-Agent) achieves a higher δ than SACM++ in 7 of 8 regimes. The single exception is OODdelay10 (δ = 0.560 vs. 0.601), i.e., under the tightest deadline budget (D=10), all methods suffer deadline broadcast-packet expiration ratios near 50%, while the always-merge strategy of SACM++ serves more total request identifiers per step (ηreq = 1.604 vs. 1.240), thereby translating into higher unique demand coverage even though its miss rate is higher.

Regime

PPO-Agent δ (↑)

SACM++ δ (↑)

ID-default Curr-file60 OOD-file120 OOD-file150 OOD-pcache0.20 Curr-pcache0.40 OOD-delay10 OOD-delay30

0.824 ± 0.001 0.823 ± 0.001 0.823 ± 0.001 0.822 ± 0.001 0.839 ± 0.001 0.817 ± 0.001 0.560 ± 0.001 0.944 ± 0.001

0.797 ± 0.001 0.796 ± 0.001 0.796 ± 0.001 0.797 ± 0.001 0.806 ± 0.001 0.806 ± 0.001 0.601 ± 0.001 0.907 ± 0.001

The policy network achieves a substantially lower broadcastpacket expiration ratio (−5.5 pp) and fewer expirations (60.22 vs. 81.48, i.e., a 26.1% reduction), and a substantially higher broadcast-efficiency score (σ = −0.002 vs. −0.451). The δ loss at OOD-delay10 thus reflects a throughput–compliance tradeoff that the method of selective merging of the policy network resolves in favor of the deadline protection. a) Multi-metric summary.: The policy network (PPOAgent) achieves the lowest broadcast-packet expiration ratio among the coded multi-casting methods in all 8 uniformdemand regimes and the highest unique demand satisfaction among the coded methods in 7 of 8 regimes (Table XII). EDUnicast (which never codes) achieves the lowest broadcastpacket expiration ratio and the highest δ overall in most regimes, while at the cost of zero coding gain. SACM++ achieves a higher δ than the policy network only at OODdelay10 and a higher request throughput in all regimes, i.e., an outcome of its always-merge strategy. No single baseline dominates the policy network across all the primary demandcentric metrics (ρ and δ; the supplementary request-level mreq is reported separately in Sec. VI-D), i.e., ED-Unicast forfeits all of the broadcast efficiency, while the policy network outperforms SACM++ by 40.9% with respect to the broadcast-packet expiration ratio ρ (ρPPO =0.208 vs. ρSACM++ =0.352, i.e., a 0.144 absolute reduction off the SACM++ baseline). Under the request-level accounting (Section VI-D), the policy network achieves a substantially lower request miss rate mreq than the SACM++ comparator (i.e., the only baseline in the main-text request-level table) in all 8 regimes, while the paired-bootstrap analysis of Table VIII shows that ED-Unicast remains the strongest deadline-protection baseline on mreq (∆mreq = +0.074 for the policy network minus ED-Unicast at IDdefault, i.e., the policy network is worse on this metric), so

PREPRINT — SUBMITTED FOR PEER REVIEW

D. Request-Level Accounting (Supplementary) The request-level metrics provide the finest-grained usercentric evaluation, tracking each original arrival through all merge aggregations and crediting completion or miss exactly once per request identifier (Section III-C0f). Table XIII reports these supplementary request-level metrics (M8–M10) for PPOAgent and SACM++ across all eight regimes. Unlike the unique-demand satisfaction δ (M2), which P is a ratio metric, the request selection score σreq = H −1 t (|Ct | − λ|Mt |) is an absolute per-step quantity whose ranking depends on the penalty weight λ. At λ=1, SACM++ achieves a higher σreq because its always-merge strategy produces more completed request identifiers per step, however, this ranking inverts at λ ≥ 2.24, i.e., the policy network’s ∼30% lower request miss rate becomes the dominant factor when the deadline violations are penalized more heavily. For the operationally relevant penalty weights (λ ≥ 2.24 on the ID-default sensitivity analysis, see Appendix P), the policy network achieves the highest σreq among the coded baselines shown here, while the uncoded EDUnicast baseline remains higher than every coded method on σreq at every λ in the ID-default table, i.e., the σreq advantage reported here is over the coded baselines, not over the EDF unicast policy. This crossover shows that the “best” policy depends on the system operator’s valuation of the deadline compliance versus the throughput. Two patterns are evident. First, the policy network (PPOAgent) achieves a substantially lower request miss rate than the SACM++ comparator (i.e., the only baseline in the main-text request-level table) in every tested regime, with reductions of 29.8% at ID-default (mreq = 0.229 vs. 0.326 for SACM++) and ranging from 7.1% (OODdelay10) to 48.0% (OOD-delay30), while the paired-bootstrap

TABLE XIII R EQUEST- LEVEL METRICS ( UNIFORM DEMAND ). E ACH ORIGINAL ARRIVAL TRACKED THROUGH AGGREGATION ; COMPLETION AND MISS CREDITED EXACTLY ONCE PER REQUEST ID. M EAN ± 95% CI (50 SEEDS × 200 EPISODES ). ηreq (↑) Regime ID-default Curr-file60 OOD-file120 OOD-file150 OOD-pcache0.20 Curr-pcache0.40 OOD-delay10 OOD-delay30

5HTXHVW0LVV5DWHmreq ORZHULVEHWWHU

we restrict the headline “lower than” phrasing to the SACM++ comparison and leave the broader extension to GCM, SACM, SACM+, and the τ -Fit family as future work. For the request selection score σreq , the policy network leads the coded baselines (SACM++) in the majority of regimes for λ ≥ 2 and in all eight regimes by λ ≥ 5 (i.e., per-regime crossover thresholds in Table XL, with the worst case at λ⋆ = 4.92 for OOD-delay10 and λ⋆ = 3.60 for Curr-pcache0.40), while the uncoded ED-Unicast baseline remains the highest σreq at every λ shown on the ID-default sensitivity table of Appendix P (e.g., at λ = 2, 3, 5, ED-Unicast scores 0.690, 0.535, 0.226 versus the policy network’s 0.610, 0.381, −0.077), i.e., at the cost of zero coding gain. The σreq advantage of the policy network is therefore over the coded baselines, not over the uncoded EDF policy. The always-merge strategy of SACM++ yields a higher per-step throughput ηreq and a higher σreq at λ=1, while this advantage inverts once the deadline misses carry a moderate penalty. The policy network occupies a distinct position on the multi-objective frontier, i.e., it is the only method that achieves a low broadcast-level broadcastpacket expiration ratio ρ, a competitive distinct file-identity coverage δ, a low per-step request Pmiss rate mreq (i.e., per the per-step definition mreq =H −1 t |Mt |, not normalized by total arrivals), and a high broadcast efficiency σ.

29



mreq (↓)

PPO

SACM++

PPO

SACM++

1.069 ± 0.001 1.069 ± 0.001 1.069 ± 0.001 1.068 ± 0.001 1.033 ± 0.001 1.115 ± 0.001 1.240 ± 0.001 1.030 ± 0.000

1.285 ± 0.002 1.285 ± 0.002 1.285 ± 0.002 1.286 ± 0.002 1.117 ± 0.001 1.489 ± 0.002 1.604 ± 0.002 1.145 ± 0.001

0.229 ± 0.001 0.230 ± 0.001 0.231 ± 0.001 0.231 ± 0.002 0.198 ± 0.001 0.251 ± 0.001 0.974 ± 0.002 0.061 ± 0.001

0.326 ± 0.001 0.327 ± 0.001 0.329 ± 0.002 0.328 ± 0.002 0.269 ± 0.001 0.354 ± 0.002 1.048 ± 0.002 0.117 ± 0.001

σreq (λ=1) (↑) PPO SACM++ 0.839 ± 0.001 0.839 ± 0.001 0.838 ± 0.001 0.837 ± 0.002 0.835 ± 0.001 0.865 ± 0.002 0.266 ± 0.003 0.969 ± 0.001

332$JHQW ('8QLFDVW 6$&0IDPLO\ )LWVZHHS

0.959 ± 0.002 0.958 ± 0.002 0.957 ± 0.002 0.958 ± 0.002 0.848 ± 0.001 1.135 ± 0.002 0.556 ± 0.003 1.027 ± 0.001

6$&0

  332$JHQW

 * m=0

=1

('8QLFDVW

=0



= 2, 3 * =3

,GHDO















5HTXHVW7KURXJKSXW req KLJKHULVEHWWHU Fig. 6. Request-level trade-off between request throughput ηreq (→) and request miss rate mreq (↓) on the ID-default uniform benchmark. SACM++ achieves the highest throughput at the cost of higher miss rates. PPO-Agent occupies the intermediate position with the lowest miss rate among codedmulticast methods. Error bars: 95% CI.

analysis at Table VIII shows that ED-Unicast remains the strongest deadline-protection baseline on mreq at ID-default (∆mreq = +0.074 for the policy network minus ED-Unicast), so the headline “lower than” statement is restricted to the SACM++ comparison, i.e., the broader extension to GCM, SACM, SACM+, and the τ -Fit family is left as future work and is not directly supported by the displayed evidence. Second, SACM++ achieves a higher request timely-throughput ηreq in every regime, because its always-merge strategy transmits more coded packets per step. This crossover mirrors the broadcast-efficiency analysis (Appendix O), where the policy network retains rank 1 among the coded methods for λ ≥ 1. A full λ-sensitivity sweep for σreq is presented in Appendix P. Fig. 6 visualizes this throughput–compliance trade-off, i.e., the policy network (PPO-Agent) occupies the intermediate position with the lowest request miss rate among the displayed comparators (the policy network and SACM++ as the coded comparators, with ED-Unicast as the uncoded EDF reference point). Fig. 7 visualizes these advantages, including the larger gains under stress conditions (Curr-pcache0.40, OOD-delay10).

PREPRINT — SUBMITTED FOR PEER REVIEW

332DGYDQWDJHRYHU6$&0



 V\VVFRUH  PLVVUDWLRUHG /100 H[SUHG



30

6WUHVV UHJLPHV

 

TABLE XIV P OLICY BEHAVIOR DIAGNOSTICS , UNIFORM DEMAND , ID- DEFAULT. AVG . INTERSECTION COMPUTED OVER MERGING STEPS ONLY; HIGHER VALUES INDICATE SELECTION OF HIGHER - QUALITY PAIRS . Method

Merge Rate

Opp Rate

Avg Inter/Merge

PPO-Agent TauFit-2 Perfect-Fit ED-Unicast GCM SACM++

0.318 ± 0.001 0.406 ± 0.001 0.133 ± 0.001 0.000 1.000 1.000

0.876 ± 0.002 0.925 ± 0.001 0.959 ± 0.001 0.965 ± 0.001 0.501 ± 0.002 0.522 ± 0.002

0.589 ± 0.004 0.359 ± 0.003 0.819 ± 0.007 — 0.274 ± 0.002 0.393 ± 0.002

 

GHI &I I I SF SF 2G 2G 2 2 & 2

,'

Fig. 7. PPO-Agent advantage over SACM++ across all evaluation regimes (uniform demand). Bars show ∆σ (blue, BE-score improvement), −∆ρ (orange, miss-ratio reduction), and −∆ε/100 (green, expiration reduction, scaled for readability). All bars are positive, indicating PPO dominance. Shaded columns mark the stress regimes where advantages grow largest. Error bars: paired bootstrap 95% CI.

Catalog size (Curr-file60 / OOD-file120 / OOD-file150), sanity check. Varying the library from 60 to 150 files has a negligible effect on any method’s performance (σ ∈ [0.975, 0.976] for the policy network and σ ≈ 0.725 for SACM++), i.e., the same observation is true for the variations of the number of files as well. This near-invariance is expected, i.e., under decentralized placement with fixed pc , the perpacket caching probability is preserved regardless of N , so the marginal side-information statistics that determine the queuestate feature distributions do not change with the catalog size. We therefore treat this axis as a sanity check confirming the feature invariance rather than a stress test. A genuinely structural catalog-size shift would require altering the placement model itself (e.g., correlated or capacity-constrained caching) and is deferred to future work. Cache density (OOD-pcache0.20 and Curr-pcache0.40). These two regimes are the most informative. At low cache density (OOD-pcache0.20), the advantage of the policy network narrows, i.e., the policy network σ=0.919 vs. SACM++ σ=0.828 (+11.0%), i.e., fewer cached subfiles means fewer feasible merge pairs at any step, while the blind-merge strategy of SACM++ causes fewer expirations (18.25 vs. 28.76 at ID-default), thereby shrinking the benefit of the method of selective merging. At high cache density (Curr-pcache0.40), the effect reverses, i.e., the policy network σ=1.038 vs. SACM++ σ=0.580 (+79.0%), i.e., with the abundant merge opportunities, SACM++ merges every step and incurs 39.72 expirations/episode, while the policy network maintains its selective strategy at only 17.35 expirations/episode. The BEscore exceeds 1.0 because the Ploosened expiration rate allows the served packet-set mass ( t Ut ) to accumulate faster than the episode horizon penalizes. Deadline budget (OOD-delay10 and OOD-delay30). Under the tightest deadline (D=10), all methods suffer large ex-

pirations, while the policy network’s σ=−0.002 outperforms SACM++’s σ=−0.451, i.e., an absolute advantage of 0.449 BE-score units. SACM++ incurs 81.48 expirations/episode vs. the policy network’s 60.22, i.e., a 26.1% reduction even under extreme stress. Under the loosest deadline (D=30), the advantage narrows to +5.5% (σ = 1.204 vs. 1.141), i.e., longer time budgets reduce the penalty for aggressive merging, thereby partially recovering the performance of SACM++. The interesting fact we observed is that the advantages of the policy network grow under the conditions that penalize the blind merging (i.e., high cache density, tight deadlines) and shrink when those conditions relax, i.e., this is the regime where the adaptive, state-dependent decision making provides the most value. E. Emergent Selective Merge Strategy To characterize the qualitative behavior of the learned policy, we examine three diagnostic metrics alongside performance: merge rate (fraction of steps where a coded merge is selected, given at least one feasible pair), opportunity rate (fraction of steps where at least one feasible pair exists), and average intersection per merge (mean |Si ∩ Sj | of the selected pair, normalized by K − 2, computed only over merging steps; under the no-self-cache generation rule and the one-gap invariant of Appendix H, the maximum admissible overlap is K −2 because neither destination cache can sit inside Si ∩Sj ). Table XIV reports these for the ID-default uniform condition. We make three observations. (1) The method of selective merging on the high-quality pairs. The policy network merges only 31.8% of the opportunities, while achieving an average intersection of 0.589 per merge, i.e., well above SACM++’s 0.393 and TauFit-2’s 0.359, i.e., the policy network merges less often, and on substantially better pairs. By restricting the coded transmissions to the pairs with large mutual side-information overlap, the policy network preserves more bandwidth headroom for unicasting the urgent requests before their deadlines expire. Fig. 8 visualizes this relationship, i.e., the policy network achieves the highest permerge coding gain at a merge rate substantially below the always-merge coded baselines (GCM and SACM++ at 1.000), while among the coded family Perfect-Fit merges even less aggressively yet at the cost of a far higher broadcast-level expiration ratio. Fig. 9 decomposes the per-episode training reward into its constituent terms (i.e., served packet-set mass, expiration

31

D 7UDLQLQJUHZDUGGHFRPSRVLWLRQ

 



332$JHQW

6$&0

 

=1

  

3HUHSLVRGHUHZDUG

0HUJHV3×PRUH EXWORZHUJDLQ



=2

 







('8QLFDVW

5DQGRP

 

332$JHQW 6$&0





0HUJH5DWH IUDFWLRQRIRSSRUWXQLWLHV 332$JHQW







=3

=0







6$&0IDPLO\

 



332$JHQW 6$&0







 

penalty, intersection bonus, union penalty). The policy network (PPO-Agent) achieves the highest total reward (54.6) among all five policies, thereby surpassing SACM++ (43.4), ED-Unicast (42.3), and GCM (41.7). The advantage stems from two sources, i.e., the policy network earns 50% higher intersection bonus per merge (0.44 vs. 0.29) P and incurs 59% less expired packet-set mass per episode ( t Et ≈ 17.5 vs. 43.2, i.e., this is distinct from the “Exp/Episode” count ε = 14.17 vs. 28.76 reported in Table IX, which counts the expired records rather than the expired packet-set mass). This indicates that the selective strategy of the policy network maximizes the reward through the merge quality and the deadline management rather than the merge volume. Fig. 10 visualises the per-episode reward distribution across all 50 holdout seeds, i.e., the policy network (PPO-Agent) consistently achieves higher per-episode rewards than every baseline, with clear separation visible at the individual-episode level. (2) Deliberate unicast-first strategy. Even though the opportunity rate is 87.6% (i.e., a feasible merge pair is almost always available), the policy network chooses to unicast approximately 68% of the time, i.e., this is not passive inaction due to infeasibility, it is a learned preference for unicasting when the merge quality or the deadline urgency does not justify the coding. (3) Comparison to Perfect-Fit. Perfect-Fit (TauFit-τ =0) is the most conservative fixed-threshold policy, merging only when m(ri , rj ) = 0 (i.e., exact side-information match, i.e., the pairwise misfit metric m is defined in Appendix M, distinct from the broadcast-level expiration ratio ρ), i.e., it achieves a high average intersection (0.819) yet a broadcast-efficiency score of only 0.877, because it forgoes many beneficial merges with slight misfit. The policy network merges 2.4× more often

([SLUDWLRQSHQDOW\ 1HWWRWDO

E 3HUPHUJHTXDOLW\ 332YV6$&0

)LWVZHHS

Fig. 8. Coding gain vs. merge rate (ID-default, uniform demand). PPO-Agent merges only 31.8% of opportunities yet achieves the highest average coding gain (g=2.162). The SACM family merges every opportunity (100%) but with lower per-merge quality. The τ -Fit sweep (connected circles) shows that relaxing the threshold increases merge rate but decreases coding gain.

*&0

8VHUVVHUYHG XVHU ,QWHUVHFWLRQERQXV

9DOXH

$YJ&RGLQJ*DLQg KLJKHULVEHWWHU

PREPRINT — SUBMITTED FOR PEER REVIEW





 

 



,QWHUVHFWLRQERQXV SHUPHUJH

([SLUDWLRQV SHUHSLVRGH

0HUJHVSHU HSLVRGH

Fig. 9. Training-reward decomposition (ID-default, uniform demand, 50 holdout seeds). (a) Per-episode reward stacked by component (5 methods): PPO-Agent achieves the highest net reward (54.6) by accumulating P more served packet-set mass while incurring less expired packet-set mass ( t Et ) than always-merge baselines. (b) Per-merge quality (PPO vs. SACM++): PPO achieves 50% higher intersection P bonus per merge and 59% less expired packet-set mass per episode ( t Et ), despite merging P 46% less often. “Expired packet-set mass” is the reward-side quantity t Et and is distinct from the “Exp/Episode” count ε reported in Table IX.

(31.8% vs. 13.3%) with moderately lower pair quality, i.e., a balance that yields a BE-score improvement of +11.3% over Perfect-Fit. No fixed-τ rule can achieve this balance without the oracle access to τ ⋆ , while the policy network discovers it directly from the queue state. Remark 4 (Behavioral contrast across demand regimes). A separately trained Zipf-demand agent (Section VII) merges 99.7% of the available opportunities, compared to the 31.8% selective rate observed here, even though the cache placement is identical. This demand-adaptive behavior shows that the architecture discovers qualitatively different strategies for different demand regimes, i.e., a flexibility no fixed-threshold policy can achieve. Taken together, the diagnostic evidence supports the following mechanistic interpretation, i.e., the policy network has learned a selective merge heuristic (i.e., merge when the intersection is large and the deadlines are comfortable, unicast otherwise) and applies it in a fully state-dependent manner. The τ -Fit family approximates this heuristic with a fixed threshold, while the policy network instantiates it adaptively

PREPRINT — SUBMITTED FOR PEER REVIEW

32

3HUHSLVRGHHYDOXDWLRQUHZDUG ,'GHIDXOW (YDOXDWLRQ5HZDUG

  

D (YDOXDWLRQUHZDUGSHUHSLVRGH =LSI 6WDJH,,, N = 100, pc = 0.30

,,

6$&0



*&0

   ('8QL5QG

±VWG

0HDQ VHHGV

E 7UDLQLQJORVVHV VPRRWKHGPHDQDFURVVVHHGV

  















(SLVRGHLQGH[ VHHGV×HSLVRGHV 332$JHQW 6$&0

*&0 ('8QLFDVW

5DQGRP

Fig. 10. Per-episode total reward visualization on a 30-episode subset of the holdout protocol (50 holdout seeds × 30 episodes; uniform demand, training reward config). The 30-episode subset is used here purely to keep the perepisode plot legible; all numerical headline metrics in this paper come from the full 50 seeds × 200 episodes evaluation protocol of Sec. V. Faint lines show raw values; bold lines show the rolling mean (window = 30). PPOAgent maintains a consistent advantage over all baselines on this subset.

for every queue configuration, with consistent performance across the tested distributions, catalog sizes, cache densities, and deadline budgets, i.e., the same observation is true for the variations of the number of files, cache fraction, and deadline budgets as well.

VII. E XTENSION S TUDY: Z IPF -D EMAND VARIANT This section evaluates a separately trained Zipf-demand agent on the skewed demand distributions to show that the same architectural and training framework extends beyond the uniform demand. The policy network remains competitive with the baselines of the coded multi-casting method, while it does not dominate all methods, i.e., ED-Unicast achieves the highest overall broadcast-efficiency score (0.847 vs. the policy network’s 0.732) by avoiding the merge-induced expirations entirely. All values follow the same statistical reporting protocol as in Section VI. a) Summary.: The interesting fact we observed is that the demand structure shapes the effective merge behavior, i.e., the uniform-demand policy network merges 31.8% of the opportunities, whereas the Zipf-demand policy network merges 99.7%, even though the cache placement remains popularity-blind (i.e., uniform-without-replacement with fraction pc ) in both cases. The descriptive diagnostic in Section VII-A is consistent with a policy-mediated component to this difference, while we treat the analysis as suggestive rather than confirmatory because it is computed at a pooled-pair granularity (i.e., see the diagnostic’s caveats in Section VII-A).



 













9DOXH/RVV



3ROLF\*UDGLHQW/RVV

7RWDOUHZDUGSHUHSLVRGH

,





 









7UDLQLQJ6WHSV PLOOLRQV 3ROLF\JUDGLHQWORVV





9DOXHORVV

Fig. 11. Training dynamics of the Track B (Zipf-demand, α=0.8) agent across 4 seeds. The x-axis shows total RL environment steps (6.05M per seed, including the 50K Phase-2 warm-up); curriculum stage transitions therefore appear at 550K and 1.05M total RL steps (corresponding to TPhase 3 = 500K and 1.0M Phase-3 steps). (a) Evaluation reward (mean ± std across seeds); vertical dashed lines mark curriculum stage transitions at 550K and 1.05M total RL steps. Horizontal dotted lines show baseline policy rewards evaluated under the same training reward configuration. (b) Policy-gradient loss (left axis, blue) and value loss (right axis, orange), both smoothed and averaged across seeds.

A. OOD Generalization — Zipf Demand (Track B) Track B evaluates a separately trained Zipf-demand agent on Zipf-distributed file requests (file-popularity law P (F = n) ∝ rank(n)−α , α=0.8). This agent uses a popularity-aware observation augmentation (dreq =14, dpair =11; ≈1.75M parameters) and is trained on Zipf(α=0.8) demand. The ZipfID condition is in-distribution for this agent; the remaining 11 conditions are non-ID (2 curriculum-seen, 9 OOD). Table XV shows the Zipf ID-default results. The main cross-track observation is that the Zipf-trained policy network merges 99.72% of the available opportunities, compared with 31.8% for the uniform-trained policy network. We caution that this comparison does not isolate the demand law, i.e., the Track B policy network uses a wider observation space than the Track A policy network (i.e., per-request popularitymass feature, dreq = 14 versus 13, and popularity features at the pair level, dpair = 11 versus 8). The behavioral contrast therefore conflates the demand law (uniform vs. Zipf), the feature augmentation (popularity-aware features vs. none), and the joint training distribution. A controlled ablation that holds the observation space fixed and varies only the demand law is left for future work, i.e., the discussion below should be read as descriptive evidence under matched-architecture, mismatchedfeature configurations rather than as a clean causal claim about the demand structure alone. Because the cache placement is uniform-without-replacement with fraction pc , each packet’s

marginal caching probability is identical regardless of the file popularity, i.e., Zipf demand therefore does not alter the perpacket side-information statistics, while Zipf demand does change which file indices co-occur in the queue. We observe that the opportunity rate drops from 0.876 (uniform) to 0.528 (Zipf), i.e., the Zipf-trained policy network merges nearly every available pair, and the performance under the near-full merging is comparable to that of the SACM family rather than substantially worse. The precise mechanism linking the popularity-blind placement and the Zipf request arrivals to a regime where the near-full merging is advantageous has not been empirically characterized, while we outline a diagnostic analysis below. a) Diagnostic: visited-state intersection distributions.: To move from the observational account above toward a mechanistic explanation, a natural diagnostic is to compare the distribution of candidate-pair intersection sizes |Si ∩ Sj |/K in the queue states actually visited by the two PPO agents (uniform-trained and Zipf-trained) under their respective demand regimes. Under uniform-without-replacement (pc =0.30) placement, the single-request marginal cache-residency law is packet-exchangeable, so the marginal distribution of the sideinformation set Sr for one independent singleton request is the same regardless of demand law. The same is not true at the two-request joint level: under skewed demand the same packet (and therefore the same Sr ) is more likely to be requested twice, so the unconditional distribution of |Si ∩ Sj | for two requests is itself shifted by the demand law, even before any policy effect. With the paper’s default N =100, B=10, the perpair same-packet probability P is 1/(N B) = 0.001 under uniform demand versus B1 f p2f ≈ 0.0033 under Zipf(α=0.8), and same-packet pairs induce identical Sr , so they push mass toward the high-intersection tail. This is a baseline shift, not a policy effect; the diagnostic we report below mixes this baseline shift with the visited-state policy effect, and the “policy-mediated” interpretation in the SACM++ comparison should be read as suggestive descriptive evidence rather than a clean decomposition. With that caveat, Zipf demand also changes which file–cache combinations co-occur in the queue at decision time, potentially shifting the conditional (visitedstate) intersection distribution beyond the baseline. Holdout evaluation traces (50 seeds × 200 episodes, logging all candidate-pair intersections at every decision step) yield a mean visited-state intersection of 0.058 under uniform demand versus 0.065 under Zipf demand (Kolmogorov–Smirnov statistic D = 0.021 at the pooled-pair granularity; nunif ≈ 1.59M and nZipf ≈ 0.62M candidate-pair observations). We report D as a descriptive effect size only: candidate-pair observations within a queue state, and across consecutive decision steps within an episode, are heavily dependent, so a standard twosample KS test is mis-specified at this pooled granularity and a nominal small-sample p-value would overstate the evidence. We therefore avoid quoting a p-value here and read the diagnostic as descriptive evidence rather than as a hypothesis test; a future seed-level or episode-level reanalysis would be needed to support an inferential claim at an independent unit. The distribution does shift upward under Zipf demand, i.e., the fraction of the zero-intersection pairs drops from 73.7%

33

%URDGFDVW(IILFLHQF\6FRUH  KLJKHULVEHWWHU

PREPRINT — SUBMITTED FOR PEER REVIEW



,GHDO

= 2, 3

 

* =2

=1

* =0

=0 ('8QLFDVW

   

332$JHQW ('8QLFDVW 6$&0IDPLO\ 6$&03RS )LWVZHHS





6$&03RS 332$JHQW 6$&0







'HDGOLQH0LVV5DWLR  ORZHULVEHWWHU

Fig. 12. Multi-objective trade-off between broadcast-efficiency score σ (↑) and broadcast-packet expiration ratio ρ (↓) under Zipf demand (α=0.8, IDdefault). Under near-full merging, all multicast methods cluster tightly; EDUnicast dominates on both axes by avoiding merge-induced expirations.

to 71.6%, while the pairs with |Si ∩Sj |/K ≥ 0.4 nearly double (2.7% → 4.1%). This suggests a concrete data-driven mechanism, i.e., the Zipf-induced file-index concentration produces queues in which a larger fraction of the candidate pairs have high intersection, so the near-full merging is less costly in terms of wasted side-information even though each individual packet’s caching probability is unchanged. Running the same diagnostic with the deterministic SACM++ baseline (which fixes the policy and varies only the demand law) shows no comparable shift in pooled effect size (D = 0.002). This is consistent with, but does not by itself prove, a policy-mediated component to the PPO shift, because the SACM++ comparison is invariant to all PPO-specific visited-state effects yet already absorbs whatever baseline two-request joint shift the samepacket calculation above would predict. We therefore read the diagnostic as descriptive evidence that PPO under Zipf reshapes queue composition toward higher-intersection states, while flagging that a clean decomposition into (a) the demandlaw baseline shift and (b) the policy-induced visited-state shift would require either conditioning on distinct requested packet IDs or a controlled counterfactual rollout that we leave to future work. We leave a full decomposition by queue depth and aggregate size to future work. Fig. 12 and Fig. 13 visualize the multi-objective tradeoffs under Zipf demand, i.e., while in the uniform track the methods spread out, all of the multicast methods cluster tightly in the high-ρ region, whereas ED-Unicast occupies the upperleft corner alone, under the near-full merging regime. Because all of the coded multi-casting methods merge nearmaximally under Zipf demand, the performance differences are smaller than in the uniform track. The policy network retains a focused advantage in the PPO-vs-SACM++-vsSACM++-Pop comparison that motivates the Track B ablation, i.e., on the BE-score, the mean of the policy network is comparable to that of SACM++ (σ = 0.732 vs. 0.728, i.e., the two ±0.002 CIs overlap, so we do not claim a

PREPRINT — SUBMITTED FOR PEER REVIEW

34

TABLE XV Z IPF DEMAND (α=0.8), IN - DISTRIBUTION . 50 SEEDS × 200 EPISODES . B OLD = BEST. BE-Score σ (↑)

Miss Ratio (↓)

Served/Tx (↑)

Coding Gain (↑)

Exp/Episode (↓)

Merge Rate (↑)

Opp Rate (↑)

Coverage δ (↑)

PPO-Agent ED-Unicast GCM SACM SACM+ SACM++ SACM++-Pop

0.732 ± 0.002 0.847 ± 0.001 0.737 ± 0.002 0.749 ± 0.003 0.738 ± 0.003 0.728 ± 0.002 0.731 ± 0.003

0.351 ± 0.001 0.133 ± 0.001 0.343 ± 0.001 0.343 ± 0.001 0.346 ± 0.001 0.351 ± 0.001 0.348 ± 0.001

1.590 ± 0.003 1.000 ± 0.000 1.544 ± 0.002 1.569 ± 0.003 1.565 ± 0.003 1.587 ± 0.003 1.571 ± 0.002

2.122 ± 0.002 — 2.095 ± 0.001 2.130 ± 0.001 2.124 ± 0.001 2.131 ± 0.002 2.133 ± 0.001

28.30 ± 0.13 7.65 ± 0.06 28.14 ± 0.11 28.35 ± 0.14 28.31 ± 0.14 28.61 ± 0.10 28.37 ± 0.13

0.997 ± 0.000 0.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000

0.528 ± 0.002 0.964 ± 0.001 0.496 ± 0.002 0.504 ± 0.002 0.503 ± 0.002 0.518 ± 0.002 0.504 ± 0.002

0.804 ± 0.001 0.869 ± 0.001 0.784 ± 0.001 0.781 ± 0.001 0.787 ± 0.001 0.795 ± 0.001 0.789 ± 0.001

,GHDO

D 7UDLQLQJUHZDUGGHFRPSRVLWLRQ =LSI

 * =0



('8QLFDVW



= 2, 3 * =3 =1

=0

     

332$JHQW

332$JHQW ('8QLFDVW 6$&0IDPLO\ 6$&03RS )LWVZHHS









3HUHSLVRGHUHZDUG

8QLTXH'HPDQG6DWLVIDFWLRQ  KLJKHULVEHWWHU

Method

6$&03RS 6$&0



  

   6$&0

*&0

%DVH7;UHZDUG ,QWHUVHFWLRQERQXV



'HDGOLQH0LVV5DWLR  ORZHULVEHWWHU 

('8QLFDVW

5DQGRP

([SLUDWLRQSHQDOW\ 1HWWRWDO

E 3HUPHUJHTXDOLW\ 332YV6$&0 332$JHQW 6$&0















9DOXH

Fig. 13. Distinct file-identity coverage δ (↑) vs. broadcast-packet expiration ratio ρ (↓) under Zipf demand. PPO-Agent achieves the highest δ among multicast methods, while ED-Unicast leads overall. SACM++-Pop does not consistently improve over SACM++ despite privileged access to the demand distribution.





332$JHQW







strict “outperforms” on this metric) and to the popularityaware oracle SACM++-Pop, while the policy network attains a competitive broadcast-packet expiration ratio at Zipf IDdefault (ρ = 0.351, i.e., tied with SACM++’s 0.351 and within +0.003 of SACM++-Pop at 0.348), and incurs the fewest expirations per episode of those three methods (28.30 vs. 28.61 for SACM++). We do not claim a global BE-score lead over the broader multicast baseline set, i.e., SACM (0.749), SACM+ (0.738), and GCM (0.737) all achieve a higher σ than the policy network (0.732) at Zipf ID-default (Table XV), and the policy network instead trades the raw BE-score for a lower broadcast-packet expiration ratio, fewer expirations, and the request-level metrics discussed below. ED-Unicast achieves the highest overall BE-score (0.847) by avoiding the mergeinduced expirations entirely, as in the uniform-demand case, i.e., its zero-merge strategy forgoes all coding gain. SACM++Pop, which uses the popularity-weighted pair scoring to exploit the known Zipf distribution, does not consistently improve over SACM++ on the deadline metrics and does not outperform the policy network on the throughput, even though having privileged access to the demand distribution unavailable to the deployed policy network. To enable direct cross-track comparison, Table XVI reports the composite broadcast-efficiency score σ for the three pri-

 





,QWHUVHFWLRQERQXV SHUPHUJH

([SLUDWLRQV SHUHSLVRGH

0HUJHVSHU HSLVRGH

Fig. 14. Training-reward decomposition (ID-default, Zipf demand, 50 holdout seeds). (a) Per-episode reward stacked by component (5 methods): under near-full merging, PPO-Agent and SACM++ achieve similar net rewards. By contrast, on the uniform track selective merging yields a clear PPO advantage. (b) Per-merge quality (PPO vs. SACM++).

mary methods across all Zipf regimes,Pcomputed from the same evaluation data using σ = H −1 t (Ut − λEt ) (Section V-D; H is the episode horizon, not the global Phase-3 step counter T of Sec. IV-D). The policy network achieves the highest BE-score among the three methods in most regimes, while in OOD-alpha0.6 the popularity-aware baseline SACM++-Pop edges the policy network by 0.001 (i.e., Pop = 0.730 vs. the policy network = 0.729), and in OOD-alpha1.0 the two methods tie at 0.732 (i.e., within 95% CI of each other). The largest advantages of the policy network occur under high cache density (i.e., Curr-pcache0.40: σPPO = 0.608 vs. σSACM++ = 0.583, +4.3%) and tight deadlines (i.e., OODdelay10: σPPO = −0.426 vs. σSACM++ = −0.449, +0.023

PREPRINT — SUBMITTED FOR PEER REVIEW

35

TABLE XVI Z IPF DEMAND , BE- SCORE SUMMARY: PPO-AGENT VS . SACM++ VS . SACM++-P OP. M EAN ± 95% CI. B OLD = BEST PER REGIME ; TIES ( WITHIN ROUNDING TO 3 DECIMAL PLACES ) ARE BOLDED JOINTLY.

PPO

BE-Score σ (↑) SACM++

Pop

0.732 ± 0.002 0.729 ± 0.003 0.732 ± 0.002 0.739 ± 0.003 0.732 ± 0.002 0.730 ± 0.003 0.731 ± 0.003 0.733 ± 0.003 0.829 ± 0.002 0.608 ± 0.003 −0.426 ± 0.003 1.146 ± 0.002

0.728 ± 0.002 0.725 ± 0.003 0.728 ± 0.003 0.732 ± 0.003 0.727 ± 0.003 0.728 ± 0.003 0.727 ± 0.003 0.728 ± 0.003 0.826 ± 0.002 0.583 ± 0.004 −0.449 ± 0.003 1.143 ± 0.002

0.731 ± 0.003 0.730 ± 0.003 0.732 ± 0.003 0.733 ± 0.002 0.730 ± 0.003 0.729 ± 0.002 0.730 ± 0.003 0.730 ± 0.003 0.821 ± 0.002 0.597 ± 0.003 −0.445 ± 0.003 1.143 ± 0.002

Regime ID-default (α=0.8) OOD-alpha0.6 OOD-alpha1.0 OOD-alpha1.2 OOD-mandelbrot Curr-file60 (Z) OOD-file120 (Z) OOD-file150 (Z) OOD-pcache0.20 (Z) Curr-pcache0.40 (Z) OOD-delay10 (Z) OOD-delay30 (Z)

3HUHSLVRGHHYDOXDWLRQUHZDUG =LSI,'GHIDXOW

7RWDOUHZDUGSHUHSLVRGH

       















(SLVRGHLQGH[ VHHGV×HSLVRGHV 332$JHQW 6$&0

*&0 ('8QLFDVW

5DQGRP

Fig. 15. Per-episode total reward visualization on a 30-episode subset of the holdout protocol (50 holdout seeds × 30 episodes; Zipf demand, training reward config). The 30-episode subset is used here purely to keep the perepisode plot legible; all numerical headline metrics in this paper come from the full 50 seeds × 200 episodes evaluation protocol of Sec. V. Faint lines show raw values; bold lines show the rolling mean (window = 30).

absolute), i.e., the same observation is true for the variations of the cache fraction and deadline budgets as well. As in the uniform track, the catalog-size axis (Curr-file60 / OOD-file120 / OOD-file150) shows near-invariance (σ ∈ [0.730, 0.733] for the policy network), i.e., consistent with the preserved per-packet caching probability under the uniform-withoutreplacement (pc ) placement (cf. Section VI-C). Across the 11 non-ID Zipf conditions (Table XVII), the policy network reduces the expirations per episode with respect to SACM++ in every regime, with the largest absolute reductions under the high-stress conditions, i.e., OOD-delay10 (the policy network 79.65 vs. SACM++ 81.30, i.e., −1.65 expirations/ep) and Curr-pcache0.40 (the policy network 38.04 vs. SACM++ 39.45, i.e., −1.41 expirations/ep). SACM++-Pop does not improve over SACM++ on the OOD-delay10 stress regime, and improves only marginally on Curr-pcache0.40 (i.e., BE-

score 0.597 vs. 0.583, broadcast-packet expiration ratio 0.408 vs. 0.411, expirations 39.41 vs. 39.45), i.e., the popularityaware refinement does not deliver a consistent advantage under the stress. The complete per-method miss-ratio breakdown for all Zipfdemand non-ID regimes is provided in Appendix Table XXIX. Remark 5 (Paired uncertainty on Zipf deltas). All deltas in Table XVIII are computed on the same 50 shared holdout seeds. Paired bootstrap 95% CIs (10 000 resamples) yield half-widths of ≈0.002–0.004 for BE-score, ≈0.001 for broadcast-packet expiration ratio, ≈0.1–0.15 for expirations, and ≈0.002 for coding gain. The BE-score, miss-ratio, and expirations deltas favoring PPO, and the coding-gain deltas favoring SACM++, all have intervals that do not cross zero; we report these as descriptive effect-size bounds rather than formal significance tests. b) Request-level accounting (Zipf).: Table XIX reports the request-level metrics (M8–M10) under Zipf demand, tracking each original arrival through the queue aggregation as in the uniform analysis (Section VI-D). The interesting fact we observed is that the result contrasts with the uniform track, i.e., the policy network (PPO-Agent) achieves both a higher request timely-throughput ηreq and a lower request miss rate mreq than SACM++ in 11 of 12 regimes, so the request selection score σreq favors the policy network at every tested penalty weight λ ∈ {0.5, 1, . . . , 10} under Zipf demand, i.e., no crossover is needed in this regime. While on the uniform track (Section VI-D), SACM++’s ∼17% higher ηreq required λ ≥ 2.24 before the policy network’s lower miss rate became decisive. Under Zipf demand, the near-full merging strategy of the policy network (99.7% merge rate) matches or exceeds the throughput of the deterministic SACM family while also maintaining lower deadline misses, i.e., a combination not achievable under the selective-merge strategy optimal for the uniform demand. The largest advantages appear under high cache density (Curr-pcache0.40: σreq = 1.202 vs. 1.129, +6.5%) and tight deadlines (OOD-delay10: 0.649 vs. 0.551, +17.8%), i.e., the same observation is true for the variations of the cache fraction and deadline budgets as well, while the sole near-tie is OOD-pcache0.20, where all methods converge

PREPRINT — SUBMITTED FOR PEER REVIEW

36

TABLE XVII Z IPF DEMAND , OOD GENERALIZATION : PPO-AGENT VS . SACM++ VS . SACM++-P OP. B OLD = BEST PER REGIME , ASSIGNED ON UNROUNDED INTERNAL MEANS ( SO TWO CELLS WITH IDENTICAL DISPLAYED PRECISION MAY STILL RANK DIFFERENTLY ). Regime ID-default OOD-alpha0.6 OOD-alpha1.0 OOD-alpha1.2 OOD-mandelbrot Curr-file60 OOD-file120 OOD-file150 OOD-pcache0.20 Curr-pcache0.40 OOD-delay10 OOD-delay30

PPO

Miss Ratio (↓) SACM++

Pop

PPO

Served/Tx (↑) SACM++

Pop

PPO

Coding Gain (↑) SACM++

Pop

PPO

Exp/Episode (↓) SACM++

Pop

0.351 ± 0.001 0.352 ± 0.001 0.350 ± 0.001 0.347 ± 0.001 0.350 ± 0.001 0.351 ± 0.001 0.351 ± 0.001 0.351 ± 0.001 0.265 ± 0.001 0.408 ± 0.001 0.552 ± 0.000 0.183 ± 0.001

0.351 ± 0.001 0.352 ± 0.001 0.350 ± 0.001 0.348 ± 0.001 0.351 ± 0.001 0.351 ± 0.001 0.352 ± 0.001 0.351 ± 0.001 0.266 ± 0.001 0.411 ± 0.001 0.555 ± 0.000 0.184 ± 0.001

0.348 ± 0.001 0.349 ± 0.001 0.348 ± 0.001 0.346 ± 0.001 0.348 ± 0.001 0.349 ± 0.001 0.349 ± 0.001 0.349 ± 0.001 0.267 ± 0.001 0.408 ± 0.001 0.555 ± 0.000 0.181 ± 0.001

1.590 ± 0.003 1.594 ± 0.003 1.586 ± 0.002 1.575 ± 0.003 1.587 ± 0.003 1.590 ± 0.003 1.593 ± 0.003 1.594 ± 0.003 1.294 ± 0.002 1.964 ± 0.003 1.845 ± 0.002 1.479 ± 0.002

1.587 ± 0.003 1.589 ± 0.002 1.580 ± 0.002 1.571 ± 0.003 1.580 ± 0.003 1.584 ± 0.002 1.590 ± 0.003 1.587 ± 0.002 1.294 ± 0.002 1.936 ± 0.003 1.827 ± 0.002 1.477 ± 0.002

1.571 ± 0.002 1.577 ± 0.003 1.566 ± 0.003 1.560 ± 0.003 1.566 ± 0.003 1.571 ± 0.002 1.573 ± 0.002 1.572 ± 0.003 1.289 ± 0.001 1.914 ± 0.003 1.801 ± 0.002 1.469 ± 0.002

2.122 ± 0.002 2.122 ± 0.001 2.121 ± 0.001 2.119 ± 0.001 2.120 ± 0.001 2.121 ± 0.001 2.122 ± 0.001 2.122 ± 0.002 2.043 ± 0.001 2.234 ± 0.002 2.098 ± 0.001 2.126 ± 0.001

2.131 ± 0.002 2.131 ± 0.001 2.129 ± 0.001 2.127 ± 0.001 2.128 ± 0.001 2.129 ± 0.001 2.132 ± 0.001 2.130 ± 0.001 2.048 ± 0.001 2.231 ± 0.001 2.108 ± 0.001 2.134 ± 0.001

2.133 ± 0.001 2.136 ± 0.001 2.131 ± 0.002 2.130 ± 0.001 2.131 ± 0.001 2.131 ± 0.001 2.132 ± 0.001 2.133 ± 0.001 2.049 ± 0.001 2.238 ± 0.001 2.114 ± 0.001 2.136 ± 0.002

28.30 ± 0.13 28.49 ± 0.13 28.19 ± 0.13 27.72 ± 0.12 28.19 ± 0.13 28.36 ± 0.12 28.40 ± 0.14 28.37 ± 0.14 18.23 ± 0.10 38.04 ± 0.12 79.65 ± 0.13 10.63 ± 0.07

28.61 ± 0.10 28.71 ± 0.13 28.45 ± 0.13 28.08 ± 0.13 28.44 ± 0.14 28.52 ± 0.12 28.70 ± 0.14 28.59 ± 0.13 18.30 ± 0.11 39.45 ± 0.16 81.30 ± 0.11 10.73 ± 0.08

28.37 ± 0.13 28.57 ± 0.13 28.22 ± 0.16 27.97 ± 0.13 28.23 ± 0.14 28.39 ± 0.13 28.45 ± 0.14 28.40 ± 0.14 18.25 ± 0.10 39.41 ± 0.14 81.59 ± 0.12 10.63 ± 0.08

TABLE XVIII PPO-AGENT ADVANTAGE OVER SACM++ (Z IPF DEMAND ). ∆ = PPO − SACM++. Regime

5HTXHVW0LVV5DWHmreq ORZHULVEHWWHU

ID-default OOD-alpha0.6 OOD-alpha1.0 OOD-alpha1.2 OOD-mandelbrot Curr-file60 OOD-file120 OOD-file150 OOD-pcache0.20 Curr-pcache0.40 OOD-delay10 OOD-delay30

 

∆ BE-Score

∆ Miss Ratio

∆ Served/Tx

∆ Coding Gain

∆ Exp/Episode

+0.004 +0.004 +0.005 +0.007 +0.005 +0.002 +0.004 +0.005 +0.003 +0.025 +0.022 +0.003

−0.001 −0.000 −0.001 −0.001 −0.001 +0.000 −0.001 −0.000 −0.001 −0.003 −0.003 −0.001

+0.004 +0.006 +0.006 +0.003 +0.006 +0.007 +0.003 +0.007 +0.000 +0.028 +0.019 +0.002

−0.009 −0.009 −0.008 −0.008 −0.007 −0.008 −0.010 −0.008 −0.005 +0.003 −0.010 −0.008

−0.312 −0.224 −0.261 −0.361 −0.243 −0.162 −0.303 −0.224 −0.061 −1.412 −1.648 −0.101

332$JHQW ('8QLFDVW 6$&0IDPLO\ 6$&03RS )LWVZHHS

6$&03RS 6$&0

332$JHQW

 

= 2, 3 =1 * =3

* m=0

('8QLFDVW

=0



,GHDO















5HTXHVW7KURXJKSXW req KLJKHULVEHWWHU Fig. 16. Request throughput ηreq (→) vs. request miss rate mreq (↓) under Zipf demand. PPO-Agent achieves both higher throughput and lower miss rate than the displayed SACM++ and SACM++-Pop comparators on this figure: no trade-off exists between PPO and these displayed comparators, unlike the uniform track (cf. Fig. 6); a request-level extension over GCM, SACM, SACM+, and the τ -Fit family is left as future work.

to similar performance. Fig. 16 visualizes this dominance, i.e., the policy network (PPO-Agent) sits strictly below and to the right of SACM++ in the ηreq –mreq plane, so no throughput– compliance trade-off exists under Zipf demand. Appendix Q presents the full λ-sensitivity analysis.

PREPRINT — SUBMITTED FOR PEER REVIEW

37

TABLE XIX R EQUEST- LEVEL METRICS (Z IPF DEMAND , α=0.8). E ACH ORIGINAL ARRIVAL TRACKED THROUGH AGGREGATION ; COMPLETION AND MISS CREDITED EXACTLY ONCE PER REQUEST ID. M EAN ± 95% CI (50 SEEDS × 200 EPISODES ). B OLD = BEST.

PPO

ηreq (↑) SACM++

Pop

PPO

mreq (↓) SACM++

Pop

PPO

σreq (λ=1) (↑) SACM++

Pop

1.290 ± 0.002 1.293 ± 0.002 1.288 ± 0.002 1.280 ± 0.002 1.289 ± 0.002 1.291 ± 0.002 1.292 ± 0.002 1.292 ± 0.002 1.116 ± 0.001 1.504 ± 0.002 1.631 ± 0.002 1.146 ± 0.001

1.282 ± 0.002 1.284 ± 0.002 1.279 ± 0.002 1.274 ± 0.002 1.281 ± 0.002 1.281 ± 0.002 1.284 ± 0.002 1.282 ± 0.002 1.116 ± 0.001 1.484 ± 0.002 1.600 ± 0.002 1.142 ± 0.001

1.273 ± 0.002 1.275 ± 0.002 1.270 ± 0.002 1.267 ± 0.002 1.271 ± 0.002 1.274 ± 0.002 1.275 ± 0.002 1.274 ± 0.002 1.119 ± 0.001 1.458 ± 0.002 1.570 ± 0.002 1.140 ± 0.001

0.312 ± 0.001 0.313 ± 0.002 0.312 ± 0.002 0.309 ± 0.001 0.311 ± 0.001 0.313 ± 0.002 0.312 ± 0.002 0.312 ± 0.002 0.269 ± 0.001 0.303 ± 0.001 0.982 ± 0.002 0.110 ± 0.001

0.326 ± 0.002 0.327 ± 0.002 0.326 ± 0.002 0.323 ± 0.001 0.324 ± 0.002 0.325 ± 0.001 0.326 ± 0.002 0.326 ± 0.002 0.270 ± 0.002 0.354 ± 0.002 1.048 ± 0.002 0.115 ± 0.001

0.334 ± 0.002 0.336 ± 0.001 0.333 ± 0.002 0.330 ± 0.002 0.332 ± 0.002 0.333 ± 0.002 0.334 ± 0.002 0.334 ± 0.002 0.268 ± 0.002 0.383 ± 0.002 1.088 ± 0.002 0.118 ± 0.001

0.978 ± 0.002 0.980 ± 0.002 0.976 ± 0.002 0.971 ± 0.002 0.978 ± 0.003 0.979 ± 0.003 0.979 ± 0.002 0.979 ± 0.003 0.848 ± 0.001 1.202 ± 0.002 0.649 ± 0.003 1.036 ± 0.001

0.955 ± 0.002 0.957 ± 0.002 0.953 ± 0.002 0.952 ± 0.002 0.957 ± 0.002 0.956 ± 0.002 0.958 ± 0.002 0.956 ± 0.002 0.847 ± 0.002 1.129 ± 0.002 0.551 ± 0.003 1.027 ± 0.001

0.939 ± 0.002 0.939 ± 0.002 0.937 ± 0.002 0.937 ± 0.002 0.939 ± 0.002 0.942 ± 0.002 0.941 ± 0.002 0.940 ± 0.002 0.852 ± 0.002 1.075 ± 0.003 0.482 ± 0.003 1.022 ± 0.001

Regime ID-default (α=0.8) OOD-alpha0.6 OOD-alpha1.0 OOD-alpha1.2 OOD-mandelbrot Curr-file60 (Z) OOD-file120 (Z) OOD-file150 (Z) OOD-pcache0.20 (Z) Curr-pcache0.40 (Z) OOD-delay10 (Z) OOD-delay30 (Z)

VIII. A BLATIONS AND A NALYSIS The training pipeline introduced in Section IV combines four components, i.e., the behavior-cloning warm start (BC), the graph-attention architecture (GraphAttn), the Expert Iteration distillation (ExIt), and the curriculum learning. This section isolates the contribution of each of these components by training five ablated variants, each with exactly one component removed, plus one combined removal (BC + ExIt), while evaluating all six of the models across the full eight-regime battery (i.e., ID-default plus the seven non-ID conditions) used in Sections VI. A. Ablation Setup Variants. Starting from the full model, we train five singlecomponent ablations and one combined ablation: (i) w/o ExIt: removes the Expert Iteration distillation loops (Sections IV-E); PPO training proceeds without any online teacher distillation after the BC warm start. (ii) w/o BC Warm-Start: removes the rollout-improved behavior cloning phase (Section IV-B); the policy head is randomly initialized before the value warm-up and PPO stages. (iii) w/o Graph-Attention: replaces the graph-pair encoder with a flat two-layer MLP of matching parameter count (target ∼1.73M parameters, matched to the Track A full model; see Appendix K) that receives the concatenated per-request and per-pair feature tensors as input; the 3/7 component columns below capture the presence of the graph-attentive pair encoder. (iv) w/o BC + ExIt: removes both the BC warm start and the ExIt distillation loops, leaving only random initialization followed by MaskablePPO with curriculum. (v) w/o Curriculum: removes all three curriculum stages; the policy trains directly on the full-difficulty environment (N = 100, pc = 0.30) from the start. Each of the variants is trained with 4 independent random seeds, while the model selection follows the same robustadvantage criterion used for the full model (Section IV-F), i.e., using 50 validation seeds withheld from the evaluation. All of the reported numbers use the same 50 evaluation holdout seeds (× 200 episodes/seed = 10,000 episodes per method per regime) shared with Section VI; each ablation variant is itself trained independently with its own 4 training seeds,

TABLE XX A BLATION STUDY: COMPONENT LEGEND . E ACH VARIANT REMOVES ONE OR TWO TRAINING COMPONENTS FROM THE FULL PPO-AGENT PIPELINE . Variant

BC

Graph-Attn

ExIt

Curriculum

Full Model w/o ExIt w/o BC Warm-Start w/o Graph-Attention w/o BC + ExIt w/o Curriculum

✓ ✓ — ✓ — ✓

✓ ✓ ✓ — (MLP) ✓ ✓

✓ — ✓ ✓ — ✓

✓ ✓ ✓ ✓ ✓ —

however, the evaluation-set seeds and the per-episode contexts are common across all of the variants and the full model, thereby making the comparison fair. Consistent with Section V-D, the primary metrics are the broadcast-packet expiration ratio (ρ, ↓) and the distinct fileidentity coverage (δ, ↑). Broadcast-efficiency metrics (BEScore σ, served/tx, coding gain, expirations) are reported for completeness, the request-level family (ηreq , mreq , σreq ) is reported as a supplementary diagnostic (the displayed requestlevel tables compare PPO only to a subset of the baselines; full-baseline coverage is left as future work, see Sec. V-D), and diagnostic metrics (merge rate, opportunity rate, reward per step) are reported only as policy-behavior summaries. B. Component Contributions at ID-Default Table XXI presents the ablation results on the ID-default regime, while Table XXII summarizes the per-component impact as signed deltas with respect to the full model. The largest single-component ID-default reliability degradation comes from removing the curriculum (∆ρ=+0.044, ∆ε=+4.46); the ExIt is the second-largest single-component ID-default contributor (∆ρ=+0.041, ∆ε=+3.49), however, it is the most uniformly large across the OOD-ablation battery (Table XXIII), which is why we discuss it first in the per-component narrative below. We then examine how the demand-centric (δ) and the request-level (σreq ) metrics give complementary, sometimes contrasting, views of the component contributions. The reward per step is reported as a training-signal diagnostic, however, we do not use it for ranking, because it is the shaped training surrogate rather than the paper’s target communications-metric family. The reward definition and weights are held fixed across the rows of Table XXI, thereby making the Reward/Step values

PREPRINT — SUBMITTED FOR PEER REVIEW

38

TABLE XXI A BLATION STUDY, ID- DEFAULT. 50 HOLDOUT SEEDS × 200 EPISODES . B OLD = BEST PER COLUMN AMONG METHODOLOGY- RELEVANT COLUMNS ; THE R EWARD /S TEP COLUMN IS THE SHAPED TRAINING SURROGATE AND IS INTENTIONALLY NOT BOLD - RANKED ( SEE FOOTNOTE † ). P RIMARY METRICS : ρ, δ; SUPPLEMENTARY: σreq . Variant Full Model w/o ExIt w/o BC Warm-Start w/o Graph-Attention w/o BC + ExIt w/o Curriculum

Reward/Step† (↑)

BE-Score σ (↑)

Miss Ratio ρ (↓)

Coverage δ (↑)

Served/Tx (↑)

Coding Gain (↑)

Exp/Episode (↓)

Merge Rate (↑)

Opp Rate (↑)

ηreq (↑)

mreq (↓)

σreq (↑)

1.092 ± 0.002 1.045 ± 0.002 1.058 ± 0.002 1.089 ± 0.002 0.984 ± 0.002 1.076 ± 0.002

0.976 ± 0.002 0.911 ± 0.002 0.936 ± 0.002 0.957 ± 0.002 0.884 ± 0.002 0.949 ± 0.002

0.208 ± 0.001 0.249 ± 0.001 0.228 ± 0.001 0.221 ± 0.001 0.221 ± 0.001 0.252 ± 0.001

0.824 ± 0.001 0.806 ± 0.001 0.829 ± 0.001 0.821 ± 0.001 0.834 ± 0.001 0.801 ± 0.001

1.323 ± 0.002 1.364 ± 0.002 1.329 ± 0.002 1.336 ± 0.002 1.234 ± 0.002 1.431 ± 0.002

2.162 ± 0.002 2.165 ± 0.002 2.144 ± 0.002 2.203 ± 0.002 2.081 ± 0.002 2.157 ± 0.002

14.17 ± 0.07 17.66 ± 0.11 15.16 ± 0.08 14.94 ± 0.09 13.95 ± 0.09 18.63 ± 0.09

0.318 ± 0.001 0.373 ± 0.002 0.333 ± 0.002 0.322 ± 0.001 0.238 ± 0.002 0.476 ± 0.002

0.876 ± 0.002 0.839 ± 0.002 0.864 ± 0.002 0.866 ± 0.002 0.908 ± 0.002 0.782 ± 0.003

1.069 ± 0.001 1.106 ± 0.001 1.093 ± 0.001 1.080 ± 0.001 1.076 ± 0.001 1.118 ± 0.001

0.229 ± 0.001 0.267 ± 0.002 0.227 ± 0.001 0.235 ± 0.002 0.215 ± 0.001 0.278 ± 0.001

0.839 ± 0.001 0.839 ± 0.002 0.866 ± 0.002 0.845 ± 0.001 0.861 ± 0.001 0.840 ± 0.001

† Reward/Step is the mean shaped training reward per step. The reward definition and weights (Section III-F5) are held fixed across the ablation rows

reported here, so Reward/Step values are directly comparable within this table; it is reported as a diagnostic only because it is the shaped training surrogate rather than the paper’s target communications-metric family. Cross-table comparability fails when the reward definition or its weights themselves change. TABLE XXII A BLATION STUDY: CHANGE VS . F ULL M ODEL (ID- DEFAULT ). S IGN CONVENTION : FOR MINIMIZATION METRICS (ρ = M ISS R ATIO , E XP /E PISODE , mreq ) POSITIVE ∆ DENOTES DEGRADATION OF THE ABLATED VARIANT RELATIVE TO THE F ULL M ODEL ; FOR MAXIMIZATION METRICS (δ = C OVERAGE , σ = BE-S CORE , S ERVED /T X , G AIN , ηreq , σreq ) POSITIVE ∆ DENOTES IMPROVEMENT. ∆ R EWARD IS SHOWN FOR COMPLETENESS AS A TRAINING - SURROGATE DIAGNOSTIC AND IS NOT USED FOR RANKING . Variant w/o ExIt w/o BC Warm-Start w/o Graph-Attention w/o BC + ExIt w/o Curriculum

∆ Reward†

∆ BE-Score

∆ Miss Ratio

∆ Coverage δ

∆ Served/Tx

∆ Gain

∆ Exp/Ep

∆ ηreq

∆ mreq

∆ σreq

−0.047 (−4.3%) −0.034 (−3.1%) −0.003 (−0.3%) −0.108 (−9.9%) −0.016 (−1.5%)

−0.065 (−6.7%) −0.040 (−4.1%) −0.019 (−1.9%) −0.092 (−9.5%) −0.027 (−2.7%)

+0.041 (+19.9%) +0.020 (+9.7%) +0.013 (+6.3%) +0.013 (+6.3%) +0.044 (+21.1%)

−0.018 (−2.2%) +0.005 (+0.6%) −0.003 (−0.3%) +0.010 (+1.2%) −0.023 (−2.8%)

+0.041 (+3.1%) +0.006 (+0.5%) +0.013 (+0.9%) −0.090 (−6.8%) +0.107 (+8.1%)

+0.003 (+0.1%) −0.018 (−0.8%) +0.041 (+1.9%) −0.080 (−3.7%) −0.005 (−0.2%)

+3.49 (+24.6%) +0.99 (+7.0%) +0.78 (+5.5%) −0.22 (−1.5%) +4.46 (+31.5%)

+0.038 (+3.5%) +0.024 (+2.3%) +0.011 (+1.0%) +0.007 (+0.6%) +0.049 (+4.6%)

+0.038 (+16.7%) −0.003 (−1.1%) +0.006 (+2.6%) −0.014 (−6.2%) +0.049 (+21.4%)

−0.000 (−0.1%) +0.027 (+3.2%) +0.005 (+0.6%) +0.021 (+2.5%) +0.000 (+0.0%)

directly comparable within this table; the appendix paragraph “Reward per step (M13)” notes only that the comparability fails across the reward definitions, i.e., not across the ablation rows reported here. Expert Iteration / DAgger Distillation (largest crossregime ρ-impact). The ExIt has the largest single-component effect on the deadline compliance, i.e., removing it raises the broadcast-packet expiration ratio by +19.9% and the expirations by +24.6% at ID-default. This pattern persists and amplifies across the non-ID regimes as well: at OOD-delay30, removing the ExIt raises the broadcast-packet expiration ratio by +37.6% (relative), and at Curr-pcache0.40, by +23.9%. The pattern is consistent with the hypothesis that the ExIt phase reinforces the deferral of merges in favor of the urgent unicasts under the deadline pressure; this is a mechanism interpretation rather than a directly measured causal attribution, however, it is consistent with the observed merge-rate and expiration patterns across the regimes. The combined removal (w/o BC + ExIt) exhibits a clear interaction effect. The interesting fact we observed is that removing both the BC and the ExIt raises the broadcast-packet expiration ratio by only +6.3%, i.e., less than removing the ExIt alone (+19.9%) or the BC alone (+9.7%). This apparent paradox is explained by the emergent ultra-conservative policy, i.e., without either the warm start or the distillation, the agent converges to the lowest merge rate in the study (0.238, vs. 0.318 for the full model) and the highest opportunity rate (0.908). The policy largely avoids the coded transmissions, thereby achieving the fewest expirations of any variant (13.95, even fewer than the full model’s 14.17), even though at the cost of substantially lower throughput (−6.8% served/tx). The BC + ExIt combination is therefore not complementary in the additive sense; removing both drives the policy into an ultraconservative basin that trades the throughput for the deadline safety, which is a qualitatively different failure mode with respect to removing either component alone.

BC Warm-Start (moderate, OOD-amplified). Removing the BC phase costs +9.7% broadcast-packet expiration ratio and +7.0% expirations at ID-default. The impact amplifies under the distribution shift, i.e., at Curr-pcache0.40 (i.e., high cache fraction), removing the BC costs +2.6 pp broadcastpacket expiration ratio with respect to the full model. Without the rollout-improved warm start, the PPO must discover the selective merge strategy (i.e., the core behavior described in Section VI-E) entirely from scratch from a random initialization, while the resulting policy converges to a suboptimal strategy with moderately higher merge rate (0.333 vs. 0.318), which is consistent with insufficient initial structure for the selective merging. Graph-Attention (smallest single-component impact). Removing the graph-attention and replacing it with a flat MLP produces the smallest single-component reliability degradation, i.e., +6.3% broadcast-packet expiration ratio (0.221 vs. 0.208) and +5.5% expirations (14.94 vs. 14.17) at IDdefault, while the throughput is essentially unchanged (+0.9% served/tx). The coding gain is marginally higher without the graph-attention (2.203 vs. 2.162, +1.9%), which suggests that the MLP replacement can exploit the simple pair structures, even though it lacks the broader relational reasoning that helps the graph-attention coordinate the merge decisions across the full request queue. The graph-attention encoder’s contribution is therefore not to the raw coding efficiency but to the reliability-aware coordination that lowers the deadline violations. C. Curriculum Learning and the Reliability–Throughput Trade-Off The curriculum result is the most counter-intuitive finding in the ablation study and warrants extended discussion. The interesting fact we observed is that removing the curriculum improves the throughput by +8.1% served/tx, even though it degrades the tabulated Reward/Step by −1.5% (1.076

PREPRINT — SUBMITTED FOR PEER REVIEW

vs. 1.092, Table XXI), while simultaneously degrading the broadcast-packet expiration ratio by +21.1% and the expirations by +31.5%, i.e., the largest single-component reliability degradation we observed. Without the curriculum, the policy trains directly on the full-difficulty environment (N = 100, pc = 0.30) from the first training step. The per-broadcast packet-set reward favors the coded transmissions (i.e., a merge with Ut =|fmg | yields a higher local Ut contribution than a unicast with Ut =1), while this local signal is so dominant that the PPO quickly learns to merge aggressively. The w/o Curriculum variant achieves a merge rate of 0.476, compared to 0.318 for the full model, i.e., a 50% increase in the merging frequency. Aggressive merging raises the Served/Tx (i.e., the packetset count µ) and the local per-step Ut incentive (i.e., coded broadcasts contribute |fmg | ≥ 2 to Ut per slot), however, the same aggressive strategy causes substantially more expirations, while the additional −Et penalty more than offsets the local Ut gain in the realized episode-average Reward/Step (which decreases by −1.5%, 1.076 vs. 1.092, Table XXI); without the deadline-conscious restraint, the policy merges even the pairs whose deadline is too tight to benefit from the additional encoded content before it expires. With the curriculum (N = 60 → 80 → 100, pc = 0.50 → 0.40 → 0.30), the agent first learns in the easy environments where the merging is abundant and the deadlines are rarely an issue, i.e., the large cache fractions create many high-quality pairs (|Si ∩ Sj | is high), while the small catalog (N = 60) means the requests rarely conflict. In this regime, aggressive merging is nearly always the right strategy, while the policy internalizes the coded-XOR structure quickly. As the difficulty increases, the agent encounters progressively more deadline pressure, i.e., more requests per cache slot, fewer high-quality pairs, and tighter cache capacity. The pattern is consistent with the interpretation that the curriculum exposes the agent to the scenarios of where not to merge, thereby gradually shifting the learned policy toward the 31.8% selective merge rate that characterizes the full model’s behavior (Section VI-E); the ablation establishes that removing the curriculum degrades the selective merging, even though it does not isolate the curriculum’s mechanism directly. Remark 6. The curriculum learning in this setting is not primarily a sample-efficiency technique, i.e., the w/o Curriculum variant converges to a high-reward policy quickly and it does not fail to converge. The curriculum shapes the qualitative character of the learned policy, i.e., the gradual introduction of the deadline pressure during the training produces a deadlineconscious selective merge strategy that cannot be recovered by training directly on the hard environment, even though given the same total sample budget. This finding is consistent with the curriculum learning theory [21], i.e., starting from an easy distribution guides the learner toward a solution basin associated with the generalizable structure (i.e., selective merging), rather than the locally optimal but brittle basin associated with the aggressive merging. For the coded caching, the reliability–throughput trade-off is the main axis along which the two basins differ.

39

D. Demand-Centric and Request-Level Perspectives The broadcast-efficiency analysis above identifies the full model as the best-performing variant on the broadcast-packet expiration ratio (ρ) and the BE-Score (σ). The problem, however, is that the formal-taxonomy primary metrics (ρ, δ; Sec. V-D) and the supplementary request-level family give a more nuanced picture, i.e., including the ranking reversals on δ and on σreq that challenge the broadcast-efficiency narrative. Ranking reversal on distinct file-identity coverage (δ). The full model is not the best on the distinct file-identity coverage, i.e., the w/o BC + ExIt variant achieves δ = 0.834, thereby surpassing the full model (δ = 0.824) by +1.2% (Table XXI), while the w/o BC Warm-Start variant ranks second (δ = 0.829, +0.6%). This reversal is explained by the relationship between the merge rate and the unique-demand coverage, i.e., the broadcast-level expiration ratio ρ uses the packet-set XOR degree Ut = |fmg | in its denominator, thereby aggressive merging inflates the denominator. The distinct fileidentity coverage δ instead counts each file identity at most once per episode, while crediting only the first successful delivery. The w/o BC + ExIt variant’s ultra-conservative policy (i.e., merge rate 0.238 vs. 0.318) carries a smaller packetset per transmission, even though it avoids the redundant retransmission of already-covered file identities, thereby yielding better distinct file-identity coverage. This variant also achieves the fewest expirations (13.95) and the lowest request-level miss rate (mreq = 0.215, −6.2% vs. full model). Ranking reversal on request-level selection score (σreq ). On the composite request-level metric σreq = ηreq − mreq , the full model ranks fifth out of the six variants (σreq = 0.839), while the w/o BC Warm-Start variant achieves the best score (σreq = 0.866, +3.2%), followed by the w/o BC + ExIt (0.861, +2.5%). The request-level metrics show a throughput– accuracy tradeoff, i.e., removing the curriculum yields the highest per-step request timely-throughput (ηreq = 1.118) but the worst per-step request miss rate (0.278), while removing the BC achieves a more favorable balance (ηreq = 1.093, mreq = 0.227). This suggests that the BC warm-start introduces a broadcast-efficiency bias, i.e., the BC training objective maximizes the broadcast-level packet-set XOR degree, which biases the initialized policy toward aggressive scheduling that helps the broadcast-efficiency metrics, even though it impairs the request-level quality on the per-step ηreq /mreq scores. The merge-rate paradox. These reversals reflect a tension between the metric families, i.e., mediated by the merge rate. Aggressive merging (i.e., w/o Curriculum: merge rate 0.476) maximizes the served packet-set count per transmission (µ = 1.431) and the per-step request timely-throughput (ηreq = 1.118), even though it produces the worst file-identity miss ratio (1 − δ = 0.199) and the worst per-step request miss rate (0.278). Conservative merging (i.e., w/o BC + ExIt: merge rate 0.238) achieves the opposite, i.e., the worst broadcastefficiency (σ = 0.884), even though the best file-identity coverage (δ = 0.834) and the best per-step request miss rate (0.215). The full model’s selective merge rate (0.318) occupies a middle ground that optimizes the broadcast-efficiency while

PREPRINT — SUBMITTED FOR PEER REVIEW

40

TABLE XXIII A BLATION STUDY: ∆ VS . F ULL M ODEL ACROSS ALL REGIMES FOR THE TWO PRIMARY METRICS AND ONE SUPPLEMENTARY METRIC . M ISS RATIO ρ ( PRIMARY, POSITIVE = WORSE ); FILE - IDENTITY COVERAGE δ ( PRIMARY, NEGATIVE = WORSE ); REQUEST SELECTION SCORE σreq ( SUPPLEMENTARY, NEGATIVE = WORSE ). Variant

ID-default

OOD-delay10

OOD-delay30

Curr-file60

OOD-file120

OOD-file150

OOD-pcache0.20

Curr-pcache0.40

+0.018 +0.008 +0.004 +0.013 +0.017

+0.024 +0.012 +0.007 +0.006 +0.029

+0.041 +0.020 +0.013 +0.013 +0.043

+0.042 +0.020 +0.013 +0.013 +0.044

+0.041 +0.019 +0.013 +0.012 +0.043

+0.024 +0.015 +0.002 +0.000 +0.032

+0.057 +0.026 +0.031 +0.036 +0.045

−0.018 +0.006 −0.002 +0.011 −0.022

−0.018 +0.005 −0.002 +0.011 −0.023

−0.016 +0.007 −0.001 +0.012 −0.022

−0.010 +0.003 +0.003 +0.011 −0.017

−0.032 +0.001 −0.014 +0.003 −0.027

−0.000 +0.029 +0.006 +0.023 +0.003

+0.000 +0.028 +0.006 +0.023 +0.001

+0.002 +0.030 +0.007 +0.025 +0.002

−0.002 +0.017 +0.006 +0.015 −0.005

−0.005 +0.025 +0.003 +0.033 +0.004

∆ Miss Ratio ρ (↑ = degradation) w/o ExIt w/o BC Warm-Start w/o Graph-Attention w/o BC + ExIt w/o Curriculum

+0.041 +0.020 +0.013 +0.013 +0.044

∆ Distinct File-Identity Coverage δ (↑ = improvement over Full Model) w/o ExIt w/o BC Warm-Start w/o Graph-Attention w/o BC + ExIt w/o Curriculum

−0.018 +0.005 −0.003 +0.010 −0.023

−0.004 +0.006 −0.005 −0.004 +0.015

−0.012 +0.001 −0.001 +0.005 −0.017

∆ Request Selection Score σreq (↑ = improvement over Full Model) w/o ExIt w/o BC Warm-Start w/o Graph-Attention w/o BC + ExIt w/o Curriculum

−0.000 +0.027 +0.005 +0.021 +0.000

−0.004 +0.029 −0.020 −0.020 +0.091

+0.002 +0.011 +0.005 +0.004 +0.004

sacrificing some file-identity and request-level performance on the per-step scores. This multi-objective tension is an inherent property of the coded caching with deadlines, i.e., a coded broadcast contributes |fmg | packet identities to the per-slot count Ut (and credits multiple original arrivals at the request level), however, it may delay individual requests waiting for the merge opportunities, thereby increasing the per-step request miss count |Mt |. E. OOD Robustness of Ablation Findings Table XXIII summarizes the per-component deltas across all the eight regimes for the two primary metrics, i.e., the broadcast-packet expiration ratio (ρ) and the distinct fileidentity coverage (δ), alongside the supplementary request selection score (σreq ). The miss-ratio panel confirms that every one of the components reduces the broadcast-packet expiration ratio (i.e., all ∆ρ > 0), while the relative ordering is consistent across the conditions. The demand-centric and the requestlevel panels give a richer picture, i.e., the ranking reversals identified at ID-default persist across most of the regimes, with exceptions under the extreme deadline pressure. We summarize several cross-regime patterns below. Curriculum: the miss-ratio penalty from removing the curriculum is the largest or second-largest across nearly all of the regimes. The degradation is most severe at OODdelay30 (+2.9 pp, +45.4% relative), where the relaxed deadline horizon most clearly separates the policies that learned the selective merging from those that merge indiscriminately. At Curr-pcache0.40 (+4.5 pp, +18.7%) and OOD-pcache0.20 (+3.2 pp, +18.4%), the high density of the merge candidates increases the cost of the aggressive merging strategy that arises without the curriculum training. ExIt: the reliability degradation from removing the ExIt is substantial across all of the regimes, with the absolute missratio increases ranging from +0.018 (i.e., OOD-delay10) to

+0.057 (i.e., Curr-pcache0.40). In relative terms, the impact is largest at OOD-delay30 (+37.6%), where the longer deadline horizons give the most scope for the deadline-aware mergedeferral behavior associated with the ExIt. At Curr-pcache0.40 (+23.9%), the high cache fraction creates many merge opportunities where the ExIt’s restraint matters most. BC Warm-Start: the OOD amplification noted at IDdefault is most pronounced at Curr-pcache0.40 (+2.6 pp broadcast-packet expiration ratio, +11.1% relative), where the large cache fraction creates many merge candidates that require the structured initialization from the BC to navigate effectively. The BC warm start is disproportionately useful under the stress. Graph-Attention: the smallest single-component miss-ratio increase across most of the regimes, with the exception of Curr-pcache0.40 where the graph-attention removal causes a larger degradation (+3.1 pp, +13.2% relative). Under the high cache-fraction regime, the graph-attention encoder’s ability to reason about the pair quality matters more as the number of viable merge candidates grows. Demand-centric OOD patterns (δ panel). The ranking reversal on the distinct file-identity coverage persists across the regimes, i.e., the w/o BC + ExIt achieves higher δ than the full model in seven of the eight conditions (∆δ > 0), with the sole exception being OOD-delay10 (∆δ = −0.004). Under the extreme deadline pressure of OOD-delay10, the w/o Curriculum variant (i.e., which merges most aggressively, merge rate 0.637) instead achieves the highest δ (+0.015 vs. full model), since maximizing the immediate throughput becomes essential for serving the unique files before they expire. The w/o BC Warm-Start variant shows consistently positive ∆δ across all of the regimes, thereby confirming that the BC-initialized policy’s broadcast-efficiency bias is a persistent, regime-independent phenomenon. Request-level OOD patterns (σreq panel). The w/o BC

PREPRINT — SUBMITTED FOR PEER REVIEW

Warm-Start variant achieves positive ∆σreq across all of the eight regimes, thereby confirming it as the most consistent variant on the request-level selection score. The advantage is largest at OOD-delay10 (+0.029) and Curr-file60 (+0.029). The interesting fact we observed is that an exception appears at OOD-delay10, i.e., the w/o Curriculum achieves ∆σreq = +0.091, which is the largest improvement of any variant in any regime. Under the extreme deadline pressure, the aggressivemerging policy’s high request throughput (ηreq = 1.361) outweighs its elevated miss rate, thereby producing the best σreq , even though with poor broadcast-efficiency metrics. This confirms that the curriculum learning shapes a deadline-conscious policy that trades the raw throughput for the selectivity, i.e., a tradeoff that is beneficial under the normal deadlines, even though it is suboptimal under the extreme pressure. Summary. Each of the training components contributes to the full model’s multi-objective performance profile, however, the direction of the contribution depends on the metric family. On the broadcast-level metrics (ρ, σ; i.e., ρ is a primary metric and σ a secondary broadcast-efficiency metric in the taxonomy of Sec. V-D, however, both are computed at the broadcast/packet-set level), the full model dominates, i.e., the curriculum learning and the Expert Iteration are the two most important components, jointly responsible for most of the broadcast-packet expiration advantage. On the file-identity coverage metric (δ), the w/o BC + ExIt variant exceeds the full model (+1.2% on δ, consistent across 7/8 regimes) by avoiding the redundant retransmission of already-covered files. On the request-level metrics (σreq ), the w/o BC Warm-Start variant achieves the best selection score (+3.2%, consistent across all the 8 regimes) by avoiding the broadcast-efficiency bias inherited from the BC training. The graph-attention has the smallest single-component effect across all of the metric families. The combined removal of the BC + ExIt exposes the non-additive component interactions, i.e., the resulting ultra-conservative policy gives up the broadcast-level packet throughput (−6.8% on Served/Tx, µ), even though it achieves the best file-identity coverage and the lowest request miss rate, thereby indicating that the training pipeline’s value lies in the qualitative character of the multi-objective tradeoff the components jointly navigate, beyond their individual contributions. F. Discussion Mechanistic interpretation of selective merging. The results across Sections VI-B–VI-E converge on a consistent mechanistic picture for the uniform-demand regime, i.e., the learned policy implements a state-dependent selective merge heuristic that conditions on the per-pair intersection size and the per-request deadline urgency, while merging only 31.8% of the opportunities and achieving a high average intersection (0.589). The interesting fact we observed is that a separately trained Zipf-demand agent (Section VII) independently discovers a qualitatively different strategy (i.e., merging 99.7% of opportunities versus 31.8% here), thereby indicating that the architecture adapts to the demand-induced queue-state distributions. This context-sensitive adaptivity, i.e., suggestive of a policy-mediated component to the cross-track behavioral

41

difference per the descriptive visited-state intersection diagnostic (Section VII; the diagnostic is descriptive only, not an inferential test), is unachievable by any fixed-threshold policy and is a central qualitative contribution of the learned agent. Stress amplification and asymmetry. A recurring pattern across the evaluation is that the agent’s advantage over the baselines grows under the conditions that penalize the blind merging (i.e., high cache density, tight deadlines) while it attenuates when those conditions relax (e.g., low cache density, where the fewer merge opportunities limit any policy’s scope for the differentiation). This asymmetry indicates that the practical value of a learned delivery policy is greatest in the operating regimes where the network load and the deadline pressure are most severe. Limitations and threats to validity. Several limitations scope the current findings. (i) The environment models a single broadcast domain with K = 5 users and pairwise XOR merges; extending to larger user populations and higherorder coded transmissions may introduce scalability challenges for the graph-attention architecture. (ii) Cache placement is fixed per episode via random decentralized prefetching; in practice, cache contents evolve through eviction and replacement, introducing non-stationarity not captured here. (iii) All evaluations are conducted in simulation with perfect cachestate knowledge; real deployments must contend with imperfect side-information estimates, heterogeneous file sizes, and time-varying channel conditions. (iv) Training requires approximately 59 hours on a single GPU (Appendix N, Table XXXVII), which may limit rapid redeployment under substantial distribution shift. (v) The catalog-size axis (N ∈ {60, 120, 150}) does not constitute a genuine distribution shift under the current placement model, since the per-packet caching probability pc is invariant to N ; incorporating noni.i.d. or capacity-constrained placement would provide a more meaningful catalog-dimension stress test. These limitations motivate the future directions outlined in Section IX. Deployment implications. From a systems perspective, the selective merge strategy suggests a design principle for the deadline-constrained coded caching, i.e., an edge server should not merge every feasible pair, but should reserve the coded transmissions for the high-intersection pairs while unicasting the urgent or low-overlap requests. Within each demand track, the learned policy’s zero-shot transfer across all of the evaluation regimes indicates that a single trained model can serve a range of the operating conditions (i.e., varying catalog size, cache density, and deadline budget) without perregime tuning, thereby lowering the operational complexity. The inference cost of the graph-attention network (i.e., forward pass over at most Pmax = 45 candidate actions; ∼3.5 ms GPU, ∼3.3 ms CPU per Appendix T) is reported as a conditional feasibility indicator, i.e., whether it meets a per-slot real-time scheduling target depends on the deployment’s slot-duration budget, which we do not import from outside the manuscript. IX. C ONCLUSION AND L IMITATIONS The coded caching promises a global caching gain that scales with the number of the edge users by exploiting the

PREPRINT — SUBMITTED FOR PEER REVIEW

cached side information for the broadcast transmissions [3], [4]. The problem, however, is that in the delay-sensitive applications, a gain–deadline tension arises, i.e., each XOR merge consumes the shared side information and risks pushing the aggregated requests past their expiration deadlines. The fixed-threshold rules face a structural tension between the coding gain and the deadline compliance, i.e., the mergeor-defer decision is queue-state-dependent, thereby any stateindependent rule gives up either the gain or the expiration ratio at the extremes (Sec. VI, τ -Fit ablation). To the best of our knowledge, after the literature sweep summarized in Section II, the prior RL delivery formulations for the coded caching had not combined the hard expirations, the keep-side control, and the dynamic invalid-action masking in one integrated delivery scheduler; we treat this as a positioning statement rather than as a definitive non-existence result. We proposed four contributions toward filling that gap, i.e., (C1) a masked discrete-action queue-state control formulation for the deadline-constrained coded delivery with the dynamic feasibility masking and a shaped reward, trained as a stationary policy under a discounted truncated continuing-control surrogate; (C2) a graph-attention policy network that captures the combinatorial queue interactions; (C3) a three-phase training pipeline combining the behavior-cloning warm start, the value pre-training, and the MaskablePPO with the curriculum learning and the Expert Iteration; and (C4) the evaluation across the 9 Track A baselines plus the PPO (10 unique methods), the 7 non-ID Track A regimes (i.e., 2 curriculum-seen, 5 unseen-parameter within the same simulator family), and the eight-regime ablation battery, plus a main-body Zipf-demand extension study (Section VII) covering 11 additional regimes. Against this benchmark (i.e., Track A, uniform demand), the σ-selected checkpoint (i.e., the model picked by the robustadvantage rule on the BE-score σ at the validation; see Sec. IV-F) achieved the lowest broadcast-packet expiration ratio ρ among all of the coded-multicast methods, thereby lowering ρ by 40.9% with respect to the SACM++ (0.208 vs. 0.352; i.e., at H=50 with the episode-end right-censoring, the absolute values are simulator-specific, see Sec. V-D) while maintaining the competitive distinct file-identity coverage and, on Track A, the highest broadcast-efficiency system score σ among the coded-multicast methods across all the 8 regimes (and the highest overall σ in 7 of the 8 Track A regimes; the ED-Unicast leads on σ at OOD-delay10). The paired bootstrap intervals favor the PPO over the SACM++ on the primary demand-centric metrics (ρ and δ; Section VI), i.e., on ρ the PPO leads the SACM++ by −0.144 (95% CI [−0.146, −0.143], Table VIII), while on δ the PPO leads the SACM++ by +0.027 (0.824 vs. 0.797 at ID-default; the PPO leads in 7 of the 8 Track A regimes, Table XII). The supplementary request-level mreq is reported separately above, i.e., the PPO leads the SACM++ (0.229 vs. 0.326), even though it trails the ED-Unicast (∆mreq = +0.074, Table VIII). The ED-Unicast also remains stronger on ρ and δ at the cost of zero coding gain. The advantage grew under the stress conditions, while the gains transferred across the full Track A non-ID battery (i.e., 2 curriculum-seen and 5 unseen-parameter regimes covering the unseen cache fractions and deadline

42

budgets, plus the parameter-invariance sweeps over the file count under fixed pc , all within the same simulator family) and the full Track B non-ID battery (i.e., 2 curriculum-seen and 9 unseen-parameter regimes within the same simulator family). Because all of the transfer experiments keep fixed K, Q, the action dimensionality, and the placement family, these results demonstrate the within-family parameter generalization rather than the broad architectural out-of-distribution robustness. Under the (supplementary) request-level accounting that tracks each original arrival through the queue aggregation, the PPOAgent achieves a substantially lower per-step request miss rate than the SACM++ (mreq = 0.229 vs. 0.326, i.e., a 29.8% relative reduction at ID-default). The paired-bootstrap analysis at Table VIII shows that the ED-Unicast remains the strongest deadline-protection baseline on mreq (∆mreq = +0.074 for the PPO minus the ED-Unicast at ID-default, i.e., the PPO is worse than the ED-Unicast on this metric), thereby we restrict the headline “lower than” phrasing to the SACM++ comparison and treat the broader “lower than all coded baselines” statement as conjectural pending the request-level extension over the GCM, SACM, SACM+, and τ -Fit family, which is left as future work. The request selection score σreq exceeds the coded baseline SACM++ once the request-level miss penalty crosses a regime-dependent threshold λ⋆ (i.e., median λ⋆ ≈ 2.24, with λ⋆ ≤ 4.92 in the worst regime). The uncoded EDUnicast baseline remains the highest σreq at every λ shown on the ID-default sensitivity table of Appendix P, thereby the PPO’s σreq advantage is over the coded baselines, i.e., not over the uncoded EDF policy. The crossover reflects a throughput–compliance tradeoff, i.e., the SACM++’s alwaysmerge strategy delivers more coded packets per step, however, the PPO’s selective merging produces fewer per-step deadlinemiss events |Mt |. The request-level family is per-step by definition, i.e., P mreq =H −1 t |Mt |, i.e., not normalized by the total number of the admitted arrivals. The “per-arrival” completion rates would require an arrival-normalized denominator that we do not report in this version. Under the Zipf-demand extension, the PPO-Agent dominates the SACM++ on σreq at every tested λ across all the 12 regimes, while remaining competitive with the popularity-aware SACM++-Pop baseline; the only neartie exception is OOD-pcache0.20 (Z), where the Pop edges the PPO at λ=1 (0.852 vs. 0.848). The PPO’s advantage stems from its near-full merging strategy under the Zipf demand, which matches the baseline throughput while retaining the lower miss rates (Appendix Q). A main-body extension (Section VII) shows that the same framework extends to the skewed demand distributions, i.e., a separately trained popularity-aware variant, using an augmented observation space, remains competitive with the coded-multicast baselines across the 11 additional Zipf-demand regimes. The ablation study confirmed that each of the four training components (i.e., the BC warm start, the graph-attention architecture, the Expert Iteration distillation, and the curriculum learning) contributes meaningfully on average, with the non-additive interactions and the per-metric reversals on δ and σreq documented in Section VIII.

PREPRINT — SUBMITTED FOR PEER REVIEW

The qualitative finding is an emergent selective merge strategy, i.e., the agent executes only 31.8% of the available merge opportunities, even though it achieves an average pair intersection of 0.589, thereby exceeding the SACM++ (0.393) and the best-BE-score τ -Fit threshold baseline (i.e., TauFit-2 at 0.359); the Perfect-Fit, i.e., the most conservative threshold rule, attains a higher per-merge intersection (0.819), even though at a substantially worse broadcast-level expiration ratio (Sec. VI, Table XIV). This state-dependent behavior (i.e., merging when the intersection is high and the deadlines are comfortable, while deferring to the earliest-deadline unicast otherwise) is not replicable by a fixed-threshold heuristic and directly explains the agent’s multi-objective advantage over the threshold-based baselines. We caution that the qualitative selective-merge behavior is established for the simulator definition adopted in Sec. III-F, i.e., including the uniform representative-destination convention kmg ∼ Unif{ki , kj } of Eq. (6); the sensitivity to the alternative representativeupdate rules (e.g., keep-side-tied or earliest-deadline-tied) is not tested here and is left as future work. The interesting fact we observed is that the Zipf-trained agent reaches a nearfull merging strategy (99.7% merge rate vs. 31.8% under the uniform demand), i.e., a pattern consistent with (though not isolating) the demand-dependent behavior, given that the two tracks differ in three couplings simultaneously (i.e., the demand law, the observation space, and the joint training distribution). A controlled ablation that holds the observation space fixed and varies only the demand law would be needed to causally attribute the shift to the demand structure alone, while this is left as future work. A visited-state intersection diagnostic (Section VII) is consistent with a policy-mediated component to the behavioral difference, however, it does not cleanly separate the policy-induced shift from a baseline tworequest joint shift induced by the demand law itself (i.e., the same-packet pairs become more likely under the skewed demand even with the popularity-blind placement); the diagnostic is descriptive only, while a controlled decomposition is left to future work. a) Deployment considerations.: The trained policy has low inference cost, i.e., a single forward pass of the graphstructured policy network on the K=5, Q=10, Pmax =45 observation requires approximately 3.5 ms on a GPU and ∼3.3 ms on a CPU on the hardware described in Appendix T. We do not import a fixed slot-duration threshold from outside the manuscript; consistent with the latency appendix, this measurement is reported as a conditional feasibility indicator tied to the deployment’s slot-duration budget and to the hardware actually deployed at the edge, i.e., not as a certified realtime guarantee. At the edge node, the agent requires three types of run-time statistics, i.e., (i) the current cache state Ck for each user k (i.e., maintained locally and updated on the eviction events), (ii) the per-request remaining deadlines dr (i.e., derived from the arrival timestamps and the configured maximum deadline D), and (iii) the pending queue’s sideinformation sets Sr (i.e., computed as a set-membership query against the cache state), while no channel-state information or demand-prediction model is required. Because the cache placement is fixed per delivery episode, the model does not

43

need the online retraining during a session, i.e., a new agent may be trained offline when the cache probability pc or the deadline budget D shifts substantially. The full source code will be released upon acceptance. b) Scope and first-order limitations.: The reported gains are conditional on three simulator and observation conventions that materially shape the throughput / deadline trade-off and the value of the keep-side control, i.e., (L1) the one-slotper-record unicast cost abstraction (Sec. III-B0c, A2), under which a unicast of an aggregate of size |fr | still consumes one channel use rather than |fr | slots; (L2) the representativedestination update kmg ∼ Unif{ki , kj } (Eq. (6)), i.e., independent of the keep-side bit κ (i.e., correctness only requires kmg ∈ {ki , kj }; the uniformity is a chosen simulator convention); and (L3) the aggregate-size observation clip min(|fr |, Umax )/Umax at Umax = 6 (Sec. III-F2, Appendix F), which aliases all states with |fr | ≥ Umax on the size feature, even though the transition and feasibility rules impose no hard cap on |fr |. Appendix G reports an empirical saturationfrequency diagnostic on the deployed checkpoint that shows the clip rate Pr[|fr | ≥ Umax ] stays below 6·10−6 on both the IDdefault and the Curr-pcache0.40 stress regime, with 90–91% of the observations being singletons (|fr |=1); the observation aliasing is therefore empirically negligible on the on-policy support, while the structural argument of Appendix F is empirically supported. What remains open is a controlled trainingtime sensitivity sweep over Umax ∈ {6, 8, 12} (or a richer aggregate-summary observation that retains the contained file identities); the qualitative selective-merge claim of this paper is therefore reported within the Umax = 6 aggregate-size convention, with the on-policy clip rate empirically verified, even though the training-time sensitivity is left as future work. Under a packet-level unicast cost model (i.e., in which an aggregate unicast charges |fmg | slots), under a different representative-update rule (e.g., keep-side-tied or earliestdeadline-tied), or under an enriched aggregate-summary observation, both the throughput / deadline frontier and the relative ranking of the merge-or-defer policies could change substantially. We therefore restate the (L1)–(L3) as first-order modeling assumptions of the present results, i.e., not as cosmetic simulator details, while the deployment-relevance and the broad delivery-policy claims in this section should be read as conditional on the (L1)–(L3) and on the contextual-POMDP surrogate of Sec. III-E. We leave the focused sensitivity sweeps over an alternative unicast cost, an alternative representative rule, and a richer aggregate observation (or a larger Umax ) for future work. c) Future work.: Three directions follow from the present results, i.e., • Multi-user coded transmissions: Extending to the higher-order multicasting (K ≥ 3 per broadcast) via the hierarchical or autoregressive action representations could approach the full theoretical global caching gain [3]. • Joint placement and delivery: Jointly optimizing the cache placement and the delivery via a two-timescale or multi-agent framework would cover the full coded caching pipeline. • Theoretical characterization of selective merging: The

PREPRINT — SUBMITTED FOR PEER REVIEW

44

emergent 31.8% merge rate lacks a formal characterization, i.e., a Lyapunov drift or online convex optimization analysis of when the selective merging is optimal would strengthen the result. In summary, we proposed a DRL-based solution for the deadline-constrained coded delivery, where the policy network reduces the broadcast-packet expiration ratio ρ by 40.9% with respect to the best coded multi-casting baseline (SACM++) on the uniform-demand benchmark, while also attaining the best broadcast-efficiency score σ among the coded multi-casting methods in 7 of 8 Track A regimes, even though the uncoded ED-Unicast baseline still attains a lower ρ and a lower requestlevel miss rate mreq by forfeiting all coding gain, so the ρ headline is restricted to 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 only at a ≈ 31.8% rate, and the same observation is true within the simulator family for the variations of the file count, the cache fraction, and the deadline budgets, even though the placement family, K, Q, and the action dimensionality are held fixed, so we describe this as within-family parameter generalization rather than fully outof-distribution evaluation. A PPENDIX A E VALUATION M ETRIC N OTATION Table XXIV lists the evaluation metric symbols used throughout the paper. Symbol

Description

Symbol

Description

Ut λ ρ ε mrate Ct ηreq σreq

Packet-set XOR degree at step t (|fmg | for a coded transmission, 1 for a unicast) Expiration penalty weight Broadcast-packet expiration ratio Expirations per episode Merge rate Newly completed request IDs at t Request timely-throughput Request selection score

Et σ µ τ orate Mt mreq A(r)

Expired packet-set mass at step t Broadcast-efficiency score Packet-set count per transmission Merge threshold (TauFit) Opportunity rate Newly missed request IDs at t Request miss rate Request-ID annotation set

TABLE XXIV E VALUATION METRIC NOTATION .

A PPENDIX D Z IPF -D EMAND OOD D ETAIL Table XXIX provides the complete per-method deadlinemiss-ratio breakdown for all Zipf-demand OOD regimes, thereby extending the three-method comparison in Section VII-A Table XVII. A PPENDIX E I LLUSTRATIVE T HREE -R EQUEST M ERGE E XAMPLE This appendix provides the complete step-by-step derivation of the three-request merge example summarized in Section III-C. Consider a system with K = 3 caches and a queue of Q = 3 pending requests at some time step t:  r0 = k=0, f ={p1 }, d=5, S={1, 2} ,  r1 = k=1, f ={p2 }, d=3, S={0, 2} ,  r2 = k=2, f ={p3 }, d=2, S={0, 1} . Step 1—Feasibility check. Pair (r0 , r1 ): cache k1 =1 holds {p1 } = f0 (since 1 ∈ S0 ), and cache k0 =0 holds {p2 } = f1 (since 0 ∈ S1 ). Both sides of (2) are satisfied, so the pair is feasible. Step 2—First broadcast (merge with keep-side κ = 0). The server broadcasts X = p1 ⊕ p2 in one channel use; cache 1 cancels p1 to recover p2 , and cache 0 cancels p2 to recover p1 . Both users are served immediately (Ut = 2). Two outcomes are decided independently at this step: (a) the keepside parameter κ = 0 selects which queue slot is preserved and which slot is replenished (here, slot 0 retains the aggregate and slot 1 is refilled with a fresh arrival rnew ); (b) the representative destination kmg is sampled uniformly at random from {k0 , k1 } = {0, 1} independently of κ (per (6)). The slot retained by κ is therefore updated to the coding-state record r0′ = k=kmg ∼ Unif{0, 1}, f ={p1 , p2 },  d= min(5, 3)=3, S={1, 2} ∩ {0, 2}={2} ,

A PPENDIX B F ULL BASELINE C OMPARISON Table XXV reports the complete twelve-row comparison (10 unique methods, i.e., Perfect-Fit = TauFit-0 and FirstFit = TauFit-3 are aliases retained for literature continuity) on the ID-default uniform-demand condition, while also including the six τ -Fit threshold rules (Perfect-Fit, TauFitτ ∈ {0, 1, 2, 3}, First-Fit) that were omitted from the mainbody Table IX. Table XXVI complements the full comparison by ranking all methods on each individual metric. A PPENDIX C U NIFORM -D EMAND OOD D ETAIL This appendix provides the complete per-method breakdowns for all uniform-demand non-ID regimes, thereby extending the two-method comparison in Section VI-C Table X. Table XXVII reports the broadcast-packet expiration ratio ρ while Table XXVIII reports the broadcast-efficiency score across all six core methods and eight regimes.

where the file set, deadline, and side-information set are determined by (3)–(5) and are unaffected by either κ or the realization of kmg . The aggregate r0′ remains in the queue to track the enlarged packet union and tightened side-information set for future XOR feasibility; it does not represent unserved demand. Note that κ alters only which queue slot the aggregate occupies (and, equivalently, which slot is freed for fresh arrivals); kmg alters only which user is treated as the representative destination for the one-gap invariant (Proposition 1). The two decisions are decoupled in our environment. Step 3—Second broadcast (chained merge). Suppose request r2 is still pending and the representative destination from Step 2 is the realization kmg = 0 (the analysis for kmg = 1 is symmetric). Pair (r0′ , r2 ): cache k2 =2 must hold f0′ = {p1 , p2 }. Since 2 ∈ S0′ = {2}, cache 2 indeed holds both packets. Conversely, cache kmg =0 must hold f2 = {p3 }; since 0 ∈ S2 = {0, 1}, this also holds. The pair is feasible. The server broadcasts X ′ = p1 ⊕ p2 ⊕ p3 in a second channel use. The two active participants decode as guaranteed by Proposition 1: user 2 (new partner) cancels {p1 , p2 } ⊂ C2

PREPRINT — SUBMITTED FOR PEER REVIEW

45

TABLE XXV F ULL BASELINE COMPARISON INCLUDING τ -F IT THRESHOLD RULES (P ERFECT-F IT, TAU F IT-τ VARIANTS , F IRST-F IT ). ID- DEFAULT, UNIFORM DEMAND . 50 HOLDOUT SEEDS × 200 EPISODES . M EAN ± 95% CI. B OLD = BEST. Method

BE-Score σ (↑)

Miss Ratio (↓)

Served/Tx (↑)

Coding Gain (↑)

Exp/Episode (↓)

PPO-Agent ED-Unicast GCM SACM SACM+ SACM++

0.976 ± 0.002 0.845 ± 0.001 0.733 ± 0.003 0.745 ± 0.003 0.731 ± 0.003 0.726 ± 0.003

0.208 ± 0.001 0.134 ± 0.001 0.345 ± 0.001 0.345 ± 0.001 0.348 ± 0.001 0.352 ± 0.001

1.323 ± 0.002 1.000 ± 0.000 1.549 ± 0.002 1.575 ± 0.002 1.572 ± 0.002 1.590 ± 0.003

2.162 ± 0.002 — 2.095 ± 0.001 2.131 ± 0.001 2.124 ± 0.001 2.131 ± 0.001

14.17 ± 0.07 7.74 ± 0.06 28.42 ± 0.15 28.64 ± 0.13 28.71 ± 0.14 28.76 ± 0.14

Perfect-Fit TauFit-0 TauFit-1 TauFit-2 TauFit-3 First-Fit

0.877 ± 0.002 0.877 ± 0.002 0.908 ± 0.002 0.915 ± 0.002 0.915 ± 0.003 0.915 ± 0.003

0.185 ± 0.001 0.185 ± 0.001 0.245 ± 0.001 0.258 ± 0.001 0.259 ± 0.001 0.259 ± 0.001

1.135 ± 0.001 1.135 ± 0.001 1.343 ± 0.001 1.405 ± 0.002 1.408 ± 0.002 1.408 ± 0.002

2.063 ± 0.002 2.063 ± 0.002 2.097 ± 0.001 2.077 ± 0.001 2.066 ± 0.001 2.066 ± 0.001

10.55 ± 0.07 10.55 ± 0.07 14.92 ± 0.10 16.22 ± 0.09 16.32 ± 0.09 16.32 ± 0.09

TABLE XXVI τ -F IT METHOD RANKINGS PER METRIC ( TOP -6, ID- DEFAULT ). R ANK 1 = BEST ON THAT METRIC . Rank 1 2 3 4 5 6

BE-Score σ (↑)

Served/Tx (↑)

Miss Ratio (↓)

Coding Gain (↑)

Exp/Episode (↓)

PPO-Agent (0.976) TauFit-2 (0.915) TauFit-3 (0.915) First-Fit (0.915) TauFit-1 (0.908) Perfect-Fit (0.877)

SACM++ (1.590) SACM (1.575) SACM+ (1.572) GCM (1.549) First-Fit (1.408) TauFit-3 (1.408)

ED-Unicast (0.134) Perfect-Fit (0.185) TauFit-0 (0.185) PPO-Agent (0.208) TauFit-1 (0.245) TauFit-2 (0.258)

PPO-Agent (2.162) SACM (2.132) SACM++ (2.131) SACM+ (2.124) TauFit-1 (2.097) GCM (2.096)

ED-Unicast (7.742) Perfect-Fit (10.55) TauFit-0 (10.55) PPO-Agent (14.17) TauFit-1 (14.92) TauFit-2 (16.22)

TABLE XXVII U NIFORM DEMAND , BROADCAST- PACKET EXPIRATION RATIO ρ (M ISS R ATIO , BROADCAST- LEVEL ; S EC . V-D) ACROSS ALL NON -ID REGIMES AND METHODS . M EAN ± 95% CI. B OLD = BEST. Regime

PPO-Agent

ED-Unicast

GCM

SACM

SACM+

SACM++

ID-default Curr-file60 OOD-file120 OOD-file150 OOD-pcache0.20 Curr-pcache0.40 OOD-delay10 OOD-delay30

0.208 ± 0.001 0.208 ± 0.001 0.208 ± 0.001 0.209 ± 0.001 0.176 ± 0.001 0.238 ± 0.001 0.500 ± 0.000 0.064 ± 0.001

0.134 ± 0.001 0.133 ± 0.001 0.133 ± 0.001 0.134 ± 0.001 0.133 ± 0.001 0.134 ± 0.001 0.495 ± 0.001 0.036 ± 0.000

0.345 ± 0.001 0.344 ± 0.001 0.344 ± 0.001 0.345 ± 0.001 0.260 ± 0.001 0.405 ± 0.001 0.555 ± 0.000 0.176 ± 0.002

0.345 ± 0.001 0.344 ± 0.001 0.344 ± 0.001 0.345 ± 0.001 0.260 ± 0.001 0.405 ± 0.001 0.553 ± 0.000 0.180 ± 0.001

0.348 ± 0.001 0.347 ± 0.001 0.347 ± 0.001 0.347 ± 0.001 0.263 ± 0.001 0.408 ± 0.001 0.555 ± 0.000 0.181 ± 0.001

0.352 ± 0.001 0.352 ± 0.001 0.353 ± 0.001 0.353 ± 0.001 0.265 ± 0.001 0.412 ± 0.001 0.555 ± 0.000 0.186 ± 0.002

to recover p3 ; user kmg = 0 cancels {p2 , p3 } ⊂ C0 to recover p1 , consistent with the one-gap invariant for the realization p⋆ = p1 (had kmg = 1 been drawn, the gap packet would instead be p⋆ = p2 and user 1 would recover it from {p1 , p3 } ⊂ C1 ). In this particular example, the nonrepresentative user can also decode because the symmetric cache structure ensures {p1 , p3 } ⊂ C1 and {p2 , p3 } ⊂ C0 ; however, this is a consequence of the example’s symmetry, not a general property of chained merges (Remark 7). The XOR degree of this broadcast is Ut = |f0′ ∪ f2 | = 3, exceeding the pairwise baseline of 2. After this merge, the aggregate’s side-information set shrinks to Smg = {2} ∩ {0, 1} = ∅, so no further merges are possible, thereby illustrating the mergeability cost of the method of aggressive chaining. A PPENDIX F O BSERVATION F EATURE D EFINITIONS Tables XXX and XXXI list the per-request and per-pair features used in the observation encoding (Section III-F2).

a) Normalization constants used in Tables XXX–XXXI.: We fix: • Umax = 6 is an observation-only clip: the packet-set size feature (aggregate size |fr |) uses min(|fr |, Umax )/Umax , so aggregates with |fr | > 6 would saturate at 1 on this feature dimension. There is no hard cap on |fr | in the merge-feasibility rule (Eq. (2)) or in the one-step transition (Algorithm 1); aggregates may grow beyond Umax packets in principle. max_union_files is the name of the corresponding implementation hyperparameter in the reference simulator and is only an observation-feature normalization constant (the input that sets Umax in the feature min(|fr |, Umax )/Umax ); it is not a transition-time or feasibility-time cap on |fr |. The observation therefore aliases all states with |fr | ≥ Umax on this feature coordinate, which we accept because (i) deep chains are rare on the onpolicy support, and (ii) the side-information set Smg shrinks monotonically with chain depth, making longer chains progressively infeasible to extend. Appendix G reports an empirical saturation-frequency diagnostic on the deployed

PREPRINT — SUBMITTED FOR PEER REVIEW

46

TABLE XXVIII U NIFORM DEMAND , BROADCAST- EFFICIENCY SCORE ACROSS ALL NON -ID REGIMES AND METHODS . M EAN ± 95% CI. B OLD = BEST. Regime ID-default Curr-file60 OOD-file120 OOD-file150 OOD-pcache0.20 Curr-pcache0.40 OOD-delay10 OOD-delay30

PPO-Agent

ED-Unicast

GCM

SACM

SACM+

SACM++

0.976 ± 0.002 0.976 ± 0.002 0.976 ± 0.002 0.975 ± 0.002 0.919 ± 0.002 1.038 ± 0.002 −0.002 ± 0.002 1.204 ± 0.002

0.845 ± 0.001 0.847 ± 0.001 0.846 ± 0.001 0.846 ± 0.001 0.846 ± 0.001 0.846 ± 0.001 0.019 ± 0.002 0.963 ± 0.001

0.733 ± 0.003 0.736 ± 0.003 0.736 ± 0.003 0.732 ± 0.003 0.833 ± 0.002 0.596 ± 0.003 −0.441 ± 0.003 1.137 ± 0.002

0.745 ± 0.003 0.748 ± 0.002 0.748 ± 0.003 0.746 ± 0.003 0.836 ± 0.002 0.613 ± 0.003 −0.427 ± 0.003 1.150 ± 0.002

0.731 ± 0.003 0.735 ± 0.002 0.737 ± 0.003 0.734 ± 0.002 0.831 ± 0.002 0.591 ± 0.003 −0.445 ± 0.003 1.144 ± 0.002

0.726 ± 0.003 0.726 ± 0.002 0.725 ± 0.003 0.725 ± 0.003 0.828 ± 0.002 0.580 ± 0.003 −0.451 ± 0.003 1.141 ± 0.002

TABLE XXIX Z IPF DEMAND , BROADCAST- PACKET EXPIRATION RATIO ρ (M ISS R ATIO , BROADCAST- LEVEL ; S EC . V-D) ACROSS ALL NON -ID REGIMES AND METHODS . B OLD = BEST. Regime

PPO-Agent

ED-Unicast

GCM

SACM

SACM+

SACM++

SACM++-Pop

ID-default OOD-alpha0.6 OOD-alpha1.0 OOD-alpha1.2 OOD-mandelbrot Curr-file60 OOD-file120 OOD-file150 OOD-pcache0.20 Curr-pcache0.40 OOD-delay10 OOD-delay30

0.351 ± 0.001 0.352 ± 0.001 0.350 ± 0.001 0.347 ± 0.001 0.350 ± 0.001 0.351 ± 0.001 0.351 ± 0.001 0.351 ± 0.001 0.265 ± 0.001 0.408 ± 0.001 0.552 ± 0.000 0.183 ± 0.001

0.133 ± 0.001 0.133 ± 0.001 0.133 ± 0.001 0.133 ± 0.001 0.134 ± 0.001 0.133 ± 0.001 0.132 ± 0.001 0.134 ± 0.001 0.134 ± 0.001 0.134 ± 0.001 0.495 ± 0.001 0.035 ± 0.000

0.343 ± 0.001 0.344 ± 0.001 0.342 ± 0.001 0.340 ± 0.001 0.342 ± 0.001 0.343 ± 0.001 0.344 ± 0.001 0.343 ± 0.001 0.261 ± 0.001 0.404 ± 0.001 0.555 ± 0.000 0.174 ± 0.001

0.343 ± 0.001 0.345 ± 0.001 0.343 ± 0.001 0.340 ± 0.001 0.343 ± 0.001 0.344 ± 0.001 0.345 ± 0.001 0.343 ± 0.001 0.261 ± 0.001 0.404 ± 0.001 0.553 ± 0.000 0.177 ± 0.001

0.346 ± 0.001 0.347 ± 0.001 0.345 ± 0.001 0.343 ± 0.001 0.345 ± 0.001 0.347 ± 0.001 0.347 ± 0.001 0.347 ± 0.001 0.263 ± 0.001 0.408 ± 0.001 0.555 ± 0.000 0.179 ± 0.001

0.351 ± 0.001 0.352 ± 0.001 0.350 ± 0.001 0.348 ± 0.001 0.351 ± 0.001 0.351 ± 0.001 0.352 ± 0.001 0.351 ± 0.001 0.266 ± 0.001 0.411 ± 0.001 0.555 ± 0.000 0.184 ± 0.001

0.348 ± 0.001 0.349 ± 0.001 0.348 ± 0.001 0.346 ± 0.001 0.348 ± 0.001 0.349 ± 0.001 0.349 ± 0.001 0.349 ± 0.001 0.267 ± 0.001 0.408 ± 0.001 0.555 ± 0.000 0.181 ± 0.001

TABLE XXX P ER -R EQUEST F EATURE V ECTOR (dREQ = 2K + 3 = 13 FOR T RACK A; 2K + 4 = 14 FOR T RACK B). F OR AN AGGREGATE ( POST- MERGE ) CODING - STATE RECORD , THE “TARGET CACHE ” FEATURE USES THE REPRESENTATIVE DESTINATION kmg (E Q . (6)), NOT THE DEMAND ORIGIN OF ANY CONSTITUENT ARRIVAL . Feature

Formula

Dim

Rationale

Target cache (one-hot)

ekr ∈ {0, 1}K

K

Destination identity

Cache-placement flags Normalized deadline Normalized packet-set size (aggregate size |fr |) Normalized degree

[⊮(c ∈ Sr )]K−1 c=0 dr /D min(|fr |, Umax )/Umax deg(r)/(Q − 1)

K 1 1 1

Side-info providers Urgency in [0, 1] Detects merged aggregates Merge opportunity count

min(m̂(fr ), mcap )/mcap

1

Demand-weighted importance

Track B additional feature Popularity mass norm

TABLE XXXI P ER -PAIR F EATURE V ECTOR (dPAIR = 8 FOR T RACK A; 11 FOR T RACK B) Feature

Formula

Rationale

Intersection norm Degree i norm Degree j norm Min deadline norm Packet-set size i (aggregate |fi |) Packet-set size j (aggregate |fj |) Queue index i norm Queue index j norm

|Si ∩ Sj |/K deg(ri )/(Q − 1) deg(rj )/(Q − 1) min(di , dj )/D min(|fi |, Umax )/Umax min(|fj |, Umax )/Umax i/(Q − 1) j/(Q − 1)

Future merge potential Request i’s alternatives Request j’s alternatives Pair’s combined urgency Aggregate size of ri Aggregate size of rj Position for GNN topology Position for GNN topology

Track B additional features Pop. mass i norm Pop. mass j norm Pop. mass union

min(m̂(fi ), mcap )/mcap min(m̂(fj ), mcap )/mcap min(m̂(fi ∪ fj ), mcap )/mcap

Demand weight of ri Demand weight of rj Combined demand weight

checkpoint that confirms (i) directly: across 20,000,000 onpolicy observations on ID-default the clip rate Pr[|fr | ≥ Umax ] is 7/2 · 107 ≈ 3.5 · 10−7 , with |fr |=1 accounting for 90.4% of observations; under the merge-heavy stress regime Curr-pcache0.40 the clip rate stays below 6 · 10−6 .

Saturation is therefore negligible on the distributions used to evaluate the deployed policy, so the observation aliasing has no measurable effect on the reported headline metrics. A controlled sensitivity sweep over Umax ∈ {6, 8, 12} at training time, and a richer aggregate summary that retains contained file identities, are left as future work. • m̂(fr ) — the popularity-mass estimate of fr under the as m̂(fr ) = P assumed Zipf distribution, computed −α p̂ , where p̂ ∝ (n + 1) is the Zipf rankn ϕ(p) p∈fr probability of file index n (α = 0.8 in the Track B base regime; ϕ(p) = ⌊p/B⌋ is the packet-to-file map of Eq. (7)). • mcap = Umax · p̂0 = 6 · p̂0 — the popularity-mass cap, set to the popularity mass of an aggregate of size Umax all carrying the most popular file (rank 0). Because |fr | is not hardcapped at Umax (see the Umax bullet above), the popularitymass features apply an explicit min(·, mcap ) clip in the numerator (matching the simulator’s pop_mass_norm routine, which returns min(m, mcap )/mcap ); this is what guarantees the [0, 1] bound on these feature dimensions. These constants are fixed at episode start and shared across all features. A PPENDIX G E MPIRICAL |fr | D ISTRIBUTION U NDER THE L EARNED P OLICY The observation feature min(|fr |, Umax )/Umax with Umax =6 aliases all aggregate-record sizes |fr | ≥ Umax to the same coordinate, and to verify that this aliasing is rare on the distributions used in the paper, we instrumented the environment to log the per-step |fr | of each queue record at observation time, and then re-evaluated the deployed selected

PREPRINT — SUBMITTED FOR PEER REVIEW

47

TABLE XXXII E MPIRICAL DISTRIBUTION OF THE AGGREGATE - RECORD SIZE |fr | OBSERVED BY THE DEPLOYED SELECTED CHECKPOINT ( TRAIN SEED 0) ON THE HOLDOUT SET (50 BASE SEEDS × 200 EPISODES PER SEED ). C OUNTS POOLED ACROSS ALL ( EVAL SEED , EPISODE , STEP, QUEUE POSITION ) OBSERVATION SAMPLES . ID- DEFAULT TOTALS 2·107 SAMPLES ; C URR - PCACHE 0.40 TOTALS 5·106 SAMPLES . |fr |

ID-default

1 2 3 4 5 6 7 Clip rate Pr[|fr | ≥ Umax ]

Curr-pcache0.40

count

%

count

%

18,081,174 1,675,662 227,575 15,098 484 7 0

90.41 8.38 1.14 0.075 0.002 4·10−5 0

4,554,171 357,151 76,910 11,122 616 29 1

91.08 7.14 1.54 0.222 0.012 5.8·10−4 2·10−5

3.5·10−7

6.0·10−6

checkpoint (seed 0) on the holdout set used throughout the paper (50 base seeds × 200 episodes per seed, H=50 steps per episode, queue length |Q|=10, i.e., totalling 5·106 observations per regime per seed and |Q|·H·episodes = 105 observations per (regime, holdout seed) pair). Table XXXII reports the pooled histogram of |fr | under two regimes, i.e., ID-default (the in-distribution evaluation regime) and Curr-pcache0.40 (a curriculum-stress regime with pcache =0.40 that produces the densest population of the mergeable pairs in Sec. VI–VIII, and is therefore the hardest test for chain depth). On both regimes the distribution is dominated by the singletons (|fr |=1 accounts for ≥ 90% of observations), while the depth–2 aggregates account for 7– 8%, and the clip rate Pr[|fr | ≥ Umax ] stays below 6 · 10−6 even on the stress regime. The maximum observed |fr | is 6 on ID-default and 7 on Curr-pcache0.40, and even on the stress regime fewer than 0.0006% of observations reach |fr |=6. The saturation is therefore negligible on the on-policy support, i.e., the observation aliasing has no measurable effect on the reported headline metrics, while the claim that “deep chains are rare on the on-policy support” from Appendix F is supported empirically on the deployed checkpoint. We do not retrain with a larger Umax in this version, considering that the clip rate is near zero on both regimes, and thereby such a sweep would not be expected to change the deployed-policy headline metrics materially. A more informative future-work direction is a richer aggregate-summary feature that retains the contained file identities (rather than only the size), since that would help the policy distinguish the aggregates with the same size but different side-information mass. A PPENDIX H C HAINED -M ERGE S TATE S UFFICIENCY This appendix formally establishes that the compressed aggregate state (kmg , fmg , Smg ) retained after a chained merge is a sufficient statistic for all the future feasibility and decodability decisions, while the proof relies on two structural constraints: (C1) the request-generation rule ensures fr ̸⊆ Ckr (i.e., a user never requests a packet it already caches), and

(C2) the XOR feasibility (2) requires each merge partner to cache the other’s packet set. A. One-Gap Invariant Proposition 1 (One-Gap Invariant). Let rmg be a codingstate record produced by any sequence of n ≥ 1 chained pairwise merges, each satisfying XOR feasibility (2) and the request-generation constraint (C1). Let p⋆ denote the original singleton packet of whichever initial request contributed the current representative destination kmg . Then fmg \ {p⋆ } ⊆ Ckmg ,

p⋆ ∈ / Ckmg .

(39)

That is, kmg caches every packet in fmg except exactly one: its own originally requested packet p⋆ . Proof: We proceed by induction on the number of merges n. Base case (n = 1). Two fresh requests ri = (ki , {pi }, di , Si ) and rj = (kj , {pj }, dj , Sj ) are merged. XOR feasibility requires {pi } ⊆ Ckj and {pj } ⊆ Cki , so each user caches the other’s packet. Constraint (C1) gives pi ∈ / Cki and pj ∈ / Ckj . Now kmg ∈ {ki , kj } is drawn uniformly. Case kmg = ki : fmg = {pi , pj }; pj ∈ Cki (feasibility) and pi ∈ / Cki (C1). Set p⋆ = pi ; then (39) holds. Case kmg = kj : By symmetry, p⋆ = pj and (39) holds. Inductive step. The simulator’s feasible-pair set Mt = {(i, j) : fi ⊆ Ckj , fj ⊆ Cki } is defined over arbitrary queue entries, so a feasible partner of an aggregate may itself be either a fresh singleton or another coding-state record. We therefore prove the inductive step in the more general case where both partners satisfy (39); the singleton case is recovered by specializing |f | = 1. Assume that after some sequence of merges, queue records ra and rb each satisfy the one-gap invariant: ra has representative destination ka and gap packet p⋆a (so fa \ {p⋆a } ⊆ Cka and p⋆a ∈ / Cka ); rb has representative destination kb and gap packet p⋆b . (A fresh singleton is the special case f = {p⋆ }.) ′ ′ ∈ {ka , kb }. = fa ∪fb with kmg Merging (ra , rb ) produces fmg XOR feasibility requires (F1) fa ⊆ Ckb and (F2) fb ⊆ Cka . ′ Case kmg = ka : By the inductive hypothesis at ra , ⋆ fa \ {pa } ⊆ Cka and p⋆a ∈ / Cka . By (F2), fb ⊆ Cka . The candidate gap p⋆a cannot lie in fb : if it did, then p⋆a ∈ fb ⊆ Cka , contradicting the hypothesis. Hence fa ∪ fb contains p⋆a , and ′ fmg \ {p⋆a } = (fa \ {p⋆a }) ∪ fb ⊆ Cka ,

while p⋆a ∈ / Cka . So (39) holds with p⋆ = p⋆a . ′ Case kmg = kb : By symmetry (swap a ↔ b), (39) holds ⋆ with p = p⋆b . The original two specializations are recovered as: (a) both partners fresh singletons (n = 1 base case), (b) one aggregate and one singleton (rb a fresh request with fb = {p⋆b }), recovering the wording of the previous draft. B. State Sufficiency Theorem Theorem 1 (Aggregate State Sufficiency). The triple (kmg , fmg , Smg ) is a sufficient statistic for all future mergefeasibility and decodability decisions involving rmg . That is,

PREPRINT — SUBMITTED FOR PEER REVIEW

for any feasible queue partner rz = (kz , fz , dz , Sz ), fresh singleton or coding-state record, with its own one-gap invariant (Proposition 1) and gap packet p⋆z (reducing to p⋆z = pz when fz is a singleton): 1) Feasibility: The XOR feasibility condition (2) for the pair (rmg , rz ) depends only on fmg , kmg , fz , kz , and the cache contents Ckz , Ckmg ; none of these requires knowledge of previously merged users’ destinations. 2) Decodability of kmg : By Proposition 1, kmg caches every packet in fmg except p⋆ ; combined with fz ⊆ Ckmg (feasibility), kmg can cancel all known packets from L X ′ = p∈fmg ∪fz p to recover p⋆ . 3) Decodability of kz : By Proposition 1 applied to rz , kz caches fz \{p⋆z } and p⋆z ∈ / Ckz . Feasibility requires fmg ⊆ Ckz , and p⋆z ∈ / fmg (otherwise p⋆z ∈ Ckz , contradicting the hypothesis). Hence (fmg ∪ fz ) \ {p⋆z } ⊆ Ckz , so kz can cancel everything except p⋆z from X ′ and recover p⋆z . The singleton case (fz = {pz }, p⋆z = pz ) is recovered by specialization. T 4) Side-information evolution: Smg = ℓ Sℓ over all predecessor requests ℓ; this is the exact set of caches holding every packet in fmg . Future feasibility requires only kz ∈ Smg (direction 1) and kmg ∈ Sz (direction 2), both computable from the aggregate state alone. Previously merged users (those whose requests were folded into rmg in earlier merges) need not be tracked: they were served at their respective merge steps, and correctness of future merges depends only on the representative kmg . Proof: Items 1, 3, and 4 follow directly from the definitions of fmg , Smg , and the feasibility condition (2): no reference to previously merged users appears in any of these expressions. Item 2 is a direct corollary of Proposition 1: the one-gap structure guarantees that kmg possesses |fmg | − 1 packets of fmg and all of fz (by feasibility), leaving exactly one unknown (p⋆ ) in the XOR sum, which kmg recovers. Remark 7 (Scope of decodability in chained merges). Proposition 1 guarantees that the two active participants of each chained merge (i.e., kmg and kz ) always decode the broadcast, while the users that are served by earlier links in the chain are not guaranteed to decode the subsequent broadcasts, i.e., a previously served user kprev may lack packets that are introduced in later merge steps. This is benign because each such user was already served at its own merge step, while the coding-state record exists solely to enable the future merges, not to re-serve the past users. A PPENDIX I C ODED T RANSMISSION R EMARKS The following remarks supplement the coded transmission model in Section III-C. Remark 8 (Chained merges and pairwise scope). Each link in a merge chain corresponds to a separate channel use, while the XOR feasibility condition (2) is re-evaluated at every step using the updated packet union fmg and the side-information set Smg = Si ∩ Sj defined in Eq. (5). Because the intersection can only weakly shrink each component admissible set

48

(Smg ⊆ Si and Smg ⊆ Sj ) while the next merge partner must hold the entire growing packet union fmg rather than only the original subfile, each successive link typically reduces the future feasibility. The reduction is strict when the new merge partner contributes at least one packet identity not already in fmg , i.e., when |fmg | strictly grows, while the chained partners that contribute no novel packet identities (i.e., the non-gap-overlap case discussed in Sec. III-C) leave the next feasibility check no harder than the previous one. In this work we therefore restrict to the pairwise feasible merges at each step, even though higher-order simultaneous multi-way merges (i.e., forming a single coded packet covering three or more users in one feasibility check) are not modelled and are identified as a future extension (Section IX). Remark 9 (Per-broadcast accounting is a packet-set count). Each link in a merge chain corresponds to a distinct channel use (i.e., one broadcast slot). The metric Ut = |fmg | is defined throughout this paper as a packet-set cardinality, i.e., the number of distinct packet identities carried in fmg at the moment of the broadcast. The request generator samples each fresh request’s packet ID independently from the library, so two active queue records may in principle carry the same packet identity. XOR feasibility (2) together with the no-self-cache constraint (C1) does not exclude all such overlaps: it only excludes the case where one record’s gap packet p⋆a coincides / Cka and the feasibilwith the other record’s gap p⋆b , since p⋆a ∈ ity condition fa ⊆ Ckb together force p⋆a ∈ Ckb , leaving the gap structures of the two records distinct. Non-gap packet overlaps are compatible with feasibility. As a counterexample template (displayed in the local shorthand (fr , kr , gap p⋆r ) that omits the deadline dr and side-information set Sr of the canonical record r = (kr , fr , dr , Sr ) since they are irrelevant to the packet-overlap argument), take ra = ({p2 , p3 }, ka , gap p3 ) and rb = ({p2 , p5 }, kb , gap p5 ) with p2 ∈ Cka ∩Ckb , p3 ∈ Ckb \ Cka , p5 ∈ Cka \ Ckb : feasibility holds, both one-gap invariants hold, and the merge produces fmg = {p2 , p3 , p5 } even though three original singleton arrivals (the two each record was built from, plus the partner just merged in) contributed to the chain. We therefore avoid claiming that Ut = |fmg | counts the original singleton arrivals, while the readers who want strict original-arrival semantics should use the request-level metrics ηreq , mreq , σreq (Sec. III-C0f), which are computed from the per-arrival identifier sets A(r) stamped at arrival time, thereby crediting each original arrival exactly once. By Proposition 1, the two active participants (i.e., kmg and the new partner kz ) always decode correctly, while each link in the chain is a distinct channel use, so summing Ut over t counts the total broadcast-slot XOR degree (i.e., a packet-set quantity) rather than redundant P data delivery. The broadcast-efficiency score σ = H −1 t (Ut − λEt ) should be read accordingly as a perslot packet-throughput-vs-channel-waste composite, not as an original-arrival completion score. Remark 10 (Keep-side parameter and queue evolution). The keep-side parameter κ is a design choice that goes beyond selecting which pair to merge. Considering that dmg = min(di , dj ) and Smg = Si ∩ Sj are fully determined by the merge rule, κ cannot change the aggregate’s deadline

PREPRINT — SUBMITTED FOR PEER REVIEW

or side-information set. Its role is exclusively to govern the queue evolution, i.e., κ decides which queue slot is vacated and replenished by a fresh arrival rnew . The representative destination kmg is a logically separate quantity, drawn uniformly from {ki , kj } independently of κ, i.e., the kept slot does not determine the representative, while the representative does not determine the kept slot. This decoupling gives the agent indirect control over the queue’s future composition and mergeability, while not entangling that control with the onegap invariant of Proposition 1, which depends only on the realized kmg . After the literature sweep summarized in Sec. II, we are not aware of any prior RL formulation for the coded caching that includes this control dimension, i.e., this is a positioning statement, not a definitive non-existence result. A PPENDIX J R EWARD AND M ASKING D ETAILS a) Reward weight selection.: The base reward uses equal weights (wserved =1, wexp =1) so that the per-step reward Rbase = Ut − Et directly mirrorsPthe evaluation-level broadcast-efficiency score σ = H −1 t (Ut − λEt ) with λ=1. The quality bonus weights (winter =0.75, wunion =0.15) and the potential-shaping weight (wΦ =0.20) were tuned on the validation split, considering the trade-off between the throughput and the deadline-compliance signals. b) Potential-based shaping.: Remark 11. The potential-based reward shaping is inspired by the policy-invariance theorem of [18], which holds exactly for an idealized fully observed continuing-state MDP. The implemented training setup is the contextual-POMDP surrogate of Definition 1 (i.e., truncated at H=50, hidden episode cache placement, aliased aggregate observations, no time-togo feature), so the theorem does not apply directly, i.e., we make no formal claim that the optimal policy under Rtotal is identical to the optimal policy under Rbase + Rquality in the implemented setup. A formal invariance result for the implemented environment would require establishing the exact-reset terminal conditions, a time-to-go feature, and an observation exposing the hidden episode context and the packet identities, while we leave such a formalization to future work. In the present paper, Rshape is treated as a heuristic credit-assignment shaping that empirically encourages the agent to transition toward the queue states with higher merge potential (i.e., a proxy for the future coding opportunities), while the empirical effect is quantified by the reward-component ablation in Sec. VIII, thereby accelerating the credit assignment in the early stages of training, where the shaped reward bridge is most useful. c) Action masking gradient bias.: Remark 12. Huang and Ontañón [13] prove that the masking procedure described in Section III-F6 introduces no bias in the gradient direction, i.e., the policy-gradient estimator remains unbiased over the feasible action sub-space. In our environment, as few as 1 (i.e., unicast only) and as many as 91 actions may be valid at a given step, depending on the queue state. Without the masking, a uniform random policy would waste approximately |A| − |Mt | − 1 actions at every

49

step on the infeasible choices, thereby substantially degrading the sample efficiency.

A PPENDIX K P OLICY A RCHITECTURE AND T RAINING D ETAILS a) Stage 1: Graph-pair encoder, full equations.: The NodeMLP lifts each per-request vector to a 128-dimensional embedding: h(0) r = ReLU(W2 ReLU(W1 xr + b1 ) + b2 ) , W1 ∈ R256×dreq , W2 ∈ R128×256 .

(40)

Two successive GraphAttentionBlocks [15] with four attention heads and dmodel = 128 then propagate the information between the requests that share a feasible merge edge, thereby (1) (2) yielding the contextual node embeddings hr and hr . The dropout is set to zero to preserve the determinism at inference. The per-step inference cost of the graph-attention encoder is O(|Mt | · dmodel ) for the message passing (i.e., bounded by Pmax · dmodel = 45 × 128) plus O(Q · dmodel ) for the node update, while the forward pass is therefore inexpensive relative to the combinatorial search it replaces. The EdgeNet forms the embedding for each candidate merge pair (i, j, keep-side) by concatenating the two node embeddings, their element-wise product, the absolute difference, and the base pair features (i.e., the first dpair −2 entries of pij ; the last two entries encode normalized queue indices and are used only to construct the merge-graph adjacency, not as EdgeNet inputs):  (2) (2) (2) (2) hj hi ⊙ hj eij = MLP hi  (2) (2) |hi − hj | pbase ∈ R64 , ij

(41)

where pbase ∈ Rdpair −2 is the base pair-feature subvector and ij the MLP maps (4 × 128 + dpair − 2) → 256 → 64, i.e., input width 4·128 + 6 = 518 for Track A (dpair = 8) and 4·128 + 9 = 521 for Track B (dpair = 11). b) Track B parameter differences.: The Track B (Zipf) agent uses dreq =14 and dpair =11, thereby changing the Node MLP input layer to 14 → 256 → 128 and the Edge MLP input layer to (4×128+9) = 521 → 256 → 64, while yielding ≈1.75M total parameters (i.e., matching Sec. IV-A, Table IV, and the architecture summary at the start of Sec. V). All other architectural choices (i.e., attention heads, hidden dimensions, critic structure) are identical. c) ExIt self-improving teacher.: Unlike the Phase 1 teacher, which is fixed and bootstraps from the SACM++ rollouts alone, the ExIt teacher uses the agent’s own critic V̂θ for bootstrapping. As the critic improves through the PPO training, the planner’s labels improve correspondingly, i.e., the student improves the teacher’s value estimates, which in turn produce better labels for the student, thereby letting the agent exceed its heuristic teachers rather than just match them. d) Full hyperparameters.:

PREPRINT — SUBMITTED FOR PEER REVIEW

50

TABLE XXXIII V ERIFIED H YPERPARAMETER S UMMARY Phase

Hyperparameter

BC (Phase 1)

Samples (NBC ) Training epochs Minibatch size Learning rate (ηBC ) Teacher rollout depth (d) Teacher MC samples (M ) Teacher top-K pairs

Warm-up (Phase 2)

Steps (frozen head)

PPO (Phase 3)

Parallel environments Steps per rollout (nsteps ) Minibatch size Epochs per update Learning rate (start → end) Clip range (ε) Target KL divergence Entropy coeff. (start → end) Discount factor (γ) GAE parameter (λ) Value function coefficient Phase-3 env steps per seed Total RL env steps per seed (incl. Phase-2 warm-up)

ExIt (Phase 3)

Start-step threshold Interval threshold Realized schedule (first fire / cadence / total fires) States collected per iteration DAgger buffer capacity Distillation epochs Distillation batch size Distillation learning rate Expert roll-in probability Planner lookahead depth Planner MC samples Planner top-K pairs

TABLE XXXV PPO-AGENT VS . ORACLE - TUNED TAU F IT (τ ⋆ ) EVALUATED ON HOLDOUT ⋆ SEEDS . τ SELECTED ON VALIDATION SET PER METRIC . Value 150,000 6 2,048 3 × 10−4 4 4 16 50,000 32 256 1,024 10 5 × 10−4 → 1 × 10−4 0.20 0.03 0.010 → 0.001 0.995 0.95 0.5 6,000,000 6,050,000

300,000 300,000 500K / ≈300K avg. / 20 fires over 24 chunks 8,192 80,000 2 2,048 1 × 10−4 0.20 5 3 12

TABLE XXXIV TAU F IT PERFORMANCE AS A FUNCTION OF CLIQUE - SIZE THRESHOLD τ . PPO-AGENT SHOWN FOR REFERENCE . B OLD = BEST PER COLUMN ( NUMERICAL WINNER ACROSS BOTH TAU F IT ROWS AND PPO); THE PPO ROW LABEL IS BOLDED ONLY TO MARK IT AS THE LEARNED REFERENCE , NOT AS A PER - CELL WIN INDICATOR . τ

BE-Score σ (↑)

Miss Ratio (↓)

Served/Tx (↑)

Coding Gain (↑)

Exp/Episode (↓)

0 1 2 3

0.877 ± 0.002 0.908 ± 0.002 0.915 ± 0.002 0.915 ± 0.003

0.185 ± 0.001 0.245 ± 0.001 0.258 ± 0.001 0.259 ± 0.001

1.135 ± 0.001 1.343 ± 0.001 1.405 ± 0.002 1.408 ± 0.002

2.063 ± 0.002 2.097 ± 0.001 2.077 ± 0.001 2.066 ± 0.001

10.55 ± 0.07 14.92 ± 0.10 16.22 ± 0.09 16.32 ± 0.09

PPO

0.976 ± 0.002

0.208 ± 0.001

1.323 ± 0.002

2.162 ± 0.002

14.17 ± 0.07

A PPENDIX L O RACLE -T UNED T HRESHOLD A NALYSIS The τ -Fit family gives a one-parameter handle on the throughput–reliability tradeoff, while Table XXXIV shows the full sweep over τ ∈ {0, 1, 2, 3} alongside the PPO. Increasing τ from 0 to 2 raises the broadcast-efficiency score monotonically (0.877 → 0.915), and then it saturates, i.e., the difference between τ =2 and τ =3 in BE-score is 0.000, within the statistical noise, even though PPO’s score of 0.976 lies well above this saturation plateau. To confirm that PPO’s advantage does not come from a suboptimal τ selection, we evaluated each TauFit policy with an oracle-tuned threshold τ ⋆ , i.e., for each of six target metrics, τ ⋆ is chosen retrospectively on the validation seeds to maximize that metric, and then evaluated on the holdout seeds. Table XXXV shows that PPO’s BE-score advantage persists across all choices of the tuning criterion, i.e., +6.61% when τ ⋆ is tuned for the BE-score itself, and up to +11.25% when τ ⋆ is tuned for the miss ratio or the expirations. The τ Fit ceiling under any oracle access is therefore strictly below PPO’s performance. Table XXXVI complements the BE-score analysis above by comparing the PPO against TauFit(τ ⋆ ) on the metric

Tuned-On Metric

τ⋆

PPO σ

TauFit σ

PPO Adv.

BE-score Served/Tx Reward/step (shaped) Avg coding gain Miss ratio Expirations/episode

2 3 3 1 0 0

0.976 ± 0.002 0.976 ± 0.002 0.976 ± 0.002 0.976 ± 0.002 0.976 ± 0.002 0.976 ± 0.002

0.915 ± 0.002 0.915 ± 0.002 0.915 ± 0.002 0.908 ± 0.002 0.877 ± 0.002 0.877 ± 0.002

+6.61% +6.65% +6.65% +7.50% +11.25% +11.25%

TABLE XXXVI P ER - METRIC COMPARISON : PPO-AGENT VS . ORACLE - TUNED TAU F IT (τ ⋆ ) EVALUATED ON THE METRIC EACH τ ⋆ WAS TUNED FOR . B OLD = BETTER ; ARROWS INDICATE METRIC DIRECTION . Metric

τ⋆

PPO

TauFit(τ ⋆ )

∆

Favors

BE-Score (↑) Coding Gain (↑) Served/Tx (↑) Miss Ratio (↓) Exp/Episode (↓)

2 1 3 0 0

0.976 ± 0.002 2.162 ± 0.002 1.323 ± 0.002 0.208 ± 0.001 14.17 ± 0.07

0.915 ± 0.002 2.097 ± 0.001 1.408 ± 0.002 0.185 ± 0.001 10.55 ± 0.07

+0.061 +0.065 −0.085 +0.023 +3.62

PPO PPO TauFit TauFit TauFit

each τ ⋆ was tuned for. The PPO wins on the composite metric (i.e., the broadcast-efficiency score) and the coding gain, while TauFit(τ ⋆ =0) achieves lower miss ratio and fewer expirations, and TauFit(τ ⋆ =3) yields higher packet-set count per transmission (µ). The interesting fact we observed is that this pattern is what one would expect, i.e., the PPO optimizes the joint reward objective, thereby trading small losses on individual narrow metrics for larger gains on the composite broadcast-efficiency score, even though no single τ -Fit threshold reproduces this multi-objective balance. A PPENDIX M E XPERIMENTAL P ROTOCOL D ETAILS a) τ -Fit misfit metric.: The τ -Fit family is based on the pairwise misfit metric of Niesen and Maddah-Ali [5], written as m(ri , rj ) throughout this paper to avoid the collision with the broadcast-level expiration ratio ρ (M1), i.e., m(ri , rj ) = Si \ (Sj ∪ {kj }) + Sj \ (Si ∪ {ki }) .

(42)

The sequential τ -fit rule sorts the queue by deadline, and then for the earliest-deadline request it scans all queue members in deadline order and merges with the first candidate whose misfit satisfies m ≤ τ (i.e., degree-aware endpoint selection), while if no such pair exists, the request is unicast. The oracle-optimal thresholds per metric are: τ ∗ = 2 for BE-score, τ ∗ = 3 for served-per-tx and reward-per-step, τ ∗ = 0 for miss-ratio and expirations, and τ ∗ = 1 for coding gain. b) Track B conditions.: The Track B agent is trained on Zipf(α=0.8) file-request demand. File requests follow a Zipf or Mandelbrot-Zipf distribution. With zero-indexed file IDs n ∈ {0, . . . , N − 1} as used throughout this paper, and consistent with the popularity-mass projection p̂n ∝ (n+1)−α in Appendix F, ( (n + 1)−α (Zipf) P (F = n) ∝ (43) (n + q + 1)−α (Mandelbrot-Zipf),

PREPRINT — SUBMITTED FOR PEER REVIEW

51

where n + 1 is the rank (so the most popular file at rank 1 corresponds to index n = 0). The earlier rank-f form f −α / (f + q)−α assumes one-indexed ranks f ∈ {1, . . . , N }; the two forms are equivalent under the substitution f = n + 1. The 12 Track B conditions (1 ID + 2 Curr + 9 OOD) are: • Zipf ID-reference: α = 0.8 (moderate tail, same system parameters as ID-default). • Tail weight: α ∈ {0.6, 1.0, 1.2}. Higher α concentrates the request distribution on fewer file indices; because cache placement is uniform-without-replacement with fraction pc and thus popularity-blind, the effect on the statistics of feasible merge opportunities is indirect and demand-mediated. • Alternative law: Mandelbrot-Zipf with α = 1.4, q = 2.0. • Cross-axis shifts: same catalog, cache density, and deadline variations as Track A (N ∈ {60, 120, 150}, pc ∈ {0.20, 0.40}, D ∈ {10, 30}) applied to the Zipf-0.8 base. The two observation spaces are incompatible; each agent can only be evaluated on its own environment version. c) Sensitivity to λ.: The composite score uses a fixed λ=1, thereby weighting the expired packet-set mass equally against the packet-set XOR degree Ut . Applications that value the reliability more highly would set λ > 1, thereby narrowing the gap to ED-Unicast, while λ < 1 would favor the throughput-maximizing policies. Appendix O presents a formal sensitivity sweep over λ ∈ {0.5, 1, 2, 3}, while the PPO retains rank 1 among all coded-multicast methods for every λ ≥ 1, i.e., the only policies that surpass the PPO at high λ are the low-merge baselines (i.e., ED-Unicast at 0% and TauFit-0 at 13.3% merge rate; Sec. V-B). d) Reward per step (M13).: Mean shaped reward accumulated per transmission step: H

R̄ =

1 X R(st , at ). H t=1

(44)

Considering that R includes the potential-based shaping and the component-specific weights (Section III-F5), this metric is not directly comparable across reward definitions (i.e., when the shaping or its weights themselves change), while within a single ablation table that holds the reward definition and weights fixed (including the ID-default ablation table of Sec. VIII), Reward/Step is a directly comparable diagnostic across the rows. It is reported as a training-signal diagnostic rather than a target metric, while all the performance comparisons use the communications metrics M1–M5. e) Statistical reporting protocol.: Considering that all methods share the same holdout seeds (i.e., paired design), every comparison is computed on the per-seed paired differences, thereby eliminating the inter-seed variance and yielding tighter uncertainty estimates than the independent evaluation would allow. For the per-method summary tables we report mean ± 95% CI across√the seed-level means (i.e., normal approximation ±1.96 σ̂/ 50). These intervals are descriptive uncertainty bands, not hypothesis tests, i.e., non-overlapping CIs do not imply a statistically significant difference [32]. For the main pairwise comparisons we additionally report the 95% percentile bootstrap confidence interval of the paired BE-score difference: for each of 10 000 resamples we draw 50 seed

indices with replacement, compute the mean paired difference ¯ = σ̄PPO − σ̄baseline , and take the 2.5th–97.5th percentile ∆σ interval. A PPENDIX N R EPRODUCIBILITY AND C OMPUTATIONAL C OST The implementation uses Python 3.13.2, PyTorch 2.0+, Stable-Baselines3 v2.1+ [30], and SB3-Contrib MaskablePPO [29]. All the random number generators are seeded deterministically, while the evaluation uses the argmax (i.e., not sampled) action selection. The complete hyperparameters are listed in Table XXXIII. Artifacts. The full source code (environment, training scripts, evaluation scripts, and configuration dataclasses) will be released in a public repository upon acceptance.2 All training configurations are specified in dedicated configuration files; evaluation uses a separate configuration. Training seeds: {0, 1, 2, 3}; validation seeds: {0, . . . , 49}; holdout seeds: {50, . . . , 99}. Episode seeding. Episode seeds follow the deterministic formula seed = 42 + s · 106 + e (s ∈ {50, . . . , 99}, e ∈ {0, . . . , 199}), and inference is deterministic (argmax decoding). Hardware. All the experiments were conducted on a single laptop equipped with an NVIDIA GeForce RTX 3080 Ti (i.e., Laptop GPU). The training required approximately 59 hours on a single GPU for the uniform track, while the evaluation requires approximately 2 hours per method per condition. The per-step policy inference (i.e., a single forward pass of the graph-structured policy network on one observation) takes approximately ∼3.5 ms on the RTX 3080 Ti GPU and ∼3.3 ms on the CPU (i.e., batch size 1, no compilation; the detailed benchmark in Appendix T), while these numbers are reported as a conditional feasibility indicator for the K=5, Q=10 setting on both GPU-equipped and CPU-only edge nodes, even though whether they meet a real-time scheduling target depends on the deployment’s slot-duration budget, which is not imported from outside the manuscript. The per-seed wallclock times are reported in Table XXXVII. Table regeneration. Every numerical table in this paper can be reproduced from the released evaluation scripts and saved model checkpoints by running the corresponding evaluation scripts followed by the aggregation scripts. A PPENDIX O B ROADCAST-E FFICIENCY S CORE S ENSITIVITY TO λ The composite broadcast-efficiency score (29) uses a fixed λ=1. To verify that PPO’s ranking advantage isPnot an artifact of this choice, we recomputed σ(λ) = H −1 t (Ut − λEt ) for λ ∈ {0.5, 1, 2, 3} from the same raw holdout data (i.e., 50 seeds × 200 episodes) without rerunning any experiment, while Table XXXVIII reports the results for five representative methods spanning the conservative–aggressive spectrum. 2 Repository link withheld during peer review; the exact commit hash will be provided in the camera-ready version.

PREPRINT — SUBMITTED FOR PEER REVIEW

52

TABLE XXXVII C OMPUTATIONAL COST. E ACH TRACK USES AN INDEPENDENTLY TRAINED AGENT. T RAINING IS SEQUENTIAL ACROSS 4 SEEDS ON A SINGLE MACHINE . E VALUATION USES 50 HOLDOUT SEEDS × 200 EPISODES PER REGIME . Metric Model parameters Training wall-clock (per seed) Training wall-clock (4 seeds) BC warm start samples Phase-3 env steps per seed Total env steps per seed (incl. Ph.-2) Parallel environments Evaluation (1 regime) Per-step inference (GPU) Per-step inference (CPU) Total end-to-end

Uniform

Zipf

∼1.73M 13.5–14.6 h ∼59 h 150,000 6,000,000 6,050,000 32 ∼2 h ∼3.5 ms ∼3.3 ms ∼61 h

∼1.75M 12.7–13.5 h ∼53 h 150,000 6,000,000 6,050,000 32 ∼2 h ∼3.5 ms ∼3.3 ms ∼55 h

TABLE XXXVIII BE- SCORE SENSITIVITY TO λ. ID- DEFAULT, 50 HOLDOUT SEEDS × 200 EPISODES . M EAN ± 95% CI. B OLD = RANK 1 OVERALL . “PPO CODED RANK ” = PPO’ S RANK AMONG THE FOUR CODED - MULTICAST METHODS (GCM, SACM, SACM+, SACM++); THE THRESHOLD - FAMILY POLICIES (TAU F IT-0/1/3, F IRST-F IT, P ERFECT-F IT ) ARE REPORTED IN FULL IN TABLE XXXIV AND ARE OMITTED FROM THE TABLE BELOW TO SAVE SPACE , WITH ONLY TAU F IT-2 RETAINED AS A REPRESENTATIVE THRESHOLD POLICY. T HE λ=1 ENTRY MATCHES THE HEADLINE AGGREGATE σ=0.976 OF S EC . VI-A BY CONSTRUCTION ( POST- HOC RECOMPUTATION OF THE SAME HOLDOUT TRAJECTORIES ). Method

λ=0.5

λ=1

λ=2

λ=3

PPO-Agent SACM++ TauFit-2 ED-Unicast SACM

1.149 ± 0.002 1.158 ± 0.001 1.160 ± 0.001 0.923 ± 0.001 1.160 ± 0.001

0.976 ± 0.002 0.726 ± 0.003 0.915 ± 0.002 0.845 ± 0.001 0.745 ± 0.003

0.609 ± 0.004 −0.139 ± 0.008 0.426 ± 0.005 0.690 ± 0.003 −0.085 ± 0.007

0.249 ± 0.006 −1.004 ± 0.012 −0.063 ± 0.008 0.535 ± 0.004 −0.916 ± 0.011

7 4

1 1

4 1

4 1

PPO rank (all 12) PPO coded rank

Three regimes emerge. (i) Low penalty (λ=0.5): The expirations barely count, so the aggressive 100%-merge baselines (i.e., SACM, SACM++, TauFit-2/3) dominate on the raw throughput, while PPO’s selective merging (31.8%) sacrifices the throughput for the deadline safety that is undervalued at this λ, i.e., its overall rank drops to 7. (ii) Balanced penalty (λ=1): The PPO achieves rank 1 overall, i.e., its selective strategy gives the best throughput–reliability balance at this operating point. (iii) High penalty (λ ≥ 2): The expiration penalty dominates, while the most conservative methods, i.e., ED-Unicast (0% merge rate) and Perfect-Fit/TauFit-0 (13.3%), rise to rank 1–3. All aggressive-merge baselines (i.e., SACM, SACM++, GCM) go deeply negative. The PPO remains rank 4 overall, even though it is rank 1 among all coded-multicast methods for every λ ≥ 1, i.e., the only policies that surpass the PPO at high λ are the low-merge baselines (i.e., ED-Unicast at 0% merge rate, and TauFit-0 at 13.3% merge rate). The interesting fact we observed is that PPO’s ranking advantage over the coded-multicast baselines holds across the operationally relevant range λ ≥ 1, while the λ<1 regime, where the deadlines are deprioritized relative to the throughput, favors the aggressive merging by design, even though this regime contradicts the paper’s motivating use case of the deadline-constrained delivery.

TABLE XXXIX R EQUEST SELECTION SCORE σreq SENSITIVITY TO λ. ID- DEFAULT, 50 HOLDOUT SEEDS × 200 EPISODES . M EAN ± 95% CI. B OLD = BEST AMONG THE THREE METHODS SHOWN . PPO-AGENT OVERTAKES SACM++ BETWEEN λ=2 AND λ=3 ( CROSSOVER AT λ≈2.24). Method

λ=1

λ=2

λ=3

λ=5

PPO-Agent SACM++ ED-Unicast

0.839 ± 0.001 0.959 ± 0.002 0.845 ± 0.001

0.610 ± 0.002 0.633 ± 0.003 0.690 ± 0.003

0.381 ± 0.004 0.306 ± 0.004 0.535 ± 0.004

−0.077 ± 0.006 −0.347 ± 0.007 0.226 ± 0.006

TABLE XL C ROSSOVER λ: SMALLEST λ AT WHICH PPO-AGENT σreq ≥ SACM++ σreq ( MEAN OVER 50 SEEDS ). Regime OOD-pcache0.20 OOD-delay30 OOD-file120 ID-default Curr-file60 OOD-file150 Curr-pcache0.40 OOD-delay10

Crossover λ 1.19 2.04 2.22 2.24 2.25 2.27 3.60 4.92

A PPENDIX P R EQUEST-L EVEL S ELECTION S CORE S ENSITIVITY TO λ

P The request selection score (36), σreq (λ) = H −1 t (|Ct |− λ|Mt |), depends on how heavily the deadline misses are penalized. We swept λ ∈ {0.5, 1, 1.5, 2, 2.5, 3, 4, 5, 7, 10} using the same 50-seed holdout data without rerunning any experiment, while Table XXXIX reports σreq at four selected λ values for the ID-default regime. Table XL reports the crossover λ, the smallest value at which PPO-Agent’s mean σreq equals or exceeds SACM++’s, across all eight evaluation regimes. Three regimes emerge, mirroring the broadcast-efficiency analysis (Section O). (i) Low penalty (λ<2): SACM++’s higher request throughput ηreq dominates, i.e., its alwaysmerge strategy delivers more coded packets per step. (ii) Moderate penalty (λ≈2–3): PPO-Agent’s ∼30% lower request miss rate becomes decisive, i.e., at λ=2.5, the PPO wins in six of eight regimes (all except Curr-pcache0.40 and OODdelay10), while at λ=3, the PPO achieves 100% seed-level win-rate in those six. (iii) High penalty (λ≥5): PPO-Agent wins in all eight regimes with 100% seed-level win-rate, while the two regimes with the highest crossover λ, i.e., Curr-pcache0.40 (λ=3.60) and OOD-delay10 (λ=4.92), are the extreme-stress conditions where SACM++’s throughput advantage is largest. For the delay-sensitive applications (i.e., the paper’s motivating use case), the deadline misses should carry a substantial penalty, while under the operationally reasonable λ ≥ 2, PPOAgent’s selective merge strategy produces higher request-level selection scores in the majority of regimes, and under λ ≥ 5 it wins in all the eight regimes.

PREPRINT — SUBMITTED FOR PEER REVIEW

53

TABLE XLI R EQUEST SELECTION SCORE σreq SENSITIVITY TO λ (Z IPF DEMAND , α=0.8). ID- DEFAULT, 50 HOLDOUT SEEDS × 200 EPISODES . M EAN ± 95% CI. B OLD = BEST. PPO-AGENT LEADS AT EVERY λ. Method PPO-Agent SACM++ SACM++-Pop

λ=1 0.978 ± 0.002 0.955 ± 0.002 0.939 ± 0.002

λ=3 0.354 ± 0.004 0.302 ± 0.005 0.272 ± 0.005

λ=5 −0.269 ± 0.007 −0.351 ± 0.008 −0.395 ± 0.008

A PPENDIX Q Z IPF R EQUEST-L EVEL S ELECTION S CORE S ENSITIVITY TO λ Under the Zipf demand, the PPO-Agent dominates SACM++ on the request selection score σreq at every tested penalty weight, even though for the uniform track a crossover at λ≈2.24 was required (Appendix P). Table XLI reports σreq at three selected λ values for the Zipf ID-default regime. PPO-Agent’s mean σreq exceeds SACM++’s at every tested λ ∈ {0.5, 1, 1.5, 2, 2.5, 3, 4, 5, 7, 10} in all the 12 Zipf regimes, while the seed-level win-rates are 98–100% in 10 of 12 regimes at λ=1. The two exceptions, i.e., OOD-pcache0.20 (58% win-rate, margin +0.001) and OOD-delay30 (90% winrate, margin +0.008), are the regimes where all the codedmulticast methods converge to near-identical performance, thereby leaving little room for the policy differentiation. The structural explanation is that the Zipf agent’s near-full merging strategy (i.e., 99.7% merge rate) matches or exceeds the throughput of the deterministic always-merge baselines while maintaining a lower request miss rate, thereby eliminating the throughput–miss-rate tradeoff that required λ ≥ 2 for the PPO dominance under the uniform demand. A PPENDIX R K EEP -S IDE A BLATION Section III-C introduced the keep-side bit κ ∈ {0, 1} as a learned action dimension that governs the queue evolution after each merge, exposed to the RL agent rather than fixed by a hand-designed endpoint rule as in SACM+/SACM++ (i.e., the retained slot is decoded deterministically from the selected pair, where κ = 0 retains ik and κ = 1 retains jk ). To isolate its contribution from the pair-selection decision, we evaluated the trained PPO-Agent under four keep-side strategies, i.e., (i) Learned, the policy’s own κ (i.e., control); (ii) Higher-degree, always retaining the endpoint with higher merge degree (i.e., the rule used by SACM+/SACM++); (iii) Earliest-deadline, retaining the endpoint with the tighter deadline; (iv) Random, uniform random (i.e., seeded for the reproducibility). In every case, the pair selection (i.e., which pair k to merge) is preserved from the model’s output, while only the keep-side bit (a mod 2) is overridden. Table XLII reports the results. The learned keep-side rule yields a BE-score of 0.976, compared with 0.969 for the closest fixed rule (i.e., Higher-degree) and 0.964–0.965 for the Earliest-deadline and the Random rules. The +0.007 advantage over the Higher-degree and +0.012 over the Earliestdeadline are modest in absolute terms (i.e., roughly onetenth of the full PPO–TauFit-2 gap, ∆σ=0.061), even though

TABLE XLII K EEP - SIDE ABLATION . PPO-AGENT PAIR SELECTION WITH DIFFERENT KEEP - SIDE RULES . ID- DEFAULT, 50 HOLDOUT SEEDS × 200 EPISODES . M EAN ± 95% CI. Keep-Side Rule

BE-Score σ (↑)

Miss Ratio (↓)

Served/Tx (↑)

Exp/Episode (↓)

Learned (full model) Higher-degree Earliest-deadline Random

0.976 ± 0.002 0.969 ± 0.002 0.964 ± 0.002 0.965 ± 0.002

0.208 ± 0.001 0.208 ± 0.001 0.209 ± 0.001 0.209 ± 0.001

1.323 ± 0.002 1.324 ± 0.002 1.323 ± 0.002 1.324 ± 0.001

14.17 ± 0.07 14.12 ± 0.07 14.16 ± 0.08 14.11 ± 0.07

they are numerically separated within the descriptive 95% uncertainty bands (i.e., non-overlapping bands between the Learned and all three alternatives on the BE-score). Consistent with the statistical-reporting protocol of Sec. V-D, we report the separation as descriptive rather than as a paired hypothesis test, i.e., the bands are unpaired CIs, while the evaluation is paired by seed, and a paired per-seed bootstrap on ∆σ would be the right inferential closure and is left as future work. The miss ratio, the served-per-tx, and the expirations are nearly identical across all the four rules. The interesting fact we observed is that the keep-side decision therefore primarily affects the BE-score through its influence on the queue evolution and the future mergeability rather than through the immediate transmission outcomes. Among the fixed rules, the Higher-degree (i.e., the heuristic used by SACM+/SACM++) performs closest to the learned policy, which is consistent with the queue-evolution control through the keep-side bit, i.e., under the simulator’s kmg ∼ Unif{kik , kjk } convention (Eq. (6)), the keep-side does not select the future representative destination of the merged record, while it selects which of the two queue slots is refilled with a fresh arrival. Refilling the lower-degree endpoint (i.e., retaining the higher-degree slot in the queue) thereby preserves more downstream merge candidates without changing the merged record’s destination draw. The contribution from the keep-side is marginal relative to the pair selection, i.e., the pair-selection decision drives most of the performance gap between the PPO and the baselines (∆σ=0.061 vs. TauFit-2), while the learned keep-side adds a further ∼1% refinement. The keep-side is a secondary control dimension, i.e., it does not substitute for the pair selection, even though it does give a measurable improvement at no additional inference cost. A PPENDIX S T RAINING -S EED S TABILITY Four independently seeded training runs (i.e., seeds 0–3) each produce a candidate model via the robust-advantage selection criterion (Section IV-F), while the main results throughout Sections VI–VIII use the best model (i.e., seed 0, selected on the validation). To verify that the reported performance is not an outlier, Table XLIII evaluates all the four seed models on the identical 50-seed holdout set (i.e., 200 episodes/seed = 10,000 episodes per model). Three of the four seeds (i.e., 0, 1, 3) cluster tightly, with BE-scores in [0.950, 0.969] and qualitatively similar selectivemerge behavior, while all the four seeds clearly exceed the best coded-multicast baseline, i.e., SACM++ (σ=0.726), considering that even the weakest seed (i.e., seed 2, σ=0.940)

PREPRINT — SUBMITTED FOR PEER REVIEW

54

TABLE XLIII T RAINING - SEED STABILITY. E ACH OF 4 INDEPENDENTLY TRAINED MODELS EVALUATED ON 50 HOLDOUT SEEDS × 200 EPISODES (10,000 EPISODES PER MODEL ). M EAN ± 95% CI. S EED 0 IS THE SELECTED MODEL USED THROUGHOUT THE PAPER . C OLUMNS ARE GROUPED AS : primary DEMAND - CENTRIC METRICS (ρ, δ; S EC . V-D), BROADCAST- EFFICIENCY METRICS (σ, SERVED / TX , EXPIRATIONS ), AND THE SUPPLEMENTARY request-level FAMILY (ηreq , mreq , σreq ). Train Seed

σ (↑)

ρ (↓)

Served/Tx (↑)

Exp/Ep (↓)

δ (↑)

ηreq (↑)

mreq (↓)

σreq (↑)

0 (selected) 1 2 3

0.969 ± 0.002 0.950 ± 0.002 0.940 ± 0.002 0.968 ± 0.002

0.203 ± 0.001 0.230 ± 0.001 0.266 ± 0.001 0.218 ± 0.001

1.300 ± 0.002 1.355 ± 0.002 1.476 ± 0.002 1.343 ± 0.002

13.76 ± 0.08 15.82 ± 0.08 21.05 ± 0.10 15.16 ± 0.09

0.824 ± 0.001 0.820 ± 0.001 0.778 ± 0.001 0.817 ± 0.001

1.061 ± 0.001 1.093 ± 0.001 1.130 ± 0.001 1.077 ± 0.001

0.228 ± 0.001 0.241 ± 0.001 0.322 ± 0.002 0.243 ± 0.002

0.833 ± 0.001 0.853 ± 0.001 0.807 ± 0.002 0.834 ± 0.002

Mean ± Std

0.957 ± 0.014

0.229 ± 0.027

1.369 ± 0.078

16.45 ± 3.31

0.810 ± 0.020

1.090 ± 0.029

0.259 ± 0.043

0.832 ± 0.019

exceeds SACM++ by +0.214 (+29.5%). The cross-seed standard deviation of 0.014 is roughly one-eighteenth of the PPO–SACM++ gap (∆σ=0.250), thereby confirming that the method’s advantage holds across the training randomness. The extended columns added in this version show that the seed 0 is also the per-seed best on both primary demandcentric metrics, thereby reaching the lowest broadcast-packet expiration ratio (ρ=0.203) and the highest distinct file-identity coverage (δ=0.824). On the supplementary request-level family, the seed 1 attains a slightly higher selection score σreq =0.853 with respect to the selected seed’s 0.833, even though this reflects a different broadcast-efficiency / requestlevel deadline-compliance trade-off rather than a weakness of the selected model on its own primary objective. The seed 2 is an outlier, i.e., it converges to a qualitatively different, aggressive merge strategy with much higher servedper-tx (1.476 vs. 1.300 for the seed 0), even though it also has much higher broadcast-packet expiration ratio (0.266 vs. 0.203), the lowest distinct file-identity coverage of any seed (δ=0.778 vs. 0.824), and about 53% more expirations per episode (21.05 vs. 13.76). This aggressive strategy resembles the behavior of the “without Curriculum” ablation (Section VIII), which suggests that the training stochasticity can occasionally push the policy into the high-throughput / lowreliability basin, even though the curriculum is enabled. The robust-advantage selection criterion (Section IV-F) correctly identifies the seed 0 as the best model on both the broadcastefficiency and the primary demand-centric metrics, i.e., the selection procedure does filter out such outliers. A PPENDIX T I NFERENCE L ATENCY B ENCHMARK Table XLIV benchmarks the per-step inference latency of the trained graph-structured policy network on both the GPU and the CPU, while the benchmark consists of 1,000 individual forward passes (i.e., single observation, batch size 1, deterministic action selection) after a 100-pass warm-up to fill the hardware caches. All the measurements use the highresolution wall-clock timers with the GPU synchronization barriers for the GPU timing. We report the measured median forward-pass latencies of 3.36 ms (i.e., GPU) and 3.19 ms (i.e., CPU) without comparing them to a generic slot-duration threshold, i.e., the applicable slot-duration target is deployment-specific, and we do not import a fixed numerical budget from outside the manuscript.

TABLE XLIV P ER - STEP INFERENCE LATENCY. S INGLE FORWARD PASS , BATCH SIZE 1, NO COMPILATION . 1,000 PASSES AFTER 100- PASS WARM - UP. Device GPU (RTX 3080 Ti) CPU

Mean (ms)

Std (ms)

Median (ms)

p95 (ms)

p99 (ms)

3.46 3.26

0.46 0.45

3.36 3.19

4.32 3.78

4.96 4.26

The 3.3–3.5 ms figure should therefore be read as a feasibility indicator conditional on the target deployment’s slot-duration budget rather than as a certified real-time guarantee. The GPU median of 3.36 ms (i.e., p99 = 4.96 ms) and the CPU median of 3.19 ms (i.e., p99 = 4.26 ms) indicate that the graphstructured policy network forward pass is practical for the single-slot decision-making on both the GPU-equipped and the CPU-only edge nodes. The CPU inference is competitive with the GPU at this model size (i.e., ∼1.73M parameters for the Track A network actually benchmarked here, while the Track B network is ∼1.75M and exhibits comparable percall latency considering the identical encoder topology, batch size 1), because the graph-attention computation is memorybound rather than compute-bound at this scale, i.e., the GPU acceleration would become advantageous only with larger batch sizes or much wider networks. a) Reference-implementation pointers.: For artifact reviewers, the reference implementation of the rejectionsample-and-uniform-destination request-generation rule of Sec. III-B (paragraph “Request Generation”) lives at coded_caching_env_beat_pf_v6.py::_gen_req in the released code. ACKNOWLEDGMENT Language polishing was assisted by a large language model (Claude, Anthropic); all scientific content, experiments, and conclusions are the sole responsibility of the author. R EFERENCES [1] Ericsson AB, “Ericsson mobility report, June 2024,” Ericsson, Tech. Rep., 2024. [Online]. Available: https://www.ericsson.com/en/ reports-and-papers/mobility-report [2] J. Liu, Y. Shi, Z. M. Fadlullah, and N. Kato, “Mobile edge caching: A survey,” IEEE Communications Surveys & Tutorials, vol. 20, no. 3, pp. 2109–2133, 2018. [3] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE Transactions on Information Theory, vol. 60, no. 5, pp. 2856– 2867, 2014.

PREPRINT — SUBMITTED FOR PEER REVIEW

[4] ——, “Decentralized coded caching attains order-optimal memory-rate tradeoff,” IEEE/ACM Transactions on Networking, vol. 23, no. 4, pp. 1029–1040, 2015. [5] U. Niesen and M. A. Maddah-Ali, “Coded caching for delay-sensitive content,” CoRR, vol. abs/1407.4489, 2014. [Online]. Available: http://arxiv.org/abs/1407.4489 [6] S. M. Asghari, Y. Ouyang, A. Nayyar, and A. S. Avestimehr, “An approximation algorithm for optimal clique cover delivery in coded caching,” IEEE Transactions on Communications, vol. 67, no. 7, pp. 4683–4695, 2019. [7] M. Ji, K. Shanmugam, A. M. Tulino, J. Llorca, and G. Caire, “An efficient multiple-groupcast coded multicasting scheme for finite fractional caching,” arXiv preprint arXiv:1511.07539, 2015. [8] G. Vettigli, M. Ji, K. Shanmugam, J. Llorca, A. M. Tulino, and G. Caire, “Efficient algorithms for coded multicasting in heterogeneous caching networks,” Entropy, vol. 21, no. 3, p. 324, 2019. [9] A. Sadeghi, F. Sheikholeslami, A. G. Marques, and G. B. Giannakis, “Reinforcement learning for adaptive caching with dynamic storage pricing,” IEEE Journal on Selected Areas in Communications, vol. 37, no. 10, pp. 2267–2281, 2019. [10] S. O. Somuyiwa, A. György, and D. Gündüz, “A reinforcement-learning approach to proactive caching in wireless networks,” IEEE Journal on Selected Areas in Communications, vol. 36, no. 6, pp. 1331–1344, 2018. [11] C. Zhong, M. C. Gursoy, and S. Velipasalar, “A deep reinforcement learning-based framework for content caching,” in 2018 52nd Annual Conference on Information Sciences and Systems (CISS). IEEE, 2018, pp. 1–6. [12] N. Naderializadeh and S. M. Asghari, “Learning to code: Coded caching via deep reinforcement learning,” in 2019 53rd Asilomar Conference on Signals, Systems, and Computers. IEEE, 2019, pp. 1774–1778. [13] S. Huang and S. Ontañón, “A closer look at invalid action masking in policy gradient algorithms,” arXiv preprint arXiv:2006.14171, 2020. [14] “SB3-Contrib: Maskable PPO (invalid action masking) documentation,” https://sb3-contrib.readthedocs.io/en/master/modules/ppo mask. html, 2026, accessed: 2026-01-11. [15] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph attention networks,” 2018. [16] T. Anthony, Z. Tian, and D. Barber, “Thinking fast and slow with deep learning and tree search,” 2017. [17] S. Ross, G. Gordon, and D. Bagnell, “A reduction of imitation learning and structured prediction to no-regret online learning,” in Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS), 2011, pp. 627–635. [18] A. Y. Ng, D. Harada, and S. Russell, “Policy invariance under reward transformations: Theory and application to reward shaping,” in Proceedings of the 16th International Conference on Machine Learning (ICML), 1999, pp. 278–287. [19] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” arXiv preprint arXiv:1707.06347, 2017. [20] J. Schulman, P. Moritz, S. Levine, M. I. Jordan, and P. Abbeel, “Highdimensional continuous control using generalized advantage estimation,” arXiv preprint arXiv:1506.02438, 2015. [21] Y. Bengio, J. Louradour, R. Collobert, and J. Weston, “Curriculum learning,” in Proceedings of the 26th Annual International Conference on Machine Learning (ICML). ACM, 2009, pp. 41–48. [22] R. Pedarsani, M. A. Maddah-Ali, and U. Niesen, “Online coded caching,” in 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 2014. [23] Y. Jiang, W. Huang, M. Bennis, and F.-C. Zheng, “Decentralized asynchronous coded caching design and performance analysis in fog radio access networks,” IEEE Transactions on Mobile Computing, vol. 19, no. 3, pp. 540–551, 2020. [24] Z. Zhang and M. Tao, “Deep learning for wireless coded caching with unknown and time-variant content popularity,” IEEE Transactions on Wireless Communications, vol. 20, no. 2, pp. 1152–1163, 2021. [25] M. Amir, E. Bedeer, M. H. Ahmed, and T. Khattab, “Coded caching for time-varying files popularities and asynchronous delivery,” IEEE Open Journal of the Communications Society, vol. 2, pp. 1458–1472, 2021. [26] H. Yang, L. F. Xie, J. Liu, and L. Lu, “Optimal scheduling in asynchronous coded caching,” IEEE Transactions on Vehicular Technology, vol. 71, no. 4, pp. 4454–4459, 2022. [27] P. Henderson, R. Islam, P. Bachman, J. Pineau, D. Precup, and D. Meger, “Deep reinforcement learning that matters,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32, no. 1, 2018.

55

[28] R. Agarwal, M. Schwarzer, P. S. Castro, A. C. Courville, and M. G. Bellemare, “Deep reinforcement learning at the edge of the statistical precipice,” in Advances in Neural Information Processing Systems (NeurIPS), vol. 34, 2021. [29] A. Raffin and Stable-Baselines Contributors, “SB3-Contrib: Experimental reinforcement learning algorithms for Stable-Baselines3,” https:// github.com/Stable-Baselines-Team/stable-baselines3-contrib, 2022, accessed: 2025-09-21. [30] A. Raffin, A. Hill, A. Gleave, A. Kanervisto, M. Ernestus, and N. Dormann, “Stable-Baselines3: Reliable reinforcement learning implementations,” Journal of Machine Learning Research, vol. 22, no. 268, pp. 1–8, 2021. [31] M. Towers, A. Kwiatkowski, J. Terry, J. U. Balis, G. De Cola, T. Deleu, M. Goulão, A. Kallinteris, A. KG, M. Krimber, R. Perez-Vicente, A. Pierré, S. Schulhoff, J. J. Tai, A. Tan, and O. G. Younis, “Gymnasium: A standard interface for reinforcement learning environments,” arXiv preprint arXiv:2407.17032, 2024. [32] G. Cumming and S. Finch, “Inference by eye: Confidence intervals and how to read pictures of data,” American Psychologist, vol. 60, no. 2, pp. 170–180, 2005.

Record · ID 196437 · SHA-256 63560f7455e207bd
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.