Bi-Level Contextual Bandits for Individualized Resource Allocation under Delayed Feedback

AI summary

Overview

Research area: Sequential decision-making under uncertainty — specifically contextual multi-armed bandits applied to fairness-aware, individualized resource allocation in high-stakes social domains (education and workforce development).

Technical level: Advanced. The paper combines constrained bandit optimization, neural outcome modeling, kernel-based delay modeling, and a bi-level (meta/base) architecture with a formal fairness lemma.

Scope: The paper proposes and empirically evaluates MetaCUB, a bi-level contextual bandit framework that allocates limited resources across demographic subgroups and then to individuals within those subgroups, while accounting for delayed feedback, cooldown constraints, dynamic cohorts, and multiple resource types.

What This Paper Is About

Decision-makers in domains such as education, employment, and healthcare must distribute scarce interventions across people, but most learning-based allocation systems assume rewards arrive immediately and treat individuals as a static, homogeneous pool. The paper addresses the gap between these idealized assumptions and real deployment conditions: interventions pay off gradually (over semesters or months), participants enter and exit in cohorts, budgets are constrained, and fairness across subgroups must be preserved. The goal is a single framework that jointly decides how much budget each subgroup receives and which specific individuals within that subgroup are most likely to benefit.

Key Contributions

1. A neural network–based learning framework that maps individual context vectors to subgroup-level treatment effects, capturing latent heterogeneity in responsiveness and improving regret relative to linear models.
2. A bi-level contextual bandit design in which a meta-level bandit allocates fractional budgets across subgroup–resource pairs and a base-level bandit selects individual recipients, jointly optimizing under fairness, cooldown, and capacity constraints.
3. A deployment-oriented architecture that models cohort-driven population change, resource-specific budgets, resource-specific delay kernels, and stochastic cooldown windows.
4. An empirical validation on two real-world datasets (ELS and JOBS) reporting superior cumulative reward, fairness, and delay adaptation compared with a suite of bandit baselines, plus a theoretical disparity-reduction lemma.

Main Findings

• Lowest cumulative regret across settings: In all four experimental configurations per dataset (immediate vs. delayed feedback crossed with linear vs. nonlinear outcome functions), MetaCUB consistently achieves the lowest cumulative regret among the compared algorithms, with lines showing mean regret over 20 runs and shaded regions indicating standard deviations.
• Delayed feedback widens the gap: The performance advantage is especially pronounced in delayed-feedback environments, where conventional bandits such as UCB and EXP3 exhibit substantially higher regret because they lack temporal sensitivity. DUCB and SWUCB are more robust under delay but still underperform MetaCUB.
• Kernel shape drives difficulty: Type-I kernels are peaked and unimodal with concentrated delay weight at early-to-mid normalized times, letting algorithms receive informative feedback quickly and reach lower regret. Type-II kernels are flatter and more dispersed, diluting reward signals and causing delay-agnostic methods to accumulate regret more rapidly, particularly in the delayed linear case, while MetaCUB remains more resilient.
• Nonlinearity helps every method: Algorithms evaluated under nonlinear reward functions incur substantially lower regret than their linear counterparts in both datasets; even classical methods such as UCB and CUCB benefit when the linearity assumption is relaxed.
• Balanced subgroup coverage: Measured as the proportion of selected individuals in each subgroup (reported in Tables 1, 4, and 5 in the Appendix), MetaCUB achieves the most balanced coverage across both datasets and feedback regimes. The extracted table content is truncated, so complete numerical values are not available here.
• Theoretical fairness guarantee: Lemma 1 (Disparity Reduction) states that, under mild assumptions on exploration and model accuracy, the max–min subgroup outcome disparity under MetaCUB is smaller than under a flat contextual bandit by a gap δ(T_m, f) > 0 that increases with meta-rounds T_m and predictor fidelity f. The full formal proof is in the Appendix.
• Reward model accuracy context: For the JOBS binary employment classification task, the paper reports 86% overall accuracy on ELS (Asian = 87%, Black = 85%, Hispanic = 86%, White = 86%), used to ensure consistent subgroup performance.
• Dataset sizes not reported in the extracted content: The paper states that detailed dataset specifications appear in the Appendix; specific sample sizes are not present in the content provided.

Methodology in Plain English

The researchers frame allocation as a constrained sequential decision problem. There are N individuals split into K demographic subgroups, R resource types each with an integer budget, and T decision rounds. At each round, the planner picks one individual–resource pair, subject to a budget constraint, a "one resource per individual per round" rule, and cooldown constraints that bar giving the same resource to the same person again for a set number of rounds.

Delayed effects are handled with a delay kernel per resource — a nonnegative function that describes what fraction of an allocation's reward shows up at each later round, summing to one. These kernels are built by discretizing a Beta distribution into T equal-width bins; the shape parameters (α, β) can represent immediate feedback, long-tailed delays, or unimodal delays, and mixtures can represent multimodal ones. The kernel parameters are chosen from plausible timing profiles and fixed during learning, though the framework accepts any normalized kernel.

Population dynamics are modeled by splitting the horizon into H = ⌈T/L⌉ contiguous blocks of length L. Each cohort is only eligible within its own block; when a block ends, that cohort exits and is replaced.

