CS Paper Radar

Contextual Bandit-Based Decomposition of Network Slice Requirements under Cumulative Resource Budget Constraints

Masaki Kobayashi, Akito Suzuki, Ryoichi Kawahara, Masahiro Kobayashi

cs.NI ·submitted 2026-09-09 02:36 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Pathwise-Budgeted LLM Routing: Online Allocation with K-Bit Tail-Cost Learning

cs.LG math.OC ·2026-11-04 ·Hanzhang Qin, Sophie H. Yu, Yuewei Zhang, Zhi-Hai Zhang
similarity 0.66
Abstract

Firms using large language models under fixed budgets must decide which model to call and whether to retry a failed task. Because a call's charge is revealed only after completion, one long response can exhaust the remaining budget and leave later tasks unserved. Our objective is to maximize the number of tasks solved before service stops. We develop a contextual bandit policy, ADP-HT, which learns each model's task-specific success probability and constructs conservative cost estimates from coarsened response-length labels on a quantile grid with $2^K$ intervals. The policy weighs predicted success against these costs, adjusting the cost penalty to realized spending and the budget available per remaining task. Under calibration, local regularity, and grid-coverage conditions, we bound the excess allowance in the policy's conservative cost estimates. At a fixed sample size, increasing $K$ reduces the discretization term but increases the estimation allowance. At the tightest tested budgets, ADP-HT solves more than twice as many MATH500 and GPQA tasks as the best implemented baseline. It achieves the highest mean cumulative score at ten of fourteen RouterBench budgets. On LiveCodeBench, it outperforms a deployed commercial router in both default and cost-saving modes at the three lowest test budgets.

0.16

Learning Which Device to Call: Online Tool Grounding for LLM Agents in IoT

cs.AI ·2026-10-18 ·Yichen Liu, Xiaochong Jiang, Haoran Yu, Lifei Liu
similarity 0.65
Abstract

The Internet of Things (IoT) gives large language model (LLM) agents access to physical observations, but one requested capability is usually offered by several devices, and the agent's plan does not say which one to call. Existing work retrieves relevant tools and checks plan feasibility, without learning which eligible device returns a useful observation. Unlike previous works, we study online tool grounding: binding an already specified tool call to one physical endpoint under service cost and device participation constraints. We propose a framework that learns which physical device should execute each agent-issued call. It formulates selection as a contextual bandit problem and combines adaptive context partitions with hierarchical endpoint trees, so that execution feedback is reused across related requests and devices. Selection balances task success against service cost while respecting device capability, authorization, battery reserves, and availability. Gaussian reward aggregation provides an optional mechanism for protecting individual feedback values. Theoretical results establish a finite-horizon regret bound and differential privacy for released reward statistics under fixed, reward-independent assignments. In a simulated loading-dock workload, the proposed router achieves higher step success and better cost-adjusted service, at lower simulated device energy and latency, than nearest-device, advertised-quality, UCB1, and LinUCB selection.

0.23

RL-based Network Slice Embedding over Space Division Multiplexed Elastic Optical Networks

cs.NI ·2026-08-29 ·Divya Khanure, Riti Gour†, Congzhou Li, Jason P. Jue
similarity 0.64
Abstract · 6 pages

Network slicing over space-division-multiplexed elastic optical networks (SDM-EONs) requires jointly managing spectrum, spatial cores, and compute resources, a coupling that many existing studies ignore by treating compute placement independently from routing and spectrum decisions. This disconnect can cause the spectrum to be allocated along a path, only for the request to fail due to insufficient compute resources along the path, or may result in compute resources being allocated without consideration for spectrum resource availability on the path between compute nodes. We propose a path-constrained reinforcement learning framework that addresses compute node selection and RMCSA, being aware of both resources, restricting the RL agent's action space to nodes along $k$-shortest paths between request endpoints. Training incorporates reward shaping to improve robustness under high load. We propose PPO-Full (Proximal Policy Optimization-Full), which jointly selects compute nodes and routing paths via a multi-dimensional action space, against distance-based heuristics, a greedy baseline, and a decoupled VONE-DRL baseline on a 24-node USNET topology under hotspot traffic conditions. Results demonstrate consistent improvements in acceptance rate over all baselines at high load, with gains becoming more pronounced as traffic intensity increases.

