Online Resource Allocation

Follow this topic Ask about this topic

Momentum

7 papers in the last four weeks, up 17% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 65

Oct 8, 2026cs.LG

Optimally Pacing Budget Spending and Learning

We establish near-optimal regret bounds for budget-constrained online learning against arbitrary classes of budget-pacing experts in the adversarial setting. In particular, given any class of

F

experts and a candidate budget pacing schedule, we provide a full-information algorithm which obtains regret

O(D \sqrt{\log F}+ \sqrt{T\log F})

against all experts whose cumulative spending stays within distance

D

of this schedule, matching lower bounds established by Braverman et al. (2025). We additionally show that our technique extends to various problems in online resource allocation, where the learner gets to see the rewards and costs of the current options available to them, and establish

O(D\sqrt{\log F})

regret bounds when fractional allocation is allowed. This is the first algorithm we are aware of which can achieve

o(\sqrt{T})

guarantees for such tasks.

Mark Braverman, Jingyi Liu, Jieming Mao +2

Department of Computer Science, Princeton University · Google Research

Online Learning Online Resource Allocation Minimax Regret

Oct 7, 2026cs.LG

Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More

We study finite-horizon online resource allocation with i.i.d. requests and an endogenous Markov state on a finite state space: each action affects the transition of the state that governs future rewards and resource consumption. In this problem, a transient fluid LP benchmark upper bounds the expected reward of every nonanticipating policy, while a stationary LP supplies randomized state-dependent controls. We assume that the stationary LP has a unique optimum and identify primal nondegeneracy and irreducibility of the optimal induced kernel as important regularity conditions in this framework. With a known request prior, we show that, under nondegeneracy and irreducibility, both frequent and infrequent re-solving attain

O(1)

regret. However, under a degenerate optimum, irreducibility yields the sharp worst-case

Θ(\sqrt{T})

rate for infrequent re-solving, while frequent re-solving can incur

Ω(T)

regret. Thus, more frequent optimization can perform asymptotically worse. With an unknown request prior, we develop a three-phase U-shaped infrequent re-solving policy that coordinates learning and inventory correction with

O(\log\log T)

LP solves. When the optimal induced kernel is irreducible and the algorithm is given the optimal target state class and a constant-cost entrance policy, it attains

O(1)

regret under nondegeneracy and

O(\sqrt{T})

regret under degeneracy. Without the target-class information, linear minimax regret is unavoidable. Numerical experiments further illustrate the instability of round-by-round re-solving relative to epoch-wise infrequent re-solving, show that thresholding greatly mitigates its loss, and find that infrequent schemes remain dominant under both known and estimated priors.

Zhaohua Chen

Taobao & Tmall Group of Alibaba, Renmin University of China

Online Resource Allocation Markov Decision Processes

Oct 1, 2026cs.NE

TRACE: Tackling Real-World Resource Assignment Problems via Agentic Heuristic Design

Dynamic resource assignment, the real-time allocation of task streams to heterogeneous processing nodes, is the backbone of modern computing infrastructure. While learning-based schedulers excel in research, industrial deployments still rely on hand-written rules that operators can read, audit, and execute within tight latency budgets. LLM-based Automatic Heuristic Design (AHD) promises to automate writing such rules. However, existing AHD frameworks were developed for combinatorial problems fully specified to the LLM, and they learn only from a scalar fitness score. In real systems, the behaviour that determines a good heuristic, such as processor speeds or power consumption, is unknown a priori: the score reveals which heuristic performs better, but not why. This missing information is recorded in the system logs that every evaluation produces. Exploiting it is non-trivial: logs are massive and noisy, the relevant signals depend on the objective, and their content and format vary across hardware and software stacks, so they can neither be fed to an LLM as is nor processed by a fixed parser. We propose TRACE, which couples an evolutionary AHD loop with an agentic knowledge-extraction workflow. A Reasoner agent analyzes the log schema in light of the objective and formulates hypotheses about the system dynamics; a Coder agent writes and executes schema-specific code to test them, producing insights or executable tools for the evolved heuristics. We evaluate TRACE on a synthetic cloud benchmark and a 5G vRAN scenario built from industrial testbed measurements and operational traffic traces. TRACE consistently outperforms state-of-the-art AHD methods in resource assignment problems and yields more auditable heuristics at under 2% overhead.

Jose A. Ayala-Romero, Andres Garcia-Saavedra, Xavier Costa-Perez

NEC Laboratories Europe · i2CAT Foundation and ICREA

Automated Heuristic Design LLM Agent Orchestration Cloud Computing Online Resource Allocation

Sep 29, 2026cs.DC

ARGOS: Reinforcement Learning-Driven Multidimensional Elasticity for Service Orchestration in the Computing Continuum

Data-intensive services in the Computing Continuum must balance analytics quality, resource usage, and cost across heterogeneous nodes with limited and uneven capacity. This balance becomes especially difficult when resource scaling reaches capacity limits, because changes in demand and cluster pressure must then be absorbed without violating client-defined quality ranges. Existing orchestrators mainly adapt resources, placements, or replicas, while analytics requirements such as coverage, sample, and freshness remain fixed. This article presents ARGOS, the Adaptive Reinforcement Learning-Driven Governance for Orchestrated Services, an end-to-end controller that formulates multidimensional elasticity as a per-request Markov decision process over analytics quality and cluster pressure, supported by capacity-aware admission. ARGOS is evaluated under controlled workloads and time-varying multi-tenant arrivals on a heterogeneous cluster. Across the controlled scenarios, the deep reinforcement learning policies consistently outperform the non-learning baselines and approach the independently tuned best-fixed reference. A separate live evaluation reports improvements over the static midpoint under realistic and saturated arrivals, with no recorded CPU or memory violations but remaining coverage violations. These results support deep reinforcement learning as an adaptive mechanism for multidimensional elasticity when resource scaling alone is insufficient.

