cs.AIMar 19, 2026

Regret Bounds for Competitive Resource Allocation with Endogenous Costs

Authors: Rui Chai

Organizations: Shanghai Sanda University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We study online resource allocation among N interacting modules over T rounds. Unlike standard online optimization, costs are endogenous: they depend on the full allocation vector through an interaction matrix W encoding pairwise cooperation and competition. We analyze three paradigms: (I) uniform allocation (cost-ignorant), (II) gated allocation (cost-estimating), and (III) competitive allocation via multiplicative weights update with interaction feedback (cost-revealing). Our main results establish a strict separation under adversarial sequences with bounded variation: uniform incurs Omega(T) regret, gated achieves O(T^{2/3}), and competitive achieves O(sqrt(T log N)). The performance gap stems from competitive allocation's ability to exploit endogenous cost information revealed through interactions. We further show that W's topology governs a computation-regret tradeoff. Full interaction (|E|=O(N^2)) yields the tightest bound but highest per-step cost, while sparse topologies (|E|=O(N)) increase regret by at most O(sqrt(log N)) while reducing per-step cost from O(N^2) to O(N). Ring-structured topologies with both cooperative and competitive links - of which the five-element Wuxing topology is canonical - minimize the computation x regret product. These results provide the first formal regret-theoretic justification for decentralized competitive allocation in modular architectures and establish cost endogeneity as a fundamental challenge distinct from partial observability. Keywords: online learning, regret bounds, resource allocation, endogenous costs, interaction topology, multiplicative weights, modular systems, Wuxing topology

More in this topic

Online Resource Allocation

Online resource allocation studies how to assign scarce capacity to arriving requests under uncertainty while balancing reward, cost, fairness, and feasibility.

See all 95 papers

Explore similar work

CardsList
Feb 6, 2026

Learning to Allocate Resources with Censored Feedback

We study an online resource allocation problem in which at each round, a budget BB must be allocated across KK arms under censored feedback. An arm yields a reward if and only if two conditions are satisfied: (i) the arm is activated according to an arm-specific Bernoulli random variable with unknown parameter, and (ii) the allocated budget exceeds a random threshold drawn from a parametric distribution with unknown parameter. Over TT rounds, the learner must jointly estimate the unknown parameters and allocate the budget so as to maximize cumulative reward facing the exploration--exploitation trade-off. We prove a worst-case regret lower bound Ω(T)Ω(\sqrt{T}) for the general model, even with known uniform threshold distributions. We then propose RA-UCB, an optimistic algorithm that leverages non-trivial parameter estimation and confidence bounds. When the budget BB is known at the beginning of each round, RA-UCB achieves a regret bound of order O~(T)\widetilde{\mathcal{O}}(\sqrt{T}), and even O(poly-log⁡T)\mathcal{O}(\mathrm{poly}\text{-}\log T) under stronger assumptions. As for unknown, round dependent budget, we introduce MG-UCB, which allows within-round switching and infinitesimal allocations, and matches the regret guarantees of RA-UCB. We then validate our theoretical results through experiments on real-world datasets.

Giovanni Montanari, Côme Fiegel, Corentin Pla +2

FairPlay Joint Team, Inria, France · CREST, ENSAE, Institut Polytechnique de Paris · Criteo AI Lab, Paris, France +1

Online Resource AllocationMulti-Armed BanditsUCB Algorithms
AskPDF
Oct 8, 2026

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 FF experts and a candidate budget pacing schedule, we provide a full-information algorithm which obtains regret O(Dlog⁡F+Tlog⁡F)O(D \sqrt{\log F}+ \sqrt{T\log F}) against all experts whose cumulative spending stays within distance DD 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(Dlog⁡F)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(T)o(\sqrt{T}) guarantees for such tasks.

Mark Braverman, Jingyi Liu, Jieming Mao +2

Department of Computer Science, Princeton University · Google Research

Online LearningOnline Resource AllocationMinimax Regret
AskPDF
Jul 2, 2026

Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy

We study online resource allocation when both rewards and consumption sizes may be continuously distributed. Requests arrive sequentially and must be accepted or rejected irrevocably under fixed resource capacities. Each request belongs to one of finitely many observable types; conditional on an observable request type, both the reward and the scalar size are random, and the realized size scales a fixed type-specific resource-consumption vector. The model allows the deterministic fluid relaxation to be degenerate. We show that additive regret is governed by the size-weighted mass of requests whose value-to-size ratios lie near the active acceptance cutoffs. We formalize this quantity through an active weighted-mass exponent p. When p > 1, this cutoff mass is thin, and the problem is genuinely hard: every online policy must incur regret of order at least T1/2−1/(2p)T^{1/2 - 1/(2p)}, and this holds for every p > 1. A sample-path marginal policy matches this lower bound up to polylogarithmic factors; and when p = 1, so that the mass grows linearly near the cutoff, it attains O((log⁡T)2)O((\log T)^2) regret. For example, if the size and the value-to-size ratio are independent and uniformly distributed, then p = 1; if instead the size and the reward are independent and uniformly distributed, then p = 2. Thus the policy achieves o(T)o(\sqrt{T}) regret throughout this regularity class without any fluid non-degeneracy assumption, allowing both primal degeneracy and dual non-uniqueness.

Jiawei Zhang

Stern School of Business New York University

Regret MinimizationOnline Resource Allocation
AskPDF