Adaptive Multi-Round Allocation with Stochastic Arrivals

• URL: http://arxiv.org/abs/2605.12111v1
• Date: Tue, 12 May 2026 13:29:06 GMT
• Title: Adaptive Multi-Round Allocation with Stochastic Arrivals
• Abstract summary: We study a sequential resource allocation problem motivated by adaptive network recruitment.<n>We first show that the single-round allocation problem admits an exact greedy solution based on marginal survival probabilities.<n>In the multi-round setting, the resulting Bellman recursion is intractable due to the high-dimensional evolution of the frontier.
• Score: 26.102812388131813
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a sequential resource allocation problem motivated by adaptive network recruitment, in which a limited budget of identical resources must be allocated over multiple rounds to individuals with stochastic referral capacity. Successful referrals endogenously generate future decision opportunities while allocating additional resources to an individual exhibits diminishing returns. We first show that the single-round allocation problem admits an exact greedy solution based on marginal survival probabilities. In the multi-round setting, the resulting Bellman recursion is intractable due to the stochastic, high-dimensional evolution of the frontier. To address this, we introduce a population-level surrogate value function that depends only on the remaining budget and frontier size. This surrogate enables an exact dynamic program via truncated probability generating functions, yielding a planning algorithm with polynomial complexity in the total budget. We further analyze robustness under model misspecification, proving a multi-round error bound that decomposes into a tight single-round frontier error and a population-level transition error. Finally, we evaluate our method on real-world inspired recruitment scenarios.

Related papers

• Generative Frontier Planning for Adaptive Peer-Referral Recruitment under Covariate-Dependent Arrivals [28.082278231005997]
  Peer-referral recruitment systems are critical for studying and intervening on hidden populations affected by infectious diseases.<n>We propose emphGenerative Frontier Planning (GFP), a model-based planner that replaces per-step Monte-Carlo sampling with a deterministic backup.<n>GFP outperforms random, reinforcement-learning, and i.i.d. dynamic-programming baselines across four discount factors.
  arXiv  Detail & Related papers  (2026-06-06T22:31:07Z)
• OpenVLThinkerV2: A Generalist Multimodal Reasoning Model for Multi-domain Visual Tasks [81.07598709704628]
  We present a novel RL training objective that replaces standard linear scaling with non-linear distributional matching.<n>We also present OpenVLThinkerV2, a highly robust, general-purpose multimodal model.
  arXiv  Detail & Related papers  (2026-04-09T17:59:39Z)
• Locally Confident, Globally Stuck: The Quality-Exploration Dilemma in Diffusion Language Models [52.61023005303122]
  We show that low-confidence remasking improves a proxy for quality while constraining the entropy of the induced sequence distribution.<n>We develop a simple Independent--Hastings sampler that approximately targets this distribution during decoding.
  arXiv  Detail & Related papers  (2026-04-01T02:01:30Z)
• A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming [29.531157410826825]
  We study nonstationary Online Linear Programming (OLP)<n>In OLP, $n$ orders arrive sequentially with reward-resource consumption pairs that form a sequence of independent, but not necessarily identically distributed, random vectors.<n>We propose a novel re-solving algorithm that integrates a dynamic programming perspective with the dual-based frameworks traditionally employed in stationary environments.
  arXiv  Detail & Related papers  (2026-03-15T23:59:30Z)
• Non-Stationary Online Resource Allocation: Learning from a Single Sample [5.81028169940199]
  We study online resource allocation under non-stationary demand with a minimum offline data requirement.<n>We propose a novel type-dependent quantile-based meta-policy that decouples the problem into modular components.
  arXiv  Detail & Related papers  (2026-02-20T10:07:35Z)
• No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! [56.80767500991973]
  We focus on two canonical settings: $(i)$ online resource allocation where rewards and costs are observed before action selection, and $(ii)$ online learning with resource constraints where they are observed after action selection, under full feedback or bandit feedback.<n>It is well known that achieving sublinear regret in these settings is impossible when reward and cost distributions may change arbitrarily over time.<n>We design general (primal-)dual methods that achieve sublinear regret with respect to baselines that follow the spending plan. Crucially, the performance of our algorithms improves when the spending plan ensures a well-balanced distribution of the budget
  arXiv  Detail & Related papers  (2025-06-16T08:42:31Z)
• Online Fair Allocation of Perishable Resources [1.4952056744888913]
  We consider a practically motivated variant of the canonical online fair allocation problem. A decision-maker has a budget of perishable resources to allocate over a fixed number of rounds. The goal is to construct a sequence of allocations that is envy-free and efficient.
  arXiv  Detail & Related papers  (2024-06-04T15:14:10Z)
• Latent State Marginalization as a Low-cost Approach for Improving Exploration [79.12247903178934]
  We propose the adoption of latent variable policies within the MaxEnt framework. We show that latent variable policies naturally emerges under the use of world models with a latent belief state. We experimentally validate our method on continuous control tasks, showing that effective marginalization can lead to better exploration and more robust training.
  arXiv  Detail & Related papers  (2022-10-03T15:09:12Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints. We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates. The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
  arXiv  Detail & Related papers  (2022-09-16T09:38:38Z)
• Coordinated Online Learning for Multi-Agent Systems with Coupled Constraints and Perturbed Utility Observations [91.02019381927236]
  We introduce a novel method to steer the agents toward a stable population state, fulfilling the given resource constraints. The proposed method is a decentralized resource pricing method based on the resource loads resulting from the augmentation of the game's Lagrangian.
  arXiv  Detail & Related papers  (2020-10-21T10:11:17Z)
• Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
  We introduce the emphregularized online allocation problem, a variant that includes a non-linear regularizer acting on the total resource consumption. In this problem, requests repeatedly arrive over time and, for each request, a decision maker needs to take an action that generates a reward and consumes resources. The objective is to simultaneously maximize additively separable rewards and the value of a non-separable regularizer subject to the resource constraints.
  arXiv  Detail & Related papers  (2020-07-01T14:24:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.