Javier Mateos-Bravo, Sergio Laso, Juan Luis Herrera +3

Department of Computer Science and Telematics Engineering, University of Extremadura, Spain · Global Process and Product Improvement S.L., Spain · Department of Mechatronics, University of Prishtina, Kosova +2

RL Control Online Resource Allocation Edge-Cloud Computing

Sep 28, 2026cs.LG

ReCo: When to Relocate Sensor Kits under Deployment Constraints -- A NILM Case Study

Many sensing tasks obtain training labels only by deploying instruments in the field. With a limited number of sensor kits, a collection deadline, and measurement downtime at every move, the collector must repeatedly decide whether to stay at the current site or relocate. We study this decision in non-intrusive load monitoring (NILM), which estimates the power drawn by individual appliances from a home's main meter and is trained on data from homes temporarily fitted with appliance-level sub-meters. In NILM, appliance usage varies with the appliance, season and climate, and the value of new data depends on how diverse the combinations of target operation and background load are. To address this, we propose a constraint-based relocation framework and instantiate it for NILM as ReCo (Relocation by Coverage gain). ReCo counts new operating regimes in a joint target-background feature space, forecasts each home's future gain from the data collected so far, and each night weighs the gain of staying against the gain of moving elsewhere after the downtime. In replayed deployments on the Plegma dataset under two kit counts and two downtime costs, ReCo outperforms fixed-dwell and count-based schedules and a threshold rule using the same metric in every setting. Its advantage is not explained by collecting more days alone and reflects allocating the days to more valuable homes and periods.

Haokun Chen, Yu Tong, Yehai Chen

McMaster University Hamilton, ON, Canada · Shanghai Eneintel Technology Co., Ltd. Shanghai, China

Non-Intrusive Load Monitoring Online Resource Allocation

Sep 24, 2026cs.AI

A General Framework for Budgeted Threshold Incentives on Request

On-demand delivery platforms pay riders through incentive activities whose tiers are set from recent completions of riders with a similar history. Operators request such plans for changing periods, rider populations, payment rules and budgets, often for holidays or bad weather, where randomized trials are scarce and take months to collect. We present a request-driven framework that composes four stages (conditional prediction, population reduction, trajectory integration and budget allocation) through seven replaceable modules that exchange conditional trajectory laws, whose award probabilities and award-marked moments give payment and uplift for any activity rule. A response-correction step reweights trajectories from abundant no-offer history to match the moments of a short pilot. We prove that, on a fixed plan menu and given the stage errors, the end-to-end value loss is bounded by the sum of four stage terms, and that for every stage there are instances on which omitting it leaves an error floor the others cannot remove. On 3,000 riders over 45 weekly origins, all 127 windows of a week are answered 11.04x faster with identical scenarios and at most 0.92% value lost by the allocation. On 24 new controlled response laws, the response correction with a one-week pilot lowers regret by 51.2% relative to a trial with the same nominal randomized rider-weeks, and a four-week pilot with exact summation comes within +0.007 of an 18-week trial. In registered studies where windows, populations, rules and binding budgets change from request to request, the framework's regret is below that of a trial with the same nominal rider-weeks and below dose interpolation of the same pilot data, and reusing its one-off preparation answers 60 requests 14.1x and 2.70x faster with identical answers. Against a nine-offer trial fitted with the framework's own dose curve, one-week regret is 0.055 lower.

Zhuolin Wu, Chengrui Zhu, Wenhua Nie +9

Meituan · National Taiwan University · Tsinghua University +1

Causal Effect Estimation Online Resource Allocation

Sep 23, 2026cs.LG

Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving

The growth of large language model (LLM) inference and search services increases the scale of online linear programming problems, motivating computationally efficient algorithms. We develop resource-adaptive stochastic gradient descent (RASGD) for stochastic online linear programming. The algorithm uses one request and current inventory to update resource prices, requiring O(m) operations for m resources and memory per arrival and no LP or sample-average optimization. The central idea is to express the current-resource pricing logic of re-solving through a first-order SGD update: each arrival refreshes the remaining-inventory allowance in the dual objective, while the stepsize decreases for early learning and increases later to match the speed of inventory adjustment. Under standard non-degeneracy conditions, our algorithm is feasible on every sample path and achieves O(\log T) expected regret against the realized fractional hindsight optimum, which matches the lower bound, even for policies that know the distribution and have unrestricted computation. The analysis converts curvature around the fixed reference price into inventory stability without tracking optimal prices at changing resource levels. Numerical experiments show that RASGD achieves regret competitive with per-arrival LP re-solving and improves upon the tested first-order baselines, while retaining the computational efficiency of first-order methods. These results establish RASGD as a computationally efficient approach to achieving high allocation quality in large-scale OLP.

Jiameng Lyu

Department of Management Science, School of Management, Fudan University, Shanghai 200433, China

Online Convex Optimization Online Resource Allocation Stochastic Gradient Descent

Sep 16, 2026cs.LG

FedPGT: Progressive Gradient Transmission for Vehicular Federated Learning over Time-Varying Channels

Vehicular federated learning (VFL) enables privacy-preserving collaborative model training for intelligent transportation systems, where communication resource allocation and gradient sparsification techniques have been explored to reduce communication overhead. However, vehicle mobility leads to rapidly varying channel conditions and transmission capacity, rendering predetermined resource allocation and sparsification decisions ineffective. In this paper, we propose FedPGT, a progressive gradient transmission scheme for VFL over time-varying channels, where vehicles progressively transmit high-magnitude gradient entries in response to instantaneous channel conditions. We establish a convergence bound that characterizes the impact of transmitted gradient entries and reveals diminishing-return behavior governed by a power-law decay. Motivated by this result, we formulate a stochastic optimization problem for online decision-making, where the main challenge lies in a cumulatively coupled, non-separable objective. To handle this challenge, we introduce per-slot surrogate transmission variables to decouple the long-term dependence across time slots and convert the original objective into an additive per-slot optimization problem, enabling a Lyapunov drift-plus-penalty approach for online scheduling. We further develop a low-complexity resource allocation algorithm for efficient online implementation. Experimental results demonstrate that the proposed scheme achieves a 3.65% accuracy improvement on the CIFAR-10 image classification task and a 12.66% reduction in average displacement error on the Argoverse trajectory prediction task compared with state-of-the-art baselines, demonstrating its applicability to diverse learning tasks under highly dynamic vehicular environments.

