1
Contextual Bandit-Based Decomposition of Network Slice Requirements under Cumulative Resource Budget Constraints
arXiv:2609.09624v1 [cs.NI] 9 Sep 2026
Masaki Kobayashi, Akito Suzuki, Ryoichi Kawahara, Masahiro Kobayashi
Abstract—End-to-end (E2E) network slices (NSs) are provisioned across multiple domains of the 5G network. In hierarchical NS management, a tenant submits a network slice request (NSR), which specifies E2E service level agreement (SLA) requirements. Rather than managing these domains directly, an E2E controller decomposes each NSR into domain-level SLA requirements and delegates resource allocation to domain-specific controllers, which return feasibility and resource-consumption feedback. A poor decomposition policy can therefore cause rejection of the current request by producing infeasible requirements or reduce future admission opportunities by concentrating resource consumption in bottleneck domains. We call this decomposition-policy optimization problem the network slice request decomposition problem (NSR-DP). For practical operation, online approaches to NSR-DP have been proposed. Such approaches must jointly meet two requirements: (R1) control long-term resource budgets and (R2) adapt each decomposition to the performance targets and guarantee levels specified in the arriving NSR’s SLA. To meet these requirements, we introduce contextual constrained kernel bandits (CCKB) as an online solution for NSR-DP. To address (R1), CCKB raises penalties for using resources that become tight, thereby discouraging decompositions that consume bottleneck resources. To address (R2), it uses Gaussian processes (GPs) to predict, for the current NSR, the reward and resource usage of candidate decompositions, allowing it to select a decomposition suited to the performance targets and guarantee levels. We establish high-probability guarantees for the resulting formulation and show through extensive 5G simulations across topology, bottleneck, and traffic-mixture settings that CCKB outperforms the baselines in the large majority of conditions. Index Terms—5G, Network Slicing, Online Learning
I. I NTRODUCTION A. Background 5G networks are expected to support service categories such as enhanced mobile broadband (eMBB), ultra-reliable and low-latency communications (URLLC), and massive machinetype communications (mMTC) [1]. Network slicing has been proposed to meet the diverse end-to-end (E2E) requirements. A 5G network comprises multiple domains: the access network Masaki Kobayashi, Akito Suzuki, Masahiro Kobayashi are with Network Service Systems Laboratories, NTT, Inc., 3–9–11 Midori-cho, Musashino-shi, Tokyo 180–8585 Japan (e-mail: [email protected]; [email protected]; [email protected]). Ryoichi Kawahara is with the Faculty of Information Networking for Innovation and Design, Toyo University, Kita-ku, Tokyo 115–8650, Japan (e-mail: [email protected]). This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.
Fig. 1. An overview of network slicing and its management architecture. A 5G network comprises multiple domains: the AN, TN, and CN. An NS is formed by interconnecting the NSSs. The hierarchical management architecture comprises the E2E controller and domain-specific controllers.
(AN), transport network (TN), and core network (CN). In each domain, resources are allocated to support individual network slice subnets (NSSs). A network slice (NS) is formed by interconnecting these NSSs [2]. To manage NSs, a hierarchical management architecture has been specified [3]. In this architecture, the E2E controller delegates NS management tasks to subordinate domainspecific controllers, which autonomously control their respective domains rather than being directly controlled by the E2E controller. Accordingly, management of each domain is entrusted to its domain-specific controller, whose internal control algorithm is treated as a black box by the E2E controller. Fig. 1 illustrates the concept of this NS management architecture. Within this hierarchical architecture, an NS is provisioned from a network slice request (NSR) that specifies the tenant’s service level agreement (SLA) requirements. As illustrated in Fig. 2, provisioning comprises three steps: (i) NSR decomposition, (ii) feasibility check, and (iii) E2E admission outcome. When admitted, the NS is realized by consuming the resources, and the E2E controller earns revenue from the tenant (Sec. III). NSR-DP: Among these NS provisioning steps, this work focuses on (i) NSR decomposition, in which the E2E controller decomposes the requirements specified in the NSR
2
Fig. 2. The NS provisioning procedure. (i) In NSR decomposition, the E2E controller decomposes the requirements specified in the NSR and delegates the resulting domain-level NSRs to domain-specific controllers. (ii) In the feasibility check, each domain-specific controller attempts resource allocation for its delegated NSR and evaluates domain-level feasibility given the remaining resources and the demand required to satisfy the decomposed NSR. (iii) In the E2E admission outcome, the E2E controller determines whether the NS is admitted and observes the corresponding reserved resource demands.
and delegates the resulting domain-level NSRs to domainspecific controllers. The decomposition policy of the E2E controller affects not only whether the current request can be admitted and generate revenue (reward), but also how much 5G capacity is consumed (resource consumption). For example, continuously imposing strict requirements (e.g., an overly short latency requirement) on the AN can deplete AN resources while leaving surplus resources in the TN and CN. This cross-domain imbalance can leave one domain as a bottleneck, thereby reducing future admission opportunities and long-term cumulative revenue. We call the problem of optimizing the decomposition policy under this tradeoff the network slice request decomposition problem (NSRDP). Although NS provisioning optimization has been widely studied [4], [5], existing formulations assume a globally coordinated E2E controller that directly manages resources across all 5G domains. This assumption is misaligned with standardized architectures, where domain-specific controllers autonomously manage each domain [3], [6]. Therefore, solving NSR-DP under this hierarchical architecture is a key problem. B. Research Objective and Challenges Motivation for Online Learning: To solve NSR-DP, the E2E controller must choose a decomposition before observing its realized provisioning outcome and thus needs predictive models of the reward and resource consumption of each NSR–decomposition pair. However, accurate model construction is challenging: (i) the E2E controller cannot observe the internal resource-allocation logic of domain-specific controllers [3], [7], which makes accurate analytical modeling [8], [9] difficult; and (ii) sufficiently broad logs of NSR– decomposition outcomes are often unavailable because commercial 5G network-slicing deployments are still scaling [10], which restricts offline supervised model learning [11]–[13]. These challenges motivate learning from sequential feedback rather than relying only on fixed pre-collected data. However, sequential learning also creates an exploration– exploitation trade-off: the controller must sometimes try uncer-
tain decompositions to improve its models, rather than always selecting the decomposition that currently appears best. Research Objective: An exploration-aware online approach to NSR-DP must satisfy two operational requirements. (R1) Long-term resource budget control: for each resource, the policy must control cumulative consumption so that long-term 5G network capacity constraints are respected. Without this capability, the policy may consume a bottleneck resource too aggressively in early rounds, causing many later requests to be rejected even when substantial capacity remains in the other domains. (R2) Request-conditioned decomposition: the decomposition must be selected according to the arriving NSR because different NSRs induce different reward–resource trade-offs across domains. For example, even within the URLLC class, requests may specify different latency targets or reliability guarantees and thus favor different domain-level allocations. Without this capability, the controller may apply a decomposition suited to one SLA specification to a request with different requirements, leading to unnecessarily strict domain-level requirements or inefficient resource consumption. Among exploration-aware online approaches, Odin [14] uses Bayesian optimization (BO) to optimize decompositions, but it satisfies neither (R1) nor (R2). We therefore seek to learn an NSR decomposition policy satisfying (R1) and (R2) from sequential feedback. Challenges: Our previous work [15] addressed both requirements by formulating NSR-DP as a linear contextual bandits with knapsacks (linCBwK) problem [16]. However, it retained two key limitations: (L1) finite/discrete decomposition search and (L2) linear realizability. Under (L1), the controller can select decompositions only from a predefined finite set, which can cause discretization-induced suboptimality. Under (L2), expected reward and resource consumption are assumed to depend linearly on the NSR–decomposition pair; nonlinear dependence can therefore cause inaccurate predictions and suboptimal decomposition. Thus, we seek an online method that preserves (R1) and (R2) while relaxing (L1) and (L2). As in our previous work [15], we analyze a stationaryresponse relaxation in which provisioning outcomes and re-
3
source consumption for each NSR–decomposition pair are time-invariant and independent of residual resources, rather than the original state-dependent process (Sec. IV). C. Our Proposal Our proposal has two parts. (i) We introduce contextual constrained kernel bandits (CCKB) as an online solution for the relaxed NSR-DP. It combines primal–dual cumulative resource control with Gaussian process (GP)-based requestconditioned decision making. (ii) We introduce a conservative proxy formulation to address a learning difficulty arising from resource-consumption feedback in NSR-DP. (i) CCKB-Based Online Solver: The solver comprises two components: (a) a constrained kernel bandits (CKB)-style primal–dual mechanism [17] and (b) contextual GP models for reward and constraint prediction over NSR–decomposition pairs, inspired by contextual GP-UCB (CGP-UCB) [18]. The context and action are the arriving NSR and its decomposition, respectively, and the long-term constraints represent resource budgets. For (a), the primal–dual mechanism operates in a continuous decomposition space: the primal step selects a decomposition, while the dual step updates budget-penalty weights from cumulative resource usage. When a resource becomes tight, the corresponding dual penalty increases, discouraging decompositions that heavily consume that resource. By optimizing the decomposition directly without finite-candidate enumeration, we relax (L1) while supporting long-term budget control (R1). For (b), the contextual GP models condition reward and resource-consumption predictions on the current NSR, thereby supporting contextual decomposition (R2). Their nonlinear model class relaxes linear realizability (L2). (ii) Conservative Proxy Formulation: Directly learning resource-consumption models for the relaxed NSR-DP from provisioning feedback introduces an additional limitation: (L3) zero-dominated resource-consumption observations. For example, if a resource is included in the request’s NS topology for only a small subset of requests and many of those requests are rejected, then most observations for that resource are zero. Consequently, the model tends to make near-zero predictions, underestimating the resource consumption of a given decomposition, which can lead the controller to select resourceintensive decompositions and thereby degrade decision quality. We address (L3) by introducing a proxy target defined only on successful rounds and on resources included in the request’s NS topology, formulating the corresponding proxy problem, and instantiating CCKB for that proxy problem (Sec. V). Performance Guarantees and Empirical Evaluation. We evaluate the proposed method theoretically under the relaxed NSR-DP and empirically under the original, state-dependent NSR-DP. The theoretical analysis quantifies the optimality loss introduced by the proxy formulation and establishes high-probability finite-time bounds on regret and cumulative constraint violation. The simulations assess whether the same proxy-based CCKB design remains effective in the original state-dependent setting (Sec. VI). The contributions of this paper are as follows: • NSR-DP Formulation: We formulate the online NSRDP for heterogeneous requests, where each decomposi-
tion is conditioned on the arriving request and coupled across a finite horizon through shared resource budgets. • CCKB-Based Online Solution: We introduce CCKB as an online solution for the relaxed NSR-DP, accommodating a continuous decision space and nonlinear reward and resource models. We also construct a conservative resource proxy from successful-round observations for resources in the request’s NS topology, thereby mitigating the zero-dominated observation problem (L3). • Finite-Time Performance Analysis: For the proxy problem, we establish finite-time regret and cumulative constraint-violation guarantees for CCKB and transfer these guarantees to the relaxed NSR-DP. The transferred regret bound includes an additional term that quantifies the optimality gap induced by the proxy formulation. • Empirical Evaluation: We evaluate our method in a 5G network simulator. Across 12 topology–bottleneck conditions, our method achieves higher mean Total Reward than our previous linCBwK-based method [15]; additional ablations assess its principal components. This paper extends our conference version [15] by generalizing the NSR-DP formulation, developing the CCKB algorithm to relax (L1) and (L2), and introducing a proxy formulation that addresses (L3) with corresponding theoretical guarantees. D. Paper Organization and Major Symbols We first review the related work (Sec. II). We then introduce the hierarchical NS management modeling (Sec. III) and formulate NSR-DP and its stationary-response relaxation (Sec. IV). Next, we present the proposed CCKB method, proxy formulation, and theoretical guarantees (Sec. V), evaluate the resulting proxy-based method through 5G simulations (Sec. VI), and discuss implementation-oriented considerations (Sec. VII). Table I summarizes the major symbols. II. R ELATED W ORK This section first reviews studies on NS provisioning optimization and identifies the properties required of an online NSR decomposition method (Sec. II-A). We then examine whether existing online-learning formulations jointly provide these properties (Sec. II-B). A. NS Provisioning Optimization Table II positions representative prior work families along four increasingly specific criteria: (G1) compatibility with hierarchical NS management, (G2) exploration-aware online decision-making, (G3) satisfaction of the online NSR-DP requirements (R1) and (R2), and (G4) relaxation of the modeling restrictions (L1) and (L2). 1) Controller-Architecture Assumptions: Centralized vs Hierarchical: NS provisioning optimization has been widely studied [4], [5]. From the NS management-architecture perspective, existing studies can be grouped into two lines. (i) Centralized E2E provisioning. Representative examples include RL- and online-learning-based E2E resource allocation and SFC deployment [19]–[22], as well as optimization-based
4
TABLE I S UMMARY OF M AJOR S YMBOLS G ROUPED BY T HEIR ROLES I. Core notation for NSR-DP and the proposed method A. Online decompositions, outcomes, and budgets s ∈ S, x ∈ X Generic NSR and decomposition, respectively. t ∈ [T ], T ∈ Z+ Round index and horizon length in the online formulation. st , x t Arriving NSR and selected decomposition at round t. max Cd,j Initial capacity and cumulative horizon budget of resource (d, j). Y t , Ut Round-t E2E admission indicator and resource-consumption vector, respectively, with Ut = 0 when Yt = 0. Wt , κprice (s), p̄ Round reward Wt = κprice (st )Yt , where κprice (s) is the revenue for request s and is bounded by p̄. B. Original and relaxed NSR-DP (Sec. IV) (Y, U) ∼ νs,x Generic provisioning outcome for a fixed request–decomposition pair under the stationary-response relaxation. f (s, x), cd,j (s, x) Expected reward and expected resource consumption means under stationary-response relaxation. max − 1/T . hd,j (s, x) Normalized constraint of the relaxed NSR-DP, cd,j (s, x)/Cd,j π ∈ Π, q(· | s) ∈ Q π: causal policy for the original online NSR-DP; q: stationary policy for the relaxed NSR-DP. OPTrel , Regrel (T ), Viorel Optimal value, regret, and cumulative normalized violation of the relaxed NSR-DP. d,j (T ) C. Proxy formulation (Sec. V) Γd (s), 1Γ Path-induced resource-index set in domain d and its membership indicator, 1Γ d,j (s) d,j (s) = 1{j ∈ Γd (s)}. prx prx Γ max mΓ (s, x), h (s, x) Success-conditioned resource demand and its normalized proxy constraint, h d,j d,j d,j = md,j /Cd,j − 1/T . prx prx prx OPT , Reg (T ), Viod,j (T ) Optimal value, regret, and cumulative normalized violation of the proxy formulation. D. CCKB and GP surrogates (Sec. V) ϕt , ρ, V Dual vector, dual cap, and dual-step-size parameter in the primal–dual updates. fˆt , ĥt,d,j , f¯t , h̄t,d,j Raw exploration estimates and the clipped surrogates used by CCKB, respectively. mΓ
f Tt−1 , Tt−1d,j
Reward data (all rounds) and constraint data (successful rounds whose requested topology includes resource (d, j)).
mΓ • , β f , β d,j µ•t−1 , σt−1 t t
Posterior mean, posterior standard deviation, and exploration widths for reward and resource-consumption GPs. II. Supporting notation for network and provisioning models E. Basic sets, indices, and network resources (Sec. III) D, d ∈ D Domain set and its index: D = {AN, TN, CN}. j ∈ [Jd ], i ∈ [M ] Indices for resource in domain d and SLA component. P Jd , Jtot , (d, j) Number of resources in domain d, total resources d∈D Jd , and resource index pair. F. NSR and decomposition model (Sec. III) s = (A, θ, R, g) NSR tuple: next-generation Node B (gNB) coverage A, traffic/service profile θ, SLA specification (R, g). R = (Ri )i∈[M ] , Ri = (Hi , Ti ) SLA components and each component’s conditioning/target event pair. Required guarantee levels for SLA components. g = (gi )⊤ i∈[M ] Rd,i (s, xT ), gd,i (s, xg ) Domain-level SLA target-event component and guarantee-level allocation for component i.
provisioning [23]–[27]. While important, these formulations assume centralized control over the underlying network resources and are therefore less aligned with standardized hierarchical management frameworks such as ETSI ZSM ISG and 3GPP management and orchestration, where an E2E controller delegates provisioning to domain-specific controllers rather than directly optimizing domain-internal resources [3], [6]. Thus, the centralized family does not satisfy (G1). (ii) Hierarchical NSR decomposition. Here, the E2E controller translates E2E requirements into domain-level targets. Representative examples include early SLA decomposition formulations [8], [9], offline machine-learning-based decomposition [11]–[13], and adaptive extensions for dynamic or multi-provider settings [28], [29]. These studies are closer to our setting because they acknowledge delegated multidomain operation, but the black-box nature of domain-specific controllers and the limited availability of broad request– decomposition logs still make online learning particularly attractive in practice. Accordingly, the analytical and offline data-driven families satisfy (G1) but not (G2). 2) Online NSR Decomposition: Among methods compatible with the standardized hierarchical setting, the relevant online studies fall into heuristic online adaptation and exploration-aware online decomposition.
(i) Heuristic online adaptation. Real-time adaptive decomposition (RADE) [28] and risk-aware iterated local search (RAILS) [29] adapt SLA decompositions online by updating point-estimate risk models through online gradient descent using recent provisioning feedback retained in a first-in, firstout (FIFO) buffer. Although these updates enable adaptation to changing conditions, their action-selection rules optimize the resulting point estimates without using predictive uncertainty and therefore do not explicitly manage the exploration– exploitation trade-off. We therefore categorize RADE and RAILS as heuristic online-adaptation methods rather than exploration-aware online algorithms. Accordingly, both methods satisfy (G1) but not (G2). (ii) Exploration-aware online decomposition. In contrast, exploration-aware methods use predictive uncertainty in action selection to balance immediate provisioning performance against information acquisition. Among such approaches, two method families are close. We provide an overview here and compare their formulations with ours in detail in Sec. IV-D. Odin [14] is the closest exploration-aware method to our setting: it tailors a BO design inspired by constrained efficient global optimization (CONFIG) [30]. Accordingly, Odin satisfies (G1) and (G2) but not (G3): its CONFIG-type formulation neither models horizon-level resource budgets (R1) nor
5
TABLE II S EQUENTIAL POSITIONING OF REPRESENTATIVE PRIOR WORK FAMILIES UNDER CRITERIA (G1)–(G4). Methods Ref.
Method family
Comparison criteria (G1) Hierarchical NS management?
(G2) Exploration-aware online?
(1-i) Centralized E2E provisioning [19]–[27] Centralized E2E No: directly controls — provisioning domain-internal resources (1-ii) Analytical and offline data-driven hierarchical decomposition [8], [9] Hierarchical analytical Yes No: uses explicit decomposition analytical models [11]–[13] Hierarchical data-driven Yes No: uses pre-collected decomposition logs (2-i) Heuristic online adaptation [28], [29] FIFO-based online Yes No: no exploration risk-model adaptation mechanism (2-ii) Exploration-aware online decomposition [14] CONFIG-type [30] Yes Yes [15] linCBwK [16] method Yes Yes Ours
Yes
Yes
(G3) Satisfies (R1)/(R2)?
(G4) Relaxes (L1)/(L2)?
—
—
—
—
—
—
—
—
No: misses (R1), (R2) Yes
— No: misses (L1), (L2)
Yes
Yes
Note: — indicates that a later criterion is not the main point of comparison once an earlier criterion is missed.
conditions decomposition selection on the arriving NSR (R2). Our previous work [15], which formulates NSR-DP as a linCBwK problem [16], is also directly relevant. Its formulation satisfies (G1)–(G3) through request-conditioned decisions under cumulative resource budgets, but not (G4): it retains (L1) by optimizing over a pre-enumerated finite candidate set and (L2) by assuming linear reward/resource models. Takeaway. The preceding review identifies the target properties for an online NSR decomposition method: compatibility with hierarchical management and exploration-aware learning, satisfaction of (R1) and (R2), and relaxation of (L1) and (L2).
(iii) Contextual bandits with across-round constraints. The methods in this group make request-conditioned decisions under across-round constraints and thus satisfy (R1) and (R2). linCBwK and SquareCBwK enforce hard budgets by stopping when a resource budget is exhausted [16], [33], [38]. In contrast, the formulations of LagrangeCBwLC, LOE2D, and Optimistic3 allow the interaction to continue throughout the horizon and measure constraint violations cumulatively [34]– [36]. linCBwK retains both (L1) and (L2) because it assumes finite arms and linear reward and consumption models [16]. SquareCBwK, LagrangeCBwLC, LOE2D, and Optimistic3 relax (L2) because they do not require linear reward and cost models, but retain a finite action set and hence (L1).
B. Online Learning We next examine whether existing online-learning formulations satisfy (R1) and (R2) while relaxing (L1) and (L2). Table III compares representative formulations. (i) Continuous-action bandits with across-round constraints. A Bayesian continuum-armed bandit with long-term constraints and CKB both optimize over continuous action domains under across-round constraints [17], [31]. In particular, CKB models nonlinear reward and constraint functions in reproducing kernel Hilbert spaces (RKHSs). These methods therefore satisfy (R1) while relaxing (L1) and (L2), but are non-contextual and hence do not satisfy (R2). (ii) Contextual continuous-action methods. CGP-UCB places a GP over the joint context–action space and supports action and context sets that are not necessarily finite, whereas RANCB uses nonlinear neural models for contextual continuous-action selection [18], [32]. Both methods satisfy (R2) while relaxing (L1) and (L2). However, CGPUCB imposes no constraints, and RANCB imposes step-wise constraints that must hold in every round rather than across the horizon. These methods therefore do not satisfy (R1).
(iv) Contextual primal–dual BO. At the algorithmic level, PDCBO and CCKB share the same core primal–dual contextual BO structure: an optimistic Lagrangian primal step followed by a projected dual update. However, the two methods adopt different performance benchmarks. PDCBO allows arbitrary time-varying contexts and compares each selected action with an optimal action for the context observed in that round [37]. In contrast, under i.i.d. requests from an unknown distribution P, our analysis benchmarks CCKB against a request-conditioned policy jointly optimized over P under a horizon-wide shared resource budget. This distributionaware benchmark captures the opportunity cost of allocating resources to the current request relative to future arrivals and therefore matches the relaxed NSR-DP. Takeaway. Among the representative methods other than PDCBO, none simultaneously satisfies (R1) and (R2) while relaxing both (L1) and (L2). Although PDCBO shares the same core primal–dual contextual BO structure as CCKB, its theoretical guarantees do not directly apply to the analysis target considered in this paper.
6
TABLE III C OMPARISON OF REPRESENTATIVE ONLINE - LEARNING FORMULATIONS UNDER PROPERTIES (R1), (R2), (L1), AND (L2). Methods Ref.
Method/formulation
Comparison properties (R1) Across-round resource control?
(R2) Requestconditioned?
Context / Performance Target
Relaxes (L1)?
Relaxes (L2)?
(i) Continuous-action bandits with across-round constraints [31] GP-UCB with constraints Yes (cumulative) No Yes [17] CKB Yes (soft cumulative) No Yes (ii) Contextual continuous-action methods [18], [32] CGP-UCB; RANCB No (none; step-wise) Yes Yes (iii) Contextual bandits with across-round constraints [16] linCBwK Yes (hard budgets) Yes No [33] SquareCBwK Yes (hard budgets) Yes No [34] LagrangeCBwLC Yes (packing/covering) Yes No [35], [36] LOE2D; Optimistic3 Yes (cumulative) Yes No (iv) Contextual primal–dual BO: shared update structure, different analysis target [37] PDCBO Yes (time average) Yes Yes CCKB (ours)
Yes (soft cumulative)
Yes
Yes
Yes Yes
— —
Yes
—
No Yes Yes Yes
— — — —
Yes
Arbitrary time-varying contexts / context-wise optimum Stochastic requests / distribution-optimized policy
Yes
Note: — indicates that this aspect is not highlighted in this comparison.
III. S YSTEM M ODEL This section formalizes the hierarchical provisioning system used throughout the paper. We consider a horizon of T ∈ Z+ provisioning rounds, indexed by t ∈ [T ]. At a high level, for the E2E controller, round t is characterized by observed request: selected decomposition: observed feedback:
st , xt , (yt , ut ),
where yt is the realized E2E admission outcome, and ut is the realized resource-consumption vector. We first define the network and request model that determines the observed request st (Sec. III-A), then represent NSR decompositions as finite-dimensional vectors and construct the continuous decomposition space X from which the controller selects xt (Sec. III-B), and finally specify how the selected xt produces the observed admission outcome yt and resourceconsumption vector ut (Sec. III-C). Notation: We use Z+ := {1, 2, . . .}, R+ := [0, ∞), and [n] := {1, . . . , n} for any n ∈ Z+ . | · | denotes cardinality (e.g., |A|). We denote finite-dimensional real vectors by bold symbols and their scalar components by the corresponding nonbold symbols. For a, b ∈ Rn , ⟨a, b⟩ := a⊤ b denotes the Euclidean inner product. For any interval [a, b] ⊂ R with a ≤ b, define clip[a,b] (z) := min{b, max{a, z}}. A. Network and NSR Model We define the network resources (Sec. III-A1) and request model (Sec. III-A2) used in each provisioning round. 1) Network Model: Let the set of 5G domains be D := {AN, TN, CN}, with d ∈ D denoting a domain. We represent the 5G network as a directed graph G = (V, E), where V = A ∪ R ∪ U contains gNBs, routers, and user plane
functions (UPFs). For each domain d, let Jd ∈ Z+ be the number of allocatable resources and let j ∈P[Jd ] index them. The total number of resources is Jtot := d∈D Jd , and remax source (d, j) has initial capacity Cd,j . In our model, admitted reservations persist across rounds and reduce the remaining max capacity; hence, Cd,j is also the cumulative capacity budget available over the horizon. Concretely, AN resources are schedulable radio units such as resource block (RB) budgets at gNBs, TN resources are egress interfaces, and CN resources are attachment interfaces at the UPF side. This paper focuses on provisioning the AN, TN, and CN resources that carry user data. Procedures that connect individual devices to the network or exchange control messages are outside the model. 2) NSR Model: An NSR comprises a coverage set A ⊆ A, a traffic/service profile θ, SLA requirement components R := M (Ri )i∈[M ] , and guarantee levels g := (gi )⊤ i∈[M ] ∈ (0, 1] . M ∈ Z+ is the number of SLA components and i ∈ [M ] indexes them. (i) Coverage Set A: The coverage set A specifies the gNBs that the requested NS must cover. For example, if A = {a1 , a2 }, the NS must cover gNBs a1 and a2 . (ii) Traffic/Service Profile θ: The traffic/service profile θ describes request-specific characteristics that influence performance, such as traffic volume. (iii) SLA Specification (R, g): Ri = (Hi , Ti ) specifies the events used to evaluate the SLA: Hi is the condition under which the guarantee is evaluated, and Ti is the performance event that must be achieved under that condition. The value gi ∈ (0, 1] is the required guarantee level. For a fixed request s and decomposition x (defined in Sec. III-B), let Prs,x denote the induced law. Together, R and g specify the SLA requirements imposed on an NS provisioned for request s as Pr(Ti | Hi ) ≥ gi ,
s,x
∀i ∈ [M ].
(1)
7
TABLE IV I LLUSTRATIVE E2E SLA REQUIREMENT COMPONENTS .
Component Hi Latency
Throughput Non-drop
Ti
Interpretation
N
{D ≤ δi } The probability that the E2E delay is at most δi , conditioned on no packet drop, is at least gi . Ω {Θ ≥ θi } The probability that the E2E throughput is at least θi is at least gi . Ω N The probability of no packet drop over the E2E path is at least gi .
In this definition, we assume Prs,x (Hi ) > 0. For illustration, let N denote the event of no packet drop over the E2E path, and let Ω denote the sure event under Prs,x . Let D and Θ denote the E2E delay and throughput random variables, respectively, with targets δi > 0 and θi > 0. Table IV gives three illustrative instantiations of Hi and Ti . Example 1. For the latency component in Table IV, (1) becomes Prs,x (D ≤ δi | N ) ≥ gi . For example, Prs,x (D ≤ 5 ms | N ) ≥ 0.9999 requires the E2E delay to be at most 5 ms for at least 99.99% of successfully delivered packets. Using this component representation, we define an NSR. Definition 1 (Network slice request). An NSR is the tuple s := A, θ, R, g . An NS provisioned for s must satisfy (R, g) over coverage set A under traffic/service profile θ. We denote the set of all NSRs by S. The coverage set A and target events Ti correspond to attributes specifiable in a GSMA NG.116 network slice type (NEST) [39].1 B. Admissible NSR Decomposition
sd (s, x): the probabilistic guarantee that the domain-specific controller for d must satisfy. (i) Domain-level components: We partition the decomposition as x := (xT , xg ). Selecting xT determines the domainlevel target events Td,i (s, xT ) from Ti , whereas selecting xg determines the domain-level guarantee levels gd,i (s, xg ) from gi . Concrete parameterizations of xT and xg are given in Sec. III-B3. We assume that each E2E conditioning event Hi is specified together with domain-level evaluation conditions Hd,i (s), each evaluable within domain d, such that \ Hi = Hd,i (s). (2) d∈D
These domain-level conditions are fixed before optimization. Accordingly, x parameterizes only the decompositions of Ti and gi , not the domain-level construction of Hi . For the latency requirement in Example 1, Hi = N and Hd,i (s) = Nd , where Nd is the event that the packet T traverses domain d without being dropped; hence, N = d∈D Nd . Using the resulting domain-level quantities and θ inherited from s, we define the delegated domain-level NSR as sd (s, x) := θ, Rd (s, xT ), gd (s, xg ) . (3) Here, Rd,i (s, xT ) := Hd,i (s), Td,i (s, xT ) , Rd (s, xT ) := ⊤ Rd,i (s, xT ) i∈[M ] , and gd (s, xg ) := gd,i (s, xg ) i∈[M ] . (ii) Operational meaning: The following inequality is the domain-level counterpart of (1) and defines when domain d satisfies component i of its delegated NSR sd (s, x). It represents hierarchical control in the NS management architecture: the E2E controller delegates the domain-level evaluation condition, target event, and guarantee level, and the domain-specific controller provisions its resources to satisfy the resulting probabilistic guarantee: Pr(Td,i (s, xT ) | Hd,i (s)) ≥ gd,i (s, xg ),
s,x
This subsection represents each NSR decomposition by a finite-dimensional parameter vector x and constructs the continuous decomposition space X from which the E2E controller selects x. We first define how x transforms an E2E request s into a delegated domain-level NSR for each domain (Sec. III-B1). We then state the admissibility conditions for preserving the original E2E SLA requirement when all delegated domain-level requirements are met (Sec. III-B2). Next, we give concrete constructions that satisfy these conditions and parameterize the resulting admissible decompositions using nonnegative weight vectors (Sec. III-B3). Finally, we remove slack from the weight vectors, define exact splits, and assemble X as a product of simplices (Sec. III-B4). 1) Domain-Level NSR Construction: Given an E2E NSR s and decomposition x, we define the domain-level NSR sd (s, x) delegated to domain d. We first (i) define the components of sd (s, x). We then (ii) state the operational meaning of 1A
NEST specifies per-use-case NS requirements as target values, but not the condition under which each target is evaluated, the probability with which it must hold, or the traffic conditions that determine performance. The components Hi , gi , and θ supply these; s therefore abstracts an NSR rather than instantiating a NEST.
∀d ∈ D, i ∈ [M ].
(4) We assume Prs,x (Hd,i (s)) > 0 whenever this conditional probability is used. 2) Admissibility Conditions: A decomposition cannot be chosen arbitrarily because, even if every domain-specific controller can satisfy its delegated request, the original E2E requirement need not be satisfied. For example, for an E2E delay target of 10 ms across the AN, TN, and CN, domain targets of (2, 3, 5) ms preserve the target because their sum is 10 ms. In contrast, targets of (4, 4, 4) ms allow every domain target to be met while the E2E delay reaches 12 ms. Therefore, the E2E controller cannot select domain-level targets independently. Operationally, for each component i, guarantee preservation requires that satisfaction of every delegated domain-level guarantee imply satisfaction of the original E2E guarantee: ∀d ∈ D,
Pr(Td,i (s, xT ) | Hd,i (s)) ≥ gd,i (s, xg )
s,x
⇒ Pr(Ti | Hi ) ≥ gi . s,x
We formalize this requirement as follows.
(5)
8
Definition 2 (Admissible decomposition). Fix an NSR s ∈ S. A decomposition x is admissible for s if, for every SLA component i ∈ [M ], \ (A1) Hi ∩ Td,i (s, xT ) ⊆ Ti , d∈D
(A2)
gi ≤
Y
(6) gd,i (s, xg ).
d∈D
Under cross-domain conditional-independence conditions that are reasonable when domain-specific controllers operate on separate resources and no common-cause failures or traffic fluctuations affect multiple domains, (A1) and (A2) are sufficient for the guarantee-preservation implication in (5). A proof and a detailed discussion of the applicability of the independence conditions are provided in Appendix A. 3) Concrete Construction of Admissible Decompositions: Definition 2 characterizes admissibility but does not provide finite-dimensional constructions. We therefore specify (i) target decomposition, in which xT determines the domain-level target events Td,i (s, xT ), and (ii) guarantee decomposition, in which xg determines the domain-level guarantee levels gd,i (s, xg ). The feasible parameter values are subsequently restricted to form the continuous decomposition space X used for optimization. Table V summarizes these constructions for the illustrative SLA components introduced in Table IV. (i) Target Decomposition: Target decomposition constructs the domain-level target events Td,i (s, xT ) from the E2E target event Ti so that Hi andTall domain-level target events jointly imply Ti , i.e., Hi ∩ d∈D Td,i (s, xT ) ⊆ Ti , as required by (A1). For the illustrative components in Table V, the construction depends on how the E2E target relates to the domain-level quantities. (a) Target-value allocation applies when a numerical E2E bound is allocated among the domains, as for latency. (b) Target-condition replication applies when no numerical split is needed and the E2E target follows from requiring every domain to satisfy its corresponding local condition, as for throughput and non-drop. (i-a) Target-value allocation: Target-value allocation constructs the domain-level target events Td,i by translating the E2E bound in Ti into one bound for each domain. For example, P consider the latency target Ti = {D ≤ δi }, where D = d∈D Dd , and Dd is the latency contributed by domain d. Let δd,i ≥ 0 denote the delay boundPassigned to domain d, and choose these bounds such that d∈D δd,i ≤ δi . For δi = 10 ms, one choice is (δd,i )d∈D = (2, 3, 5) ms. On Hi , if every domain-specific controller satisfies its delegated latency target Td,i = {Dd ≤ δd,i }, then X X D= Dd ≤ δd,i ≤ δi , d
T
d
and hence Hi ∩ d∈D Td,i ⊆ Ti , which verifies (A1). (Generic construction): The latency example above is an instance of the following construction for any E2E quantity that is the sum of its domain-level contributions. We use Qi , Qd,i , τi , and τd,i to denote the generic counterparts of D, Dd , δi , and δd,i , respectively, with τi > 0. The construction is summarized as follows:
•
Input: The E2E target event is written as follows: X Ti = {Qi ≤ τi }, Qi = Qd,i . d∈D
Allocation: A nonnegative vector wi = (wd,i )d∈D , where wd,i is the fraction of the E2E bound assigned to domain P d, satisfying d∈D wd,i ≤ 1, and defining the domain-level bounds as τd,i := wd,i τi . • Output: The domain-level target events
•
Td,i (s, xT ) := {Qd,i ≤ τd,i }. The latency targets (2, 3, 5) ms above T correspond to wi = (0.2, 0.3, 0.5). The output satisfies d Td,i (s, xT ) P ⊆ Ti , and hence (A1) holds. If the required relation is instead d Qd,i ≥ τi , the same construction applies by reversing the inequalities in Ti , Td,i , and the allocation-sum condition. (i-b) Target-condition replication: Unlike target-value allocation, target-condition replication does not divide a numerical E2E bound among the domains. Instead, it defines Td,i by applying the condition in Ti to the corresponding domain. Consider the E2E throughput target Ti = {Θ ≥ θi } introduced in Table IV. Let Θd denote the throughput in domain d. We model the E2E throughput as the bottleneck across the domains, i.e., Θ = mind Θd . Therefore, \ Ti = {Θ ≥ θi } = {Θd ≥ θi }, d∈D
and setting Td,i = {Θd ≥ θi } consequently satisfies (A1). For example, if θi = 100 Mbit/s, the same target Θd ≥ 100 Mbit/s is imposed on every domain. (Generic construction): The throughput example above is an instance of the following construction. We use Cd,i (s) to denote a target event that can be evaluated within domain d; it is not a decomposition parameter. In the throughput example, Cd,i (s) = {Θd ≥ θi }, whereas, for the non-drop component, Cd,i (s) = Nd . The construction is summarized as follows: • Input: The E2E target event can be written as \ Ti = Cd,i (s). d∈D
Allocation: No numerical target value is allocated, and no target-decomposition parameter is introduced. • Output: The domain-level target events •
Td,i (s, xT ) := Cd,i (s), d ∈ D. T T The output satisfies Hi ∩ d∈D Td,i (s, xT ) ⊆ d∈D Cd,i (s) = Ti , which verifies (A1). (ii) Guarantee Decomposition: Guarantee decomposition constructs the delegated guarantee levels gd,i (s, xg ) so that their product is at least the E2E level gi , as required by (A2). We use the following exponent-weight parameterization: • Input: The E2E guarantee level gi ∈ (0, 1]. • Allocation: Nonnegative exponent weights η i = (ηd,i )d∈D P satisfying d ηd,i ≤ 1. • Output: The domain-level guarantee levels η
gd,i (s, xg ) := gi d,i .
9
TABLE V I LLUSTRATIVE TARGET AND GUARANTEE DECOMPOSITIONS . xg
x
T {Td,i }d∈D (i) Target decomposition: Ti −−→
− → {gd,i }d∈D (ii) Guarantee decomposition: gi −
Rule
E2E input Ti
Parameter xT
Domain output Td,i
E2E input gi
Parameter xg
Domain output gd,i
Latency
(i-a) Allocation
{D ≤ δi }
P wi ≥0, d wd,i ≤1
{Dd ≤ wd,i δi }
gi
gi d,i
Throughput
(i-b) Replication
{Θ ≥ θi }
None
{Θd ≥ θi }
gi
P η i ≥0, d ηd,i ≤1 P η i ≥0, d ηd,i ≤1 P η i ≥0, d ηd,i ≤1
Component
Non-drop
(i-b) Replication Success event: N
None
P
Nd
gi
η
Because gi ∈ (0, 1], the output satisfies gi ≤ gi d d,i = Q d∈D gd,i (s, xg ). Thus, (A2) holds. Remark 1. The latency, throughput, and non-drop components above are illustrative. An additional SLA component can be incorporated by defining domain-level target and guarantee constructions that satisfy (A1) and (A2), respectively. 4) Exact-Split Decomposition Space: Sec. III-B3 introduces nonnegative domain-weight vectors: wi allocates a numerical target value, whereas η i allocates a guarantee level. We call such a weight vector an exact split if its entries sum to 1. We next explain why the decomposition space X available to the E2E controller retains only exact splits. (i) Slack Removal for Target Allocation: For an additive upper-bound target P Ti = {Qi ≤ τi }, admissibility requires P w ≤ 1. If d d,i d wd,i < 1, part of the E2E target bound is not assigned to any domain. Increasing one or more weights until they sum to 1 relaxes the corresponding domain-level targets while preserving (A1). For example, the latency weights wi = (0.2, 0.3, 0.4) are admissible but leave 10% of the E2E delay budget unused. Replacing them with (0.2, 0.3, 0.5) preserves admissibility, uses the full budget, and makes no delegated target stricter. (ii) Slack Removal for Guarantee P Guarantee Allocation: P admissibility Q requires η ≤ 1. If η d d,i d d,i < 1 and gi < 1, then d gd,i > gi , so the delegated guarantee levels collectively exceed the E2E level required by (A2). Because η gi d,i is nonincreasing in ηd,i for gi ∈ (0, 1], increasing one or more exponent weights until they sum to 1 makes no delegated guarantee stricter and preserves (A2). (iii) Product-of-Simplices Decomposition Space: The arguments in (i) and (ii) show that allocation slack can be removed from both wi and η i without making any delegated requirement stricter or violating (A1) or (A2). We therefore restrict both weight vectors to exact splits. By definition, each exact-split weight vector is nonnegative and sums to 1, and hence belongs to the following (|D|−1)-dimensional simplex: ( ) X |D| ∆|D|−1 := a ∈ R≥0 ad = 1 . d∈D
Fig. 3 shows this simplex for a latency allocation vector, together with one exact split and one non-admissible split. Let KT , Kg ∈ Z≥0 denote the numbers of SLA components whose target values and guarantee levels, respectively, are decomposed using domain-weight vectors. Accordingly,
CN
η
η
gi d,i η gi d,i
non-admissible: wi = (0.4, 0.4, 0.4) P d wd,i = 1.2, so (4, 4, 4) ms exact split: wi = (0.2, 0.3, 0.5)
AN
TN
Fig. 3. Simplex for latency allocation vector with δi = 10 ms. Each point in the simplex is a weight vector wi ∈ ∆2 , which yields domain-level delay targets (wAN,i δi , wTN,i δi , wCN,i δi ) whose sum is exactly δi .
the targetspaces are XT = and guarantee-decomposition |D|−1 KT |D|−1 Kg ∆ and Xg = ∆ , respectively. Their Cartesian product gives the overall decomposition space KT +Kg X = XT × Xg = ∆|D|−1 . (7) C. Per-Round Hierarchical Provisioning Procedure We formalize the three-stage provisioning procedure illustrated in Fig. 2. First, given st and the selected decomposition xt , the E2E controller constructs and delegates the domainlevel inputs (Sec. III-C1). Each domain-specific controller then evaluates provisioning feasibility and reports its feasibility and resource-demand outputs (Sec. III-C2). Finally, the E2E controller aggregates these outputs into the observed admission outcome yt and resource-consumption vector ut (Sec. III-C3). 1) NSR Decomposition and Domain-Level Delegation: Under the standardized hierarchical NS management architecture, the E2E controller delegates management tasks while domainspecific controllers autonomously manage their respective domains [3], [6]. In this paper, we model the information exchanged in this delegation by assuming that, at round t, the E2E controller provides each domain-specific controller d ∈ D with two complementary inputs: • Path-Induced Resource Set Γd (st ): This set identifies which domain resources may be used to provision the NSR. • Delegated Request sd (st , xt ): Defined in (3), this request specifies the traffic profile and decomposed SLA requirements that the domain-specific controller uses to determine how much of each resource is required to provision the NSR. Using these two inputs, each domain-specific controller determines the allocation amounts and evaluates feasibility through its internal control procedure, whose input–output behavior is specified in Sec. III-C2. Fig. 4 summarizes this delegation interface and the corresponding role separation.
10
Thus, Yt = 1 if and only if every domain is locally feasible, and the request is admitted exactly in this case. (Realized Resource Consumption Ut ): The E2E controller then constructs Ut ∈ RJ+tot as ( Bt,d,j , Yt = 1 ∧ j ∈ Γd (st ), (10) Ut,d,j := 0, Yt = 0 ∨ j ∈ / Γd (st ). A rejected request therefore incurs no resource consumption, whereas on an admitted round, only resources in the requested NS topology incur consumption, equal to their reported resermax vation demand Bt,d,j . In either case, 0 ≤ Ut,d,j ≤ Cd,j almost surely. At the end of the round, the E2E controller observes realizations yt and ut of the aggregate outcome (Yt , Ut ). Fig. 4. Role separation in hierarchical provisioning. The E2E controller provides the path-induced resource set Γd (st ) and delegated request sd (st , xt ); each domain-specific controller retains control of its internal resource allocation and reports feasibility and, when locally feasible, demand.
We now formally define Γd (s). For each request s and covered gNB a ∈ A, let Φpath (s, a) denote the directed downlink path selected by the E2E controller using a fixed routing rule from the selected UPF u ∈ U to a, represented by the resources traversed along the path, including the downlink output resource of a. For example, Φpath (s, a) may be obtained as a shortest admissible path from the selected UPF to a. The resulting resource set in domain d is Γd (s) := {j ∈ [Jd ] | ∃a ∈ A, (d, j) ∈ Φpath (s, a)} .
(8)
Because the routing rule is fixed, Γd (s) is determined before a decomposition is selected.2 2) Domain-Level Feasibility Check: After receiving the two delegated inputs Γd (st ) and sd (st , xt ), each domainspecific controller applies its internal control procedure Φd , and outputs the following two random domain-level variables: • Feasibility Indicator Yt,d ∈ {0, 1}: This binary indicator equals 1 when the controller can provision the delegated request sd (st , xt ) using the resources in Γd (st ) under its current local conditions, and 0 otherwise. J • Demand Vector Bt,d ∈ R+d : When Yt,d = 1, Bt,d,j gives the amount that would be reserved from resource (d, j) if the E2E request were admitted. For j ∈ / Γd (st ), Bt,d,j = 0. We treat Φd as a black box in the problem formulation. Appendix H gives its concrete instantiation for the experiments. 3) E2E Admission and Consumption: The E2E controller aggregates the domain-level outputs Yt,d and Bt,d to determine two round-level quantities: the admission indicator Yt and resource consumption Ut . (Admission Indicator Yt ): Yt is defined as Y Yt := Yt,d . (9) d∈D 2 Path selection is therefore outside the black box: the E2E controller computes Φpath (s, a), and hence Γd (s), itself. Only the internal input–output mapping Φd , which turns (Γd (s), sd (s, x)) into a feasibility indicator and a demand vector, is treated as a black box.
IV. NSR-DP AND I TS R ELAXATION At each round t, the provisioning procedure in Sec. III-C is executed, and the E2E controller’s decision is the decomposition xt ∈ X . We first formulate this sequential decomposition-selection problem as the NSR-DP, in which a causal policy selects xt from the current NSR and past provisioning feedback (Sec. IV-A). Because its state-dependent provisioning responses make the problem difficult to analyze, we then introduce a stationary-response relaxation for tractable algorithm design (Sec. IV-B). Finally, we define regret and cumulative normalized constraint violation as performance criteria for designing and evaluating online policies for the relaxed problem (Sec. IV-C) and compare the relaxed NSRDP formulation with prior formulations (Sec. IV-D).
A. NSR-DP We first define the round reward and causal policy class (Sec. IV-A1), and then formulate the NSR-DP (Sec. IV-A2). 1) Reward and Causal Policy: To quantify the value of successful provisioning, let κprice : S → R+ denote the revenue earned by the network operator when request s is successfully provisioned, and assume 0 ≤ κprice (s) ≤ p̄ for some finite upper bound p̄. The round reward is Wt := κprice (st )Yt .
(11)
Next, we define the history and policy class. At the end of round t, the E2E controller observes realizations yt ∈ {0, 1} of Yt and ut = (ut,d,j )d∈D,j∈[Jd ] of Ut . The history is t Ht := (sτ , xτ , yτ , uτ ) τ =1 ,
H0 := ∅.
(12)
Let Ht be the set of admissible histories through round t, with H0 := {∅}, and let P(X ) be the set of probability measures on X . Let Π be the class of causal randomized policies π = (πt )Tt=1 with πt : S × Ht−1 → P(X ). 2) Optimization Formulation: The decision variable of the original NSR-DP is the policy π ∈ Π. For each π ∈ Π, let Eπ denote expectation under the stochastic process induced by π.
11
With the reward Wt and resource consumption Ut,d,j defined in (11) and (10), respectively, the problem is " T # X OPT := max Eπ Wt (13a) π∈Π
s.t.
f (s, x) := E(Y,U)∼νs,x [κprice (s)Y ] ,
t=1
Eπ
" T X
With Assumptions 1 and 2 imposed on the original NSR-DP in (13), the conditional mean reward and resource consumption depend only on the current request–decomposition pair. For each (s, x), let (Y, U) ∼ νs,x and define these means as
# max Ut,d,j ≤ Cd,j ,
d∈D ∀j∈[J . (13b) d]
t=1
The objective (13a) maximizes expected cumulative reward, and each constraint (13b) limits the expected cumulative max consumption of resource (d, j) by Cd,j . Remark 2 (Expected Constraints and Hard Capacity Enforcement). For tractable online algorithm design and analysis, (13b) expresses each resource budget over the horizon as a constraint on expected cumulative consumption, following the standard long-term soft-constraint setting reviewed in Sec. II-B. These per-resource constraints discourage the online policy from consuming bottleneck resources too aggressively. However, an expected constraint does not guarantee that realmax ized cumulative consumption remains within Cd,j for every realization of requests and provisioning outcomes. Because physical resource capacities cannot be exceeded in operation, the experiments check the remaining capacities in every round, reject any request that cannot be accommodated, and thereby evaluate the proposed method under hard capacity enforcement. Developing an alternative NSR-DP formulation that directly enforces physical capacity constraints and deriving corresponding theoretical guarantees remain future work. B. Stationary-Response Relaxation In the original NSR-DP, the conditional distribution of (Yt , Ut ) may depend on the history Ht−1 , through past provisioning outcomes and the resulting remaining capacities. To obtain a tractable model for algorithm design, we adopt a stationary-response relaxation that abstracts away this state dependence by assuming that the response distribution depends only on the current pair (st , xt ). We first formalize this relaxation through a stationary response law (Sec. IV-B1). We then use this law to derive the relaxed NSR-DP (Sec. IV-B2). 1) Stationary Response Law: We formalize the stationaryresponse relaxation through the following assumption. Assumption 1 (Stationary response law). There is a family of distributions {νs,x }(s,x)∈S×X on {0, 1} × RJ+tot such that, under any policy π, (Yt , Ut ) | (Ht−1 , st , xt ) ∼ νst ,xt ,
∀t ∈ [T ].
(14)
That is, conditional on the current pair (st , xt ), the provisioning outcome (Yt , Ut ) is independent of the past history Ht−1 , and the same response law applies across rounds. 2) Derivation of the Relaxed NSR-DP: The reduction uses the following request-arrival assumption. Assumption 2 (Independent request arrivals). At the beginning of each round t, request st is independently drawn from a common unknown distribution P on S.
cd,j (s, x) := E(Y,U)∼νs,x [Ud,j ] .
(15)
For any π ∈ Π, let Prπ denote the trajectory law induced by π. We represent its request-conditioned decomposition choices by qπ,t (· | s) := Prπ (xt ∈ · | st = s) and their time average PT by q̄π (· | s) := T −1 t=1 qπ,t (· | s). Under Assumptions 1 and 2, the objective and budget terms in (13) depend on π only through q̄π . In particular, the reward objective satisfies " T # T X X Eπ Wt = Es∼P Ex∼qπ,t (·|s) [f (s, x)] t=1
t=1 = T · Es∼P Ex∼q̄π (·|s) [f (s, x)] .
The budget terms in (13b) admit the same reduction with cd,j in place of f , yielding the average per-round constraints below. Relaxed Formulation and Exactness: Let Q be the class of measurable stationary request-conditioned policies q(· | s) ∈ P(X ), which contains q̄π for every π ∈ Π. Using the expected reward f (s, x) and expected consumption cd,j (s, x) of resource (d, j) for each request–decomposition pair, as defined in (15), the resulting relaxed NSR-DP is OPTrel := maxEs∼P Ex∼q(·|s) [f (s, x)] (16a) q∈Q
max Cd,j d∈D , ∀j∈[J . s.t. Es∼P Ex∼q(·|s) [cd,j (s, x)] ≤ d] T (16b)
The objective (16a) maximizes expected per-round reward, while each constraint (16b) limits expected per-round conmax sumption to Cd,j /T . The policy therefore determines both the decomposition used for each request and the allocation of the shared resource budget across heterogeneous requests over the decision horizon. Conversely, any q ∈ Q can be implemented by the causal policy πt (· | st , Ht−1 ) = q(· | st ). Hence, under Assumptions 1 and 2, the reduction is exact. C. Policy Evaluation Criteria Difficulty of online learning for the relaxed NSR-DP: In the online setting, the primitives P and {νs,x }(s,x)∈S×X are unknown, so the optimizer and optimal value of (16) cannot be computed. This information gap is the central challenge in solving the relaxed NSR-DP online. With full information, the Lagrangian dual of (16) decomposes across request types and can be solved by standard subgradient methods, with expectations evaluated exactly when tractable and approximated numerically otherwise. To evaluate and design online policies under this information gap, we fix any π ∈ Π and consider both (i) its reward gap from the full-information benchmark and (ii) its cumulative budget excess. (i) Regret: To measure the reward gap, we compare the policy’s cumulative mean reward with the relaxed optimum: Regrel (T ) := T OPTrel −
T X t=1
f (st , xt ).
(17)
12
Here, f (s, x), defined in (15), is the expected PT reward for the request–decomposition pair (s, x). Thus, t=1 f (st , xt ) is the cumulative mean reward of the evaluated online policy, whereas T OPTrel is the cumulative expected reward achieved by an offline optimal policy that knows the request distribution P and provisioning-outcome laws {νs,x }. Accordingly, Regrel (T ) measures the cumulative mean-reward gap between the online policy, which operates without knowing P or {νs,x }, and this offline optimum. (ii) Violation: To measure how much cumulative conmax sumption exceeds the capacity budget Cd,j , we define the normalized per-round constraint function hd,j : hd,j (s, x) :=
cd,j (s, x) 1 − . max Cd,j T
(18)
We then define Viorel d,j (T ) :=
" T X t=1
# hd,j (st , xt )
,
d∈D ∀j∈[J . d]
(19)
+
Here, cd,j (s, x), defined in (15), is the expected consumption of resource PT (d, j) for the request–decomposition pair (s, x). Thus, t=1 hd,j (st , xt ) is positive exactly when the evaluated online policy’s cumulative mean consumption of max resource (d, j) exceeds its capacity budget Cd,j . Accordingly, rel Viod,j (T ) measures the normalized amount of this excess. D. Requirements and Applicability of Prior Methods We first summarize the requirements (R1) and (R2) encoded in the relaxed NSR-DP (Sec. IV-D1). We then compare the relaxed NSR-DP with the formulations underlying the two exploration-aware online approaches [14], [15] identified in Sec. II. We show that neither formulation directly targets the full relaxed NSR-DP and explain how these mismatches can lead to suboptimal reward or budget mismatch (Sec. IV-D2). 1) Requirements of the Relaxed NSR-DP: In the relaxed NSR-DP (16), (R1) is imposed by the resource constraints (16b), which require every feasible q ∈ Q to keep the max expected per-round consumption at most Cd,j /T . (R2) is encoded by optimizing over the policy class Q, whose elements map each arriving request s to a distribution q(· | s) ∈ P(X ). 2) Comparison with Prior Formulations: Absence of (R1) and (R2) in the CONFIG Formulation: Odin [14] adopts a CONFIG-type formulation [30] that does not account for these two requirements. For (R1), CONFIG, with constraint PT function g, measures cumulative constraint violation as t=1 [g(xt )]+ [30, Def. 2.8], whereas (19) uses the positive part of the sum. Because CONFIG applies the positive part separately in each round, a negative value of g(xt ) in one round cannot offset a positive value in another; hence, it does not represent a resource budget shared across the T rounds. For (R2), its decision xt does not depend on an arriving NSR st , unlike q(· | s) in (16). Restricted Formulation in Our Previous Method: Our previous method [15], based on linCBwK [16], accounts for both (R1) and (R2). However, it restricts the decomposition space to a finite subset X̄ ⊂ X selected in advance, equivalently restricting q(· | s) from P(X ) to P(X̄ ). This restriction
can exclude decompositions needed to attain the optimum of (16), giving rise to (L1) finite/discrete decomposition search. The previous method also assumes that the expected reward f (s, x) and resource consumption cd,j (s, x) are linear in the request–decomposition pair (s, x). If these functions are nonlinear, this assumption cannot represent them accurately, giving rise to (L2) linear realizability. These limitations motivate an online solver that directly targets (16) without imposing (L1) or (L2). V. P ROPOSED M ETHOD Method Overview: We first present CCKB, a general online learning algorithm that can directly target the relaxed NSR-DP by treating requests as contexts, decomposition decisions as actions, and resource budgets as long-term constraints (Sec. V-A). Direct application of CCKB to the relaxed NSRDP requires GP regression for the original constraint functions hd,j . However, such regression is hindered by (L3) zerodominated resource-consumption observations, which can degrade the decision performance of CCKB. To address (L3), we formulate a conservative proxy problem for the relaxed NSR-DP (Sec. V-B). We then instantiate CCKB for this proxy problem (Sec. V-C). Fig. 5 summarizes this overall procedure. Positioning and Contributions: CCKB combines the primal–dual resource-control mechanism of CKB [17] with contextual GP models over request–decomposition pairs, following the modeling principle of CGP-UCB [18]. This combination shares the same core primal–dual contextual BO structure as PDCBO [37]. Building on this structure, we formulate and analyze its application to the relaxed NSR-DP, including a conservative proxy construction for (L3) and finitetime bounds on Regrel (T ) and every Viorel d,j (T ). A. CCKB for the Relaxed NSR-DP At round t, after observing context st and selecting action xt , define zt := (st , xt ). For the relaxed NSR-DP, let f be the expected reward in (15), and let h := (hd,j )d∈D, j∈[Jd ] be the vector of normalized resource constraints defined in (18). Their function classes are Ff := {f : S × X → [0, p̄]} and Fhd,j := {h : S × X → [−1/T, 1 − 1/T ]}. We first present the CCKB algorithm in this relaxed-NSR-DP notation (Sec. V-A1) and then discuss the difficulty that arises when CCKB is applied directly to the relaxed NSR-DP (Sec. V-A2). 1) Primal–Dual CCKB Solver: Algorithm 1 summarizes CCKB for the relaxed NSR-DP. The core elements of Algorithm 1 are (i) exploration strategies and (ii) a dual vector, which constitute the CKB-like primal–dual mechanism [17]. (i) Exploration Strategies: In lines 4 and 5, the exploration h mappings have the form Aft , At d,j : Ht−1 → RS×X . Here, RS×X denotes the set of all real-valued functions on S × X . Given the history Ht−1 , Aft returns the raw exploration h estimate fˆt of the expected reward f , whereas At d,j returns ĥt,d,j of the normalized mean constraint hd,j . Clipping these estimates to the ranges of their target functions yields the reward and constraint surrogates f¯t ∈ Ff and h̄t,d,j ∈ Fhd,j . We instantiate the reward mapping Aft to return an upper confidence bound (UCB) of f and each constraint mapping
13
Fig. 5. Overview of the proposed method: (i) the CCKB algorithm; and (ii) the proxy derivation.
Algorithm 1 CCKB for the relaxed NSR-DP: contextual extension of the CKB primal–dual framework [17] Require: Horizon T , dual cap ρ, dual step size V > 0, reward h mappings Aft , constraint mappings At d,j 1: Initialize H0 ← ∅, ϕ1 ← 0 ∈ [0, ρ]Jtot 2: for t = 1, . . . , T do 3: ▷ Construct surrogates. 4: fˆt ← Aft (Ht−1 ) h 5: ĥt ← At d,j (Ht−1 ) d∈D, j∈[J ] d 6: f¯t (s, x) ← clip (fˆt (s, x)) [0,p̄]
h̄t (s, x) ← clip[−1/T, 1−1/T ] (ĥt (s, x)) 8: ▷ Primal step. 9: At (x | st ) ← f¯t (st , x) − ⟨ϕt , h̄t (st , x)⟩ 10: Select xt ∈ arg maxx∈X At (x | st ) 11: ▷ Observe outcomes. 12: Observe feedback (yt , ut ). 13: ▷ Dual step. 14: ϕt+1 ← proj[0,ρ]Jtot ϕt + V1 h̄t (st , xt ) 15: Update Ht . 16: end for 7:
h
At d,j to return a lower confidence bound (LCB) of hd,j . The reward UCB assigns larger values to decompositions with a high predicted reward or high reward uncertainty, whereas the constraint LCB assigns smaller values to decompositions with low predicted resource consumption or high consumption uncertainty. Given the acquisition function At in line 9, using these reward and constraint mappings favors decompositions that may yield high rewards or consume few resources. For continuous X , the maximization in line 10 is solved numerically (e.g., by multi-start sequential least-squares quadratic programming (SLSQP) [40]). To apply CCKB to a particular problem, its reward maph ping Aft and constraint mappings {At d,j }d∈D, j∈[Jd ] must be instantiated for that problem. Section V-A2 describes how
these mappings are instantiated when CCKB is applied directly to the relaxed NSR-DP, whereas Sec. V-C describes how the corresponding mappings are instantiated when CCKB is applied to the proxy problem. (ii) Dual Vector: The dual vector ϕt = (ϕt,d,j )d∈D, j∈[Jd ] stacks the resource-wise shadow prices in the primal–dual mechanism. When resource (d, j) is repeatedly tight, projected ascent increases ϕt,d,j , which amplifies the penalty term during action selection and discourages actions that rely heavily on that resource (line 9). Hence, resource importance is reflected adaptively through the dual variables. 2) Direct Application of CCKB to the Relaxed NSR-DP: We first instantiate the reward and constraint mappings in Algorithm 1 for the relaxed NSR-DP, and then explain why this direct application encounters (L3). Direct Instantiation: The mappings in Algorithm 1 are implemented as follows: f • Reward Mapping At : Use all past operator-reward observations κprice (sτ )yτ to fit a GP regression model for f , and return its raw UCB estimate. hd,j : For each resource (d, j), • Constraint Mapping At use all past normalized consumption observations max uτ,d,j /Cd,j − 1/T to fit a GP regression model for hd,j , and return its raw LCB estimate. However, this direct constraint GP regression encounters (L3) zero-dominated resource-consumption observations. By max (10), its regression response ut,d,j /Cd,j −1/T reflects the demand Bt,d,j only when Yt = 1 and j ∈ Γd (st ), and otherwise equals the repeated value −1/T . When such repeated values dominate the training data, they obscure how Bt,d,j varies with the request–decomposition pair zt = (st , xt ), making the constraint GP difficult to fit accurately. B. Conservative Proxy Problem Algorithm 1 relaxes (L1) and (L2) for the relaxed NSR-DP but encounters (L3) when directly fitting a constraint GP for
14
hd,j . To address this remaining limitation, we derive a proxy problem whose constraint functions are more amenable to GP fitting. Specifically, we construct the proxy constraint hprx d,j so that it can be estimated using only resource-consumption observations uτ,d,j from rounds satisfying yτ = 1 and j ∈ Γd (sτ ) (Sec. V-B1). We then formulate the proxy problem using hprx d,j , and show that any policy feasible for the proxy problem is also feasible for the relaxed NSR-DP, which allows us to replace the original constraints with the proxy constraints while preserving feasibility (Sec. V-B2). 1) Proxy Construction: Starting from the selected observations uτ,d,j , we (i) define the conditional mean demand mΓd,j and use it to decompose the original mean consumption cd,j , and then (ii) derive an upper bound on cd,j and substitute it into hd,j to define the conservative proxy constraint hprx d,j . (i) Mean Consumption Decomposition: We introduce the following quantities and use them to decompose the mean consumption cd,j in (15): • Provisioning Success: p(s, x) := Pr(Y = 1 | s, x) is the probability that provisioning succeeds for (s, x). • Topology Membership: For each NSR s, the topologymembership indicator records whether resource (d, j) belongs to the requested NS topology and is defined as 1Γd,j (s) := 1{j ∈ Γd (s)} . •
By (10), Ud,j = 0 whenever Y = 0. We distinguish the cases p(s, x) = 0 and p(s, x) > 0. For an on-path input with p(s, x) = 0, Y = 0 almost surely. Because the success-conditioned expectation E[Ud,j | Y = 1, s, x] is then not uniquely defined, (21) assigns its zero extension. Consequently, cd,j (s, x) = p(s, x)mΓd,j (s, x) = 0. For inputs with p(s, x) > 0, conditioning on Y and substituting the definitions above gives cd,j (s, x) = E[Ud,j | s, x] (22)
= p(s, x)mΓd,j (s, x).
(23)
Replacing cd,j in the definition of hd,j in (18) with the upper bound (23), we define the proxy constraint3 hprx d,j (s, x) :=
mΓd,j (s, x) 1 − . max Cd,j T
Here, f (s, x), defined in (15), is the expected reward for the request–decomposition pair (s, x). The proxy objective (25a) is identical to the relaxed objective (16a), whereas the proxy resource constraint (25b) replaces the relaxed constraint (16b). In the remainder, we use OPTprx as the benchmark. For a policy π, define the proxy counterparts of (17) and (19) by Reg
prx
prx
(T ) := T · OPT
−
T X
f (st , xt ),
(26)
t=1
Vioprx d,j (T ) :=
" T X
# hprx d,j (st , xt )
t=1
.
(27)
+
(ii) Feasibility Transfer to the Relaxed NSR-DP: Normax malizing (23) by Cd,j and subtracting 1/T shows that hd,j (s, x) ≤ hprx d,j (s, x).
(28)
Taking expectations in (28) gives the following result. Lemma 1 (Feasibility transfer under conservative proxying). For q ∈ Q, if q is feasible for (25), then q is feasible for (16). If Lemma 1 did not hold, a policy feasible for the proxy problem could violate the relaxed NSR-DP constraints, so solving the proxy problem would not justify resource-budget feasibility for the relaxed NSR-DP. The lemma therefore allows us to optimize and analyze the proxy problem while preserving feasibility for the relaxed NSR-DP. Corollary 1(ii) quantifies the resulting optimality loss. C. CCKB Instantiation for the Proxy Problem
The equality also holds when p(s, x) = 0, as shown above. (ii) Proxy Constraint Derivation: Equation (22) expresses the mean consumption as the product of the provisioningsuccess probability and the zero-extended conditional mean demand. Because p(s, x) ≤ 1, it gives the upper bound cd,j (s, x) ≤ mΓd,j (s, x).
OPTprx := max Es∼P Ex∼q(·|s) [f (s, x)] (25a) q∈Q h h ii s.t. Es∼P Ex∼q(·|s) hprx ≤ 0. (25b) d,j (s, x)
(20)
Conditional Mean Demand: Define the mean demand represented by the selected observations as ( j∈Γd (s), E[Ud,j | Y = 1, s, x] , p(s,x)>0 , Γ md,j (s, x) := (21) 0, otherwise.
= p(s, x)E[Ud,j | Y = 1, s, x]
We write hprx := (hprx d,j )d∈D, j∈[Jd ] for the stacked proxy max constraint vector. Since 0 ≤ Ud,j ≤ Cd,j almost surely, the prx 1 proxy constraint satisfies − T ≤ hd,j (s, x) ≤ 1 − T1 . 2) Proxy Problem and Feasibility Transfer: (i) We first formulate the proxy problem induced by hprx and define its performance metrics. (ii) We then show that feasibility for the proxy problem implies feasibility for the relaxed NSR-DP. (i) Proxy Problem and Performance Metrics: Using hprx d,j , we define the following proxy optimization problem OPTprx :
(24)
3 Further justification of this design choice and a discussion of alternative modeling methods are provided in Sec. VII-B.
We now instantiate Algorithm 1 for the proxy problem (25). Proxy Instantiation: The proxy problem retains the reward target f but replaces each constraint target hd,j with hprx d,j , defined in (24). Accordingly, the reward mapping Aft reh mains unchanged, whereas each constraint mapping At d,j is hprx replaced by At d,j . Other components of Algorithm 1 remain unchanged. The mappings are implemented as follows: f • Reward Mapping At (Unchanged): Use the same reward mapping as in the direct instantiation (Sec. V-A2). hprx d,j • Constraint Mapping At : Retain only past rounds satisfying yτ = 1 ∧ 1Γd,j (sτ ) = 1, fit a GP for mΓd,j to the resource-consumption observations uτ,d,j , and convert its LCB into a raw exploration estimate of hprx d,j .
15
TABLE VI C OMPARISON OF THE DIRECT AND PROXY CCKB INSTANTIATIONS . Surrogate Design
CCKB Instantiation
Specification
Direct
Proxy
Reward
Target Mapping
f Aft
f (unchanged) Aft (unchanged)
Target
hd,j
hprx d,j
Mapping
At d,j
h
At d,j
h
prx
Table VI summarizes the correspondence between the two instantiations. The following subsubsections provide concrete GP-basedprximplementations of the exploration mappings Aft h and {At d,j }d∈D, j∈[Jd ] . We first specify the common GP posterior notation and feature-map design (Sec. V-C1), and then instantiate the reward mapping Aft (Sec. V-C2) and the hprx proxy constraint mappings {At d,j }d∈D, j∈[Jd ] (Sec. V-C3). 1) Common GP Settings: To fix the notation, (i) we first specify common GP posterior notation for a scalar function •, which is followed by (ii) our additional design of feature maps. For each modeled function • (i.e., • = f for reward and • = mΓd,j for each constraint (d, j)), we define a dataset • • • . Tt−1 ⊂ (S × X ) × R, with sample count Nt−1 := Tt−1 (i) GP Posterior Summaries: For each modeled function •, we use a zero-mean GP surrogate with kernel k• and • regularization parameter η• > 0. Given Tt−1 , standard GP regression with the regularized Gram matrix K•t−1 +η• I yields • the posterior mean µ•t−1 (z) and standard deviation σt−1 (z); • see [41]. Here, Kt−1 is the kernel Gram matrix over the • training inputs. When p Tt−1 = ∅, these quantities reduce to the prior values 0 and k• (z, z), respectively. (ii) Feature Map: To allow different inductive biases across the modeled functions, we use function-specific feature maps on the joint input z: φ• : S × X → Z• . We then define each kernel through φ• as k• (z, z ′ ) := κ• φ• (z), φ• (z ′ ) , where z, z ′ ∈ S × X and κ• is a positive semidefinite kernel. This is equivalent to defining a kernel on z, but makes the representation explicit. 2) Reward Mapping: Reward learning is fully observed, and the reward-training dataset up to round t − 1 is f := {(zτ , κprice (sτ )yτ )}t−1 Tt−1 τ =1 .
Using these posterior summaries with • = f , we define the raw reward UCB estimate as f fˆt (z) := µft−1 (z) + βtf (αf )σt−1 (z).
mΓ
those rounds are retained in Tt−1d,j : mΓ Tt−1d,j := (zτ , uτ,d,j )
Surrogate Type
Constraint
1Γd,j (st ) = 1. Although ut,d,j is observed at every round, only
(29)
Since f (z) ∈ [0, p̄], the reward surrogate used in Algorithm 1 is f¯t (z) := clip[0,p̄] fˆt (z) . The exploration mapping Aft in Algorithm 1 is instantiated as Aft (Ht−1 ) := fˆt . Here αf ∈ (0, 1) controls the reward confidence level, and the corresponding exploration width βtf (αf ) is specified in Sec. V-D3. 3) Constraint Mapping: For each resource (d, j), the constraint GP models mΓd,j in (21), i.e., the success-conditioned demand on resources included in the request’s NS topology. Selective constraint update keeps only rounds with yt = 1 and
τ ∈ [t − 1], yτ = 1, 1Γd,j (sτ ) = 1 .
This filter addresses (L3) by removing zeros caused by rejected requests and by resources outside the request’s NS topology before fitting the GP. For z = (s, x), we define the raw demand LCB estimate from the posterior summaries for mΓd,j : Γ Γ Γ µmd,j (z)−β md,j αh σ md,j (z), 1Γ (s) = 1, t t−1 d,j Jtot t−1 m b Γt,d,j (z) := 0, 1Γd,j (s) = 0. (30) The posterior quantities in the first branch are defined and evaluated only at on-path inputs. Here αh ∈ (0, 1) is the total failure probability allocated to simultaneous confidence bounds for all Jtot unknown demand functions. For each resource (d, j), we allocate failure probability αh /Jtot to the mΓ
confidence bound for mΓd,j , and βt d,j (αh /Jtot ) ∈ R>0 is the corresponding exploration width. We then derive a raw exploration estimate of the proxy constraint as: b hprx t,d,j (z) :=
m b Γt,d,j (z) 1 − . max Cd,j T
(31)
Since hprx d,j (z) ∈ [−1/T, 1 − 1/T ], the proxy constraint prx surrogate is h̄prx t,d,j (z) := clip[−1/T, 1−1/T ] ĥt,d,j (z) , and hprx
At d,j (Ht−1 ) := ĥprx t,d,j . Accordingly, the proxy instantiation h
hprx
substitutes At d,j ← At d,j and h̄t,d,j ← h̄prx t,d,j in Algorithm 1. D. Theoretical Guarantees Theorem 1 bounds the regret Regrel (T ) and cumulative constraint violation Viorel d,j (T ) for CCKB applied directly to the relaxed NSR-DP. For proxy-based CCKB, Corollary 1 uses GP surrogate-error bounds to bound Regprx (T ), transfers this bound to Regrel (T ) by accounting for the proxy optimality gap, and bounds Viorel d,j (T ). Scope of Theoretical Results: Algorithm 1 remains executable when the analytical assumptions fail, but its guarantees may not hold. These guarantees concern the relaxed NSR-DP; effectiveness for the original NSR-DP (13) is evaluated empirically in Sec. VI with residual resources explicitly managed. 1) Regularity and Optimization Conditions: We adopt the standard bounded-RKHS conditions [17]. Assumption 3 (RKHS and kernel conditions). The means f and hd,j lie in the RKHSs of kf and khd,j , with ∥f ∥Hkf ≤ B f and finite ∥hd,j ∥Hkh . On inputs with 1Γd,j (s) = 1, d,j
mΓd,j ∈ HkmΓ
Γ
with norm at most B md,j . All kernels satisfy
d,j
k• (z, z) ≤ 1 and are continuous in their action arguments. Assumption 4 (Measurability in the request). For every fixed x ∈ X , the function f (·, x) is measurable. For every resource (d, j), hd,j (·, x), the zero extension of mΓd,j (·, x), and the indicator 1Γd,j (·) are measurable.
16
For q ∈ Q, define vqf (s) := Ex∼q(·|s) [f (s, x)] and vqh (s) := h Ex∼q(·|s) [h(s, x)], whose (d, j) component is vq d,j (s). Assumption 5 (Slater condition). For each fixed horizon T , there exist a policy q ◦ ∈ Q and a margin ξT > 0 such that Es∼P [vqh◦ (s)] ≤ −ξT 1. Provided that the relaxed NSR-DP and the proxy problem each admit an optimal policy and satisfy Assumption 5 for their respective constraints, Corollary S1 guarantees the existence of optimal dual vectors with finite ℓ1 norms. We denote prx corresponding norm bounds by Λrel T and ΛT , respectively. The corollary and its application to the proxy problem are stated in Appendix B-A; the proof is in Appendix E-A. 2) Finite-Time Performance Guarantees for CCKB: We establish finite-time regret and cumulative constraint-violation guarantees for CCKB applied directly to the relaxed NSRDP. We first specify the surrogate conditions and requestconcentration events used in Theorem 1, together with their failure-probability budgets, and then state the resulting finitetime bounds and their overall confidence level. We subsequently instantiate the same guarantee for the proxy problem. (i) Surrogate Conditions: Algorithm 1 selects actions and updates the dual vector using the surrogates f¯t and h̄t,d,j in place of f and hd,j . Following the GP-UCB analysis of the original CKB [17], we characterize their accuracy through (C1) one-sided bounds used for action selection and (C2) cumulative-error bounds along the selected actions. (One-Sided-Bound Condition): The reward surrogate must not underestimate the reward, whereas each constraint surrogate must not overestimate its target constraint. Specifically, for every t ∈ [T ] and z ∈ S × X , (C1):
f (z) ≤ f¯t (z), h̄t (z) ≤ h(z).
(32)
Here, the vector inequality is interpreted componentwise. (Cumulative-Error Condition): The estimation errors along the selected inputs must not accumulate too quickly. For zt = (st , xt ), let Wf (T ) ≥ 0 and W h (T ) ∈ RJ+tot denote deterministic upper bounds on the cumulative reward and constraint estimation errors, respectively, and require the following, with the vector inequality interpreted componentwise: T X
(C2):
f¯t (zt ) − f (zt ) ≤ Wf (T ),
t=1 T X
(33)
h(zt ) − h̄t (zt ) ≤ W h (T ).
t=1
The surrogate functions f¯t and h̄t are constructed from the random history Ht−1 , whereas the selected input zt = (st , xt ) depends on the realized request st and the selected action. Consequently, (C1) and (C2) contain random quantities and need not hold for every realization. As in the original reg CKB [17], let Esur denote the event on which (C1) and the first vio inequality in (C2) hold, and let Esur denote the event on which vio reg (C1) and both inequalities in (C2) hold. Thus, Esur ⊆ Esur . We use αsur as a common failure-probability budget. The regret reg bound requires Pr(Esur ) ≥ 1 − αsur , whereas the constraintvio violation bound requires Pr(Esur ) ≥ 1 − αsur .
(ii) Request-Sequence Concentration: Along the realized request sequence, the aggregate request-wise reward values vqf⋆ (st ) and constraint values vqh⋆ (st ) may deviate from their expectations Es∼P [vqf⋆ (s)] and Es∼P [vqh⋆ (s)], respectively. The f h parameters αctx and αctx are the failure-probability budgets for the reward and constraint concentration inequalities in Propositions S3 and S4, respectively (Appendix C). (iii) Performance Guarantee: We establish finite-time regret and cumulative constraint-violation bounds for CCKB applied directly to the relaxed NSR-DP, with the regret bound expressed in terms of Wf (T ) and the violation bound also using W h (T ). Each bound is established on the intersection of its required surrogate and request-concentration events. A f h union bound gives the overall probability 1−αctx −αctx −αsur . Theorem 1 (Finite-time regret and constraint-violation bounds). Suppose that the relaxed NSR-DP admits an optimal policy and that Assumptions 2, 3, and 4 hold. For failure f f h h + αctx + , αctx , αsur ∈ (0, 1)√satisfying αctx probabilities αctx αsur < 1, choose ρ > 0, and set V := Jtot T /ρ in Algorithm 1. reg ) ≥ 1 − αsur . Then, with (i) Regret: Suppose that Pr(Esur f h probability at least 1 − αctx − αctx − αsur , there exists a finite upper bound Breg (T ) such that Regrel (T ) ≤ Breg (T ) q q p̄ T log αf1 + ρJtot T log αh1 ctx ctx = O . (34) p + Wf (T ) + ρ Jtot T (ii) Constraint violation: Suppose, in addition, that Assumption 5 holds. For the fixed horizon T , choose ρ ≥ 2Λrel T , and vio ) ≥ 1 − αsur . Then, with probability at suppose that Pr(Esur f h − αsur , there exists a finite upper bound least 1 − αctx − αctx Bvio (T ) such that the following inequality holds for every (d, j): Viorel d,j (T ) ≤ Bvio (T ) q Wf (T ) + Jtot T log αh1 ctx . = O ρ p +∥W h (T )∥1 + Jtot T
(35)
f The proof is in Appendix E-C. The log(1/αctx ) and h log(1/αctx ) terms in (34) and (35) arise from concentration over the realized request sequence and have no counterpart in CKB. 3) GP-Based Proxy Guarantee: Theorem 1 leaves the cumulative surrogate-error bounds Wf (T ) and W h (T ) abstract. We instantiates these quantities for proxy-based CCKB using GP confidence widths and maximum information gains. We first specify the required GP assumptions and exploration widths and then derive explicit bounds on Wf (T ) and W h (T ). Substituting these bounds into Theorem 1 yields Corollary 1.
Assumption 6 (Reward observation noise). The residual Wt − f (zt ) is conditionally σ f -sub-Gaussian given (Ht−1 , zt ). Assumption 7 (Proxy-demand observation noise). On rounds with Yt = 1 and 1Γd,j (st ) = 1, the residual Ut,d,j − mΓd,j (zt )
17
Γ
is conditionally σ md,j -sub-Gaussian given (Ht−1 , zt , Yt = 1, 1Γd,j (st ) = 1).
(ii) Relaxed NSR-DP regret: If the relaxed NSR-DP also admits an optimal policy, then, on the same event,
Definition 3 (Maximum information gain). For each modeled function •, define 1 γn• := max n log det I + η•−1 K•Zn , (36) Zn ∈dom(•) 2
Regrel (T ) = Regprx (T ) + T ∆prx (T ) ≤ Bprx (T ) + T ∆prx (T ).
(42)
where Zn = (z1 , . . . , zn ) and K•Zn := [k• (za , zb )]na,b=1 . For the reward model, dom(f ) = S × X . For resource (d, j), dom(mΓd,j ) = {(s, x) ∈ S × X | 1Γd,j (s) = 1}.
If, additionally, Assumption 5 holds for the proxy constraints and Assumption 8 holds with MT ≥ Λrel T , then 2p̄ prx rel Reg (T ) ≤ Bprx (T ) + ΛT −1 . (43) aT
Exploration Widths: Under Assumptions 3, 6, and 7, we follow the GP-UCB instantiation of CKB [17, Corollary 1] to set the exploration widths used in the reward UCB (29) and the proxy-demand LCB (30). With normalized noise scales Γ √ p ed,j := σ md,j / ηmΓd,j , these widths are σ ef := σ f / ηf and σ s 1 f f f f βt (αf ) := B +e σ 2 γt−1 +1+log , (37) αf v ! u u Γ Γ mΓ Jtot α md,j h d,j md,j t βt := B . +e σd,j 2 γ mΓ +1+log d,j Jtot αh Nt−1
(iii) Constraint violation: Suppose also that Assumption 8 holds with MT ≥ ρ and Assumption 5 holds for the proxy constraints. Choose ρ ≥ 2Λprx T , and fix αw ∈ (0, 1) such that f h αctx + αctx + αf + αh + αw < 1. Then, with probability at f h least 1 − αctx − αctx − αf − αh − αw , the following bound holds simultaneously for every resource (d, j): f γT Jtot γTf + Jtot + aT √ ρ rel Γ e Viod,j (T ) ≤ O T md′ ,j ′ . (44) X X γT + p̄ aT ′ Cdmax ′ ,j ′ ′
(38)
For fixed ρ and failure probabilities, √ the proxy-regret bound in (41) is sublinear whenever γTf T = o(T ). This condition alone does not ensure that the relaxed-NSR-DP regret in (42) is sublinear, because of the separate term T ∆prx (T ). Under the additional conditions in part (ii), this term is bounded by Λprx T (2p̄/aT − 1), which does not grow with T explicitly; hence, if Λprx and 1/aT remain bounded in T , proxy T conservatism contributes only an O(1) cumulative-regret term and (43) is sublinear. The explicit bounds and proof are in Appendix B-D (Corollary S4) and Appendix E-F.
Assumption 8 (Existence of a valuable decomposition for every request). For the fixed horizon T , there exist constants MT > 0 and aT > 0 such that, for P-almost every request s, X X mΓd,j (s, x) ≥ aT . (39) max f (s, x) − MT max x∈X Cd,j d∈D j∈[Jd ]
In words, almost every request has at least one decomposition whose expected reward exceeds MT times its total normalized conditional resource demand by at least aT . Remark 3 (Interpretation of Assumption 8). The condition excludes request populations containing a non-negligible subset for which every decomposition is unlikely to succeed or consumes too many resources relative to its revenue. Removing this condition remains future work. Define the nonnegative per-round proxy gap by ∆prx (T ) := OPTrel − OPTprx .
d ∈D j ∈[Jd′ ]
VI. E VALUATION We conducted experiments in a 5G simulator. We first describe the experimental 5G network and NSR settings (Sec. VI-A), then summarize the comparison methods (Sec. VI-B) and define the evaluation metrics (Sec. VI-C). We then present experiments and their results. Table VII summarizes the experiments and their corresponding objectives.
(40)
e suppresses logarithmic factors in T , inverse The notation O failure probabilities, and Jtot , while treating the kernels k• , Γ the RKHS-norm bounds B f and B md,j , the noise scales σ ef and σ ed,j , and the regularization parameters η• as fixed. Corollary 1 (Concrete finite-time bounds for proxy-based f f h h CCKB). Fix αf , αh , αctx , αctx ∈ (0, 1) such that αctx +αctx + αf + αh < 1. Suppose that Assumptions 1, 2, 3, 4, 6, and 7 hold and that the proxy √ problem admits an optimal policy. Choose ρ > 0, set V := Jtot T /ρ, and use the exploration widths in (37) and (38). f h (i) Regret: With probability at least 1−αctx −αctx −αf −αh , √ √ √ e p̄ T + ρJtot T + γ f T . Regprx (T ) ≤ Bprx (T ) = O T (41)
A. Experimental Setup 1) 5G Network: We use four topologies with 12 gNBs (Fig. 6): Tree, Tree dual-UPF, Ring, and Ring dual-UPF. General Settings: We model a 5G system as a finite-buffer queueing network in which each traversed interface is represented by an M/M/1/K queue. The experiments generate only downlink user-plane traffic. Across all four configurations, the maximum UPF-to-gNB path length is at most 100 km, which satisfies the 20 to 300 km assumption range in [42]. For propagation-delay calculations, we assume a propagation speed of 1.96×108 m/s. Each access-link abstraction is configmax ured with maximum capacity CAN = 17.83 Gbit/s, 128 buffer slots, and zero propagation distance. These AN settings are shared across all four topologies. The radio profile comprises one user equipment (UE) per gNB, i.e., 12 UEs in total. We use
18
TABLE VII E VALUATION OBJECTIVES OF THE EXPERIMENTS .
Section
Evaluation Objective
Effectiveness and Robustness Sec. VI-D Overall Effectiveness Across Topologies and Domain Bottlenecks: Evaluates whether the complete method improves cumulative reward and resource allocation relative to the baselines across network topologies and domain bottlenecks. Sec. VI-E Robustness to Heterogeneous Requests: Evaluates whether the proposed method remains effective relative to the baselines when URLLC and eMBB requests coexist and their traffic composition changes. Ablation Studies Sec. VI-F Effects of Relaxing (L1) and (L2): Isolates the effects of continuous decomposition search for relaxing (L1) finite/discrete decomposition search and GP surrogate modeling for relaxing (L2) linear realizability, relative to our previous method [15]. Sec. VI-G Effect of Addressing (L3): Evaluates whether learning CCKB’s proxy constraint target only from successful rounds and resources included in the request’s NS topology mitigates (L3) zero-dominated resource-consumption observations. Sec. VI-H Effects of Mechanisms for (R1) and (R2): Isolates the contributions of dual-based long-horizon resource-budget control for (R1) and request-conditioned surrogate modeling for (R2). Scalability and Sensitivity Analyses Sec. VI-I Computational Scalability: Evaluates per-round runtime and total runtime as the numbers of gNBs increase. Appendix J Hyperparameter Robustness: Evaluates the sensitivity of total reward to the dual-cap parameter, which limits the dual penalty weights, and the GP exploration-scale parameter, which controls the confidence widths.
Fig. 6. Four topology configurations used in evaluation (|A| = 12): (1) Tree, (2) Tree dual-UPF, (3) Ring, and (4) Ring dual-UPF.
max CAN as the nominal service-capacity ceiling of each downlink queue. Its derivation from the custom wideband radio profile, relation to the standardized NR bandwidth configurations, and mapping to the queue service rate are given in Appendix H-D. Across transport and core-facing links, each directed link is parameterized by distance, bandwidth, and buffer depth, so queueing and propagation are modeled. Following these settings, we set four topologies as follows: (1) Tree, (2) Tree dual-UPF: Both tree configurations share the same TN/AN structure: four TN routers, each serving three gNBs, i.e., twelve TN-to-AN links, each configured at 70 km, 20 Gbit/s, and 256 buffer slots. In the single-UPF tree, one UPF connects radially to all four TN routers through four CN-to-TN links, each set to 30 km, 40 Gbit/s, and 512 slots. In the dual-UPF tree, two UPFs dual-home every TN router (eight CN-to-TN links in total), with each CN-to-TN link set to 30 km, 20 Gbit/s, and 512 slots. Hence, total CN-side ingress capacity is 160 Gbit/s in both tree configurations. (3) Ring, (4) Ring dual-UPF: Both configurations use the same access fan-out structure as the tree configurations (four TN routers, each serving three gNBs), but configure the twelve TN-to-AN links at 10 km, 20 Gbit/s, and 256 slots and connect the TN routers in a four-hop ring (30 km, 50 Gbit/s, and 256 slots per TN hop). In the single-UPF ring, one UPF attaches to one TN router through one CN-to-TN link (30 km, 160 Gbit/s, 512 slots). In the dual-UPF ring, two UPFs attach to two opposite TN routers through two CN-to-TN links, each
configured at 30 km, 80 Gbit/s, and 512 slots. Thus, total CNside ingress capacity is again 160 Gbit/s in both configurations. 2) Hierarchical Network Slice Management: We instantiate the hierarchical NS management framework as follows. (i) Path Assignment: Within the E2E controller, the fixed path-assignment rule determines Γd (st ), the path-induced resource set in domain d, as defined in Sec. III-C1. In the experiments, for each active gNB a, the controller selects uniformly at random one of the minimum-distance paths from any UPF in U to a. The selected path defines Φpath (st , a). Controller ownership is fixed by interface type: CN manages only core-facing attachment links (from the UPF to router ingress), TN manages intra-transport links and transport-toaccess links, and AN manages radio-side resources at gNBs. (ii) Domain-Specific Controller Procedure: Within each domain-specific controller, the internal procedure Φd computes resource demands and evaluates the local feasibility of the delegated request, as defined in Sec. III-C2. In the experiments, we instantiate Φd using an M/M/1/K model over the resources in Γd (st ). The controller first evaluates SLA feasibility at the physical upper ratio. An infeasible upper ratio produces a local rejection; otherwise, the controller computes the capacityreq bounded estimate βbt,d,j of the minimum required ratio. The complete experimental instantiation of Φd , including the random allocation overhead and final check against remaining capacity, is given in Appendix H.
19
3) Network Slice Request: We instantiate the NSR tuple s = (A, θ, R, g) with its distribution PNSR mix as follows. (i) NSR Instantiation: We consider two request classes, URLLC and eMBB, which impose contrasting latency, reliability, and throughput requirements on user-plane traffic. We exclude mMTC because evaluating its support for a very large number of connected devices [43] would require modeling device connections, which is outside our scope. For both classes, we set R = (R1 , R2 , R3 ) and g = (g1 , g2 , g3 )⊤ . We map URLLC and eMBB to 5QI 86 and 5QI 6, respectively [44]. The complete mapping from each experimental parameter to an element of (A, θ, R, g), together with the class-conditional values, is given in Table S2. The decomposition rules are detailed in Sec. VI-A4. The URLLC packet-size setting reported in Table S2 follows 3GPP TR 38.824 [45], whereas the eMBB delay and throughput settings follow 3GPP TS 28.530 [6] and ITU-R M.2410 [43]. NSR (ii) NSR Distribution: Let PNSR URLLC and PeMBB denote the class-conditional NSR distributions. For each request, the parameters listed as intervals in Table S2 are sampled independently and uniformly from those intervals, whereas the parameters listed as single values are fixed within each class. NSR NSR We use PNSR mix = α PeMBB + (1 − α) PURLLC , where α ∈ [0, 1] is the eMBB mixing ratio. The successful-provisioning revenue function is fixed classwise as κprice (s) = 1 for URLLC and κprice (s) = 50 for eMBB, reflecting the larger resource footprint of eMBB. 4) Instantiation of the Decomposition Space: Following the target and guarantee constructions in Sec. III-B3, we use the exact splits defined in Sec. III-B4. The components R1 , R2 , and R3 represent the latency, throughput, and nondrop requirements, respectively. Only R1 uses target-value allocation; R2 and R3 use target-condition replication and therefore introduce no target-decomposition parameters. Thus, KT = 1. We apply guarantee decomposition to all three components, so Kg = 3. With D = {AN, TN, CN}, (7) therefore gives the experimental decomposition space
TABLE VIII OVERVIEW OF C OMPARED M ETHODS Method
(i) Surrogate Model
(ii) Search Space
(iii) Selection Algorithm
CCKB (Ours) linCBwK [15] CONFIG [30] Random
Nonlinear GP Linear GP Nonlinear GP None
Continuous Discrete Continuous Continuous
Primal–dual (Alg. 1) Primal–dual (Alg. 1) CONFIG Uniform random
B. Comparison Methods
1) Common Settings: To ensure a fair policy comparison, we use common settings for surrogate inputs and observations, hyperparameters, and the learning protocol where applicable. (i) Surrogate Inputs and Observations: All surrogatebased methods use the same input, output processing, and observation-noise models, as detailed in Appendix G. These experimental fitting choices are distinct from the conditional sub-Gaussian assumptions in Sec. V-D. (ii) Hyperparameters: For implementation, we replace the confidence widthsp in (37) and (38) with the common tunable log(t + 2), where cβ > 0. This schedule schedule βt = c β √ grows as Θ( log t). Although this simplification enables a common implementation across the GP models, it does not satisfy the exploration-width conditions in (37) and (38), and thus the corresponding theoretical guarantee cannot be invoked for the experimental implementation. Similar practical modifications have been adopted in prior empirical work [49]. Unless otherwise specified in each experimental setup, we set cβ = 0.1. For CCKB and linCBwK, which use primal–dual updates, we set the dual-cap parameter to ρ = 1.0. (iii) Learning Protocol: Unless otherwise specified, each run consists of T = 400 rounds. For GP-based policies, each run begins with 50 rounds of uniformly random exploration. Thereafter, the surrogate models are refitted every five rounds. For each GP, parameter learning is attempted up to 20 times. A fit is considered unsuccessful if none of these attempts produces a numerically valid fit, either because parameter learning does not converge or because the covariance matrix cannot be stably factorized. If the reward GP or any constraint GP cannot be fitted successfully at a round when surrogate refitting is scheduled, the event is counted once as a surrogaterefitting failure. For each failed model, the E2E controller reuses its most recent valid reward or constraint estimate, when available. If any failed surrogate has no valid previous fit, the controller performs random exploration. We report the frequency of such failures using the Surrogate-Refitting Failure Rate defined in Sec. VI-C.
We prepare three baselines: linCBwK [15], CONFIG [30], and Random. They differ in (i) Surrogate Model: how they model reward and resource consumption, (ii) Search Space: which decomposition space they search, and (iii) Selection Algorithm: how they select decompositions, as summarized in Table VIII. We present the settings shared across methods (Sec. VI-B1), formalize the surrogate-model and decomposition search-space options (Sec. VI-B2), and provide the detailed method-specific instantiations (Sec. VI-B3).
2) Surrogate Models and Decomposition Search Spaces: Of the three design dimensions summarized in Table VIII, this subsection formalizes the surrogate-model and decompositionsearch-space options used by the compared methods. (i) Surrogate-Model Options: The two choices for the surrogate-model dimension are a nonlinear GP, and a linear GP. Following the notation in Sec. V-C, we instantiate their kernels on the feature vector ũ(z) as follows. (nonlinear): The Matérn-5/2 kernel with automatic relevance
XT = ∆2 ,
Xg = (∆2 )3 ,
X = (∆2 )4 .
(45)
5) Runtime: All experiments were run in a Docker container on an Intel Xeon Platinum 8468 server (2 sockets × 48 physical cores, 192 logical CPUs) with 256 GB RAM. The kernel version was Linux 5.15.0. The Python runtime was Python 3.12.12, and the BO/GP stack comprised PyTorch 2.10.0, BoTorch 0.16.1, and GPyTorch 1.15.1 [46]–[48].
20
CN
CN (wAN , wTN , wCN ) = (0.2, 0.2, 0.6)
wlb wd ≥ wlb
TN
AN (1) Continuous Region W
cont
AN (wlb )
TN
disc (2) Discrete Region W0.2 (wlb )
Fig. 7. Continuous and discrete candidate regions for a single simplex field. (1) Continuous: W cont (wlb ) = {w ∈ ∆2 | wd ≥ wlb , ∀d}. (2) Discrete: disc (w ) for ∆ W∆ lb grid = 0.2; filled black points are retained candidates. grid
determination (ARD) is defined by √ √ 5 2 k •,Mat (z, z ′ ) := σk,• 1 + 5 r• + r•2 e− 5r• , 3 D X (ũj (z) − ũj (z ′ ))2 where r•2 := . ℓ2•,j j=1
(46) (47)
(linear): The linear kernel is defined by 2 k •,Lin (z, z ′ ) := σk,• ũ(z)⊤ ũ(z ′ ).
(48)
2 Here, σk,• denotes the kernel output scale for target •. The Matérn-5/2 form provides a standard nonlinear GP prior with moderate smoothness on ũ(z) [50], and ARD assigns dimension-specific length-scales {ℓ•,j }D j=1 to capture anisotropy across feature dimensions. (ii) Search-space Options: Recall from (45) that the experimental decomposition space is X = (∆2 )4 . For numerical stability, all methods restrict X by imposing the coordinate-wise lower bound wlb = 0.05 on every simplex field. Continuoussearch methods use this restricted region directly, whereas discrete-search methods use its grid-discretized subset. (continuous): For a single simplex field, define the lowerbounded continuous region as W cont (wlb ) := {w ∈ ∆2 | wd ≥ wlb , ∀d ∈ D}. The corresponding search space is 4 Xcont (wlb ) := W cont (wlb ) . (49) disc (discrete): For a single simplex field, let W∆ (wlb ) ⊆ grid cont W (wlb ) denote the grid-discretized subset of the continuous region. Here, ∆grid > 0 is the simplex grid step size, disc i.e., W∆ (wlb ) keeps feasible points whose coordinates lie grid on the ∆grid -spaced lattice, so smaller ∆grid yields a finer discretization and a larger candidate set. The corresponding four-field search space is 4 disc (w ) . (50) X∆grid (wlb ) := W∆ lb grid
Thus, X∆grid (wlb ) is the grid-discretized subset of Xcont (wlb ). Fig. 7 visualizes this construction for a single simplex field. 3) Method-Specific Instantiations: We now specify the implementation of each method. (i) CCKB (Ours): For the reward target f and every constraint target mΓd,j , CCKB uses the nonlinear Matérn-5/2 kernel with ARD defined in (46)–(47) , i.e., k f = k f,Mat and Γ Γ k md,j = k md,j ,Mat for all (d, j). The primal step optimizes At (x | st ) over Xcont (wlb ).
(ii) linCBwK [15]: For the reward target f and every constraint target mΓd,j , linCBwK uses the linear-kernel GP Γ Γ defined in (48) , i.e., k f = k f,Lin and k md,j = k md,j ,Lin for all (d, j). With the linear kernel, each GP posterior mean is linear in the common feature vector ũ(z) , as in Bayesian linear regression [41], thereby recovering (L2) linear realizability assumed in our previous method [15]. Its primal step evaluates At (x | st ) for every x ∈ X∆grid (wlb ) and selects a maximizer. By the four-field construction above, the number of candidates 4
disc (wlb ) . We use ∆grid = 0.2 to is X∆grid (wlb ) = W∆ grid keep exhaustive evaluation tractable, yielding 1296 candidate decompositions. (iii) CONFIG [30]: Odin [14] minimizes a sum of unknown domain-level cost functions subject to an E2E SLA constraint, whereas our formulation maximizes provisioning reward subject to cumulative resource-budget constraints. A direct implementation of Odin would therefore require changing our objective and constraint model. Instead, we use CONFIG, the non-contextual constrained-BO method on which Odin’s design is based, as the decomposition-selection algorithm under our formulation. CONFIG uses the same GP kernels as CCKB. To retain CONFIG’s non-contextual structure, we fix the NSR component of every GP input to the first-round request, i.e., ztcfg = (s1 , xt ), rather than (st , xt ). Consequently, CONFIG selects xt without conditioning on the current request st . Finally, CONFIG searches over Xcont (wlb ). (iv) Random: Each round samples a feasible decomposition from Xcont (wlb ).
C. Evaluation Metrics We use (i) Total Reward as the primary performance metric. We additionally use (ii) Resource Usage Ratio to examine how each policy distributes resource consumption across domains. For surrogate-based policies, we report (iii) Surrogate-Refitting Failure Rate to assess the numerical reliability of methods. Under mixed traffic, we report both Total Reward and SuccessfulSlice Count, together with a per-class breakdown; Sec. VI-E explains why both aggregate metrics are needed. For each policy under each experimental setting, we perform multiple T -round runs with different random seeds. We report Total Reward and Resource Usage Ratio as the mean and standard deviation across runs. In contrast, each reported Surrogate-Refitting Failure Rate pools the failed and scheduled refitting operations over all runs covered by that result. (i) Total Reward: We define the total reward as R :=
T X
κprice (st ) yt .
t=1 avail (ii) Resource Usage Ratio: Let CT,d,j denote the remaining capacity of resource (d, j) at the end of one run. The usage ratio is defined as
ud :=
Jd max avail Cd,j − CT,d,j 1 X . max Jd j=1 Cd,j
21
(iii) Surrogate-Refitting Failure Rate: We first define the number of surrogate-refitting failures in one run as Cfit :=
T X
1[surrogate refitting fails at round t] .
t=1
A scheduled refitting operation is counted once as a failure if the reward GP or any constraint GP exhausts its fitting attempts without a valid fit. This metric is not applicable to Random, which does not fit surrogate models. D. Overall Effectiveness Across Topologies and Domain Bottlenecks 1) Setup: We consider only the URLLC class, corresponding to α = 0 in the mixed-NSR model PNSR mix . We evaluate all four topology configurations in Fig. 6 under three domain-bottleneck profiles, each of which reduces the resource availability of the AN, TN, or CN. These combinations yield 12 experimental conditions, each of which is evaluated over 10 runs with different random seeds. The bottleneck profiles are implemented using the resourceavailability vector (aAN , aTN , aCN ), where the capacity of max resource j ∈ [Jd ] in each domain d ∈ D is scaled to ad Cd,j . We use (0.2, 1.0, 1.0), (1.0, 0.2, 1.0), and (1.0, 1.0, 0.2) for the AN, TN, and CN bottleneck profiles, respectively. 2) Result: The comparison yields the three observations. Total Reward: Across the 12 topology–bottleneck conditions, CCKB achieves higher mean Total Reward than linCBwK in every condition (Fig. 8). This consistent improvement supports the practical effectiveness of CCKB’s two extensions over linCBwK that directly relax (L1) finite/discrete decomposition search and (L2) linear realizability. Compared with CONFIG, CCKB achieves higher mean Total Reward in 9 of the 12 conditions. The exceptions are Tree dual-UPF with an AN bottleneck, Tree dual-UPF with a CN bottleneck, and Ring with a TN bottleneck, for which the reward gaps are visually small in Fig. 8. This comparison indicates that jointly addressing the two NSR-DP requirements, (R1) long-horizon multi-resource budget control and (R2) request-conditioned decomposition, is practically important. Resource Usage Ratio: Fig. 9 provides a complementary view of resource allocation. The bottleneck domain exhibits the highest usage ratio and is typically close to saturation across methods and conditions. Overall, CCKB, linCBwK, and CONFIG tend to show higher usage ratios in non-bottleneck domains than Random. For CONFIG, however, higher non-bottleneck usage does not always translate into higher mean Total Reward. For example, under the Tree topology with a TN bottleneck, CONFIG places heavier load on non-bottleneck domains than CCKB but obtains lower mean Total Reward. Our failurecase inspection shows that CONFIG sometimes assigns overly strict domain latency targets δt,d to selected non-bottleneck domains. When δt,d is smaller than the propagation delay required in the corresponding domain, slice construction fails. A plausible explanation for selecting such targets is degraded reward-model fidelity under CONFIG’s context-agnostic GP
TABLE IX S URROGATE -R EFITTING FAILURE R ATE BY METHOD , AGGREGATED OVER ALL TOPOLOGY– BOTTLENECK CONDITIONS .
CCKB
linCBwK
CONFIG
Random
0/8,400 (0.00%)
407/8,400 (4.85%)
0/8,400 (0.00%)
N/A
evaluation, which may overestimate the benefit of strict decompositions and misjudge their provisioning success. Surrogate-Refitting Failure Rate: Table IX summarizes the surrogate-refitting failure rate. CCKB and CONFIG complete all 8,400 scheduled refitting operations without failure, whereas linCBwK fails in 407 of 8,400 operations (4.85%); the metric is not applicable to Random because it does not fit surrogate models. This failure rate directly indicates lower numerical fitting stability for linCBwK in this setting and motivates the follow-up negative log predictive density (NLPD) analysis of surrogate fidelity in Sec. VI-D3. 3) Follow-up Analysis: To further examine the surrogate fidelity suggested by the resource-usage and refitting-stability results, we use the Tree topology with an AN bottleneck as a focused diagnostic condition and compare the constraint-GP NLPD trajectories. Here, NLPD is used as a surrogate-fit metric; lower values indicate better fit. Fig. 10 shows a consistent ordering: CCKB keeps the lowest NLPD, CONFIG is lower than linCBwK but still above CCKB, and linCBwK remains highest with the broadest dispersion. Thus, the contextual nonlinear constraint-GP in CCKB provides the best predictive fit among the compared surrogates in this condition, while linCBwK’s poorer fit is consistent with the higher surrogaterefitting failure rate in Table IX. E. Robustness to Heterogeneous Requests 1) Setup: We consider the Tree and Ring topologies under all three bottleneck profiles, yielding six topology–bottleneck conditions. For each condition, we vary the eMBB mixing ratio over α ∈ {0, 0.02, 0.04, 0.06, 0.08}. Each condition is evaluated over 10 runs with different random seeds. Mixture Range: We determine the sweep range from the aggregate mean offered traffic rate of each request class before provisioning and resource-allocation decisions, rather than from the request counts alone. For each class, this rate is the product of the number of covered gNBs, the packetarrival rate per gNB, and the mean packet size. Let Lurllc and Lembb denote the corresponding class-specific rates. Under the settings in Table S2, a URLLC request covers three gNBs and generates Lurllc = 3 × 20,000 × 1,600 = 96 Mbit/s, whereas an eMBB request covers nine gNBs and generates Lembb = 9×15,000×9,600 = 1,296 Mbit/s. Thus, one eMBB request generates 13.5 times as much offered traffic as one URLLC request. Consequently, the request mixing ratio alone does not reflect how strongly the introduced eMBB requests affect the aggregate offered traffic. The two classes contribute equally to the mean offered traffic at α⋆ = Lurllc /(Lembb + Lurllc ) ≈ 0.069. Because α = 0.08 is the first tested ratio above this balanced point, the sweep captures the intended transition from URLLC-only traffic to a mixed workload in
22
(i) Tree
CCKB (Ours)
linCBwK
CONFIG
Random
TN
CN
AN
TN
(ii) Tree dual-UPF
(iii) Ring
(iv) Ring dual-UPF
Mean total reward
300 200 100 0
AN
TN
CN
AN
CN
AN
TN
CN
Fig. 8. Mean Total Reward under the three domain-bottleneck profiles for CCKB, linCBwK, CONFIG, and Random: (i) Tree, (ii) Tree dual-UPF, (iii) Ring, and (iv) Ring dual-UPF. Each subplot corresponds to one topology, and each AN, TN, or CN label denotes the bottleneck domain d, for which ad = 0.2, while ad′ = 1.0 for every other domain d′ ̸= d. Bars and whiskers show the mean and standard deviation over 10 runs, respectively. Higher is better.
Bottleneck: AN Bottleneck: TN
50
Bottleneck: CN
50
Resource usage ratio (%)
50
0 100
0 100
0
CCKB (Ours)
(i) Tree
100
linCBwK
(ii) Tree dual-UPF
CONFIG
Random
(iii) Ring
(iv) Ring dual-UPF
AN
TN
CN
AN
TN
CN
AN
TN
CN
AN
TN
CN
AN
TN
CN
AN
TN
CN
AN
TN
CN
AN
TN
CN
AN
TN
CN
AN
TN
CN
AN
TN
CN
AN
TN
CN
Fig. 9. Resource Usage Ratio at the end of each run for CCKB, linCBwK, CONFIG, and Random. Bars show the mean, and whiskers show the standard deviation. Underlined domain labels (e.g., AN) denote the bottleneck; lower values on that domain and higher values on non-bottleneck domains are preferable. 0.5
CCKB (Ours) linCBwK CONFIG
0.0
Mean NLPD
-0.5 -1.0 -1.5 -2.0 50
100
150
200
Round
250
300
350
400
and constraint exploration estimates for URLLC and eMBB requests. Let ct ∈ C := {URLLC, eMBB} denote the class of the round-t NSR. For each class k ∈ C, let fˆt,k and {ĥt,d,j,k }d,j denote its raw reward and constraint exploration estimates. The active estimates at round t are constructed as X fˆt (st , x) := 1{ct = k} fˆt,k (st , x), (51) k∈C
Fig. 10. Constraint-GP NLPD trajectories under the Tree topology with an AN bottleneck. Lines show the means over 10 runs, and shaded bands show cross-run variability. Lower values indicate better predictive quality.
which the two classes make comparable contributions to the aggregate mean offered traffic. Evaluation Metric: Under mixed traffic, we report two metrics. Total Reward is the optimization objective itself. However, eMBB requests are few in number, and each is priced 50 times higher than a URLLC request. Total Reward is therefore largely determined by the small number of admitted eMBB slices. This number varies considerably across seeds, and the differences between methods are comparable to or smaller than that variation. Total Reward therefore has limited resolution for comparing methods. We use Successful-Slice Count as the primary metric because it is less sensitive to this variation, and report Total Reward and the per-class breakdown in Appendix I. Class-Specific Exploration Estimates: To avoid pooling observations from request classes with substantially different traffic loads and SLA parameters, we maintain separate reward
ĥt,d,j (st , x) :=
X
1{ct = k} ĥt,d,j,k (st , x).
(52)
k∈C
By (51) and (52), only the estimates matching the arriving request class are evaluated and updated, while the primal–dual control loop remains unified.4 We apply the same class-specific split to CCKB, linCBwK, and CONFIG, so their performance differences are not attributable to class separation. 2) Result: CCKB attains the highest mean in five, six, five, four, and five of the six conditions at α = 0, 0.02, 0.04, 0.06, and 0.08, respectively (Fig. 11). Equivalently, it ranks first in 25 of the 30 evaluated points: 14 of 15 in the Tree topology and 11 of 15 in the Ring topology. Excluding the URLLC-only baseline, CCKB remains best in 20 of the 24 heterogeneous-traffic points, showing that its mean-count advantage persists throughout the sweep toward bandwidthbalanced traffic rather than being confined to the singleclass setting. The five exceptions are concentrated in the TN 4 The class-specific construction does not share observations across request classes. Consequently, each model is trained on fewer observations than a shared cross-class model; developing a model that exploits similarities between the two classes is left for future work.
23
320
(1) AN bottleneck
(2) TN bottleneck
280
Mean successful slices
240
(3) CN bottleneck
CCKB (Ours) linCBwK CONFIG Random
TABLE X FACTORIAL A BLATION D ESIGN (2 × 2): S URROGATE M ODELS AND D ECOMPOSITION S EARCH S PACES .
200 160 120 80 40 00.00 0.02 0.04 0.06 0.08
0.00 0.02 0.04 0.06 0.08
0.00 0.02 0.04 0.06 0.08
Method
(i) Surrogate Model
(ii) Search Space
CCKB (Ours) Lin-Cont Mat-Disc linCBwK
Nonlinear GP Linear GP Nonlinear GP Linear GP
Continuous Continuous Discrete Discrete
400
CCKB Lin-Cont
Mat-Disc linCBwK
TN
CN
320
(1) AN bottleneck
(2) TN bottleneck
280
Mean successful slices
240
(3) CN bottleneck
CCKB (Ours) linCBwK CONFIG Random
300 200
200 160
100
120 80
0
40 00.00 0.02 0.04 0.06 0.08
Mean total reward
(a) Tree topology.
0.00 0.02 0.04 0.06 0.08
0.00 0.02 0.04 0.06 0.08
AN
Fig. 12. Mean Total Reward by bottleneck for four ablation variants on the Tree topology (error bars indicate standard deviation).
(b) Ring topology. Fig. 11. Mean number of successfully provisioned NSs over 10 runs as the eMBB mixing ratio varies over α ∈ {0, 0.02, 0.04, 0.06, 0.08} under AN, TN, and CN bottleneck conditions in (a) Tree and (b) Ring topologies.
bottleneck (Tree at α = 0.04 and Ring at α ∈ {0, 0.06, 0.08}) and Ring–CN at α = 0.06. Even at these points, the largest absolute deficit from CCKB to the best competing mean is 3.4 successfully provisioned slices, and the largest relative deficit is 3.2% of the competing mean. Thus, the few ranking reversals are small compared with the overall admission levels. Appendix I reports Total Reward and the per-class breakdown for the same runs. CCKB attains higher Total Reward than linCBwK at 23 of the 24 mixed-traffic points (mean +19) and than Random at all 24 (mean +77), consistent with the Successful-Slice Count ranking. Against CONFIG, the comparison is mixed (15 of 24, mean +6): averaged over the mixing ratios, CCKB admits more URLLC slices in each topology–bottleneck condition, and eight of the nine points where CONFIG leads are driven by the eMBB component rather than by URLLC admissions. F. Effects of Relaxing (L1) and (L2) 1) Setup: The setup follows Sec. VI-D1, except that we focus on the Tree topology and evaluate its three bottleneck conditions. Ablation Design: To isolate the effects of the two improvements addressing (L1) and (L2), we compare four variants obtained by independently combining two surrogate-model options (nonlinear and linear GPs) and two decomposition search-space options (continuous and discrete). Table X summarizes the resulting 2 × 2 design. For both the reward and constraint surrogates, the nonlinear GP option uses k •,Mat , whereas the linear GP option uses k •,Lin . These kernels are defined in (46)–(47) and (48), respectively. The continuous-search variants optimize over
Xcont (wlb ) defined in (49), whereas the discrete-search variants evaluate all candidates in X∆grid (wlb ) defined in (50). All parameter settings are identical to those used in the preceding experiments. 2) Result: The ablation yields two main observations. Total Reward: CCKB achieves the highest mean Total Reward in all three bottleneck conditions (Fig. 12). The comparison with Lin-Cont indicates that, under the same continuous search space, the nonlinear GP instantiation is more effective than the linear GP instantiation. The comparison with MatDisc further shows that, under the same nonlinear surrogate model, continuous search is also beneficial. By contrast, LinCont does not consistently outperform linCBwK, suggesting that enlarging the search space alone does not overcome the limitations of linear reward and constraint surrogates. Surrogate-Refitting Failure Rate: The reward comparison alone does not reveal the numerical stability of the surrogate models. Table XI shows that CCKB completes all 2,100 scheduled surrogate-refitting operations without failure, whereas the other three designs exhibit nonzero failure rates. Thus, among the compared designs, CCKB achieves the highest Total Reward while maintaining stable surrogate refitting.
G. Effect of Addressing (L3) 1) Setup: The setup follows Sec. VI-F1. Ablation Design: We compare three variants that differ only in the sample selection rule used for the constraint proxy learner: (i): CCKB uses only samples from rounds satisfying both yτ = 1 and 1Γd,j (sτ ) = 1, (ii): Path-Only removes the condition yτ = 1 and uses samples satisfying 1Γd,j (sτ ) = 1, and (iii): No-Filter uses all observations and directly learns the relaxed-NSR-DP constraint hd,j . The samples retained by
24
TABLE XI S URROGATE -R EFITTING FAILURE R ATE FOR THE SURROGATE - MODEL / SEARCH - SPACE ABLATION ON THE T REE TOPOLOGY. CCKB
Lin-Cont
Mat-Disc
linCBwK
0/2,100 (0.00%) 71/2,100 (3.38%) 235/2,100 (11.19%) 86/2,100 (4.10%)
the three variants are (i)
CCKB:
(ii) Path-Only: (iii) No-Filter:
(zτ , uτ,d,j ) (zτ , uτ,d,j ) (zτ , uτ,d,j )
τ ∈[t−1], yτ =1, 1Γ d,j (sτ )=1 τ ∈[t−1], , 1Γ d,j (sτ )=1
,
τ ∈ [t − 1] .
2) Result: The filter ablation yields two observations. Total Reward: CCKB achieves the highest mean Total Reward in all three bottleneck conditions (Fig. 13(a)), supporting the practical benefit of using both filters in the proxy construction. All three variants complete all 2,100 scheduled refitting operations without failure, so this reward comparison is not confounded by surrogate-refitting instability. Constraint-Surrogate Fit: The constraint GP in CCKB attains the lowest NLPD (Fig. 13(b)), showing that the combined filters also provide the best predictive fit among the three variants. Path-Only is lower than No-Filter in the early rounds, but its NLPD deteriorates once resource depletion starts (e.g., around round 260 in the AN-bottleneck case). Together, the reward and NLPD results support learning the proxy target hprx d,j with both sample-selection filters rather than directly learning hd,j from all observations, thereby supporting the practical effectiveness of the proposed treatment of (L3). H. Effects of Mechanisms for (R1) and (R2) 1) Setup: The setup follows Sec. VI-F1. Ablation Design: We compare CCKB with three variants: w/o Context removes context conditioning, w/o Dual removes dual-based budget control, and w/o Context & Dual removes both components. All four variants use the same kernel, continuous search space, training protocol, and hyperparameters. Among the ablation variants, w/o Context retains the primal–dual mechanism and therefore corresponds to a noncontextual, proxy-based CKB instantiation. (w/o Context): To ablate the request conditioning used to address (R2), the two variants without context conditioning use the same fixed-request surrogate-input construction as that used for CONFIG in Sec. VI-B3. Specifically, we replace the current request st with the first-round request s1 , evaluating the surrogates at (s1 , x), rather than (st , x). (w/o Dual): To ablate the dual-based budget control used to address (R1), the two variants without dual-based budget control skip the dual update in Line 14 of Algorithm 1, so the dual variables remain at zero. Consequently, the dual penalty is inactive throughout the run. 2) Result: Fig. 14 shows that CCKB achieves the highest mean Total Reward in all three bottleneck conditions. Relative to CCKB, w/o Dual reduces the mean reward by 74.2, 80.0, and 62.3 under the AN, TN, and CN bottlenecks, respectively. By contrast, w/o Context yields smaller reductions of 19.9, 6.7, and 7.0, respectively. w/o Dual and w/o Context & Dual
form the lower-performing pair in every condition, with only a small additional difference between them. All four variants complete all 2,100 scheduled surrogaterefitting operations without failure (0/2,100 per method); therefore, we omit a separate failure-rate table for this ablation, and the reward differences are not confounded by surrogaterefitting instability. These descriptive results suggest that the dual-based mechanism for (R1) provides the dominant contribution, while the context-conditioning mechanism for (R2) provides a smaller complementary improvement. I. Computational Scalability 1) Setup: Unless stated below, the setup follows Sec. VI-F1. We use five runs with different random seeds, refit the GP models every round, and impose no domain bottleneck by setting the resource-availability vector to (aAN , aTN , aCN ) = (1.0, 1.0, 1.0). Experiment Design: We use the Tree topology and increase the network size as |A| ∈ {12, 24, 36, 48} and |R| ∈ {4, 8, 12, 16}. We compare CCKB, linCBwK, and Random under the same CPU allocation, which averages 9 cores per run. CONFIG is omitted because its runtime is likewise dominated by the same GP computations as CCKB; including it would therefore not provide a distinct scaling comparison. 2) Result: The evaluation yields two main observations. Per-Round Runtime: Fig. 15a shows that CCKB has the highest per-round runtime, followed by linCBwK, while Random is much lower. At |A| = 12, the mean per-round runtime is 8.64 s for CCKB, 1.39 s for linCBwK, and 0.045 s for Random. Although the measured operations differ, CCKB’s computational overhead is below the approximately 30 s reported for the instantiation of an NS on an experimental multi-slice platform [51], suggesting compatibility with orchestration workflows operating on a timescale of tens of seconds. CCKB’s per-round runtime increases gradually over the horizon, whereas linCBwK remains lower and Random remains nearly constant. The gradual growth under CCKB is consistent with the selective updates in its constraint-surrogate construction limiting the growth of effective training samples. Scaling with Network Size: Fig. 15b shows monotonic runtime growth for all methods as |A| increases. For CCKB, the total run duration increases approximately linearly with |A| over the tested range. This trend is consistent with the complexity discussion in Sec. VII-A, where the dominant cost scales linearly with the number of resource-side models. VII. D ISCUSSION A. Time Complexity and Implementation Remarks We compare the computational complexity of the proposed method with that of our previous method [15]. We focus on the dominant cost of constructing the estimates fˆt and ĥprx t,d,j , from which the clipped surrogates used by CCKB are obtained. In our previous method [15], the corresponding reward and constraint estimates are computed by linear regression with a fixed p-dimensional parameter vector. When the inverse covariance matrix is updated recursively via the Sherman– Morrison formula [52], the per-model update cost is O(p2 ).
25
400 300
AN Bottleneck
Mean NLPD
Mean total reward
CCKB Path-Only No-Filter
CCKB
Path-Only
TN Bottleneck
No-Filter
CN Bottleneck
-1.5
200 100
-2.0
0
AN
TN
100
CN
200
Round
300
(a) Mean Total Reward by bottleneck.
400
100
200
Round
300
400
100
200
Round
300
400
(b) Constraint GP NLPD history by bottleneck.
Fig. 13. Effects of the proxy-construction filters. (a) Mean Total Reward. (b) Constraint-GP NLPD trajectories; lower values indicate better predictive fit.
CCKB w/o Context
Mean total reward
300
w/o Dual w/o Context & Dual
200 100 0
AN
TN
CN
Fig. 14. Mean Total Reward by bottleneck for the four context/dual ablation variants on the Tree topology (error bars indicate standard deviation).
25
Step Duration (s)
B. Rationale for the Proxy Design
CCKB linCBwK Random
20 15 10 5 0
0
50
100
150
200
Step
250
300
350
400
(a) Per-round runtime at |A| = 12.
8000
Run Duration (s)
CCKB linCBwK Random
6000 4000 2000 0
12
Sec. V-C1. Thus, at round t, the dominant per-model update cost is O(t3 ) in the worst case. Since the number of constraint models is again on the order of Jtot , the per-round complexity is upper-bounded by O(Jtot t3 ). Summing this from t = 1 to T , the total computational complexity becomes O(Jtot T 4 ). Hence, compared with our previous method [15], the current exact-GP implementation significantly increases the computational cost from O(Jtot p2 T ) to O(Jtot T 4 ). This suggests that, although the proposed method improves modeling flexibility, further acceleration techniques such as sparse/approximate GP methods [53], [54] will be important.
24
gNB Count
36
48
(b) Total runtime per T = 400-round run as |A| increases. Fig. 15. Runtime scalability over five runs. Lines in (a) and markers in (b) show the means, and bands show the 10th–90th percentiles across runs.
Since the number of constraint models is on the order of the total number of resources Jtot , the per-round computational complexity is O(Jtot p2 ). Therefore, over T rounds, the total complexity is O(Jtot p2 T ). By contrast, in the current naive exact-GP implementation of the proposed method, each surrogate update requires inversion of the regularized Gram matrix K•t−1 + η• I specified in
The proxy constraint is learned from resource-consumption observations for successful requests and resources included in the requested NS topology, thereby avoiding the many zero observations described in (L3). It replaces the unknown provisioning-success probability p(s, x) by its upper bound of one. An alternative is to estimate p(s, x) and the conditional mean demand mΓd,j (s, x) separately and multiply the two estimates. This alternative could make the constraint less conservative, but a confidence bound for the resulting constraint would have to account for errors in both estimates and in their product. Moreover, estimating a probability from the binary provisioning outcome generally requires numerical approximation rather than the closed-form calculations used for GP regression of the demand [41]. We therefore use the current proxy because it requires only the demand model and allows us to derive the confidence bounds used in our theoretical analysis. VIII. C ONCLUSION This paper addressed online NSR decomposition in hierarchical 5G management, where an E2E controller must select request-conditioned continuous decompositions while respecting long-horizon multi-resource budgets. We formulated the NSR-DP and introduced CCKB as an online solution for it. CCKB combines primal–dual budget control with contextual GP surrogates to learn nonlinear relationships between requests, decompositions, provisioning success, and resource demand without restricting the search to a finite set of decompositions. To handle zero-dominated resourceconsumption observations caused by rejected requests and resources outside the requested NS topology, we derived a
26
conservative proxy problem for the stationary-response relaxation of the NSR-DP. We established high-probability finitetime regret and cumulative constraint-violation bounds for the proxy problem and transferred both guarantees to the relaxed NSR-DP. The relaxed-problem regret bound includes an explicit additive term that quantifies the optimality gap induced by the proxy formulation. In 5G network simulations, CCKB achieved higher mean Total Reward than linCBwK [15] in all 12 topology–bottleneck conditions and than CONFIG [30] in 9 of the 12 conditions. Extending these guarantees to state-dependent responses and improving scalability through approximate GP updates remain important future directions.
R EFERENCES [1] ITU-R M.2083-0, “IMT Vision–Framework and overall objectives of the future development of IMT for 2020 and beyond,” 2015. [2] J. F. Santos, W. Liu, X. Jiao, N. V. Neto, S. Pollin, J. M. MarquezBarja, I. Moerman, and L. A. DaSilva, “Breaking down network slicing: Hierarchical orchestration of end-to-end networks,” IEEE Commun. Mag., vol. 58, no. 10, pp. 16–22, 2020. [3] ETSI ISG ZSM, “ETSI GS ZSM 003 v1.1.1,” 2021. [4] I. Afolabi, T. Taleb, K. Samdanis, A. Ksentini, and H. Flinck, “Network slicing and softwarization: A survey on principles, enabling technologies, and solutions,” IEEE Commun. Surveys Tuts., vol. 20, no. 3, pp. 2429–2453, 2018. [5] R. Su, D. Zhang, R. Venkatesan, Z. Gong, C. Li, F. Ding, F. Jiang, and Z. Zhu, “Resource allocation for network slicing in 5G telecommunication networks: A survey of principles and models,” IEEE Netw., vol. 33, no. 6, pp. 172–179, 2019. [6] 3GPP, “Management and orchestration; Concepts, use cases and requirements,” Tech. Rep. 3GPP TS 28.530, Version 18.2.0 (Release 18), 2025. [7] ETSI ISG ZSM, “ETSI GS ZSM 002 v1.1.1,” 2019. [8] Y. Chen, S. Iyer, X. Liu, D. Milojicic, and A. Sahai, “SLA decomposition: Translating service level objectives to system level thresholds,” in Proc. Int. Conf. Autonomic Computing (ICAC), 2007, pp. 3–12. [9] ——, “Translating service level objectives to lower level policies for multi-tier services,” Cluster Computing, vol. 11, pp. 299–311, 2008. [10] Ericsson, “Differentiated connectivity entering the market at speed,” 2026. [Online]. Available: https://www.ericsson.com/en/reports-and-papers/mobility-report/ articles/service-packaging-differentiated-connectivity-june-2026 [11] M. Iannelli, M. R. Rahman, N. Choi, and L. Wang, “Applying machine learning to end-to-end slice SLA decomposition,” in Proc. IEEE Conf. Network Softwarization (NetSoft), 2020, pp. 92–99. [12] D. De Vleeschauwer, C. Papagianni, and A. Walid, “Decomposing SLAs for network slicing,” IEEE Commun. Lett., vol. 25, no. 3, pp. 950–954, 2021. [13] C. S.-H. Hsu, D. De Vleeschauwer, and C. Papagianni, “SLA decomposition for network slicing: A deep neural network approach,” IEEE Netw. Lett., vol. 5, no. 4, pp. 294–298, 2023. [14] D. Cheng, R. Sheshadri, A. Kak, N. Choi, X. Zhou, and B. Ji, “Odin: Effective end-to-end SLA decomposition for 5G/6G network slicing via online learning,” in Proc. 26th Int. Symp. Theory, Algorithmic Found., Protocol Design Mobile Netw. Mobile Comput. (MobiHoc), 2025, pp. 131–140. [15] M. Kobayashi, A. Suzuki, and M. Kobayashi, “Optimizing availability decomposition for network slicing using bandit algorithms,” in Proc. 2025 34th Int. Conf. Comput. Commun. Netw. (ICCCN), 2025, pp. 1–9. [16] S. Agrawal and N. R. Devanur, “Linear contextual bandits with knapsacks,” in Adv. Neural Inf. Process. Syst. (NIPS), vol. 29, 2016, pp. 3458–3467. [17] X. Zhou and B. Ji, “On kernelized multi-armed bandits with constraints,” in Adv. Neural Inf. Process. Syst. (NeurIPS), vol. 35, 2022, pp. 14–26. [18] A. Krause and C. S. Ong, “Contextual gaussian process bandit optimization,” in Advances in Neural Information Processing Systems (NIPS), vol. 24, 2011, pp. 2447–2455. [19] Q. Liu, N. Choi, and T. Han, “Onslicing: Online end-to-end network slicing with reinforcement learning,” in Proc. 17th Int. Conf. Emerging Networking EXperiments Technol. (CoNEXT), 2021, pp. 141–153.
[20] Y. Xiao, Q. Zhang, F. Liu, J. Wang, M. Zhao, Z. Zhang, and J. Zhang, “NFVdeep: Adaptive online service function chain deployment with deep reinforcement learning,” in Proc. IEEE/ACM Int. Symp. Quality Service (IWQoS), 2019, pp. 21:1–21:10. [21] H. Bai, Y. Zhang, Z. Zhang, and S. Yuan, “Latency equalization policy of end-to-end network slicing based on reinforcement learning,” IEEE Trans. Netw. Service Manag., vol. 20, no. 1, pp. 88–103, 2023. [22] M. Helmy, A. A. Abdellatif, N. Mhaisen, A. Mohamed, and A. Erbad, “Slicing for AI: An online learning framework for network slicing supporting AI services,” IEEE Trans. Netw. Service Manag., vol. 22, no. 6, pp. 5239–5254, Dec. 2025. [23] Q. Zhang, F. Liu, and C. Zeng, “Online adaptive interference-aware VNF deployment and migration for 5G network slice,” IEEE/ACM Trans. Netw., vol. 29, no. 5, pp. 2115–2128, 2021. [24] L. Tang, G. Zhao, C. Wang, P. Zhao, and Q. Chen, “Queue-aware reliable embedding algorithm for 5G network slicing,” Computer Networks, vol. 146, pp. 138–150, 2018. [25] J. L. Vieira, E. L. C. Macedo, A. L. E. Battisti, J. Noce, P. F. Pires, D. C. Muchaluat-Saade, A. C. B. Oliveira, and F. C. Delicato, “Mobility-aware SFC migration in dynamic 5G-edge networks,” Computer Networks, vol. 250, p. 110571, 2024. [26] J. S. Camargo, E. Coronado, W. Ramirez, D. Camps-Mur, S. S. Deutsch, J. Pérez-Romero, A. Antonopoulos, O. Trullols-Cruces, S. GonzalezDiaz, B. Otura, and G. Rigazzi, “Dynamic slicing reconfiguration for virtualized 5G networks using ML forecasting of computing capacity,” Computer Networks, vol. 236, p. 110001, 2023. [27] W.-K. Chen, Y.-F. Liu, Y.-H. Dai, and Z.-Q. Luo, “QoS-aware and routing-flexible network slicing for service-oriented networks,” IEEE Trans. Netw. Service Manag., vol. 22, no. 6, pp. 6021–6036, Dec. 2025. [28] C. S.-H. Hsu, C. Papagianni, P. Grosso, and D. De Vleeschauwer, “Online SLA decomposition: Enabling real-time adaptation to evolving network systems,” in Proc. 2025 Joint Eur. Conf. Netw. Commun. 6G Summit (EuCNC/6G Summit), 2025, pp. 55–60. [29] C. S.-H. Hsu, C. Papagianni, and P. Grosso, “RAILS: Risk-aware iterated local search for joint SLA decomposition and service provider management in multi-domain networks,” in Proc. 2025 IEEE 26th Int. Conf. High Perform. Switching Routing (HPSR), 2025, pp. 174–179. [30] W. Xu, Y. Jiang, B. Svetozarevic, and C. Jones, “Constrained efficient global optimization of expensive black-box functions,” in Proc. 40th Int. Conf. Mach. Learn. (ICML), vol. 202, 2023, pp. 38 485–38 498. [31] Z. Shi and A. Eryilmaz, “A bayesian approach for stochastic continuumarmed bandit with long-term constraints,” in Proc. 25th Int. Conf. Artif. Intell. Statist. (AISTATS), vol. 151, 2022, pp. 8370–8391. [32] J. A. Ayala-Romero, A. Garcia-Saavedra, and X. Costa-Perez, “Riskaware continuous control with neural contextual bandits,” Proc. AAAI Conf. Artif. Intell., vol. 38, no. 19, pp. 20 930–20 938, Mar. 2024. [33] Y. Han, J. Zeng, Y. Wang, Y. Xiang, and J. Zhang, “Optimal contextual bandits with knapsacks under realizability via regression oracles,” in Proc. 26th Int. Conf. Artif. Intell. Statist. (AISTATS), vol. 206, 2023, pp. 5011–5035. [34] A. Slivkins, X. Zhou, K. A. Sankararaman, and D. J. Foster, “Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression,” J. Mach. Learn. Res., vol. 25, no. 394, pp. 1–37, 2024. [35] H. Guo and X. Liu, “Stochastic constrained contextual bandits via lyapunov optimization based estimation to decision framework,” in Proc. 37th Conf. Learn. Theory (COLT), vol. 247, 2024, pp. 2204–2231. [36] H. Guo, L. Zu, and X. Liu, “Triple-optimistic learning for stochastic contextual bandits with general constraints,” in Proc. 42nd Int. Conf. Mach. Learn. (ICML), vol. 267, 2025, pp. 21 252–21 276. [37] W. Xu, Y. Jiang, B. Svetozarevic, and C. N. Jones, “Primal-dual contextual bayesian optimization for control system online optimization with time-average constraints,” in Proc. 62nd IEEE Conf. Decis. Control (CDC), 2023, pp. 4112–4117. [38] A. Badanidiyuru, J. Langford, and A. Slivkins, “Resourceful contextual bandits,” in Proc. 27th Conf. Learn. Theory (COLT), vol. 35, 2014, pp. 1109–1134. [39] Generic Network Slice Template, GSMA Permanent Reference Document NG.116, Version 10.0, 2024. [40] D. Kraft, “A software package for sequential quadratic programming,” DFVLR German Aerospace Center, Institute for Flight Mechanics, Oberpfaffenhofen, Germany, Tech. Rep. DFVLR-FB 88-28, 1988. [41] C. E. Rasmussen and C. K. I. Williams, Gaussian Processes for Machine Learning, ser. Adaptive Computation and Machine Learning. Cambridge, MA: MIT Press, 2006. [42] Han Li, “5G Transport Network Requirements, Architecture and Key Technologies,” ITU-T Workshops and Seminars, China Mobile, Geneva,
27
Switzerland, 2017. [Online]. Available: https://www.itu.int/en/ITU-T/ Workshops-and-Seminars/20171016/Documents/2.%20Han%20Li.pdf [43] ITU-R, “Minimum requirements related to technical performance for IMT-2020 radio interface(s),” Tech. Rep. ITU-R M.2410-0, 2017. [44] 3GPP, “System Architecture for the 5G System (5GS),” Tech. Rep. 3GPP TS 23.501, Version 18.10.0 (Release 18), 2025. [45] ——, “Study on physical layer enhancements for NR ultra-reliable and low latency case,” Tech. Rep. 3GPP TR 38.824, Version 16.0.0 (Release 16), 2019. [46] PyTorch, 2026. [Online]. Available: https://pytorch.org/ [47] BoTorch, 2026. [Online]. Available: https://botorch.org/ [48] GPyTorch, 2026. [Online]. Available: https://gpytorch.ai/ [49] K. Kandasamy, J. Schneider, and B. Poczos, “High dimensional bayesian optimisation and bandits via additive models,” in Proc. 32nd Int. Conf. Mach. Learn. (ICML), vol. 37, 2015, pp. 295–304. [50] B. Matérn, Spatial Variation, 2nd ed., ser. Lecture Notes in Statistics. Springer, 1986, vol. 36. [51] G. García-Avilés, M. Gramaglia, P. Serrano, F. Gringoli, S. FuentePascual, and I. Labrador-Pavón, “Experimenting with open source tools to deploy a multi-service and multi-slice mobile network,” Comput. Commun., vol. 150, pp. 1–12, Jan. 2020. [52] J. Sherman and W. J. Morrison, “Adjustment of an inverse matrix corresponding to a change in one element of a given matrix,” The Annals of Mathematical Statistics, vol. 21, no. 1, pp. 124–127, 1950. [53] J. Quiñonero-Candela and C. E. Rasmussen, “A unifying view of sparse approximate gaussian process regression,” Journal of Machine Learning Research, vol. 6, no. 65, pp. 1939–1959, 2005. [54] M. Titsias, “Variational learning of inducing variables in sparse gaussian processes,” in Proc. 12th Int. Conf. Artif. Intell. Stat. (AISTATS), vol. 5, 2009, pp. 567–574. [55] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, U.K.: Cambridge University Press, 2004. [56] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” Journal of the American Statistical Association, vol. 58, no. 301, pp. 13–30, 1963. [57] K. Azuma, “Weighted sums of certain dependent random variables,” Tohoku Mathematical Journal, vol. 19, no. 3, pp. 357–367, 1967. [58] S. R. Chowdhury and A. Gopalan, “On kernelized multi-armed bandits,” in Proc. 34th Int. Conf. Mach. Learn. (ICML), vol. 70, 2017, pp. 844– 853. [59] C. D. Aliprantis and K. C. Border, Infinite Dimensional Analysis: A Hitchhiker’s Guide, 3rd ed. Berlin, Germany: Springer, 2006. [60] Y. Efroni, S. Mannor, and M. Pirotta, “Exploration-exploitation in constrained MDPs,” 2020, arXiv:2003.02189. [61] N. Srinivas, A. Krause, S. Kakade, and M. Seeger, “Informationtheoretic regret bounds for gaussian process optimization in the bandit setting,” IEEE Trans. Inf. Theory, vol. 58, no. 5, pp. 3250–3265, 2012. [62] R. W. Wolff, “Poisson arrivals see time averages,” Oper. Res., vol. 30, no. 2, pp. 223–231, Mar./Apr. 1982. [63] 3GPP, “NR; User Equipment (UE) radio access capabilities,” Tech. Rep. 3GPP TS 38.306, Version 18.6.0 (Release 18), 2025. [64] ——, “NR; Base Station (BS) radio transmission and reception,” Tech. Rep. 3GPP TS 38.104, Version 18.10.0 (Release 18), 2025.
A PPENDIX A P ROOF T HAT D OMAIN -L EVEL G UARANTEES I MPLY THE E2E G UARANTEE This appendix proves the implication in (5): for an admissible decomposition, satisfying every domain-level SLA guarantee implies satisfying the original E2E guarantee. The proof uses one assumption about target achievement after the evaluation conditions hold in every domain, together with the construction of the domain-level evaluation conditions in (2). We first state the assumption and use the latency requirement to explain when the assumption is appropriate (Sec. A-A). We then prove (5) (Sec. A-B). A. Assumption Used in the Proof The proof requires the following assumption about the domain-level target events.
Assumption S1 (Domain-level target events after all evaluation conditions hold). For each s ∈ S, iT∈ [M ], and admissible decomposition x for s such that Prs,x ( d∈D Hd,i (s)) > 0, the following conditions hold: (i) The events Td,i (s, T xT ), d ∈ D, are mutually independent under Prs,x ( · | d′ ∈D Hd′ ,i (s)). (ii) For every d ∈ D, ! \ Hd′ ,i (s) Pr Td,i (s, xT ) s,x
d′ ∈D
= Pr(Td,i (s, xT ) | Hd,i (s)) . s,x
Condition (i) implies that the joint target-achievement probability, conditional on all domain-level evaluation conditions, factorizes as ! \ \ Hd,i (s) Pr Td,i (s, xT ) s,x
d∈D
d∈D
! =
Y
\
Pr Td,i (s, xT )
d∈D
s,x
Hd′ ,i (s) .
d′ ∈D
Condition (ii) states that whether the evaluation conditions also hold in the other domains does not change the targetachievement probability in domain d. Latency Example and Scope: For the latency requirement, Hd,i (s) is the event that the packet is not dropped in domain d, and Td,i (s, xT ) is the event that the delay in domain d does not exceed the limit allocated to domain d. Condition (i) means that, among packets not dropped in any domain, meeting or missing the allocated delay limit in one domain does not make the limits in the other domains more or less likely to be met. Condition (ii) means that, among packets not dropped in domain d, selecting only those also not dropped in any other domain does not make the delay limit in domain d more or less likely to be met. Thus, packets that pass through all other domains are neither more nor less likely to meet the delay limit in domain d. Conditions (i) and (ii) can be appropriate for the hierarchical NS management architecture considered in this paper when each domain-specific controller operates independently, uses resources assigned only to the corresponding domain, and is not affected by a failure or traffic change that simultaneously affects several domains. B. Guarantee Preservation Proof. Fix s ∈ S, i ∈ [M ], and an admissible decomposition xTfor s. Equation (2) and Prs,x (Hi ) > 0 ensure that Prs,x ( d∈D Hd,i (s)) > 0. Assumption S1 gives ! \ \ Pr Td,i (s, xT ) Hd,i (s) s,x
d∈D
d∈D
! (i) Y = Pr Td,i (s, xT )
\
d∈D (ii) Y
d′ ∈D
=
d∈D
s,x
Hd′ ,i (s)
Pr(Td,i (s, xT ) | Hd,i (s)) .
s,x
(S1)
28
TABLE S1 P ROBLEMS AND CCKB INSTANTIATIONS IN THE THEORETICAL ANALYSIS . Analysis Stage
Benchmark Problem
CCKB Instantiation
Generic finite-time guarantee (Theorem 1) Proxy finite-time guarantee (Corollary S2) Transferred finite-time guarantee (Corollary S3) Concrete guarantee with explicit surrogate-error bounds (Corollary S4)
Relaxed NSR-DP (16)
Direct
Proxy problem (25)
Proxy-based
Relaxed NSR-DP (16)
Proxy-based
Remark S1 (Generality of the CCKB guarantee). The finitetime guarantee in Theorem 1 is not limited to network slicing and applies to other bounded contextual constrained decisionmaking problems with the same structure. Specifically, the theorem relies only on the contextual objective and longterm-constraint structure in (16), Assumptions 2, 3, and 4, and the surrogate conditions in (32) and (33), rather than on network-slicing-specific formulation details; the constraintviolation part additionally uses Assumption 5.
Proxy problem (25) and Proxy-based relaxed NSR-DP (16)
To prove (5), assume that all domain-level guarantees in (4) hold. Prs,x (Ti ∩ Hi ) Pr(Ti | Hi ) = s,x Prs,x (Hi ) T (A1) Prs,x Hi ∩ d∈D Td,i (s, xT ) ≥ Prs,x (Hi ) ! \ = Pr Td,i (s, xT ) Hi s,x
d∈D
! (2)
\
= Pr
s,x
Td,i (s, xT )
d∈D
(S1) Y
=
d∈D
\
Hd,i (s)
d∈D
Pr(Td,i (s, xT ) | Hd,i (s)) .
s,x
(S2)
Using the domain-level guarantees in (4) and condition (A2) in Definition 2, Y Pr(Ti | Hi ) ≥ gd,i (s, xg ) ≥ gi . (S3) s,x
d∈D
Hence, whenever all delegated inequalities in (4) hold, the original E2E requirement Prs,x (Ti | Hi ) ≥ gi also holds. Consequently, conditions (A1) and (A2) imply (5) under Assumption S1. A PPENDIX B I NTERMEDIATE R ESULTS AND E XPLICIT B OUNDS
B. Proxy Instantiation prx We now apply Theorem 1 to the proxy problem. Let Esur denote the event on which (C1) and (C2) hold after replacing h and h̄t with hprx and h̄prx t , respectively. On this event, let Wf (T ) and W h (T ) denote the cumulative error bounds in (33) after these replacements. Corollary S2 (Finite-time bounds for proxy-based CCKB). Suppose that the proxy problem admits an optimal policy and that Assumptions 2, 3, and 4 hold. Fix the failure √ probabilities as in Theorem 1, choose ρ > 0, and set V := Jtot T /ρ. (i) Proxy regret: Suppose that the proxy versions of the onesided bounds in (32) and the reward cumulative-error bound in (33) hold jointly with probability at least 1 − αsur . Then, f h − αsur , with probability at least 1 − αctx − αctx Regprx (T ) ≤ Breg (T ),
A. Slater Consequences and Generality The following corollary records the standard consequence of Slater’s theorem used in the finite-time analysis [55, Sec. 5.2.3]. Corollary S1 (Consequence of Slater’s condition). Suppose that the relaxed NSR-DP in (16) admits an optimal policy. Under Assumption 5, its primal and dual optimal values coincide. Moreover, there exist an optimal dual vector ϕ⋆ ≥ 0 and, for the fixed horizon T , a finite bound Λrel T such that (S4)
(S5)
where Breg (T ) is the bound in (34), evaluated using the proxy reward cumulative-error bound. (ii) Proxy constraint violation: Suppose, in addition, that Assumption 5 holds for the proxy problem. For the fixed be a finite bound on the norm of an horizon T , let Λprx T optimal dual vector for that problem, choose ρ ≥ 2Λprx T , and prx suppose that Pr(Esur ) ≥ 1 − αsur . Then, with probability at f h least 1 − αctx − αctx − αsur , Vioprx d,j (T ) ≤ Bvio (T )
This section records the intermediate results and explicit surrogate-error scales underlying Corollary 1. Table S1 summarizes the proof stages.
∥ϕ⋆ ∥1 ≤ Λrel T < ∞.
The proof is provided in Appendix E-A. The same conclusion applies to the proxy problem after replacing h with hprx , provided that the proxy problem admits an optimal policy and Assumption 5 holds. We denote the corresponding proxy dualnorm bound by Λprx T .
(S6)
for every d ∈ D and j ∈ [Jd ], where Bvio (T ) is the bound in (35), evaluated using both proxy cumulative-error bounds. C. Finite-Time Transfer to the Relaxed NSR-DP The per-round optimality gap is defined in (40). Lemma 1 shows that the proxy feasible set is contained in the relaxed feasible set. Because the two problems have the same objective, ∆prx (T ) ≥ 0. The following corollary uses ∆prx (T ) to relate the relaxed and proxy regret and violation metrics for the same realized request–action sequence. Corollary S3 (Finite-time transfer to the relaxed NSR-DP). (i) Regret: On the event in part (i) of Corollary S2, Regrel (T ) = Regprx (T ) + T ∆prx (T ) ≤ Breg (T ) + T ∆prx (T ).
(S7)
29
Here, Regprx (T ) is the cumulative mean-reward difference from the optimal proxy policy, whereas T ∆prx (T ) is the optimal-value difference caused by using the proxy problem. (ii) Constraint violation: On the event in part (ii) of Corollary S2, prx Viorel (S8) d,j (T ) ≤ Viod,j (T ) ≤ Bvio (T ), for every d ∈ D and j ∈ [Jd ]. Proof. The regret identity follows directly from (17), (26), and (40). For the violation bound, (28) gives T X
hd,j (st , xt ) ≤
t=1
T X
hprx d,j (st , xt ).
t=1
Applying the nondecreasing function [ · ]+ and then the corresponding part of Corollary S2 proves the claim.
The proof is provided in Appendix E-D. The following proposition bounds the optimality gap introduced by conservative proxying. Proposition S2 (Proxy optimality gap). Suppose that Assumptions 3, 4, and 8 hold, the relaxed NSR-DP admits an optimal policy, the proxy problem admits an optimal policy, and Assumption 5 holds for hprx . Under these conditions, the proxy problem and the relaxed NSR-DP admit optimal dual vectors. Let ϕ⋆prx and ϕ⋆rel denote such vectors, and, for the fixed horizon T , let finite bounds Λprx and Λrel T satisfy T prx ⋆ ⋆ rel rel ∥ϕprx ∥1 ≤ ΛT , ∥ϕrel ∥1 ≤ ΛT . If ΛT ≤ MT , then 2p̄ 1 X X ⋆ ϕprx,d,j − 1 . (S11) 0 ≤ ∆prx (T ) ≤ T aT d∈D j∈[Jd ]
Consequently, D. Explicit Surrogate Errors and Performance Bounds Corollary S4, the final result of this subsection, gives concrete finite-time bounds on the proxy regret, its transfer to Regrel (T ), and Viorel d,j (T ) for proxy-based CCKB under the GP assumptions in Sec. V-D. To establish this result, the following proposition shows that the reward and proxyconstraint surrogates satisfy the conditions in (32) and (33) with high probability and gives explicit finite-time bounds on the cumulative surrogate errors. Proposition S1 (Concrete bounds on cumulative surrogate errors). Fix a horizon T and failure probabilities αf , αh ∈ (0, 1) whose sum is less than one. Suppose that Assumptions 1, 3, 6, and 7 hold. Define q q Φf (T ; αf ) := T γTf · B f + σ ef γTf + 1 + log α1f . (S9) If Algorithm 1 uses the exploration widths in (37) and (38), then, with probability at least 1 − αf − αh , the proxy versions of the one-sided bounds in (32) hold and Wf (T ) = O(Φf (T ; αf )) . Suppose, in addition, that Assumption 8 holds and MT ≥ ρ. Fix αw ∈ (0, 1) such that αf +αh +αw < 1. For each resource (d, j), define Ψd,j (T ; αf , αh , αw ) " 1 := Φf (T ; αf ) aT v u Γ r m d,j T γT p̄ u J + T log tot + max u t −1 Cd,j αw log 1 + ηmΓ d,j !# r mΓ J tot d,j mΓ × B d,j + σ ed,j γT + 1 + log . αh
Λprx T T
2p̄ −1 . aT
(S12)
The proof is provided in Appendix E-E. Corollary S4 (Concrete finite-time bounds for proxy-based f f h h CCKB). Fix αf , αh , αctx , αctx ∈ (0, 1) such that αctx +αctx + αf + αh < 1. Suppose that Assumptions 1, 2, 3, 4, 6, and 7 hold and that the proxy √ problem admits an optimal policy. Choose ρ > 0, set V := Jtot T /ρ, and use the exploration widths in (37) and (38). f h − αctx − (i) Proxy regret: With probability at least 1 − αctx αf − αh , Regprx (T ) ≤ Bprx (T ) q q p̄ T log αf1 + ρJtot T log αh1 ctx ctx . := O p + Φf (T ; αf ) + ρ Jtot T (S13) (ii) Relaxed NSR-DP regret: If the relaxed NSR-DP also admits an optimal policy, then, on the same event, Regrel (T ) = Regprx (T ) + T ∆prx (T ) ≤ Bprx (T ) + T ∆prx (T ).
(S14)
If, in addition, the conditions of Proposition S2 hold, then 2p̄ Regrel (T ) ≤ Bprx (T ) + Λprx − 1 . (S15) T aT (S10)
Let Ψh (T ; αf , αh , αw ) := (Ψd,j (T ; αf , αh , αw ))d∈D, j∈[Jd ] . prx Then, with probability at least 1 − αf − αh − αw , Esur holds, the preceding bound on Wf (T ) remains valid, and W h (T ) d,j = O(Ψd,j (T ; αf , αh , αw )) for every resource (d, j).
∆prx (T ) ≤
(iii) Constraint violation: Suppose, in addition, that Assumption 8 holds with MT ≥ ρ, that Assumption 5 holds for the proxy constraints, and that, for the fixed horizon T , let ϕ⋆prx be an optimal proxy dual vector and Λprx a finite bound T prx satisfying ∥ϕ⋆prx ∥1 ≤ Λprx < ∞. Choose ρ ≥ 2Λ T T , and fix f h αw ∈ (0, 1) such that αctx + αctx + αf + αh + αw < 1. Then, f h with probability at least 1 − αctx − αctx − αf − α h − α w , q Φf (T ; αf ) 1 + J T log tot h αctx ρ Viorel d,j (T ) ≤ O p + ∥Ψh (T ; αf , αh , αw )∥1 + Jtot T (S16) for every resource (d, j).
30
For fixed ρ, if Φf (T ; αf ) = o(T ), the proxy-regret bound in (S13) is sublinear in T . The relaxed regret in (S14) retains the separate term T ∆prx (T ). The proof is provided in Appendix E-F. A PPENDIX C C ONCENTRATION B OUNDS FOR THE R EALIZED R EQUEST S EQUENCE This section states and proves two bounds that compare quantities evaluated on the realized request sequence with their expectations under the request distribution P. Both proofs use standard concentration inequalities and follow the same three steps: (i) express the target difference as a centered sum, (ii) bound the range of each summand, and (iii) apply a concentration inequality. For a fixed contextual policy, Proposition S3 applies Hoeffding’s inequality because, under Assumption 2, the reward terms form an i.i.d. sum. Proposition S4 instead applies the Azuma–Hoeffding inequality because the weights on the resource-consumption terms may depend on earlier rounds. Proposition S3 (Reward concentration over requests). For any q ∈ Q, define ∆fctx (q, T ) :=
T X
Es∼P [vqf (s)] − vqf (st ) .
t=1
Then, for any δ ∈ (0, 1), with probability at least 1 − δ, r T 2 f log . ∆ctx (q, T ) ≤ p̄ 2 δ f Proof. Fix any q ∈ Q, and let µq := Es∼P vqf (s) . Define Dtf := µfq − vqf (st ). (i) Centered i.i.d. sum. By Assumption 2, s1 , . . . , sT are i.i.d. from P, so D1f , . . . , DTf are i.i.d. and E[Dtf ] = 0. Moreover, T X ∆fctx (q, T ) = Dtf . t=1
(ii) Range bound. Since vqf (s) = Ex∼q(·|s) [f (s, x)] and 0 ≤ f (s, x) ≤ p̄, we have vqf (st ) ∈ [0, p̄]
⇒
Dtf ∈ [µfq − p̄, µfq ].
Hence each Dtf has range width at most p̄. (iii) Hoeffding. Applying Hoeffding’s inequality [56], for any ε > 0, ! T X 2ε2 f Pr Dt ≥ ε ≤ 2 exp − 2 . T p̄ t=1 q Setting ε := p̄ T2 log 2δ yields ! r T 2 f Pr ∆ctx (q, T ) ≤ p̄ log ≥ 1 − δ. 2 δ
Proposition S4 (Resource-consumption concentration over requests). For any q ∈ Q and constant B ≥ 0, let {ψ t }Tt=1 ⊆ RJ+tot be a sequence such that ψ t is measurable with respect to the history available before st is observed and ∥ψ t ∥1 ≤ B almost surely for every t. Define ∆hctx (q, ψ, T ) :=
T X
ψ t , vqh (st ) − Es∼P [vqh (s)] .
t=1
Then, for any δ ∈ (0, 1), with probability at least 1 − δ, r T 2 h log . ∆ctx (q, ψ, T ) ≤ B 2 δ Proof. Fix any q ∈ Q, a constant B ≥ 0, and a sequence {ψ t }Tt=1 ⊆ RJ+tot satisfying the conditions in Proposition S4. Define µhq := Es∼P [vqh (s)] ∈ RJtot . Let Ft := σ(Ht ) for t = 0, . . . , T be the natural filtration generated by the history in (12). Define Dth := ψ t , vqh (st ) − µhq . (i) Centered martingale-difference sum. By assumption, ψ t is Ft−1 -measurable. By Assumption 2 and the causal round protocol, st ∼ P is independent of Ft−1 , so E vqh (st ) | Ft−1 = µhq . The Ft−1 -measurability of ψ t then gives E Dth | Ft−1 = ψ t , µhq − µhq = 0. Thus, {Dth }Tt=1 is a martingale-difference sequence with respect to {Ft }Tt=0 , and ∆hctx (q, ψ, T ) =
T X
Dth .
t=1
(ii) Conditional range bound. For each coordinate (d, j), by − T1 ≤ hd,j (s, x) ≤ 1 − T1 , we have 1 1 hd,j . vq (st ) ∈ − , 1 − T T Because every coordinate of ψ t is nonnegative, conditional on Ft−1 , 1 Dth ∈ − ∥ψ t ∥1 − ψ t , µhq , T 1 1− ∥ψ t ∥1 − ψ t , µhq , T so the conditional range width of Dth is at most ∥ψ t ∥1 ≤ B. (iii) Azuma–Hoeffding. If B = 0, then ψ t = 0 almost surely PT for every t, so t=1 Dth = 0 and the bound is immediate. Otherwise, applying the Azuma–Hoeffding inequality for martingale differences with bounded conditional ranges [56], [57], for any ε > 0, ! T X 2ε2 h Pr Dt ≥ ε ≤ 2 exp − . T B2 t=1 q Setting ε := B T2 log 2δ yields ! r T 2 h Pr ∆ctx (q, ψ, T ) ≤ B log ≥ 1 − δ. 2 δ
31
A PPENDIX D S UCCESS -W EIGHTED P OSTERIOR W IDTH UNDER S ELECTIVE C ONSTRAINT U PDATES This section states and proves the success-weighted posterior-width result used to bound the cumulative constraintsurrogate error. We first state the result and then present the proof idea and formal proof. Lemma S1 (Success-weighted posterior-width bound under selective updates). Fix a resource (d, j). Suppose that Assumptions 1, 3, and 7 hold. Define ( Γ md,j σt−1 (zt ), 1Γd,j (st ) = 1, ωt,d,j := 0, 1Γd,j (st ) = 0. Thus, the posterior standard deviation is evaluated only for inputs satisfying 1Γd,j (st ) = 1. Then, for every δ ∈ (0, 1), with probability at least 1 − δ, v u r mΓ T u X 2T γT d,j 1 u + 2T log . p(st , xt )ωt,d,j ≤ t −1 δ log 1 + ηm t=1 Γ
q-th retained observation. The Schur-complement determinant identity gives mΓ d,j −1 det I + ηmΓ KZq d,j mΓ d,j −1 −1 1 + ηm . = det I + ηmΓ KZq−1 Γ vq d,j
d,j
Multiplying this identity over the update rounds, taking logarithms, and using the definition of maximum information gain in (36) give mΓ d,j
NT 1 1 X mΓ d,j −1 −1 log 1 + ηm = log det I + ηm Γ vq Γ KZ mΓ d,j d,j 2 q=1 2 d,j N
!
T
≤γ
mΓ d,j
.
mΓ
NT d,j
Assumption 3 and the fact that posterior variance does not exceed prior variance imply 0 ≤ vq ≤ 1. By the concavity of v 7→ log(1 + η −1 v), for every η > 0 and v ∈ [0, 1], log(1 + η −1 v) ≥ v log(1 + η −1 ).
d,j
Proof idea. A standard information-gain argument bounds the cumulative posterior width over the rounds in which the constraint model is updated, namely, those satisfying Yt = 1 and 1Γd,j (st ) = 1. The desired bound weights the width on every on-path round by its provisioning-success probability. A martingale concentration argument transfers the standard bound from the model-update rounds to this successprobability-weighted sum.
Applying this inequality with η = ηmΓd,j , summing over the update rounds, and combining it with the preceding information-gain bound give mΓ d,j
T NX
−1 log 1 + ηm Γ
d,j
mΓ
NT d,j
vq ≤
q=1
X
−1 log 1 + ηm Γ vq d,j
q=1
≤ 2γ
mΓ d,j
.
mΓ
NT d,j
Proof of Lemma S1. For each round t ∈ [T ], let Xt be the posterior standard deviation counted only when successful provisioning produces an update of the constraint model for resource (d, j): Xt := Yt ωt,d,j .
t=1
Xt =
mΓ
X
d,j σt−1 (zt ).
t∈[T ] Yt =1, 1Γ d,j (st )=1
If NT = 0, this sum is zero and the desired bound is immediate. Otherwise, enumerate the update rounds as mΓ τ1 < · · · < τ mΓd,j . For q ∈ [NT d,j ], let NT
Z0 := ∅,
and define vq :=
Γ 2 m στq d,j (z ) , −1 τq
d,j 2γ m Γ X NT d,j . vq ≤ −1 log 1 + ηm q=1 Γ
(S17)
To bound the cumulative PTposterior width over the modelupdate rounds, namely, t=1 Xt , we apply the cumulative posterior-width argument of [58, Lemma 4] to the retained update sequence. Specifically, we combine the variance-sum bound in (S17) with the Cauchy–Schwarz inequality: mΓ
mΓ d,j
Zq := zτ1 , . . . , zτq ,
mΓ
mΓ
NT d,j
d,j
(i) Width on model-update rounds. By the definition of Xt , T X
Therefore,
mΓ q ∈ NT d,j .
T X t=1
NT d,j
Xt =
X √
vq
q=1
v u mΓ u NT d,j u X (a) u mΓ ≤ tNT d,j vq
(S18)
q=1
v Γ Γ u u 2N md,j γ md,jΓ T m (b) u NT d,j u . ≤t −1 log 1 + ηm Γ d,j
Because the constraint posterior changes only in update rounds, vq is the posterior variance immediately before the
Here, (a) follows from the Cauchy–Schwarz inequality, and (b) follows from (S17).
32
(ii) Transfer to the success-probability-weighted width. Using Xt = Yt ωt,d,j , we obtain E[Xt | Ht−1 , st , xt ] = E[Yt ωt,d,j | Ht−1 , st , xt ] (a)
= ωt,d,j Pr(Yt = 1 | Ht−1 , st , xt )
(b)
= ωt,d,j p(st , xt ).
Here, (a) holds because ωt,d,j is determined by (Ht−1 , st , xt ) and Yt is binary. Equality (b) follows from the stationary response law in Assumption 1; when 1Γd,j (st ) = 0, both sides are zero by the definition of ωt,d,j . Define Dt := Xt − E[Xt | Ht−1 , st , xt ]. By definition, E[Dt | Ht−1 , st , xt ] = 0, which also gives E[Dt | Ht−1 ] = 0. Thus, {Dt }Tt=1 is a martingale difference sequence. By definition, ωt,d,j = 0 when 1Γd,j (st ) = 0. Otherwise, the fact that a posterior variance does not exceed the corresponding prior variance and the kernel normalization in Assumption 3 give 0 ≤ (ωt,d,j )2 ≤ kmΓd,j (zt , zt ) ≤ 1. Since Yt ∈ {0, 1}, this gives 0 ≤ Xt ≤ 1 and |Dt | ≤ 1. The Azuma–Hoeffding inequality [57] therefore implies that, with probability at least 1 − δ, r T X 1 (S19) Dt ≥ − 2T log . δ t=1 Summing the conditional-expectation equality over t, using the definition of Dt , and applying (S19) gives T X
p(st , xt )ωt,d,j =
t=1
= ≤
T X t=1 T X
E[Xt | Ht−1 , st , xt ] Xt −
T X
t=1
t=1
T X
r Xt +
t=1
Dt
1 2T log . δ
Combining this inequality with (S18) yields, with probability at least 1 − δ, v Γ Γ u u 2N md,j γ md,jΓ r T T m u X 1 NT d,j u + 2T log . p(st , xt )ωt,d,j ≤ t −1 δ log 1 + η t=1 mΓ d,j
and bounds ∥ϕ⋆ ∥1 (Sec. E-A). We then establish requestwise Lagrangian optimality (Sec. E-B). Afterward, we prove Theorem 1, which gives finite-time bounds on the relaxed regret Regrel (T ) and constraint violations Viorel d,j (T ) for general CCKB (Sec. E-C). Next, we prove Proposition S1, which bounds the cumulative proxy surrogate errors Wf (T ) and [W h (T )]d,j (Sec. E-D). We then prove Proposition S2, which bounds the optimality gap OPTrel − OPTprx (Sec. E-E). Finally, we combine these two propositions to prove Corollary S4 (Sec. E-F).
A. Proof of Corollary S1 For the proof, write F (q) := Es∼P [vqf (s)],
Using these quantities, define the Lagrangian and the dual function, respectively, as L(q, ϕ) := F (q) − ⟨ϕ, G(q)⟩,
D(ϕ) := sup L(q, ϕ). q∈Q
Proof. 1) Strong Duality: The relaxed benchmark (16) depends on a policy q only through the finite-dimensional vector (F (q), G(q)). By their definitions, F and G are linear in q. Because Q is closed under policy mixtures, its image under the linear map q 7→ (F (q), G(q)) is therefore convex [55, Sec. 2.3.2]. The problem is therefore convex with finitely many inequality constraints. Applying the standard Slater theorem [55, Sec. 5.2.3] under Assumption 5 gives strong duality and ensures that the dual optimum is attained. Let q ⋆ be an optimal policy, whose existence is assumed in Corollary S1, and let ϕ⋆ be an optimal dual vector. Their optimality and strong duality give F (q ⋆ ) = OPTrel = D(ϕ⋆ ). 2) Finite Norm of an Optimal Dual Vector: Substituting the Slater policy q ◦ into the dual function and using G(q ◦ ) ≤ −ξT 1 give OPTrel = D(ϕ⋆ ) ≥ L(q ◦ , ϕ⋆ ) = F (q ◦ ) − ⟨ϕ⋆ , G(q ◦ )⟩ ≥ F (q ◦ ) + ξT ∥ϕ⋆ ∥1 . Rearranging and using 0 ≤ F (q ◦ ) ≤ OPTrel ≤ p̄ give
mΓ
Finally, NT d,j ≤ T and the maximum information gain is nondecreasing in its sample count. Substituting these two bounds gives the claim in Lemma S1.
G(q) := Es∼P [vqh (s)].
∥ϕ⋆ ∥1 ≤
p̄ OPTrel − F (q ◦ ) ≤ < ∞. ξT ξT
⋆ rel Hence, a finite bound Λrel T satisfying ∥ϕ ∥1 ≤ ΛT exists.
A PPENDIX E P ROOFS OF THE CCKB AND P ROXY G UARANTEES This section establishes the theoretical guarantees underlying the general CCKB analysis and its proxy instantiation. We first prove Corollary S1, which establishes strong duality
For any optimal policy q ⋆ and optimal dual vector ϕ⋆ , primal feasibility and strong duality imply complementary slackness: ϕ⋆ , Es∼P [vqh⋆ (s)] = 0.
(S20)
33
B. Request-Wise Lagrangian Optimality To derive the upper bound on Viorel d,j (T ), we compare the benchmark policy q ⋆ with the selected action xt for the same request in terms of f (s, x) − ⟨ϕ⋆ , h(s, x)⟩. The following lemma shows that the corresponding conditional value under q ⋆ is no smaller than the value of any action for almost every request. Lemma S2 (Request-wise Lagrangian optimality). Suppose that the relaxed NSR-DP admits an optimal policy, that Assumptions 3 and 4 hold, and that Assumption 5 holds. Let (q ⋆ , ϕ⋆ ) be a primal–dual optimal pair. Then, for P-almost every s and every x ∈ X , {f (s, x′ ) − ⟨ϕ⋆ , h(s, x′ )⟩} vqf⋆ (s) − ⟨ϕ⋆ , vqh⋆ (s)⟩ = max x′ ∈X ⋆ ≥ f (s, x) − ⟨ϕ , h(s, x)⟩.
(S21) Proof. For fixed ϕ⋆ , define ℓϕ⋆ (s, x) := f (s, x) − ⟨ϕ⋆ , h(s, x)⟩. Assumptions 3 and 4 make this function measurable in s and continuous in x. Because X in (7) is compact, a maximizer exists for every request and can be selected measurably [59, Thm. 18.19]. The corresponding deterministic policy belongs to Q. For every q ∈ Q, L(q, ϕ⋆ ) = Es∼P Ex∼q(·|s) [ℓϕ⋆ (s, x)] ≤ Es∼P max ℓϕ⋆ (s, x) , x∈X
where the inequality holds because an average cannot exceed the maximum. The measurable policy above attains the upper bound; hence, sup L(q, ϕ⋆ ) = Es∼P max ℓϕ⋆ (s, x) . q∈Q
x∈X
By strong duality and complementary slackness in (S20), q ⋆ attains the supremum on the left. Therefore, ⋆ ⋆ ⋆ Es∼P max ℓϕ (s, x) − Ex∼q (·|s) [ℓϕ (s, x)] = 0. x∈X
The integrand is nonnegative and therefore equals zero for P-almost every s. Expanding ℓϕ⋆ gives (S21). The same conclusion applies to the proxy problem under the corresponding assumptions, after replacing h with hprx . For a fixed request, the path indicators are fixed and kernel regularity gives continuity in x, while Assumption 4 gives measurability in s. Thus, the same measurable-selection argument applies. C. Proof of Theorem 1 The proof follows the primal–dual argument used for general CKB guarantees [17, Theorem 3.3]. First, we construct the joint high-probability event used in the analysis (Sec. E-C1). Second, we establish the CCKB master inequality (Sec. E-C2). Finally, we combine the master inequality with the primal–dual relations to derive the regret and constraint-violation bounds (Sec. E-C3).
1) Joint High-Probability Event: For q ∈ Q, a nonnegative predictable sequence ψ = {ψ t }Tt=1 , and B ≥ 0, define the events ) ( r T 2 f f log , (S22) Ectx (q, δ) := |∆ctx (q, T )| ≤ p̄ 2 δ ( ) r T 2 h Ectx (q, ψ, B, δ) := |∆hctx (q, ψ, T )| ≤ B log . 2 δ (S23) Let q ⋆ be an optimal policy. For the regret bound, set reg f f Ectx := Ectx (q ⋆ , αctx )
h h ∩ Ectx q ⋆ , {ϕt }Tt=1 , ρJtot , αctx . Because q ⋆ is fixed, Proposition S3 applies to the first event. For the second event, Algorithm 1 determines ϕt before observing st and ensures ∥ϕt ∥1 ≤ ρJtot , so Proposition S4 applies. A union bound gives f reg h − αctx . ) ≥ 1 − αctx Pr(Ectx
Thus, the first two concentration events, together with the surrogate event specified in part (i) of Theorem 1, are sufficient for the regret bound. For the constraint-violation bound, let (q ⋆ , ϕ⋆ ) be the primal–dual pair in Corollary S1, let {ϕ⋆ }Tt=1 denote the constant sequence, and set f f vio Ectx := Ectx (q ⋆ , αctx ) h αctx h ⋆ T ∩ Ectx q , {ϕt }t=1 , ρJtot , 2 h ⋆ T h ⋆ rel αctx ∩ Ectx q , {ϕ }t=1 , ΛT , . 2
The constant sequence is predictable, and ∥ϕ⋆ ∥1 ≤ Λrel T . Applying the same two concentration propositions and a union bound over all three events gives f vio h Pr(Ectx ) ≥ 1 − αctx − αctx . vio Intersecting this event with Esur gives the probability stated in part (ii) of the theorem. 2) CCKB Master Inequality: For brevity, write zt = (st , xt ), and define
Regrel seq (T ) :=
T X
vqf⋆ (st ) − f (zt ) .
(S24)
t=1
The following lemma is the vector-valued, contextual counterpart of the key decomposition in the original CKB analysis [17, Theorem 3.3]. The scalar constraint term is replaced by an inner product with the vector of contextual constraints, and ∆hctx accounts for the realized request sequence. √ Lemma S3 (CCKB master inequality). Set V = Jtot T /ρ. If the one-sided bounds in (32) and the reward cumulativeerror bound in (33) hold, then the following inequality holds
34
for ϕ = 0, with the term involving W h (T ) equal to zero. On vio Esur , it holds for every ϕ ∈ [0, ρ]Jtot : * Regrel seq (T ) +
ϕ,
T X
+
Regrel (T ) = ∆fctx (q ⋆ , T ) + Regrel seq (T ).
≤ Wf (T ) + ⟨ϕ, W h (T )⟩ + ∆hctx q ⋆ , {ϕt }Tt=1 , T √ V ∥ϕ∥22 ρ Jtot T + + . 2 2
(S25)
Proof. Fix ϕ ∈ [0, ρ]Jtot . We decompose the left-hand side into four terms that can be controlled by the primal selection rule, the surrogate-error bounds, the dual update, and the feasibility of q ⋆ , respectively: * ϕ,
T X
+ h(zt )
t=1
= T1 + T2 +
T X
ϕ − ϕt , h̄t (zt ) +
T X
t=1
ϕt , vqh⋆ (st ) ,
t=1
(S26) where T1 :=
T X vqf⋆ (st ) − ⟨ϕt , vqh⋆ (st )⟩ t=1
−
T X
T X
and the surrogate event specified in part (i) of the theorem, set ϕ = 0 in Lemma S3, and combine (S27) with the reward concentration bound in (S22), instantiated with q = q ⋆ f and δ = αctx , and the constraint concentration bound in (S23), instantiated with q = q ⋆ , ψ = {ϕt }Tt=1 , B = ρJtot , and h δ = αctx . Because ⟨0, W h (T )⟩ = 0, this step does not use the constraint cumulative-error bound. This proves (34). 2) Contextual Correction for the Violation Bound: For the violation bound, we reuse the coordinate-isolation argument of Efroni et al. [60], as adopted in the scalar CKB analysis [17, Thm. 3.3]. Once (S25) is available, the coordinate choice and the subsequent algebra are unchanged. We only need to account for two differences: the benchmark policy is defined under P, whereas the sequential regret is evaluated on the realized requests, and the master inequality (S25) contains a vector-valued surrogate error. We first establish the correction for the realized requests. Applying Lemma S2 to xt , summing over t, expanding ∆hctx , and then using complementary slackness in (S20) give + * T X ⋆ rel h(zt ) Regseq (T ) + ϕ , ≥
T X f¯t (zt ) − f (zt ) + ϕ, h(zt ) − h̄t (zt ) .
t=1
t=1
The surrogate directions in (32) and the primal maximization vio in Algorithm 1 give T1 ≤ 0. On Esur , the cumulative bounds in (33) give T2 ≤ Wf (T ) + ⟨ϕ, W h (T )⟩ . For ϕ = 0, the constraint-surrogate term in T2 vanishes, so the same inequality follows from only the reward cumulative-error bound. The projected dual update implies ϕ − ϕt , h̄t (zt ) ≤
V ∥ϕt − ϕ∥22 − ∥ϕt+1 − ϕ∥22 2 ∥h̄t (zt )∥22 + . 2V
Summation, ϕ1 = 0, and ∥h̄t (zt√ )∥22 ≤ Jtot bound the 2 corresponding sum by V ∥ϕ∥2 /2 + ρ Jtot T /2. For the fourth term, feasibility of q ⋆ gives Es∼P [vqh⋆ (s)] ≤ 0. Together with ϕt ≥ 0, the definition of ∆hctx therefore gives T X
(S27)
reg On Ectx
t=1
f¯t (zt ) − ⟨ϕt , h̄t (zt )⟩ ,
t=1
T2 :=
Proof of Theorem 1. 1) Regret Bound: The population regret decomposes as
h(zt )
t=1
Regrel seq (T ) +
3) Regret and Constraint-Violation Bounds:
⟨ϕt , vqh⋆ (st )⟩ = ∆hctx q ⋆ , {ϕt }Tt=1 , T
t=1
+
T X
ϕt , Es∼P [vqh⋆ (s)]
t=1 ≤ ∆hctx q ⋆ , {ϕt }Tt=1 , T .
Substitution into (S26) proves the claim.
T X
ϕ⋆ , vqh⋆ (st )
t=1 (a)
= ∆hctx q ⋆ , {ϕ⋆ }Tt=1 , T + T ϕ⋆ , Es∼P [vqh⋆ (s)] (b) = ∆hctx q ⋆ , {ϕ⋆ }Tt=1 , T s (c) T 4 rel log h . ≥ −ΛT 2 αctx
(S28)
Here, (a) follows from the definition of ∆hctx , (b) from complementary slackness in (S20), and (c) from the constraintconcentration event in (S23), instantiated with B = Λrel T and h δ = αctx /2. (S28) is the additional step required by the contextual setting. 3) Coordinate Isolation and Violation Bound: We now apply the standard coordinate-isolation step. Fix (d, j), let ed,j be its standard basis vector, and set ρ ϕ(d,j) := ϕ⋆ + ed,j . 2 Because ∥ϕ⋆ ∥1 ≤ Λrel ≤ ρ/2, this vector lies in [0, ρ]Jtot and T can be substituted into (S25). Its left-hand side decomposes as * + T X (d,j) rel Regseq (T ) + ϕ , h(zt ) * = Regrel seq (T ) +
⋆
ϕ ,
t=1 T X
+ h(zt )
t=1 T
ρX ≥ hd,j (zt ) − Λrel T 2 t=1
s
T
+
ρX hd,j (zt ) 2 t=1
T 4 log h . 2 αctx
(S29)
35
Here, the final inequality follows from (S28). Moreover, ∥ϕ(d,j) ∥2 ≤ ρ and each of its coordinates is vio at most ρ. On Ectx , the constraint-concentration event for T {ϕt }t=1 gives s T 4 h ⋆ T ∆ctx q , {ϕt }t=1 , T ≤ ρJtot log h . (S30) 2 αctx Substituting (S30) into the right-hand side of (S25) and comparing it with the left-hand-side lower bound in (S29) give T D E ρX hd,j (zt ) ≤ Wf (T ) + ϕ(d,j) , W h (T ) 2 t=1 s 4 T + ρJtot log h 2 αctx √ (d,j) 2 V ∥ϕ ∥2 ρ Jtot T + + 2 s2 T 4 log h . + Λrel T 2 αctx
Taking the positive part, multiplying by 2/ρ, and using V = √ Jtot T /ρ and Λrel T /ρ ≤ 1/2 yield " T X
# ≤
hd,j (zt )
t=1
+
2Wf (T ) ρ | {z }
Proof of Proposition S1. 1) Confidence Events: Applying the standard kernelized-bandit confidence theorem [58], [61] to the reward observations gives an event Ef with probability at least 1 − αf on which, simultaneously for every t ∈ [T ] and z ∈ S × X, f |f (z) − µft−1 (z)| ≤ βtf (αf )σt−1 (z).
E 2 D (d,j) ϕ , W h (T ) ρ {z } | O(∥W h (T )∥1 )
(S31)
Apply the same theorem to the retained subsequence of each constraint model, allocate failure probability αh /Jtot to each model, and take a union bound. This gives an event Eh with probability at least 1 − αh on which, simultaneously for every t ∈ [T ], resource (d, j), and z = (s, x) satisfying 1Γd,j (s) = 1, Γ αh md,j mΓ mΓ d,j d,j Γ σt−1 (z). (S32) md,j (z) − µt−1 (z) ≤ βt Jtot No confidence relation is needed off path: the zero extensions in (21) and (30) make both the proxy constraint and its surrogate equal −1/T there. 2) Pointwise Surrogate Bounds: On Ef , the definition of the reward UCB in (29) and the reward confidence relation in (S31) bound the gap between fˆt and f . Since f (z) ∈ [0, p̄], clipping fˆt to this interval preserves its optimistic direction and cannot increase the gap. Therefore, the following bound holds uniformly in z and, in particular, at zt : f 0 ≤ f¯t (zt ) − f (zt ) ≤ 2βtf (αf )σt−1 (zt ).
O(Wf (T )/ρ)
+
D. Proof of Proposition S1
(S33)
On Eh , the demand LCB in (30) and the constraint confidence relation in (S32) similarly bound the gap between mΓd,j and m b Γt,d,j . Substitution into (31), followed by clipping to the known proxy constraint range, gives, for every (d, j),
s
+ 2Jtot | O(Jtot
+
T 4 log h 2 αctx } √ {z
T log(1/αh ctx ))
V ∥ϕ(d,j) ∥22
+ {z √
ρ |
O( Jtot T )
s
+
p
2Λrel T ρ | √ O(
Jtot T }
T 4 log h . 2 αctx {z }
T log(1/αh ctx ))
Since Jtot ≥ 1, collecting these terms gives " T # X Wf (T ) + ∥W h (T )∥1 hd,j (zt ) =O ρ t=1 + q p + Jtot T log αh1 + Jtot T , ctx
which proves (35). Assumption 5 guarantees that a finite Λrel T exists for each fixed horizon, as required by the constraint-violation part of Theorem 1.
mΓ 2βt d,j (αh /Jtot ) prx prx ωt,d,j . 0 ≤ hd,j (zt ) − h̄t,d,j (zt ) ≤ max Cd,j
(S34)
3) Cumulative Reward-Surrogate Error: The cumulative reward-surrogate error is bounded as T X
T (a) X f f¯t (zt ) − f (zt ) ≤ 2 βtf (αf )σt−1 (zt )
t=1
t=1 (b)
≤ 2βTf (αf )
T X
f (zt ) σt−1
t=1
(S35)
q (c) f f = O βT (αf ) T γT (d)
= O(Φf (T ; αf )) .
Here, (a) follows from (S33), (b) from the monotonicity of βtf (αf ), (c) from the cumulative posterior-width bound [58, Lemma 4], and (d) from the definitions of βTf (αf ) and Φf (T ; αf ). The event Ef ∩ Eh has probability at least 1 − αf − αh , so the pointwise directions and (S35) prove the first part of the proposition without Assumption 8. 4) Cumulative Constraint-Surrogate Error: For the remainder of the proof, additionally suppose that Assumption 8 holds and MT ≥ ρ.
36
Auxiliary reward-UCB floor: We first establish an auxiliary lower bound on the reward UCB f¯t . Define the shifted proxy quantities prx gd,j (s, x) := hprx d,j (s, x) +
mΓd,j (s, x) 1 = max T Cd,j
all these bounds hold. On this event, the pointwise bound and the monotonicity of the exploration parameters in (38) give X prx hd,j (zt ) − h̄prx t,d,j (zt ) t∈H mΓ
2β d,j (αh /Jtot ) X ≤ T ωt,d,j max Cd,j t∈H
and 1 prx ḡt,d,j (s, x) := h̄prx . t,d,j (s, x) + T
mΓ 4p̄βT d,j (αh /Jtot ) X ≤ p(st , xt )ωt,d,j max aT Cd,j t∈H
(S36)
On Ef ∩ Eh , the pointwise bounds and clipping give
Γ
m T 4p̄βT d,j (αh /Jtot ) X p(st , xt )ωt,d,j ≤ max aT Cd,j t=1 ! r mΓ Jtot p̄ d,j mΓ d,j + 1 + log =O B +σ ed,j γT max aT Cd,j αh v u "u #! r mΓ T γT d,j Jtot u + T log × t . −1 αw log(1 + ηm Γ )
prx prx 0 ≤ ḡt,d,j (s, x) ≤ gd,j (s, x) ≤ 1.
For the realized request st , Assumption 8 gives a pointwise comparator x◦t ∈ X such that X X prx f (st , x◦t ) − MT gd,j (st , x◦t ) ≥ aT . (S37) d∈D j∈[Jd ]
d,j
Using x◦t as a comparator yields (a)
f¯t (zt ) ≥ f¯t (zt ) − ⟨ϕt , ḡtprx (zt )⟩ (b)
≥ f¯t (st , x◦t ) − ⟨ϕt , ḡtprx (st , x◦t )⟩ X X prx (c) ≥ f (st , x◦t ) − ρ gd,j (st , x◦t ) d∈D j∈[Jd ] (d)
≥ f (st , x◦t ) − MT
X X
(S38)
prx gd,j (st , x◦t )
d∈D j∈[Jd ] (e)
≥ aT . Here, (a) follows from the nonnegativity of ϕt and ḡtprx ; (b) follows because, by (S36), replacing h̄prx with ḡtprx subtracts t the action-independent constant ∥ϕt ∥1 /T from the acquisition and hence preserves its maximizer; (c) from reward optimism, ϕt ∈ [0, ρ]Jtot , and 0 ≤ ḡtprx ≤ gprx ; (d) from MT ≥ ρ and the nonnegativity of gprx ; and (e) from (S37). Partition of rounds: Fix a resource (d, j). (S34) gives mΓ 2βt d,j (αh /Jtot ) prx prx ωt,d,j . 0 ≤ hd,j (zt ) − h̄t,d,j (zt ) ≤ max Cd,j
Split the rounds into
aT t : p(st , xt ) ≥ 2p̄
aT 2p̄
H :=
and L :=
t : p(st , xt ) <
.
Accordingly, the cumulative error decomposes into its contributions over H and L, which we bound separately. High-success rounds (t ∈ H): Apply Lemma S1 to every resource with failure probability αw /Jtot . A union bound gives an event Ew with probability at least 1 − αw on which
The second inequality uses 1 ≤ 2p̄ p(st , xt )/aT for t ∈ H; the third uses the nonnegativity of p(st , xt )ωt,d,j ; and the final equality follows from (38) and Lemma S1. Low-success rounds (t ∈ L): For every t ∈ L, the definition of L gives f (zt ) = κprice (st )p(st , xt ) aT . ≤ p̄ p(st , xt ) < 2 Combining this inequality with (S38) gives aT . f¯t (zt ) − f (zt ) ≥ 2 Because the proxy target and surrogate both lie in [−1/T, 1 − 1/T ], their pointwise difference satisfies 2 ¯ prx 0 ≤ hprx ft (zt ) − f (zt ) . d,j (zt ) − h̄t,d,j (zt ) ≤ 1 ≤ aT Therefore, X prx 2 Φf (T ; αf ) prx hd,j (zt ) − h̄t,d,j (zt ) ≤ Wf (T ) = O . aT aT t∈L
Combining the two parts yields W h (T ) d,j = O(Ψd,j (T ; αf , αh , αw )) simultaneously for all resources. 5) Joint Event: The joint event Ef ∩ Eh ∩ Ew has probability at least 1 − αf − αh − αw . Consequently, under the proxy prx substitutions hd,j ← hprx d,j and h̄t,d,j ← h̄t,d,j , the directional conditions in (32) and the cumulative-error conditions in (33) prx hold. Thus, Esur holds on this joint event, which proves the proposition. E. Proof of Proposition S2 Proof of Proposition S2. 1) Dual Existence and Norm Bounds: We first establish the existence of the optimal dual vectors ϕ⋆prx and ϕ⋆rel , together with their finite norm bounds Λprx and Λrel T . Corollary S1 applies directly to the proxy T
37
problem and yields an optimal dual vector ϕ⋆prx with finite ◦ norm bound Λprx T . Let q and ξT denote the Slater policy and margin for the proxy constraints, respectively. Because h ≤ hprx , Hence, q ◦ is also a Slater policy for the relaxed constraints with the same margin. The corollary therefore also applies to the relaxed NSR-DP and yields an optimal dual vector ϕ⋆rel with finite norm bound Λrel T . 2) Support Restriction: We first show that an optimal relaxed policy assigns probability only to decompositions satisfying p(s, x) ≥ aT /(2p̄). (23) and the definitions of hd,j and hprx d,j give 1 1 . 0 ≤ hd,j (s, x) + ≤ hprx d,j (s, x) + T T Moreover, ∥ϕ⋆rel ∥∞ ≤ ∥ϕ⋆rel ∥1 ≤ Λrel ≤ MT . Hence, T Assumption 8 permits the same shift-and-comparator argument used to establish (S38), with (f¯t , h̄prx t , ϕt ) replaced by (f, h, ϕ⋆rel ). Thus, every request-wise relaxed-Lagrangian maximizer x satisfies f (s, x) ≥ aT for P-almost every s. Since f (s, x) ≤ p̄ p(s, x), every such maximizer satisfies p(s, x) ≥ aT /p̄. Lemma S2 states that an optimal relaxed ⋆ policy qrel can put probability mass only on request-wise Lagrangian maximizers. Therefore, aT aT p(s, x) ≥ ≥ (S39) p̄ 2p̄ ⋆ for P-almost every s and qrel (· | s)-almost every x. 3) Proxy Constraint Bound: We next bound the proxyconstraint values of the optimal relaxed policy. Fix a resource ⋆ (d, j). On the support of qrel , (22) and (S39) give 1 cd,j (s, x) max − T p(s, x)Cd,j
(a) 2p̄ c 1 d,j (s, x) − ≤ max aT Cd,j T
! (S40) cd,j (s, x) 1 1 2p̄ + − −1 max Cd,j T T aT 1 2p̄ (b) 2p̄ = hd,j (s, x) + −1 . aT T aT Here, (a) follows from (S39), and (b) follows from the ⋆ definition of hd,j in (18). Taking expectations under qrel gives 2p̄ = aT
prx ⋆ (·|s) [h Es∼P Ex∼qrel d,j (s, x)] (a) 2p̄
1 ⋆ (·|s) [hd,j (s, x)] + ≤ Es∼P Ex∼qrel aT T (b) 1 2p̄ −1 . ≤ T aT
2p̄ −1 aT
(a) OPTprx = sup F (q) − ⟨ϕ⋆prx , Gprx (q)⟩ q∈Q
(b)
⋆ ⋆ ≥ F (qrel ) − ⟨ϕ⋆prx , Gprx (qrel )⟩
prx
Es∼P [vqh◦ (s)] ≤ Es∼P [vqh◦ (s)] ≤ −ξT 1.
hprx d,j (s, x) =
It follows that
(S41) Here, (a) follows from (S40), and (b) follows from the ⋆ feasibility of qrel for the relaxed NSR-DP. 4) Optimality-Gap Bound: We finally convert the preceding proxy-constraint bound into an optimality-gap bound through the proxy dual problem. For q ∈ Q, define the proxy constraint vector by prx G (q) d,j := Es∼P Ex∼q(·|s) [hprx d,j (s, x)].
(c)
⋆ = OPTrel − ⟨ϕ⋆prx , Gprx (qrel )⟩.
Here, (a) follows from strong duality and the dual optimality ⋆ of ϕ⋆prx , (b) follows because qrel ∈ Q, and (c) follows from ⋆ the optimality of qrel for the relaxed NSR-DP and the identical objectives of the relaxed and proxy problems. Rearranging this inequality and applying (S41) componentwise give ⋆ OPTrel ≤ OPTprx + ⟨ϕ⋆prx , Gprx (qrel )⟩ X X (d) 2p̄ 1 ϕ⋆prx,d,j −1 . ≤ OPTprx + T aT d∈D j∈[Jd ]
Here, (d) also uses ϕ⋆prx
≥ 0. Subtracting OPTprx proves the upper bound in (S11). The lower bound follows from Lemma 1. Finally, (S12) follows from ∥ϕ⋆prx ∥1 ≤ Λprx and T ϕ⋆prx ≥ 0. F. Proof of Corollary S4 Proof. 1) Explicit Finite-Time Bounds: (i) Proxy Regret: The first part of Proposition S1 gives the proxy one-sided bounds and Wf (T ) = O (Φf (T ; αf )) with failure probability at most αf + αh . Substitution into part (i) of Corollary S2 proves (S13). (ii) Relaxed NSR-DP Regret: Part (i) of Corollary S3 then gives (S14). Under its additional conditions, Proposition S2 gives 2p̄ prx T ∆prx (T ) ≤ ΛT −1 , aT which proves (S15). (iii) Constraint Violation: Under the additional conditions in part (iii), the second part of Proposition S1 also gives ∥W h (T )∥1 = O ∥Ψh (T ; αf , αh , αw )∥1 with joint failure probability at most αf +αh +αw . Substitution into part (ii) of Corollary S2, followed by part (ii) of Corollary S3, proves (S16). Combining each surrogate event with its two request-concentration events gives the stated probabilities. 2) Simplified Rates: For the rates in Corollary 1, hold the kernel, norm, noise, and regularization parameters fixed. For every nonzero modeled kernel, monotonicity gives γT• ≥ γ1• > 0, so (S9) and (S10) give √ e f T ), Φf (T ; αf ) = O(γ T #! √ " T p̄ mΓ f d,j e Ψd,j (T ; αf , αh , αw ) = O γT + max γT . aT Cd,j An identically zero kernel models only the zero function and has zero posterior width, so its surrogate-error contribution vanishes directly. Substituting the rate for Φf into (S13) gives (41). For constraint violation, summing the per-resource rates
38
√ for Ψd,j and using Jtot ≤ Jtot in (S16) gives (44). The regret-transfer identity and the proxy-optimality-gap term are unaffected by this simplification, which gives (42) and (43).
A PPENDIX F E XPERIMENTAL N ETWORK S LICE R EQUEST I NSTANTIATION Table S2 provides the complete parameter mapping and class-conditional values for the experimental setup in Sec. VI-A3.
standardize the raw input vector uraw (z). The resulting vector is denoted by ũ(z). The statistics remain fixed until the next scheduled refit and are applied to both the training inputs and candidate inputs. Dimensions that are constant in the current training inputs are mapped to zero. B. Output Processing and Observation-Noise Models for Surrogate Fitting For zt = (st , xt ), both the reward and constraint GPs use Gaussian likelihoods. The reward observation is modeled as (reward)
A PPENDIX G I MPLEMENTATION D ETAILS FOR C OMPARISON M ETHODS For the joint request–decomposition input z = (st , x) ∈ S × X , this section details the construction of the standardized kernel input ũ(z) used by the GPs underlying the raw reward estimate fˆt and the raw resource-wise constraint estimates b ht,d,j (Sec. G-A). It also specifies how the constraint outputs are processed and which observation-noise models are used to fit these GPs (Sec. G-B) in the comparison setup summarized in Sec. VI-B. A. Feature Map for Decomposed SLA Requirements The kernel input ũ(z) is constructed in two stages: (i)
(ii)
z 7−→ uraw (z) 7−→ ũ(z). Stage (i) transforms the decomposed SLA requirements so that larger values consistently represent stricter requirements, despite differences in their original units and directions, and concatenates the transformed values into uraw (z). Stage (ii) standardizes every dimension using the current training inputs of each GP, producing ũ(z) whose dimensions have comparable numerical scales for kernel evaluation. (i) Fixed Input Transformation: In the experiment of Sec. VI-A4, x = (w, η 1 , η 2 , η 3 ), where w, η 1 , η 2 , η 3 ∈ ∆|D|−1 . For the numerical values expressed in the units listed in Table S2, we transform the decomposed requirements so that a larger value represents a stricter domain-level SLA requirement: (latency)
− log(δt wd ),
(throughput)
log(θt ),
(guarantee)
− log(1 − gt,id,i ),
η
i ∈ {1, 2, 3}.
These transforms assign larger values to stricter requirements and are finite over the parameter ranges in Table S2. We concatenate the latency and throughput components over d ∈ D, and the guarantee components over (d, i) ∈ D × {1, 2, 3}, to form the unstandardized kernel feature vector uraw (z). The coverage set At and traffic profile θ t are not included in this input transformation. Their use in constraintGP training and prediction is described in Sec. G-B. (ii) Standardization Using Training Data: At every scheduled refit, each reward or constraint GP computes the mean and standard deviation of each dimension of uraw (z) over its current training inputs. The GP uses these statistics to
Wt = f (zt ) + εft .
(S42)
For the constraint observations, define the aggregate mean (1) offered traffic rate of the round-t request as Lt := |At |λt mB,t , where |At | is the number of covered gNBs, λt is the packet(1) arrival rate per gNB, and mB,t is the mean packet size. This quantity is used to express the observed resource consumption per unit of offered traffic rate before fitting the constraint GPs. Define the traffic-normalized observation and its corresponding mean as Vt,d,j :=
Ut,d,j , Lt
µVd,j (zt ) :=
mΓd,j (zt ) . Lt
(S43)
For the successful, on-path rounds included in the constraint training set, the observation model is (constraint)
Vt,d,j = µVd,j (zt ) + εVt,d,j .
(S44)
Noise Models and Fitting: The reward GP uses one noise variance shared by all observations (homoscedastic noise), whereas each constraint GP uses a noise variance estimated separately for each observation (heteroscedastic noise), as detailed below. Since Gaussian random variables are subGaussian, the homoscedastic and heteroscedastic Gaussian likelihood models are consistent with the noise conditions in Assumptions 6 and 7. We next describe how the reward and constraint GPs model observation noise and fit their parameters. At each scheduled refit, the kernel and likelihood parameters are fitted by maximizing the marginal likelihood. In the descriptions below, τ ∈ [t−1] indexes a training round for the reward or constraint model used in round t. 1) Reward Estimate (Homoscedastic Noise): For the reward GP in Sec. V-C2, the fitting model for (S42) is εfτ ∼ N (0, v f ),
(S45)
where v f is one noise variance fitted and shared by all reward observations. 2) Constraint Estimates (Traffic Normalization and Heteroscedastic Noise): The constraint estimates combine two operations with distinct purposes. (i) Traffic normalization removes the increase in resource consumption caused by a higher offered traffic rate, whereas (ii) the heteroscedastic noise model represents the residual variation that remains after normalization. The two operations are described below. (i) Traffic Normalization and Output Rescaling: Resource demand depends not only on the decomposed SLA requirements but also directly on the coverage set At and
39
TABLE S2 E XPLICIT MAPPING FROM EXPERIMENTAL PARAMETERS TO NSR TUPLE ELEMENTS AND DECOMPOSITIONS
NSR Instantiation Rule
URLLC (5QI 86)
eMBB (5QI 6)
Decomposition
A
Active-cell ratio ρA
ρA = 0.25
ρA = 0.75
No decomposition.
θ
Packet-arrival rate per gNB (packets/s) (1) Packet-size mean mB (bits)
20,000 1,600
15,000 9,600
No decomposition.
δt : target delay; δt ∈ [2, 5] ms
δt : target delay; δt = 0.3 s
P Choose wt,d ( d wt,d = 1); split delay budget as δt,d = wt,d δt .
R
R1 : Latency component R1 = (Nt , {Dt ≤ δt }), where Dt is the delay random variable (s). R2 : Throughput component R2 = (Ω, {Θt ≥ θt }), where Θt is the throughput random variable (Mbit/s). R3 : Non-drop component R3 = (Ω, Nt ) (fixed template)
θt : target rate; θt ∈ [100, 120] Mbit/s No class-specific parameter
Fixed per-domain check Θt,d ≥ θt ; no event decomposition parameter.
g
θt : target rate; θt ∈ [10, 25] Mbit/s No class-specific parameter
g1 : Guarantee for latency component R1 g1 = 99.99%
g1 = 98%
g2 : Guarantee for throughput component R2
g2 ∈ [99, 99.9]%
g2 ∈ [95, 98]%
g3 : Guarantee for non-drop component R3
g3 = 99.999%
g3 = 99.9999%
traffic profile θ t . For example, increasing the number of covered gNBs in At or the packet-arrival rate specified by θ t increases the aggregate traffic that the slice must carry, even when the decomposed requirements remain fixed. The resulting increase in traffic raises the demand on the AN, TN, and CN resources that carry that traffic. In our experimental implementation of the constraint GPs, we represent this dominant traffic-volume effect through the (1) aggregate offered traffic rate Lt = |At |λt mB,t and model the total demand as scaling with Lt . Because this known multiplicative structure can be encoded directly, we do not include At or θ t in the kernel input. This choice avoids requiring each resource-wise GP to infer the same trafficvolume scaling from a limited number of observations and instead focuses kernel learning on the relationship between the decomposed SLA requirements and the resource demand per unit of offered traffic. The fitting and prediction procedures are summarized below. (Fitting): For resource (d, j), fitting uses the trafficnormalized observations Vτ,d,j . Before fitting, observations above the empirical 99th percentile of the training set are replaced by that percentile to prevent a small number of unusually large values from dominating the fit. After this preprocessing, the GP is fitted, yielding a posterior mean and standard deviation on the Vt,d,j scale. (Prediction): At prediction, the posterior mean and standard max deviation on the Vt,d,j scale are multiplied by Lt /Cd,j . This rescaling converts the per-unit demand into the request’s total resource demand expressed as a fraction of the resource capacity. The rescaled posterior quantities are then used to form a lower confidence bound. (ii) Heteroscedastic Noise Estimation: Each constraint GP models the residual in (S44) using a separate variance vτ for
No event decomposition. P Choose ηt,d,1 ( d ηt,d,1 = 1); ηt,d,1 split as gt,d,1 = gt,1 . P Choose ηt,d,2 ( d ηt,d,2 = 1); ηt,d,2 . split as gt,d,2 = gt,2 P Choose ηt,d,3 ( d ηt,d,3 = 1); ηt,d,3 . split as gt,d,3 = gt,3
each training round τ : εVτ,d,j ∼ N (0, vτ ).
(S46)
The observation-specific variances allow the amount of unexplained variation in resource-consumption observations to differ across request–decomposition pairs; the single variance v f used by the reward GP would not represent these differences. To estimate vτ in (S46), we first fit a constraint GP with (0) one shared noise variance to Vτ,d,j . Using the mean V̂d,j (zτ ) predicted by the initial GP at each training input, we compute (0) rτ := Vτ,d,j − V̂d,j (zτ ), ξτv := log rτ2 + ϵlog . (S47) Here, ϵlog > 0 is a stabilizing offset that keeps the logarithmic target finite when rτ = 0. A second GP with one shared noise variance is fitted to ξτv . The mean ξˆτv predicted by the second GP determines vτ = clip[vmin , vmax ] exp(ξˆτv ) . (S48) Here, 0 < vmin < vmax are the lower and upper clipping bounds on the observation-specific noise variance, respectively. In all experiments, we set ϵlog = 10−8 , vmin = 2 × 10−3 , and vmax = 1. The constraint GP is then refitted once using vτ as the fixed noise variance for training round τ. A PPENDIX H T HE P ERFORMANCE E VALUATION M ODEL This section specifies the experimental implementation of the domain-specific controllers. The experimental performance model evaluates downlink user-plane traffic from the selected UPFs to the active gNBs. Accordingly, each selected route is oriented from CN through TN to AN and includes the downlink radio-side output resource at its gNB endpoint, which abstracts the final transmission to the served terminal. Given
40
TABLE S3 P RINCIPAL SYMBOLS FOR THE EXPERIMENTAL CONTROLLER IMPLEMENTATION
Network-level Composition and Admission λt out λin t,d,j , λt,d,j
Yt,d,j , Yt,d , Yt Bt,d,j rem Ct,d,j
Simulator state collecting the current resource-level input and output traffic rates. Input and success-branch output packet-arrival rates at resource (d, j). Resource-level, domain-level, and E2E feasibility indicators. et,d,j for Domain demand report containing U j ∈ Γd (st ) and zero otherwise. rem Remaining capacity; Crem := (Ct,d,j )d,j . t
Per-resource Feasibility and Allocation edge edge δt,TN,j , gt,TN,i
ᾱt,d,j req βbt,d,j βet,d,j et,d,j U
TN edge-level thresholds produced by the deterministic TN mapping (i ∈ {1, 2, 3}). rem max Physically available ratio Ct,d,j /Cd,j . Feasible-side bisection estimate of the minimum required ratio within the physical range. Trial required ratio after the nonnegative random overhead. max Trial-demand value βet,d,j Cd,j for an evaluated resource. Queueing and SLA Metrics
µt,d,j (β) ρt,d,j (β) pt,d,j,n (β) Λout t,d,j (β) Θt,d,j,Twin
Service rate under the candidate capacity max . βCd,j Traffic intensity for M/M/1/Kd,j at candidate ratio β. Stationary probability that queue length is n. Accepted-packet rate at resource (d, j) under candidate ratio β. Windowed throughput random variable at resource (d, j).
the path-induced resource set Γd (st ) and the delegated request sd (st , xt ), each controller works backward from the SLA targets specified in sd (st , xt ) through an M/M/1/K queueing model to determine the required capacity of each resource in Γd (st ). As specified in Sec. VI-A3, the experiments instantiate M = 3, with Rt,1 , Rt,2 , and Rt,3 representing conditional latency, throughput, and non-drop, respectively. The simulator performs this calculation from CN through TN to AN, passes the output traffic rate of each resource to the next resource, and admits the request only when every traversed resource is feasible. In this section, we first describe how the simulator passes traffic through the resources from CN to AN and admits a request only if every required resource can support it (Sec. H-A). We then explain how a controller determines the capacity required at one resource and checks it against the available capacity (Sec. H-B). Finally, we specify the M/M/1/K-based conditional-latency, throughput, and non-drop probabilities evaluated at each resource and their comparison with the delegated probability targets (Sec. H-C). Algorithm S1 summarizes the complete per-request procedure. Table S3 summarizes the principal symbols used throughout this section.
Algorithm S1 Sequential Domain Composition and Atomic Admission for One Request Require: st , xt ; {Γd (st ), sd (st , xt )}d∈D ; current remaining capacities Crem t 1: λt ← I NITIALIZE S OURCES(st ) 2: for d = CN, TN, AN, in this order do (Yt,d , λt , Bt,d ) 3: ← E VALUATE D OMAIN(d, Γd (st ), sd (st , xt ), λt ) 4: if Yt,d = 0 then 5: return 0, 0, Crem t 6: end if 7: end for (Yt , Ut , Crem t+1 ) 8: ← ATOMIC A DMISSION {Bt,d }d∈D , Crem t 9: return Yt , Ut , Crem t+1 10: procedure E VALUATE D OMAIN(d, Γd (st ), st,d , λt ) 11: Yt,d ← 1 12: Bt,d ← 0 13: for each j ∈ Γd (st ), in topological order do
et,d,j , λout ) (Yt,d,j , U t,d,j rem ← E VALUATE R ESOURCE(st,d , λin t,d,j , Ct,d,j ) 15: Yt,d ← Yt,d Yt,d,j et,d,j 16: Bt,d,j ← U 17: if Yt,d,j = 0 then 18: return Yt,d , λt , and Bt,d 19: end if 20: λt ← P ROPAGATE R ATE(d, j, λout t,d,j , λt ) 21: end for 22: return Yt,d , λt , and Bt,d 23: end procedure
14:
) 24: procedure ATOMIC A DMISSION ({Bt,d }d∈D , Crem t 25: Ut ← (Bt,d )d∈D rem 26: Crem − Ut t+1 ← Ct 27: return 1, Ut , Crem t+1 28: end procedure
A. Network-level Composition and Atomic Admission At round t, each Φd receives the path-induced resource set Γd (st ) and delegated request sd (st , xt ). Because the input traffic rate of each resource is determined by the output traffic rates of its preceding resources, the simulator evaluates resources sequentially from CN through TN to AN and propagates each output rate downstream (Sec. H-A1). This sequencing only carries the upstream traffic rates downstream; each controller otherwise uses its delegated inputs and local operational state independently. Within each domain d, the resource-level success indicators Yt,d,j are combined into Yt,d . Evaluation stops at the first resource-level failure and returns Yt = 0 and Ut = 0 without evaluating the remaining resources. If every traversed resource is feasible, the domain demand reports are committed atomically as the realized resource-consumption vector Ut (Sec. H-A2). 1) Source Initialization and Traffic Propagation: To determine the traffic offered to each resource, the simulator first assigns the request traffic to the selected CN roots
41
(I NITIALIZE S OURCES). It then passes the output traffic rate of each successfully evaluated resource to the resources that follow it on the selected paths (P ROPAGATE R ATE). These two steps update λt as the simulator proceeds from CN through TN to AN. (i) I NITIALIZE S OURCES. This procedure initializes λt by assigning the CN-root input rates separately for each selected UPF; all other resource-level rates are populated by subsequent calls to P ROPAGATE R ATE. Let ιt (a) ∈ U be the UPF selected for active gNB a ∈ At . For each c ∈ U, define the active gNBs assigned to c as At (c) := {a ∈ At | ιt (a) = c}. For each a ∈ At (c), let Pt (c, a) denote the selected directed downlink path from c to a. For each CN root edge j leaving c, define At (c, j) := {a ∈ At (c) | (CN, j) ∈ Pt (c, a)}.
(S49)
The offered source rate associated with UPF c is λsrc t,c := |At (c)|λt ,
(S50)
where λt is the common offered packet-arrival rate per active gNB, specified by the traffic/service profile θ t of request st (Definition 1). For each CN root edge j leaving c, the input rate is initialized as λin t,CN,j := |At (c, j)|λt .
(S51)
(S52)
The fraction of the output of (d, j) directed to (d′ , j ′ ) is therefore nt (d′ , j ′ )/nt (d, j). The corresponding contribution and the total input rate of (d′ , j ′ ) are ′ ′ out nt (d , j ) , λcontrib t,(d,j)→(d′ ,j ′ ) := λt,d,j nt (d, j) X λin λcontrib t,d′ ,j ′ := t,(d,j)→(d′ ,j ′ ) . (d,j)→(d′ ,j ′ )
j∈Γd (st )
The implementation evaluates this conjunction by short circuit: once some Yt,d,j = 0, it returns Yt,d = 0 and skips the et,d,j is the internal trial-demand remaining resources. Here, U value returned by E VALUATE R ESOURCE, whereas Bt,d,j is the corresponding domain-level report exposed by E VALUATE D O MAIN, consistent with the controller interface in Sec. III-C2. When Yt,d = 1, every traversed resource has been evaluated, et,d,j := 0 and the implementation uses the zero-extension U for j ∈ / Γd (st ). The complete domain demand report is then et,d,j , Bt,d,j := U
Thus, traffic is partitioned across the selected UPFs and their root edges rather than replicated. (ii) P ROPAGATE R ATE. P ROPAGATE R ATE distributes the output traffic rate λout t,d,j of a successfully evaluated resource (d, j) among the resources (d′ , j ′ ) that follow it on the selected paths and records their resulting input rates λin t,d′ ,j ′ in λt . In the four experimental topologies, the selected paths form a directed tree rooted at each UPF. Thus, if resource (d, j) feeds resource (d′ , j ′ ), every active gNB whose path contains (d′ , j ′ ) also has a path containing (d, j). Because all active gNBs in a request have the same offered rate λt , the output of (d, j) is divided in proportion to the number of these gNBs served through each following resource. To express this number, define nt (d, j) := |{a ∈ At | (d, j) ∈ Pt (ιt (a), a)}| .
2) Domain Demand Reporting and Atomic Admission: The simulator does not reduce any resource capacity while evaluating the individual resource requirements. Instead, E VALUATE D OMAIN aggregates the resource-level indicators {Yt,d,j }j∈Γd (st ) into Yt,d and, when all of them equal 1, constructs the domain demand report Bt,d . E VALUATE D OMAIN and the outer domain loop terminate at the first local failure. If all domain evaluations succeed, ATOMIC A DMISSION commits {Bt,d }d∈D . This prevents a request that fails in one domain from consuming capacity. (i) E VALUATE D OMAIN. Let Yt,d,j ∈ {0, 1} indicate et,d,j . whether resource (d, j) can support its trial demand U Conceptually, the domain-level indicator combines these resource-level indicators: Y Yt,d := Yt,d,j . (S54)
(S53)
Only resources traversed by the current request are processed, so the denominator nt (d, j) is positive whenever this propagation rule is used.
j ∈ [Jd ].
(S55)
(ii) ATOMIC A DMISSION. The E2E admission result is the conjunction of the domain-level indicators: Y Yt := Yt,d . (S56) d∈D
The algorithm evaluates this conjunction by short circuit. If unchanged. Yt = 0, it returns Ut = 0 and leaves Crem t If Yt = 1, all domain demand reports are complete, and rem ATOMIC A DMISSION commits them jointly. Let Ct,d,j denote the capacity of resource (d, j) available immediately before rem max := round t, initialized as C1,d,j := Cd,j , and write Crem t rem (Ct,d,j )d,j . On the successful branch, the realized consumption and remaining capacity are Ut,d,j := Bt,d,j , rem rem Ct+1,d,j := Ct,d,j − Ut,d,j .
(S57)
Hence, if any traversed resource is infeasible, no capacity is consumed and all remaining capacities are unchanged. B. Per-resource Required Capacity and Feasibility Check For each resource (d, j), the controller first tests whether the remaining capacity can satisfy the delegated SLA checks under the current input traffic and, if so, determines the minimum required capacity within that physical range. This calculation uses the delegated request st,d := sd (st , xt ), the input rate rem λin t,d,j , and the remaining capacity Ct,d,j . Upon local success, out it also determines the output rate λt,d,j passed to the resources evaluated next. Algorithm S1 implements this calculation as E VALUATE R ESOURCE. The steps below assume λin t,d,j > 0
42
(the implementation skips a zero-input resource and returns et,d,j , λout ) = (1, 0, 0)). (Yt,d,j , U t,d,j We first translate the delegated domain-level SLA requirements in st,d into resource-level checks for the traversed resources (Sec. H-B1). We then test the physical upper ratio and, when that upper ratio is feasible, use bisection to estimate the minimum required ratio within the physical range (Sec. H-B2). Finally, we add the experimental allocation variation, form the et,d,j , check it against the remaining internal trial demand U capacity, and determine Yt,d,j and, upon local success, λout t,d,j (Sec. H-B3). 1) Constructing Per-resource SLA Checks: For every resource on the selected path, the evaluator derives resourcelevel conditional-latency, throughput, and non-drop checks from the delegated domain-level requirements. AN and CN (Direct Use): An experimental path contains one resource from each of the AN and CN domains. The corresponding delegated domain-level checks are therefore applied directly to those resources. TN (Fixed Uniform Split): A TN path may contain several TN resources, so the controller translates each delegated TNdomain requirement into checks for the traversed resources. This translation applies the same target- and guaranteeallocation construction as the admissible decomposition in TN be the maximum number Definition 2 and Table V. Let Hmax of TN-managed resources on any selected UPF–gNB path in the environment. Its values for the Tree, Tree dual-UPF, Ring, and Ring dual-UPF configurations are 1, 1, 3, and 2, respectively. For the current TN-domain latency threshold δt,TN and probability targets gt,TN,i , the controller specializes both the latency-target weight and each guarantee-allocation TN exponent uniformly to 1/Hmax , yielding edge δt,TN,j :=
δt,TN , TN Hmax
1/H TN edge gt,TN,i := (gt,TN,i ) max ,
(S58) i ∈ {1, 2, 3}.
nondecreasing in β. Accordingly, the evaluation has two steps: (i) the controller first tests the physical upper ratio and then, only when that ratio is feasible, (ii) searches for the minimum required ratio within the physically available range. (i) Physical Upper-Ratio Check. The physical upper ratio before evaluating the current request is ᾱt,d,j :=
rem Ct,d,j max ∈ [0, 1]. Cd,j
(S60)
The stated range follows because the remaining capacity max is initialized to Cd,j and only decreases upon admission. The implementation sets Feasiblet,d,j (0) = 0 and first evaluates Feasiblet,d,j (ᾱt,d,j ). If Feasiblet,d,j (ᾱt,d,j ) = 0, monotonicity implies that no ratio within the physically available range is feasible. The procedure therefore returns et,d,j , λout ) = (0, 0, 0); the short-circuit rules in (Yt,d,j , U t,d,j Algorithm S1 then terminate the request evaluation. (ii) Capacity-Bounded Minimum-Ratio Search. If Feasiblet,d,j (ᾱt,d,j ) = 1, the controller applies bisection over [0, ᾱt,d,j ]. The feasible side of the final interval is returned as req βbt,d,j , the numerical estimate of the minimum required ratio within the physical range. 3) Trial Demand, Local Feasibility, and Output Rate: Using the physical upper ratio ᾱt,d,j and the result of the preceding minimum-ratio search, the E VALUATE R ESOURCE et,d,j , (ii) determines procedure (i) constructs the trial demand U the resource-level feasibility indicator Yt,d,j , and, only upon local success, (iii) computes the output rate λout t,d,j propagated to downstream resources. These three steps are detailed below. (i) Trial Demand Construction. To represent variation in a domain-specific controller’s allocation decisions that is not captured by the analytical queueing calculation, the procedure req adds a small nonnegative random overhead to βbt,d,j . After Feasiblet,d,j (ᾱt,d,j ) = 1 has been established, the procedure samples εt,d,j ∼ Uniform(0, εmax,d ) (S61)
TN On a selected path containing nhop ≤ Hmax TN resources, and under the simulator’s approximation that their success events independently across resources and rounds, with εmax,d = 0.05 for every d ∈ D in all experiments, and forms are independent, the two preservation relations are X edge req εt,d,j nhop βet,d,j := βbt,d,j e , δt,TN,j = TN δt,TN ≤ δt,TN , (S62) Hmax et,d,j := βet,d,j C max . j on path U d,j Y edge n /H TN gt,TN,i = (gt,TN,i ) hop max ≥ gt,TN,i , i ∈ {1, 2, 3}. req The feasible-side estimate βbt,d,j represents the computed minj on path imum required ratio, so the nonnegative multiplier models ran(S59) dom allocation overhead above that value. This perturbation is Thus, this split satisfies the same target-preservation and the simulator-level implementation of the allocation variation guarantee-allocation relations as an admissible decomposition. described above; it is distinct from the stationary-response law 2) Physical Feasibility and Minimum-Ratio Search: To ν for the final provisioning outcome (Y, U). s,x determine the resource allocation for the delegated request req εt,d,j (ii) Local Feasibility Check. Since βet,d,j = βbt,d,j e st,d , the controller first searches for the minimum allocation req max ratio, measured relative to the initial capacity Cd,j , needed and εt,d,j ≥ 0, we have βet,d,j ≥ βbt,d,j . The monotonicity of at resource (d, j). It uses β ≥ 0 as this normalized search Feasiblet,d,j (β) ensures that βet,d,j also satisfies the resourcemax variable, so the corresponding candidate capacity is βCd,j . local SLA requirements; local feasibility additionally requires in For the current st,d and input rate λt,d,j , let Feasiblet,d,j (β) ∈ βet,d,j ≤ ᾱt,d,j . Within this branch, the resource-level feasibilmax {0, 1} indicate whether the candidate capacity βCd,j satisfies ity indicator is therefore the resource-local SLA requirements. Its formal definition is given in Sec. H-C4. Under that definition, Feasiblet,d,j (β) is Yt,d,j := 1{βet,d,j ≤ ᾱt,d,j }. (S63)
43
If Yt,d,j = 0, the request evaluation terminates before computing or propagating an output rate; the fixed return signature uses zero for its unused third component. (iii) Output-Rate Evaluation. When Yt,d,j = 1, the procedure evaluates and returns the output rate at the trial ratio: out e (S64) λout t,d,j := Λt,d,j βt,d,j .
3) Per-resource SLA Probability Models: The queueing quantities above determine the non-drop, conditional-latency, and throughput probabilities used by the resource-local feasibility predicate Feasiblet,d,j . (i) Non-drop Probability. Define the per-resource non-drop event by Nd,j := {Qd,j < Kd,j }. For candidate ratio β > 0, the non-drop probability is
Here, Λout t,d,j (β) denotes the accepted-packet rate under candidate ratio β, formally defined in (S67).
Pr(Nd,j ) = 1 − pt,d,j,Kd,j (β).
C. M/M/1/K-based SLA Metric Calculation This subsection first instantiates the M/M/1/K model for each resource from the environment configuration, requestdependent traffic descriptors, current input rate λin t,d,j , and candidate allocation ratio β (Sec. H-C1). It then uses the instantiated model to determine µt,d,j (β), ρt,d,j (β), the queuelength distribution, and the accepted-packet rate Λout t,d,j (β) (Sec. H-C2). Finally, these quantities determine the three SLAsuccess probabilities (Sec. H-C3), which are combined to define Feasiblet,d,j (β) (Sec. H-C4). 1) M/M/1/K Model Instantiation: This subsubsection instantiates the common M/M/1/K model used for every traversed resource (d, j). The environment configuration assigns max each resource its maximum capacity Cd,j , queue depth Kd,j , and propagation distance ℓd,j , and fixes the propagation speed vprop and throughput window Twin . For request st , the traffic/service profile θ t specifies the common per-gNB (1) source packet-arrival rate λt and the mean packet size mB,t in bits. At each resource, the experimental model treats packet arrivals as a Poisson process with the current input rate λin t,d,j and packet sizes as independent exponential random variables. Consequently, the second packet-size moment is (2) (1) mB,t = 2(mB,t )2 . 2) Queueing Quantities and Accepted Rate: For each resource (d, j), candidate ratio β > 0, and round-specific input rate λin t,d,j , the service rate µt,d,j (β) and traffic intensity ρt,d,j (β) used by the capacity-bounded feasibility search are µt,d,j (β) := ρt,d,j (β) :=
max βCd,j (1) mB,t λin t,d,j
,
µt,d,j (β)
(ii) Conditional Latency Probability. By the Poisson arrivals see time averages (PASTA) property [62], an arriving packet observes the stationary queue-length distribution pt,d,j,n (β). Hence, its queue-length distribution conditional on Nd,j is pN t,d,j,n (β) := Pr(Qd,j = n | Nd,j ) β
=
.
Qd,j ∈ {0, . . . , Kd,j } denotes the steady-state number of packets in the M/M/1/Kd,j system at resource (d, j), including the packet in service. Here and below, Prβ denotes probability under the current request, input rate, and candidate ratio β. For β > 0, let pt,d,j,n (β) := Prβ (Qd,j = n). Writing ρ := ρt,d,j (β), it is given by 1−ρ ρn , ρ ̸= 1, 1 − ρKd,j +1 pt,d,j,n (β) = (S66) 1 , ρ = 1, Kd,j + 1 for n ∈ {0, . . . , Kd,j }. For β > 0, the resulting acceptedpacket rate is in Λout (S67) t,d,j (β) := λt,d,j 1 − pt,d,j,Kd,j (β) .
(S69)
pt,d,j,n (β) . 1 − pt,d,j,Kd,j (β)
This definition applies for n = 0, . . . , Kd,j − 1. The Erlang sys mixture models the system delay Dd,j , which includes both waiting and service time. Let ℓd,j be the propagation distance of resource (d, j), and define prop τd,j :=
ℓd,j , vprop
sys prop Dd,j := Dd,j + τd,j .
(S70)
For a positive input rate and any latency threshold δ, the conditional latency probability is Pr(Dd,j ≤ δ | Nd,j ) β
Kd,j −1
=
X
prop pN . t,d,j,n (β)FErlang(n+1,µt,d,j (β)) δ − τd,j
n=0
(S71) Here, for k ∈ N, µ > 0, and Z ∼ Erlang(k, µ), the CDF FErlang(k,µ) is given by FErlang(k,µ) (x) = Pr(Z ≤ x) 0, =
(S65)
(S68)
β
x < 0, k−1 X
(µx)m −µx , 1 − e m! m=0
(S72)
x ≥ 0.
(iii) Throughput Probability. Let Twin > 0 denote the duration of the observation window used for the throughput check. In all experiments, we set Twin = 0.1 s. The random variable Θt,d,j,Twin represents the average accepted-packet bit rate over this window, obtained by dividing the total size of the packets accepted during the window by Twin : Θt,d,j,Twin :=
1 Twin
Nt,d,j (Twin )
X
Lpkt t,m ,
(S73)
m=1
where Nt,d,j (·) is the accepted-packet counting process and {Lpkt t,m }m are packet sizes, independent of one another and of (1) (2) Nt,d,j (·), with moments mB,t and mB,t . To obtain a tractable throughput probability, the experimental model adopts two approximations for a candidate ratio β > 0: it models Nt,d,j (·) as a Poisson process with rate Λout t,d,j (β) and applies a
44
normal approximation to the resulting compound-Poisson sum Twin Θt,d,j,Twin . Under these approximations, ! (2) out (1) Λt,d,j (β)mB,t out Θt,d,j,Twin ≈ N Λt,d,j (β)mB,t , . (S74) Twin Hence,
(1) (β)mB,t θ − Λout t,d,j . Pr(Θt,d,j,Twin ≥ θ) ≈ 1 − Φ q β (2) out Λt,d,j (β)mB,t /Twin (S75) The two approximations above are motivated as follows. (Poisson Approximation.) The model assumes that finitebuffer blocking is sufficiently rare for its effect on packetarrival timing at downstream resources to be negligible. This low-blocking assumption is expressed as pt,d,j,Kd,j (β) = Pr(Qd,j = Kd,j ) β
= 1 − Pr(Nd,j ) ≪ 1.
(S76)
β
Under this Poisson approximation, the throughput probability is evaluated using only the accepted-packet rate Λout t,d,j (β) in (S67), without tracking the queue-state dependence of accepted packet arrivals. Because this rate incorporates the mean packet loss predicted by the M/M/1/Kd,j model, the approximation retains its mean effect while neglecting its effect on downstream packet-arrival timing. (Normal Approximation.) The model assumes that the expected number of accepted packets Λout t,d,j (β)Twin is sufficiently large. Because the independent packet sizes have a finite second moment, the central limit theorem then supports the normal approximation to the compound-Poisson sum Twin Θt,d,j,Twin . 4) Resource-local Feasibility Predicate: For the current delegated request st,d and a resource with positive input rate λin t,d,j , the controller evaluates each candidate ratio β > 0 by combining conditional-latency, throughput, and non-drop checks. To express their domain-specific targets uniformly, define ( edge δt,TN,j , d = TN, δ̄t,d,j := δt,d , d ∈ {AN, CN}, ( (S77) edge gt,TN,i , d = TN, ḡt,d,j,i := gt,d,i , d ∈ {AN, CN}, where i = 1, 2, 3 correspond to conditional latency, throughput, and non-drop, respectively. The derivation of the TNspecific targets is given in Sec. H-B1. Using these targets, E VALUATE R ESOURCE evaluates the predicate n o (D) (Θ) (N ) Feasiblet,d,j (β) := 1 Ct,d,j (β) ∧ Ct,d,j (β) ∧ Ct,d,j (β) , (S78) where (D)
Ct,d,j (β) := Pr(Dd,j ≤ δ̄t,d,j | Nd,j ) ≥ ḡt,d,j,1 , β
(Θ) Ct,d,j (β) := Pr(Θt,d,j,Twin ≥ θt ) ≥ ḡt,d,j,2 , β (N )
Ct,d,j (β) := Pr(Nd,j ) ≥ ḡt,d,j,3 . β
(S79)
As shown below, Feasiblet,d,j (β) is nondecreasing in β, req which justifies applying bisection to compute βbt,d,j , the numerical estimate of the minimum feasible ratio (Sec. H-B2). Monotonicity for Bisection. Increasing β increases the service rate µt,d,j (β), which does not decrease the conditionallatency or non-drop probability. It also does not decrease the accepted-packet rate Λout t,d,j (β), and hence the throughput probability under the normal approximation. Thus, under the queueing and approximation models above, the probabilities (D) (Θ) (N ) defining Ct,d,j (β), Ct,d,j (β), and Ct,d,j (β) are nondecreasing in β. Therefore, Feasiblet,d,j (β) is also nondecreasing. D. NR-Parameterized Access-Link Capacity Each downlink is represented by a finite-buffer queue with 128 packet slots and zero propagation distance. Its capacity is calculated independently per gNB from the following profile: 273 RBs, numerology µ = 3 (120-kHz subcarrier spacing), 256-QAM (Qm = 8), eight MIMO layers, maximum codingrate factor Rmax = 948/1024, downlink overhead OH = 0.18, scaling factor f = 1, and downlink duty factor rDL = 1. We convert these parameters to the nominal downlink rate using the TS 38.306 approximate maximum-data-rate expression [63]. For one downlink, its bit/s form is NRB · 12 max (1−OH)rDL , (S80) CAN = vlayers Qm f Rmax Tsµ where Tsµ = 10−3 /(14 · 2µ ) is the average OFDM symbol duration under the normal cyclic prefix. Substitution gives max CAN ≈ 17.83 Gbit/s,
(S81)
per gNB. The pair NRB = 273 and µ = 3 is not a transmissionbandwidth configuration specified in TS 38.104: at 120-kHz subcarrier spacing, its listed maximum is 264 RBs for a 400MHz channel [64]. We therefore do not present this profile as a standards-compliant NR carrier. Instead, it is an NRparameterized custom wideband experimental profile. For candidate allocation ratio β, the access-queue service rate is max βCAN µt,AN,j (β) = . (S82) (1) mB,t (S82) is consistent with the general per-resource definition in Sec. H-C2. A PPENDIX I T OTAL R EWARD AND P ER -C LASS R ESULTS UNDER M IXED T RAFFIC This section complements the Successful-Slice Count results in Sec. VI-E with Total Reward and its class-specific components from the same runs. Let NrU and NrB be the admitted URLLC and eMBB counts in run r, respectively. Under the class prices in Sec. VI-A3, Total Reward is Rr = NrU +50NrB . Fig. S1 shows the two class contributions. Across the 24 mixed-traffic points, CCKB attains higher Total Reward than linCBwK at 23 points, with a mean difference of +19, and than Random at all 24 points, with
45
(a) Tree topology.
(2) TN bottleneck (3) CN bottleneck 600 (1) AN bottleneck 500 400 300 200 100 0 350 CCKB (Ours) linCBwK 300 CONFIG Random 250 200 150 100 50 00.00 0.02 0.04 0.06 0.08 0.00 0.02 0.04 0.06 0.08 0.00 0.02 0.04 0.06 0.08
Mean URLLC reward Mean eMBB reward
Mean URLLC reward Mean eMBB reward
(2) TN bottleneck (3) CN bottleneck 600 (1) AN bottleneck 500 400 300 200 100 0 350 CCKB (Ours) linCBwK 300 CONFIG Random 250 200 150 100 50 00.00 0.02 0.04 0.06 0.08 0.00 0.02 0.04 0.06 0.08 0.00 0.02 0.04 0.06 0.08
(b) Ring topology.
Mean total reward
Fig. S1. Mean class-specific reward contributions over 10 runs under mixed traffic. In each subfigure, the upper panels show the eMBB contribution 50NrB , and the lower panels show the URLLC contribution NrU , under AN, TN, and CN bottlenecks. The sum of the two contributions is Total Reward.
(1) sweep
300 200 100 0 0.1
AN CN TN
0.4
0.7
(2) c sweep
1.0
0.1
AN CN TN
0.4
c
0.7
1.0
Fig. S2. Hyperparameter sensitivity of the proposed algorithm. (1) Effect of the dual-cap parameter ρ with cβ = 0.1. (2) Effect of the exploration-scale parameter cβ with ρ = 1.0. Each curve reports mean Total Reward over 10 runs for each bottleneck condition.
a mean difference of +77. Against CONFIG, CCKB is higher at 15 points, with a mean difference of +6. Averaged over the mixing ratios, CCKB admits more URLLC slices in each topology–bottleneck condition; eight of the nine points where CONFIG attains higher Total Reward are driven by the eMBB component rather than by URLLC admissions. A PPENDIX J H YPERPARAMETER ROBUSTNESS A. Setup The setup follows Sec. VI-F1. Sweep Design: In the ρ sweep, we fix cβ = 0.1 and vary ρ ∈ {0.1, 0.4, 0.7, 1.0}. In the cβ sweep, we fix ρ = 1.0 and vary cβ ∈ {0.1, 0.4, 0.7, 1.0}. B. Result The two sweeps exhibit different patterns. The ρ sweep shows little visible change in Total Reward across the tested range (Fig. S2). The reward curves remain nearly flat for all three bottleneck conditions, suggesting that the proposed method is relatively insensitive to the precise value of the dual-cap parameter in this setting. For the cβ sweep, larger values consistently degrade performance across all three bottleneck settings. This trend suggests that, in the present problem setting, emphasizing exploration too strongly is not beneficial.