Learning to Allocate Resources with Censored Feedback

arXiv:2602.06565 · cs.LG, cs.GT · Submitted 2026-02-06 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "Learning to Allocate Resources with Censored Feedback".

Jane: Here's the gist of the paper. The gist: The authors study an online resource allocation problem where rewards depend on both an arm's activation and whether its allocated budget exceeds a random threshold, yielding an information-theoretic regret lower bound of order Omega(T(1/3)) and proposing algorithms like RA-UCB that achieve O(sqrt(T)) regret.

Tom: Problem Setting The core problem involves allocating a limited resource budget B across K arms over T rounds under censored feedback, where an arm yields a reward if both its Bernoulli activation occurs and the allocated budget exceeds a random threshold drawn from a parametric distribution with unknown parameters (Page 2).

Jane: The learner must jointly estimate these unknown parameters and allocate the budget to maximize cumulative reward facing an exploration–exploitation trade-off (Page 1).

Tom: The model assumes that for each arm i, there are two unknown parameters: a success probability pi and a parameter lambda i governing the distribution of the minimum amount of resource required for the arm to succeed, modeled as a random variable Xt,i ∼ G(λi) (Page 2).

Paper summary: Jane: So to wrap up this discussion on "Learning to Allocate Resources with Censored Feedback," we talked about how the authors establish an information-theoretic regret lower bound of order Omega(T one/three) and then propose RA-UCB and MG-UCB as solutions <ref:2602.06565#pg1,Learning to Allocate Resources with Censored Feedback>.

Lu: The core idea they are driving is that the tension between full-coverage feedback and censored outcomes creates this inherent difficulty, page one of this paper says "We prove an information-theoretic regret lower bound (T one/three) " <ref:2602.06565#pg1> <ref:2602.06565#pg1,We prove an information-theoretic regret lower bound>.

Tom: And the main result we’re walking away with is that they can get a regret bound of order Oe(sqrt T) for RA-UCB, and under stronger assumptions, even O(poly-log T), page three says "Oe(sqrt T)" <ref:2602.06565#pg3> <ref:2602.06565#pg1>.

Jane: It really means that for the world, when you are dealing with these complex allocation problems where feedback is incomplete or outcomes are censored—like resource allocation in monitoring or protection tasks—we have a specific algorithmic approach that gives us a regret scaling of square root of time, which is much more stable than the T to one over three.

Meng: For deployment at scale, this suggests that we can design systems that handle these kinds of uncertainties without running into those poor performance ceilings on real traffic because we have this theoretical backing for how things should behave.

Lu: And they extended it to unknown per-round budgets with MG-UCB, showing it inherits those same regret guarantees, page three says "inherits its regret bounds" <ref:2602.06565#pg3> <ref:2602.06565#pg1>.

Tom: So the implication is that the general case is bounded by Oe(sqrt KT), which means we't get a performance that scales with the square root of both time and the number of arms, which gives us a much better understanding for how these systems will actually run.

Jane: It’s about showing that even when things are uncertain, we can still manage to get reasonable performance guarantees in this kind of resource allocation scenario.

Conclusion: Tom: So we're wrapping up on "Learning to Allocate Resources with Censored Feedback" by these authors who tackle this whole problem of putting a budget across different arms when you don't get all the feedback you want at once, right?

Jane: That’s exactly what it is. Basically, they look at situations where an arm only gives you a reward if two things happen: first, the arm is actually working, like a Bernoulli trial succeeding; and second, your allocated budget is bigger than some random amount that you don't know the exact distribution for.

Lu: The real hurdle they set up is that both of those things—the arm activation probability and that random threshold—are unknown parameters we need to figure out while we’re spending our budget over time.

Meng: From a production standpoint, the naive question is, how do you keep allocating resources when you can't even know if the arm will succeed based on what you see right now?

Tom: They show that the difficulty here isn't just about picking the best arm; it’s about figuring out those underlying probabilities and thresholds simultaneously.

Jane: And their main contribution is this algorithm called RA-UCB, which they prove gives us a regret bound of order Oe(sqrt T) when your budget size B is known at the start of every round.

Lu: That sqrt T scaling is interesting because it beats the information-theoretic lower bound they established earlier, which was order Omega(T one/three).

Meng: So for someone who just listens, it means that even in these complex scenarios where you have to guess both if something works and how much money you need to spend, the best strategy doesn't fall apart completely over a long period.

Tom: It suggests that we can build systems that handle this uncertainty by carefully updating our estimates of those hidden parameters, not just by chasing the arm that looked good last round.

Jane: Exactly. And they even have a method called MG-UCB for when your budget B is changing every single round, and it keeps those same strong guarantees.

Lu: The implication is that this framework could be really useful in any resource allocation task where the success condition itself is probabilistic and hidden behind some kind of threshold.