Jintao Yan, Tan Chen, Yuxuan Sun +2

Beijing National Research Center for Information Science and Technology, Department of Electronic Engineering, Tsinghua University, Beijing 100084, China. · School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China.

Communication-Efficient Distributed Training Online Resource Allocation Federated Learning

Sep 14, 2026cs.CL

Intelligence Under Time Constraints: Rethinking Test-Time Compute

Intelligence under time constraints requires deciding not only how much to compute, but when computation is worth starting. We study this problem in streaming interactions, where evidence arrives incrementally and may be revised. Early computation has more time to finish but rests on incomplete evidence; waiting improves information while shrinking computational slack. We call this the information-slack dilemma. We take the evidence-dependent computational job as the unit of analysis: when to start it, what supports its result, and when that result can be committed. Advance computation is valuable only insofar as its benefits survive the costs of verification, invalidation, and recovery. This applies to grounded incremental processing and reusable preparation as well as future-dependent speculation. We propose a research agenda on computation under evolving evidence, prioritizing selective recovery under controlled evidence revisions. Evaluation should separate earlier-execution effects, deployment value against a full-input alternative, and the added value of predictive policies, while accounting for shared-resource costs. The objective is not maximal advance computation, but more trustworthy, on-time responses within a declared resource envelope.

Xiaotian Zhang

Trooly.AI

Inference-Time Scaling Inference-Time Compute Allocation Online Resource Allocation

Sep 3, 2026cs.GT

EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments

We study the allocation of indivisible goods among agents with identical additive valuations, focusing on envy-freeness up to one good (EF1) and Nash social welfare (NSW). Since every maximum-NSW allocation is EF1 under additive valuations, the associated threshold problem inherits the known strong NP-hardness of NSW maximization under identical additive valuations and is strongly NP-complete. We therefore focus on welfare guarantees satisfied by arbitrary EF1 allocations. Although every such allocation is known to achieve an

e^{-1/e}

-approximation to the unrestricted optimal NSW, we identify conditions yielding stronger guarantees. Under uniform valuations, every EF1 allocation is NSW-optimal. Under an

\varepsilon

-small-item condition, every EF1 allocation achieves an explicit approximation ratio

ρ_n(\varepsilon)

satisfying

ρ_n(\varepsilon) = 1-O(\varepsilon^2)

as

\varepsilon\to 0

for fixed

n

. We further consider the stronger sequential requirement that

\operatorname{EF1}

be maintained after every item assignment. For this setting, we introduce \emph{PriorityNet}, a deep reinforcement learning framework trained with Proximal Policy Optimization (PPO) and equipped with prospective

\operatorname{EF1}

action masking, which guarantees prefix-wise

\operatorname{EF1}

by construction. Across 3,000 test instances in each of the offline full-information and random-order online regimes (

n\in[2,20]

,

m\in[5,100]

), PriorityNet achieves mean normalized

\operatorname{NSW}

values of

0.9911

and

0.9701

, respectively. Relative to the offline Longest Processing Time (LPT) heuristic and the online least-valued-bundle rule, it attains instance-wise win-minus-loss rates of

+27.10\%

and

+17.87\%

. Its aggregate welfare matches the offline LPT baseline to four decimal places and modestly improves upon the online baseline, from

0.9694

to

0.9701

.

Zih-Sian Yang, Yi-Hao Chen, Yu-Te Kuan +3

National Taiwan Ocean University, Keelung City 202301, Taiwan · National Yang Ming Chiao Tung University, Hsinchu City 300, Taiwan

Fair Resource Allocation Online Resource Allocation

Sep 1, 2026cs.DS

Prediction-Assisted Pricing and Admission for LLM APIs with Stochastic Token Consumption

An LLM application often sells or internally allocates several service products: a small or premium model, a short or long token cap, and possibly multiple posted prices. The operational decision is not merely which model answers a prompt. A price changes purchase probability, a token cap changes both user value and the tail of resource consumption, and accepted requests compete for shared compute and premium-model capacity. Demand and output length are initially uncertain, while an offline model may provide useful but imperfect predictions. We formulate sequential pricing and admission with stochastic resource consumption. Each arriving request belongs to an observable segment. The platform chooses a product--price pair or makes no offer; purchase, revenue, and resource use are then random. An offline predictor supplies a uniform, validated error radius for every segment--product cell. We propose Prediction-Clipped UCB (PCUCB), which intersects the offline prediction interval with an online confidence interval, evaluates products using resource shadow prices, and reserves a sample-path envelope before commitment. The prior gives a fast start when accurate, while online learning protects the platform when predictions are coarse. The analysis is modular. On a simultaneous confidence event, regret against a buffered fluid benchmark is bounded by a pacing term plus the cumulative diameter of the intersected intervals. For

J

segment-product cells and prediction radius

\varepsilon

, this yields

\widetilde O\left( \sqrt{T}+(1+\barΛ) \min\{T\varepsilon,\sqrt{JT}\} \right),

where

\barΛ

bounds operational shadow prices. Thus the algorithm smoothly interpolates between an almost full-information regime and learning from scratch. Hard feasibility holds on every sample path through reservation envelopes.

Patrick Wong

LLM Serving Learning-Augmented Algorithms Dynamic Pricing Online Resource Allocation