To solve the problem, the authors propose MetaCUB, which works in two phases:

• Meta level: With a computational budget of T_m iterations, the algorithm samples candidate meta-policies from the interior of the probability simplex over subgroup–resource pairs, starting from n_0 initial policies. Rather than fitting a separate Gaussian Process in this high-dimensional space, it reuses the learned outcome model f as a simulation-based surrogate, running multiple stochastic rollouts to estimate a mean and standard deviation for each candidate. It then selects the next policy using a UCB acquisition rule balancing mean utility against uncertainty.
• Base level: Given the meta-policy, each subgroup–resource cell gets a target allocation count n_{k,r} = ⌊z̄_r^k · |I_k|⌋. Within each cell, individuals are scored by a local UCB rule combining the predicted reward from f with an uncertainty term, and the top n_{k,r} individuals receive the resource.

Baselines include UCB, LinUCB, CUCB, EXP3, mEXP3, DUCB, and SWUCB. For ELS (GPA regression) the study uses ridge regression and a neural network for linear and nonlinear mappings; for JOBS (binary employment classification) it uses logistic regression and the same neural network. Cohorts run 8 semesters for ELS and 12 months for JOBS. Cooldowns are sampled uniformly from {1, 2, 3} rounds. All experiments use 20 independent random seeds, implemented in Python 3.11.5 with NumPy, scikit-learn, and BoTorch, on an Apple M4 Pro (14-core CPU, 20-core GPU, 16-core Neural Engine, 24 GB RAM) running macOS 15.5.

Why This Matters

Impact on research: The paper argues that most contextual bandit methods treat delay as a nuisance variable or assume fixed, context-independent lags, and that prior work typically targets either individual personalization or group fairness but rarely both. MetaCUB's contribution is to combine a kernelized, resource-specific delay model with a hierarchical allocation structure, and to provide a formal disparity-reduction result alongside empirical fairness measures.

Real-world applications:

• Education: financial aid packaging and tutoring allocation to students, as modeled with the Educational Longitudinal Study dataset.
• Workforce development: job training and support program delivery, evaluated with the JOBS randomized field experiment.
• Healthcare: prioritizing treatments and interventions whose efficacy manifests over days or weeks, and where repeated treatment is restricted.
• Social welfare and public programs: distributing limited benefits across cohorts that enroll and exit on fixed cycles.

Industry relevance: Any organization that must sequence a limited budget across many people with delayed, unevenly distributed returns — platform incentives, customer retention offers, clinical outreach, or public-sector benefit delivery — faces the same structural problem. The framework's explicit handling of budgets, pacing rules, and cohort turnover makes it closer to a deployable operating model than approaches that assume instantaneous, unconstrained feedback. The authors also release code at https://github.com/sinatorrr/MAB.

Future Directions

• Adaptive or meta-learned delay kernels: The paper notes that kernel parameters are fixed during learning and that the framework supports adaptive or meta-learned kernel estimation when greater flexibility is needed, leaving this as an open avenue.
• Richer delay shapes: Mixtures of Beta densities are mentioned as a way to represent more complex or multimodal delays; whether these improve results is not reported in the provided content.
• Tightening the fairness guarantee: Lemma 1 depends on mild assumptions about exploration and model accuracy, and the disparity gap δ(T_m, f) is only sketched in the main text; the full proof is deferred to the Appendix, so the practical tightness of the bound remains to be examined.
• Validation beyond simulation: All reported experiments are simulations over the ELS and JOBS datasets with synthetic delay and cooldown structures; the paper does not report a live deployment, raising the question of how the framework performs under real institutional feedback loops.

Target Audience

This paper is most useful to researchers in reinforcement learning, bandit theory, and algorithmic fairness who work on constrained sequential decision-making; to applied machine learning practitioners building allocation systems for education, workforce, or healthcare settings where outcomes are delayed; and to policy and operations analysts who need to understand how fairness constraints, budgets, cooldowns, and cohort turnover can be encoded into a single learning framework. A background in contextual bandits and UCB-style exploration is helpful, since the technical level is advanced.

Authors’ abstract

Equitably allocating limited resources in high-stakes domains-such as education, employment, and healthcare-requires balancing short-term utility with long-term impact, while accounting for delayed outcomes, hidden heterogeneity, and ethical constraints. However, most learning-based allocation frameworks either assume immediate feedback or ignore the complex interplay between individual characteristics and intervention dynamics. We propose a novel bi-level contextual bandit framework for individualized resource allocation under delayed feedback, designed to operate in real-world settings with dynamic populations, capacity constraints, and time-sensitive impact. At the meta level, the model optimizes subgroup-level budget allocations to satisfy fairness and operational constraints. At the base level, it identifies the most responsive individuals within each group using a neural network trained on observational data, while respecting cooldown windows and delayed treatment effects modeled via resource-specific delay kernels. By explicitly modeling temporal dynamics and feedback delays, the algorithm continually refines its policy as new data arrive, enabling more responsive and adaptive decision-making. We validate our approach on two real-world datasets from education and workforce development, showing that it achieves higher cumulative outcomes, better adapts to delay structures, and ensures equitable distribution across subgroups. Our results highlight the potential of delay-aware, data-driven decision-making systems to improve institutional policy and social welfare.