0.28

CoSlice: Coordinated Multi-Agent Reinforcement Learning for 5G Network Slicing Allocation

cs.NI cs.LGcs.MA ·2026-11-18 ·Pengxin Wang, Nakjung Choi, Jingdi Chen
similarity 0.63
Abstract

Radio Access Network (RAN) slicing is a shared resource allocation problem: each slice seeks to satisfy its Service Level Agreement (SLA) with minimal radio-resource consumption, while all slices compete for a limited resource budget. This creates both an intra-slice trade-off between SLA assurance and resource efficiency and an inter-slice conflict over shared resources, calling for specialized yet coordinated control. In this work, we present CoSlice, a coordinated multi-agent reinforcement learning framework for inter-slice physical resource block allocation in Open Radio Access Network (O-RAN). CoSlice uses preference-conditioned slice agents for fast resource allocation and an LLM-based coordinator to adapt their objectives using global network observations at a slower timescale. We formulate the problem as a multi-objective partially observable stochastic game (mo-POSG), establish the existence of a Preference Correlated Equilibrium, and derive a sublinear regret bound for the learning procedure. We implement the algorithm by using a two-stage training procedure that consists of multi-objective pretraining and joint optimization. We build a network slicing evaluation environment using ORANSlice and its radio-frequency simulator (RFsim), supporting realistic protocol-stack execution and application traffic across multiple slices. Experimental results show that CoSlice reduces both average and tail SLA violations compared with other centralized and multi-agent baselines under diverse slice workloads.

0.24

Satisficing Regret Minimization in Bandits with Knapsacks

cs.LG stat.ML ·2026-10-29 ·Qing Feng, Tianyi Ma, Ruihao Zhu
theory similarity 0.62
Abstract

We study satisficing regret minimization in bandits with knapsacks (BwK), where a learner sequentially selects randomized policies, i.e., distributions over arms, to obtain mean rewards above a satisficing threshold as frequently as possible while respecting finite resource budgets. The performance is measured by satisficing regret, the cumulative deficits of the selected policies' mean rewards below this threshold. Resource constraints introduce two difficulties: an algorithm can incur linear satisficing regret even with small standard regret as deficits to the threshold cannot be compensated, and random consumption can cause early resource depletion even when policies are feasible in expectation. To address these challenges, we propose SELECTwK, a general algorithmic template that uses a BwK learning oracle algorithm with sub-linear expected (standard) regret upper bound to search for and test candidate satisficing policies (i.e., policies whose mean rewards exceed satisficing threshold and whose expected resource consumption is feasible over the time horizon). Our regret analysis, supported by an LP-duality argument, establishes that SELECTwK attains constant expected satisficing regret when a satisficing policy exists. We further introduce a stronger regret condition that bounds the expected sum of positive reward deficits to the optimal one at each time step, under which SELECTwK achieves a sharper constant bound together with a sub-linear bound in the time horizon. As a complement, SELECTwK still preserves the oracle's sub-linear expected standard regret bound if the satisficing threshold is unattainable. Finally, we establish the oracle conditions and corresponding satisficing regret bound for existing finite-armed BwK and dynamic pricing algorithms, and conduct numerical experiments on dynamic pricing with limited inventory to demonstrate the empirical performance of SELECTwK.

0.15

Multinomial Subset Routing with Sum-Max Rewards and Operational Constraints

cs.LG cs.AI ·2026-08-17 ·Quan Zhou, Yiyan Huang
similarity 0.62
Abstract