Aug 12, 2026cs.DC

User-Assisted Collaborative Distributed Inference for Efficient QoS-Aware Autoscaling

Growing demand for artificial intelligence (AI) inference services requires scalable infrastructure, yet centralized serving costs rise with demand. We propose a collaborative distributed inference system combining dedicated infrastructure with resources contributed by service users. Dedicated resources provide baseline capacity for maintaining quality of service (QoS), while volunteered resources absorb increasing demand without proportional growth in centralized infrastructure. To capture stochastic and dynamic interactions among users, resources, tasks, and policies, we develop a high-dimensional generative Markov model with structured temporal factorization. The model supports simulation and provides a foundation for task scheduling and QoS-aware resource allocation optimization. We evaluate the system across user populations, resource capacities, and centralized and distributed scheduling policies. Simulations show that distributed scheduling becomes increasingly advantageous as the user population grows, improving request completion and P99 latency while substantially reducing dedicated resource consumption. These results demonstrate the feasibility of user-assisted collaborative inference for infrastructure-efficient autoscaling.

Alfreds Lapkovskis, Ali Beikmohammadi, Sindri Magnússon +1

Department of Computer Systems and Sciences, Stockholm University SE-106 91 Stockholm, Sweden

Distributed Inference Online Resource Allocation

Aug 12, 2026cs.LG

FunnelCausalNet: Funnel-aware Joint Conversion-Revenue Uplift for Multi-tier Coupon Allocation

Coupon campaigns seek to lift both conversion and revenue, but gross merchandise value (GMV) follows a deterministic funnel from conversion to conditional order value and is zero-inflated and heavy-tailed. We propose FunnelCausalNet, an uplift estimator coupling a binary conversion head with a nonnegative conditional-value head through

μ_{\mathrm{gmv}}=μ_{\mathrm{conv}}μ_{\mathrm{val}}

. Under explicit RCT, support, rate-gap, and cross-head covariance-control assumptions, an idealized leading-order MSE comparison identifies a regime in which funnel composition can reduce pointwise variance; this is a heuristic, not a guarantee for the shared-representation neural model. The estimator is paired with marginal split-conformal CATE summaries, combined through a Bonferroni union as audit bands, and a Lagrangian budgeted allocator using RCT-anchored estimates for subsidy-aware ROI accounting. On semi-synthetic multi-tier Criteo-MT7, FunnelCausalNet's mean AUUC_GMV is within one seed standard deviation of the leading feature-interaction baseline among eleven baselines, while a controlled ablation reduces GMV effect error versus direct GMV regression by 18--48% across tested zero-inflation regimes. On de-identified industrial Hotel-Coupon RCT logs with about 4.9 million hold-out exposure records per seed, expected-outcome evaluation sweeps full LP frontiers; FunnelCausalNet has the best seed-averaged mean DeltaROI at all seven correlated anchors from 10% to 60%, which we treat as descriptive frontier consistency rather than independent significance. On sparse binary-spend public benchmarks, revenue-focused rankers can dominate uplift-curve proxies, defining an explicit regime boundary.

Yu Zhang, Zhihan Wang, Guanlin Chen +2

AMap Alibaba Group, Beijing, China · AMap Alibaba Group · Beijing, China

Conditional Average Treatment Effect Estimation Online Resource Allocation

Aug 11, 2026cs.NI

ImpactHO: Importance-Aware KV Cache Transfer for Multi-User Edge LLM Handover

Edge LLMs must preserve inference continuity when a user hands over between edge nodes, requiring key-value (KV) cache transfer to the target node. However, simultaneous handovers saturate the backhaul, preventing full cache delivery within the mobility-imposed transfer window. Rather than allocating bandwidth as if all cache entries were equally valuable, we order each user's KV cache by importance and transmit only its most informative fraction, turning token-level sparsity into communication savings. We cast the transfer as a multi-user backhaul allocation problem that maximizes average accuracy across users. Each user's partial-cache accuracy serves as its utility: a sigmoid that fits measurements on the RULER benchmark with

R^2>0.99

across models and context lengths. Because importance ordering front-loads the high-value entries, the concave region of the accuracy curve spans nearly the entire cache. Our proposed allocator keeps served users within this region, making each per-slot allocation problem convex. The optimum is derived via a closed-form weighted water-filling solution that generalizes information-theoretic water-filling and enables online scheduling. The proposed allocator attains over 93.7% average accuracy in a 500ms transfer window, within 0.5pp of the full-cache ceiling, and reaches 98.2-99.5% of a clairvoyant upper bound.

Minwoo Kim, Soochang Song, Namyoon Lee +2

Department of Electrical Engineering, Pohang University of Science and Technology (POSTECH), Pohang 37673, South Korea · Department of Electrical and Computer Engineering, Ajou University, Suwon 16499, South Korea

KV Caching Edge Computing LLM Inference Scheduling KV-Cache Management Online Resource Allocation

Aug 10, 2026cs.LG

MARA: Flow-Matching-Guided Multi-Agent Resource Allocation for Computational Resource Efficient Learning

Allocating limited computation among concurrent learning tasks is difficult when each task must reach a target loss before a deadline but its required training effort is unknown. Existing approaches combine online loss prediction with adaptive resource allocation, yet commonly treat computation as continuously divisible throughput. We instead study a practical setting in which tasks arrive over time and computation is provided by discrete nodes. This setting introduces both uncertain demand and constrained sequential decisions. We propose MARA, which predicts future loss trajectories with conditional flow matching and coordinates compute nodes through a cooperative multi-agent autoregressive policy. A potential-based progress reward supplies intermediate training feedback while preserving the undiscounted task-completion objective. Across in-distribution, reinforcement-learning, and vision workloads, flow matching reduces remaining-resource prediction error relative to weighted least squares. At the scheduler's training load, MARA completes 63.46% of tasks on average, 8.54 percentage points above strong baseline Learning with Adaptive Resource Allocation (LARA), and remains ahead under unseen heavier workloads.