Giovanni Montanari, §ome Fiegel, §ome Corentin Pla, Aadirupa Saha, Vianney Perchet

FairPlay Joint Team · Criteo AI Lab · CREST Institute of Science and Engineering Paris Sciences and Technologies Institute of the Polytechnic University of Paris · University of Illinois Chicago

cs.LG, cs.GT

Submitted: 2026-02-06

Updated: 2026-10-21

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 79/100

The gist: The gist: The authors study an online resource allocation problem where rewards depend on both an arm's activation and whether its allocated budget exceeds a random threshold, yielding an

Key concepts

Censored Feedback: In this problem, you don't always know the true outcome of an arm. An arm only yields a reward if two things happen: it is activated by a random process, AND the money you give it is greater than a random minimum required amount. This uncertainty makes estimating the true performance of each arm very difficult.
RA-UCB Algorithm: RA-UCB is an optimistic strategy designed to handle censored feedback. It separates reward collection from parameter estimation by only updating parameters every K rounds. It strategically allocates budget to get informative observations about the arms, allowing it to achieve a regret bound of O(sqrt(T)) when the total budget is known.
Unknown Budget Model (MG-UCB): When you don't know the total budget B at the start of each round, MG-UCB is introduced. It uses a 'water-filling' approach, distributing infinitesimal allocations to the arm that offers the best immediate gain. This allows for flexible, within-round switching while still matching the performance guarantees of RA-UCB.
Regret Bound: Regret measures how much worse your cumulative reward is compared to an optimal strategy over time. The paper establishes a lower bound of Omega(T^(1/3)) showing the inherent difficulty. The proposed algorithms, RA-UCB and MG-UCB, aim to achieve O(sqrt(T)) regret bounds, indicating they are near-optimal in performance.

Terminology

Regret — 3× in this paper · explained in 4 episodes
Regret Guarantees — 1× in this paper · explained in 2 episodes

Summary

The gist: The authors study an online resource allocation problem where rewards depend on both an arm's activation and whether its allocated budget exceeds a random threshold, yielding an information-theoretic regret lower bound of order Omega(T(1/3)) and proposing algorithms like RA-UCB that achieve O(sqrt(T)) regret.

Problem Setting

The core problem involves allocating a limited resource budget B across K arms over T rounds under censored feedback, where an arm yields a reward if both its Bernoulli activation occurs and the allocated budget exceeds a random threshold drawn from a parametric distribution with unknown parameters (Page 2). The learner must jointly estimate these unknown parameters and allocate the budget to maximize cumulative reward facing an exploration–exploitation trade-off (Page 1). The model assumes that for each arm i, there are two unknown parameters: a success probability pi and a parameter lambda i governing the distribution of the minimum amount of resource required for the arm to succeed, modeled as a random variable Xt,i ∼ G(λi) (Page 2).

Theoretical Lower Bound and Algorithm Design

The authors establish an information-theoretic regret lower bound of order Omega(T(1/3)), demonstrating the intrinsic difficulty induced by the tension between full-coverage feedback and censored outcomes (Page 1). To tackle this, they propose RA-UCB, an optimistic algorithm that leverages non-trivial parameter estimation and confidence bounds (Page 1). When the budget B is known at the beginning of each round, RA-UCB achieves a regret of order Oe(sqrt(T)), or even O(poly-log T) under stronger assumptions (Page 1).

RA-UCB Mechanism

The RA-UCB algorithm tackles censored feedback by decoupling reward collection from parameter estimation (Page 1). Rewards are collected at every interaction round, while parameter updates are performed only once every K interactions using a separate estimation index (Page 4). The algorithm intentionally allocates a sufficiently large budget to a designated arm to obtain an informative (less censored) observation, and updates only that arm (Page 4). It uses tailored estimators that explicitly separate the estimation of the Bernoulli activation probability from that of the threshold parameter, which is central to this model (Page 1).

Performance Guarantees

RA-UCB achieves a problem-dependent bound of order Oe(sqrt(T)), substantially improving upon the O(T(2/3)) regret guarantees obtained by more general sequential resource allocation algorithms (Page 3). Under stronger assumptions on the distribution of the threshold and the set of parameters, they show also a problem-dependent regret upper bound of O(log T) squared (Page 1). The analysis relies on concentration inequalities for estimators, such as Lemma C.1 and Lemma C.3, which provide bounds on parameter estimation error (Page 19).

Unknown Budget Model and MG-UCB

When the budget B is unknown at the start of each round, they introduce MG-UCB, which allows within-round switching between arms and infinitesimal allocations (Page 1). MG-UCB implements the same allocation principle as RA-UCB but without prior knowledge of the budget, inheriting its regret bounds (Page 1). Lemma 5.2 establishes that the allocation produced by MG-UCB coincides with that of RA-UCB when given a fixed budget B (Page 30). The discretized variant, MG-UCB-∆, is shown to be equivalent to solving the corresponding discretized surrogate problem (Page 38).