We study online routing to subsets of experts under aggregate bandit feedback and long-run operational constraints. Expert contributions can be complementary: for each task dimension, the best selected expert determines the contribution, and the total reward aggregates these dimension-wise maxima. At the same time, capacity, budget, and fairness requirements impose lower and upper bounds on long-run expert activation frequencies. A fixed deterministic subset cannot generally satisfy such heterogeneous requirements, motivating a stochastic routing policy. We formalize this problem as Multinomial Subset Routing (MSR). The learner maintains a distribution \(q\) over \(K\) experts, samples an expert independently \(M\) times from \(q\), and routes each task to the distinct sampled experts. We propose OMD-Approachability, which combines online mirror descent with Blackwell's approachability to optimize MSR under two-sided operational constraints. We establish \(O(T^{-1/2})\) average reward regret and expected constraint violation. We also quantify the approximation gap induced by a linear surrogate, and evaluate the approach on a real-world crowdsourcing dataset.

0.09

Lag: A Mean-Field Optimal Policy for Online Assignment with Reusable Resources

cs.LG cs.PFmath.OC ·2026-10-13 ·Keerthana Gurushankar
theory similarity 0.62
Abstract

We study online task assignment with reusable resources. This problem arises in peer reviewer assignment, skill-based call routing, rideshare matching, emergency dispatch, and crowdsourcing: Tasks arrive according to a geometric process and must be immediately assigned to servers that become temporarily busy, yielding rewards that depend on the task-server pair. The goal is to maximize long-run average reward. We cast the problem as a contextual restless multi-armed bandit (CRMAB). We derive an occupancy-measure LP (OCC-LP) that upper-bounds the reward of any work-conserving policy. From its dual we obtain Lag, a closed-form index policy. We introduce a scaling regime in which the number of copies of each server and the number of arrivals per step grow together. This regime yields the first deterministic fluid limit for a contextual bandit. In it, Lag is asymptotically optimal. Finally, we evaluate our algorithms on peer review datasets and call center routing. The Lagrangian index achieves 83-99% of the LP upper bound across all load levels. Moreover, the Lagrangian index policy significantly outperforms the natural greedy assignment scheme, improving reward by up to 12.3% on journal data and 36% on structured synthetic instances.

0.25

Sense Once, Serve Many: Common-Trace Factorized Constrained PPO for Online Sensing-Session Consolidation in Multi-Tenant ISAC Networks

cs.NI cs.LG ·2026-08-29 ·Dang-Dung Vu
similarity 0.61
Abstract · 13 pages, 4 figures, 6 tables

Integrated sensing and communication (ISAC) networks can serve compatible requests through shared sensing sessions, but consolidation couples admission, reuse, profile selection, sensing service-level agreements (SLAs), communication quality of service (QoS), and future commitments. We formulate this problem as a constrained Markov decision process and propose Common-Trace Factorized Constrained Proximal Policy Optimization (CT-PPO). During training, stochastic policy replicas share the same primitive workload trace; leave-one-out discounted Monte Carlo return contrasts provide reward credit to applicable actor factors, while constraint credit remains factor/prefix-specific. Across five training seeds and matched workloads, CT-PPO achieves the highest mean macro return, exceeding matched Joint-Credit PPO (JC-PPO) by 0.934 (95% confidence interval [0.702, 1.164]) and SLA-Aware Greedy by 1.847; versus JC-PPO, it reduces sensing-resource cost by 6.277 and raises accepted requests per created session by 0.0806. A four-way ablation shows that the factorized surrogate alone yields no detectable macro-return gain, whereas adding common-trace reward credit produces the dominant improvement. Without retraining, CT-PPO retains a return advantage at low, nominal, and high arrival loads, with the strongest gain under clustered arrivals. Deployment uses public observations and hard masks; CT-PPO's extra parameters are training-side, its actor footprint matches JC-PPO, and actor-only CPU latency is effectively unchanged.

0.38