Hanye Zhao, Muning Wen, Yong Yu +1

Shanghai Jiao Tong University

Learning-Augmented Algorithms Online Resource Allocation

Aug 8, 2026cs.DB

ScaleSense: Cost-Intelligent Scaling Framework via Learned Resource Estimation in Alibaba AnalyticDB

Cloud-native serverless data warehouses achieve fine-grained elasticity by decoupling storage from compute, yet determining the optimal resource allocation for highly heterogeneous ad-hoc queries remains a formidable industrial challenge. Our analysis of production workloads in Alibaba AnalyticDB exposes a costly ``provisioning trap'': the fear of catastrophic resource depletion drives users to blindly over-provision resources, wasting immense monetary budgets without alleviating non-CPU bottlenecks (e.g., I/O saturation). To break this impasse, we propose ScaleSense, a proactive, query-level resource scaling framework. Specifically, it features a multi-faceted query encoder that jointly models plan topologies and hardware specifications. Crucially, a quantile-based resource predictor estimates multi-dimensional physical footprints, acting as a reliable safety net for optimal resource scaling. An auto-scaling controller then navigates the performance-cost Pareto frontier, dynamically tailoring allocations to specific business priorities without requiring model retraining. Evaluations on over 1.36 million production queries show that ScaleSense achieves state-of-the-art prediction accuracy with good prediction interval coverage. By achieving a 76.7% relative improvement in optimal resource configuration selection over the best baseline, this approach addresses the critical performance-cost trade-off while maintaining low-overhead inference latency, confirming its practical performance in production deployments. Under the performance-optimization policy, ScaleSense satisfies user-defined performance requirements while reducing monetary cost by up to 5.22x.

Yifan Wu, Yuhan Li, Zhenhua Wang +6

The State Key Laboratory of Blockchain and Data Security Zhejiang University · Alibaba Cloud Computing

Online Resource Allocation Relational Databases

Aug 7, 2026cs.AI

Adaptive Two-Level Allocation of a Conserved Capacity Budget Across Locations and Service Classes

We study how to share a single conserved capacity budget across many locations and two service classes when demand is uneven, time-varying, and can exceed supply. The shape recurs: an origin's request-rate cap split across its edge locations, a licensed throughput cap across premium and standard tenants, or an egress budget between latency-critical and batch workloads. We present a two-level algorithm. The first level redistributes capacity within a class across locations by proportional deficit and excess redistribution; the second lends capacity elastically between classes when one has surplus and the other deficit. We prove it conserves the budget exactly, preserves non-negativity, and reaches a stable allocation in one iteration under stationary demand because it carries no per-cycle state, at O(KN) cost per cycle for K classes and N locations. We evaluate it defending a CDN's per-domain budget under volumetric attack, where the classes are confirmed-legitimate and not-yet-cleared traffic; across 8 contention scenarios on a 22-location topology it serves 66-93% of high-priority demand, competitive with a single-class linear-programming optimum, while never leaving capacity idle or over-committing whenever aggregate demand meets or exceeds the budget (the contention regime these scenarios evaluate). Two findings carry beyond the application. First, a throughput-maximizing objective is wrong under contention: a two-class LP maximizing total served load serves less high-priority load than our demand-proportional, reservation-respecting allocator in most scenarios, because it cannot tell that some load it serves is the contention. Second, inter-class borrowing earns its complexity under bursty load, improving high-priority service by 1.5 points (isolated by ablation), and is neutral under stationary demand. A 5-location prototype with real HTTP traffic validates the pipeline.

Simone Mainardi, Kaushal Bansal, Prabhat Singh

Network Security Salesforce, Inc. Dublin, Ireland

Online Resource Allocation

Aug 6, 2026cs.LG

LLM Inference Under Bursty Workload Distribution: Modifying the WAIT Algorithm

Large Language Models (LLMs) such as ChatGPT and Claude are widely used for information retrieval and problem-solving. Recent work has focused on improving scheduling algorithms to boost throughput while maintaining low latency. However, these approaches often assume Poisson request arrivals with constant rates - an assumption that fails to reflect the inherently bursty and dynamic nature of real-world traffic. We propose a lightweight extension to the state-of-the-art WAIT algorithm [1], which adapts to time-varying arrival rates without prior traffic knowledge. The proposed algorithm performs online estimation of request intensity based on observed interarrival times. Using Markov Modulated Poisson Process (MMPP)-based synthetic workloads with diverse request types, we conduct a simulation-based evaluation demonstrating that the proposed method achieves higher throughput than Sarathi-Serve [2], ORCA [3], and vLLM [4] in the evaluated low arrival-rate shift scenarios while maintaining comparable latency.

Anjali Gangadhar Katageria, Shobha Rani, Raghu Nandan Sengupta

Department of Mathematics, Indian Institute of Technology Dharwad, Dharwad, Karnataka, India · Department of Management Sciences, Indian Institute of Technology Kanpur, Kanpur, Uttar Pradesh, India

LLM Inference Scheduling Online Resource Allocation LLM Request Scheduling

Aug 6, 2026cs.MA

ASGE-RR: Agentic Service Graph Embedding with Revisable Reservations for Dynamic AI-Agent Calls