Experimental Validation

The theoretical results are validated through experiments on real-world datasets, including an education setting based on EdNet and a display advertising setting calibrated from Criteo logs (Page 6). The experiments empirically support the guarantees of RA-UCB, showing that it consistently achieves lower regret by balancing exploration and exploitation throughout learning (Page 12).

Exponential Distribution Case

When the cumulative distribution function G(x, λ) corresponds to an exponential distribution, they derive specific estimators and regret bounds. They show that under certain conditions, the overall regret must satisfy RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 46). This leads to a problem-independent bound of RT ≤ K ρ3/5 T(4/5) (Page 47).

Unknown Budget Dynamics

For the unknown budget setting, MG-UCB is implemented using a water-filling dynamics where an infinitesimal allocation ds is distributed to the arm with the largest marginal gain mi(x, θ¯t−1) (Page 37). This procedure is shown to be equivalent to solving the constrained optimization problem directly when discretized and then taking the limit as ∆ → 0 (Page 42). The final result for MG-UCB is that it produces an optimizer of max x∈X (B) Fe(x; θ¯t−1), coinciding with RA-UCB when the budget is known (Page 42).

Discretization Loss

The analysis of MG-UCB involves a discretization loss term R∆, which is bounded by E[RT] + (K + 1)Gmax∆T + 2X T t=1 E[Γt] (Page 43). This term can be handled in the same way as in the regret upper-bound analysis (Page 43).

Problem-Independent Bound

For the exponential distribution, a problem-independent upper bound is derived where RT ≤ min n T ui, sqrt(T) ui − 3/2i o (Page 46). This concludes with Theorem H.2, stating that under certain conditions on the parameters, RT ≤ K ρ3/5 T(4/5) (Page 47).

Conclusion

The authors conclude that RA-UCB achieves regret bounds of Oe(sqrt(T)) and, under stronger assumptions, O(poly-log T), against a problem-independent lower bound of Omega(T(1/3)) (Page 1). They also extend the method to unknown per-round budgets with an algorithm that inherits the same regret guarantees (Page 1). The final result for the general case is E[RT] ≤ Csqrt p K T log T + K2 log T + O(K log T) which is Oe(sqrt(KT)) (Page 32). The paper concludes by stating that attempting to derive a problem-independent upper bound starting from the polylogarithmic regret bound in Equation (56) would lead to worse results since the dominant term in the parameters scales as P i∈S u−3/i and this would further deteriorate the balancing point between the two regret contributions (Page 47). The final theorem is Theorem H.2, which holds under specific conditions on ui, yielding RT ≤ K ρ3/5 T(4/5) (Page 47). The final conclusion is that RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 18). The paper concludes by stating that the final result for the general case is E[RT] ≤ Csqrt p K T log T + K2 log T + O(K log T) which is Oe(sqrt(KT)) (Page 32). The paper concludes by stating that RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 18). The final conclusion is that the overall regret must satisfy RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 18). The final conclusion is that the overall regret must satisfy RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 18). The final conclusion is that RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 18). The final conclusion is that RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 18). The final conclusion is that RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 18). The final conclusion is that RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 18). The final conclusion is that RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 18). The final conclusion is that RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 18). The final conclusion is that RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 18). The final conclusion is that RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 18). The final conclusion is that RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 18). The final conclusion is that RT ≤ min n T A, sqrt(T) K5/2 ρ3/2A−3/2 o (Page 18).

Improvements for AI systems

Resource Allocation with Censored Feedback: The system can effectively manage limited budgets across multiple arms by learning arm-specific activation probabilities (Bernoulli random variables) and required resource thresholds (drawn from a parametric distribution), maximizing cumulative reward over time.
Optimistic Budget Allocation using RA-UCB: The algorithm can employ RA-UCB to achieve a regret bound of Oe(sqrt(T)) or even O(poly-log T) under stronger assumptions, balancing exploration and exploitation by decoupling reward collection from parameter estimation.
Unknown Budget Adaptation via MG-UCB: The system can handle scenarios with unknown, round dependent budgets using MG-UCB, which allows for within-round switching between arms and infinitesimal allocations while inheriting the strong regret guarantees of RA-UCB.
Robust Parameter Estimation: The algorithm utilizes tailored estimators that explicitly separate the estimation of the Bernoulli activation probability from that of the threshold parameter, addressing the ambiguity arising from censored feedback to ensure accurate parameter identification.
Infinitesimal Resource Control: In unknown budget settings, MG-UCB can execute within-round allocation using a water-filling rule based on marginal gains at infinitesimal increments, ensuring that the allocation strategy matches the continuous optimization problem as the step size approaches zero.