AI-agent workflows often involve remote calls to models, memory stores, and tools distributed across a network. As execution progresses, these dependency calls collectively form an agentic service graph (ASG). Unlike traditional service requests, many dependency calls are revealed only at runtime. Consequently, allocating resources to a currently visible call may consume capacity later needed by a call from a higher-value workflow. We formulate this challenge as Agentic Service Graph Embedding (ASGE), an online network-control problem that maps runtime-revealed workflow calls to service replicas and network paths under capacity, cost and deadline constraints. We present ASGE-RR, an online ASGE controller with revisable reservations. ASGE-RR protects capacity for likely future calls while enforcing the constraints. ASGE-RR evaluates candidate replica-and-path mappings against predicted workflow continuations and updates reservations as new execution information becomes available. We evaluate ASGE-RR using OpenHands and GPT Researcher workflows executed with gpt-5.6-luna and replayed over in two complementary experimental environments, a controlled Docker testbed and a WAN testbed. The investigation shows that all the evaluated AI-agent tasks expose at least one runtime-revealed dependency call that can be steered before connection establishment. Exploiting this control point, even though the experimental environments are small-scale, ASGE-RR already demonstrates noticeable potential: It completes (up to) 10% more workflow value than a same-information rolling-horizon controller and a current-call steering controller on the WAN testbed. The results suggest that runtime-revealed workflow structure creates a new network control opportunity: protecting resources for likely future calls allows more AI-agent workflows to finish in time.

Trond Vatten, Yuming Jiang

Norwegian University of Science and Technology (NTNU), Trondheim, Norway

Agentic Workflows Online Resource Allocation

Aug 5, 2026cs.DC

Hierarchical Server Architecture for Agentic Science

Agentic science is transforming the landscape of computational work, and is applied to scientific pipelines and workload managers. Scientific workloads require specialized hardware within and between institutions. Automated resource discovery is an essential step for scheduling workloads with specific hardware and environmental requirements. In this paper, we present a hierarchical, dynamic architecture and accompanying software to discover resources across diverse cloud, edge, and HPC systems. The design enables concurrent, asynchronous negotiation, selection, and dispatch of requests for work using secretary agents. The agents probe and discover 51 real and simulated providers across 7 categories. We perform 19,973 negotiation and 6,952 selection simulations to assess reliability of decisions, demonstrating high (87.71%) negotiation accuracy and selection costs comparable to more traditional strategies. Designed for extensibility and currently supporting the US DOE Genesis Mission, this architecture exemplifies the importance of careful coordination between agents, discovery tools, and infrastructure for agentic science.

Vanessa Sochat, Daniel Milroy

Lawrence Livermore National Laboratory Livermore, California, USA

Multi-Agent Coordination AI Agents for Scientific Discovery Online Resource Allocation

Aug 5, 2026cs.LG

Differentiating Through Dual Prices: End-to-End Policy Learning Under Capacity Constraints

Many social services assign scarce resources, such as housing assistance or hospital interventions, to people who arrive one at a time: each arrival must receive a decision immediately, and the long-run usage of every resource must stay within its capacity. We study how to learn such an assignment policy from logged observational data. The standard pipeline is decision-blind: fit one outcome model per arm by regression, price each capacitated resource from the fitted models, and assign each arrival the arm whose predicted outcome minus price is largest. We instead train the outcome models end-to-end, differentiating an off-policy estimate of the deployed policy's value through the dual prices themselves. We study two formulations: an exact nonconvex one, and a convex relaxation whose optimum always satisfies the capacity constraints in expectation and which is suboptimal by at most a term linear in the smoothing temperature and logarithmic in the number of arms. Every method is evaluated in a queueing simulation with resources replenished at their capacity rates. Across six datasets, the two end-to-end variants take the top slots on a deployment-adjusted value index at every delay cost, including zero; when capacities are binding, decision-blind baselines frequently violate them and incur much longer queueing delays. On the largest dataset, a hospital cohort of seventy thousand patients, end-to-end training also achieves significantly higher policy value, a margin that survives a capacity-matched neural baseline. Flexible decision-blind regression remains the stronger pure predictor where ground truth is measurable; end-to-end training is best suited to settings where resources are genuinely scarce and feasibility matters.

Mohammadsaeed Haghi, Mahdi Salmani, Nima Kelidari

University of Southern California

Constrained Optimization Differentiable Optimization Online Resource Allocation

Aug 4, 2026cs.AI

Less Traffic, Better Outcomes: Competition-Aware Request Dispatch in Real-Time Ad Exchanges

Real-time bidding (RTB) ad exchanges typically forward nearly all incoming requests to demand-side platforms (DSPs), even though only a small fraction receive bids. This over-distribution weakens auction outcomes: DSPs throttle participation under compute and budget constraints, reducing the effective use of limited bidding capacity. We present a competition-aware request dispatch framework that uses distributional bid prediction and probabilistic forwarding to decide whether each request should be sent to each DSP. The system adapts per-DSP thresholds over time through lightweight policy optimization to track non-stationary market conditions. We evaluate the framework through four sequential online experiments on a production platform serving over 20 billion daily requests. A full multi-DSP deployment reduces DSP request volume under the policy by 34.2% while increasing net revenue by 4.6% (p<0.001) in a recent 14-day window after an initial DSP adaptation period. Further analysis highlights strong heterogeneity across traffic segments and reveals that aggregate metrics can be misleading. Segment-level and per-DSP analyses suggest that the policy surfaces comparative advantages among DSPs, improving monetized outcomes without increasing overall request volume.

Jonaid Shianifar, Blaz Mramor, Fangda Zou +5

Huawei Ireland Research Center, Dublin, Ireland · Huawei, Nanjing, China

Online Advertising Online Resource Allocation Real-Time Bidding

Aug 3, 2026cs.LG

Online Algorithms via Minimax and Posterior Matching

Competitive analysis is central to the study of online algorithms, but upper bounds are often highly problem-specific. We develop a more unifying methodology via the minimax viewpoint. Guided by Yao's principle, we reduce worst-case competitive analysis to Bayesian online design under an arbitrary correlated prior over arrival sequences. For such a prior, let

X^*

be the hindsight-optimal fractional solution for the realized instance, and let

X^{(t)}=\mathbb E[X^*\mid \mathcal F_t]

be its posterior process. Our guiding rule is posterior matching: at each time

t

, choose the feasible online action that tracks the current posterior

X^{(t)}

as closely as the online constraints permit. We show that this single principle yields optimal or near-optimal guarantees for several classical online fractional problems, including set cover, load balancing, matching and more general resource-allocation problems, recovering or improving state-of-the-art bounds in these settings with norm/concave objectives. Via known rounding reductions, it also yields randomized integral guarantees for weighted paging, MTS on star metrics, and ski-rental. At a technical level, our analysis reduces competitive guarantees to key probabilistic inequalities for the vector martingales generated by the posterior of the offline optimum. The resulting framework gives a reusable route from Bayesian online design under arbitrary correlated priors to information-theoretic worst-case competitive guarantees.

Thomas Kesselheim, Marco Molinaro, Kalen Patton +1

Institute of Computer Science, University of Bonn. · Microsoft Research and PUC-Rio. · School of Mathematics, Georgia Tech. +1

Competitive Analysis Online Resource Allocation

Jul 30, 2026cs.LG

Multi-channel Uplift Policy Learning

E-commerce platforms must allocate fixed marketing budgets across multiple channels to maximize business utility. However, standard predict-then-optimize (PTO) paradigms fail in this compositional space due to observational confounding and severe extrapolation. We formulate this challenge as a simplex-constrained uplift decision problem and propose ReAlloc, a fast-slow causal framework. Specifically, an agile Orthogonal Teacher extracts unbiased local gradients from short-term logs, while an Explanation-Guided Student distills them into a structured marginal field over long-term horizons. This design enables support-aware, conservative decisions that capture cross-channel substitutions. Extensive simulations and large-scale online A/B tests on Taobao platform demonstrate that ReAlloc achieves simultaneous lifts in both pay order and income.

Changjian Liu, Tianyu Wang, Xiaoxuan Deng +7

Peking University Beijing, China · Alibaba Group Beijing, China · Beihang University Beijing, China +1

Online Resource Allocation

Jul 29, 2026cs.NI

Harnessing Large Language Models for Intelligent Resource Allocation in the Internet of Everything

The rapid development of the Internet of Everything (IoE) is accelerating the adoption of intelligent applications. However, the massive number of connected devices generates diverse and heterogeneous tasks, which pose increasing challenges for dynamic resource scheduling in IoE environments. Using their superior semantic understanding and reasoning capabilities, Large Artificial Intelligence Models (LAIMs) demonstrate significant potential to handle complex scheduling scenarios and improve resource utilization efficiency. This paper investigates a task-oriented LAIM-driven resource scheduling mechanism, which constructs a multidimensional scheduling decision model by integrating task semantics, network states, and constraint conditions. Furthermore, a task-oriented prompt generation method is designed to establish a deep association between task requirements and network state. In the proposed resource allocation scheme, an external evaluation and feedback module is incorporated to conduct real-time feasibility verification and performance evaluation of scheduling strategies, thus enhancing the robustness and adaptability of scheduling. Simulation results demonstrate that the proposed Large Language Model (LLM)-driven network architecture and resource allocation scheme achieve significant improvements in convergence speed, processing latency, and energy consumption, effectively enhancing IoE task responsiveness and resource utilization.

Haijun Zhang, Zhuojun Duan, Zijun Wu +2

Hebei Key Laboratory of Space-Air-Ground Intelligent Communication and Beijing Engineering and Technology Research Center for Convergence Networks and Ubiquitous Services, University of Science and Technology Beijing, Beijing, China

Large Language Model-Guided Optimization Internet of Things Online Resource Allocation

Jul 25, 2026cs.GT

Online Fair Division with Budget Constraints

We study an online variant of discrete fair division under generalized assignment budget constraints. Goods arrive one at a time and must be assigned irrevocably to a feasible agent or to charity, which holds all unallocated goods, while fairness is evaluated only against budget-feasible subsets of every recipient's bundle. We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness, even in highly symmetric instances. We then identify bounded density spread as a structural condition that restores meaningful guarantees, obtaining approximation algorithms for arbitrary item sizes and showing that, under common valuations and sufficiently small goods, these guarantees can be strengthened to an optimal deterministic frontier. We further study resource augmentation, where the online algorithm is allowed slightly larger budgets than the fairness benchmark, and characterize the resulting improvement in the achievable guarantees. Finally, we develop a learning-augmented framework based on predicting joint value-size types, proving consistency under perfect predictions, robustness to prediction error, and showing that separate predictions of value and size marginals are insufficient to recover strong fairness guarantees.

Saar Cohen, Nicholas Teh, Paul W. Goldberg +1

Department of Computer Science, University of Oxford, UK

Fair Resource Allocation Learning-Augmented Algorithms Approximation Algorithms Online Resource Allocation

Jul 18, 2026cs.LG

Certified-Gap Dual-Price Policies for Real-Time Truckload Bid Acceptance with Relocating, Clock-Constrained Resources

A truckload carrier must accept or reject each load tender within seconds. The decision depends on fleet state, hours-of-service (HOS) clocks, and appointment windows. We model this as a weakly coupled dynamic program in which the resources relocate and carry clocks: serving a request moves the truck to a new market and depletes its clocks, and whether a truck can serve a request depends on its state. Occupancy-based reusable-resource models do not cover this setting. We build a real-time dual-price policy from the same Lagrangian relaxation that gives the problem's upper bound. Policy and bound come from one object, so every run reports a certified optimality gap. We prove three things. First, the certificate is valid for any duals, any discretization, and any surrogate quality. Second, the policy's same-time spatial-gradient rule is exactly fluid complementary slackness, and the policy is asymptotically optimal in the subcritical fluid regime; the fitted prices are also portable across sample paths, by linear-programming basis stability. Third, certificates have limits: per-resource Lagrangian slack can stay bounded away from zero at every fleet size. We exhibit a three-truck kernel with an exact rational certificate and a replication lemma. On a public closed-loop benchmark with thirty paired seeds, the policy -- which needs no rollout labels, only one offline dual solve -- beats a rollout-trained surrogate on two of three scenarios (tight: +2.0 pp, 95% CI [+0.5, +3.6], Wilcoxon p = 0.023; mild: +3.5 pp, CI [+2.4, +4.5]) and ties the third. It decides in 0.04-0.09 ms, three orders of magnitude faster than the Monte Carlo rollout teacher. Its certificates are stable across ten bounded instances per scenario, at 57-64% of optimal, within 3-6 points of what the 1000x-slower teacher certifies.

Aswin Chandrasekaran

Bubba AI

Real-Time Scheduling Intelligent Transportation Systems Vehicle Routing Constrained Optimization Online Resource Allocation Real-Time Bidding

Jul 15, 2026cs.LG

From Novice to Expert: Cost-Aware Bandits for Evolving Worker Performance in Crowdsensing

Mobile crowdsensing (MC) recruits mobile users to perform sensing tasks using their smartphones, enabling large-scale applications such as traffic monitoring and environmental sensing. A fundamental challenge is online worker recruitment under uncertainty, where the platform must learn workers' sensing performance while operating with a limited budget. Existing learning-based MC recruitment methods typically assume that each worker's sensing quality is stationary with a fixed mean over time. In practice, however, worker performance often improves with experience and eventually stabilizes, while the incurred sensing cost can be unknown in advance due to time-varying device and context states. In this paper, we study a budget-constrained online recruitment problem in which the platform selects one worker in each round, observes the sensing quality and incurred cost, where the expected sensing quality of each worker increases with experience and eventually converges to a plateau, and repeats until the budget is exhausted. We formulate this problem as a structured bandit model where each worker's expected reward evolves according to an unknown increasing-then-converging function of its participation count, and each worker has an unknown expected cost. We develop a cost-aware online learning framework that jointly learns evolving reward trajectories and heterogeneous costs, detects performance saturation, and allocates the limited budget to maximize long-term sensing utility. We provide theoretical performance guarantees and validate the proposed approach through extensive experiments, demonstrating consistent improvements over baselines that ignore experience-driven dynamics or assume known costs.

Yin Huang, Qingsong Liu, Jie Xu

Manning College of Information and Computer Sciences, University of Massachusetts Amherst

Multi-Armed Bandits Non-Stationary Bandits Online Resource Allocation

Jul 11, 2026cs.DC

Stateful Worlds, Stateless Elasticity: Exact-State Serving for Interactive World Models

A persistent interactive world model keeps its running state resident on the GPU that serves it: a multi-gigabyte attention cache, almost all of it rewritten at every generation step. That state cannot be recomputed in interactive time or approximated without changing the world, so a live session pins its device. The pin is a scheduling problem. WorldMove moves a live session under one guarantee: the destination is bit-identical to the source, or nothing is installed. It relocates the cache in 18.8 ms same-node, 101x faster than save/load. It holds a checksum-verified 92.1-94.8 Gb/s on a 100 Gb fabric. At that rate the cache fits inside one interactive block. Migrating an actively generating session, it converges at a block boundary and the destination continues the world bit for bit. An admissibility condition decides each move. The move must complete inside the readout horizon, over bandwidth that covers the state plus its dirty rate. Lifted to a fleet schedulability test, it governed a consolidation loop that executed 48 of 48 migrations bit-identical across two providers. Two constraints are structural. Bit-exactness survives only inside a controlled configuration of one GPU architecture, so moving the state is the only way to preserve it exactly in interactive time. Verification cannot hide inside the wire on this fabric. Receive-path checksums stall the transport at protocol timescales under fan-in, and unscheduled incast silently collapses a receiver while every delivered byte stays correct. An incast-aware admission controller holds zero misses to 1.4x offered load and sheds overload as rejects. A lossless GPU codec widens the admission gate to fabrics raw motion cannot use. We exercise the serving loop and the mover separately, each end to end. Their composition on one fabric is unbuilt. Exact-state elasticity is a joint scheduling problem over transport and verification.

Jin Li, Jiawei Chen

Harvard University · Harvard University Cambridge, MA, USA · Independent Researcher

Distributed Inference Online Resource Allocation Interactive World Models

Jul 9, 2026cs.LG

Quota Marketplace: Dynamic Pricing for Efficient Allocation of ML Training Resources

The escalating demand for Machine Learning (ML) training resources in recent years has resulted in a substantial gap between the high demand and the available supply. Efficient allocation of these scarce and expensive resources is crucial for organizations to maximize their return on investment. Existing resource allocation mechanisms, like Karma [OSDI'23], are designed to guarantee Pareto efficiency and max-min fairness in settings with dynamic (time-varying) user demands, but fail to preserve these key properties in the presence of demands with heterogeneous values. Given the ubiquity and inevitability of heterogeneity in organizational values of different workloads, effective resource allocation policies must accommodate these variations. In this paper, we describe the design, implementation, deployment, and theoretical analysis of Quota Marketplace, a market-based mechanism to efficiently allocate ML training chips (like GPUs), explicitly addressing scenarios with demands of heterogeneous value. We detail the implementation of this mechanism within Google and present metrics that demonstrate its impact. We also discuss many business-critical requirements that the Quota Marketplace handles quite effectively, and document the gains and opportunities it has unlocked. We establish theoretically how this market-based approach achieves the essential properties of Pareto efficiency and max-min fairness by allowing the users to express the value of their workloads and enabling dynamic resource pricing based on supply and demand fluctuations. Ultimately, the market facilitates resource allocation that aligns with organizational priorities.

Balasubramanian Sivan, Renato Paes Leme, Mihai Tiuca +6

Google · Drexel University

Fair Resource Allocation Dynamic Pricing Online Resource Allocation