# Online Budget Allocation with Censored Semi-Bandit Feedback

arXiv: https://arxiv.org/abs/2508.05844 · HTML: https://mlsanity.com/paper/2508.05844/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 23 references that are in the map.
- First posted on arXiv 7 Aug 2025.

## Builds on (most cited first, 13 of 13)

- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [MetaLLM: A High-performant and Cost-efficient Dynamic Framework for Wrapping LLMs](https://mlsanity.com/paper/2407.10834/) (2024)
- [LLM Bandit: Cost-Efficient LLM Generation via Preference-Conditioned Dynamic Routing](https://mlsanity.com/paper/2502.02743/) (2025)
- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [Stochastic Bandits for Multi-platform Budget Optimization in Online Advertising](https://mlsanity.com/paper/2103.10246/) (2021)
- [Sparsity, variance and curvature in multi-armed bandits](https://mlsanity.com/paper/1711.01037/) (2017)
- [Multi-channel Autobidding with Budget and ROI Constraints](https://mlsanity.com/paper/2302.01523/) (2023)
- [Optimal Resource Allocation with Semi-Bandit Feedback](https://mlsanity.com/paper/1406.3840/) (2014)
- [Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism](https://mlsanity.com/paper/2011.00330/) (2020)
- [Multi-Platform Autobidding with and without Predictions](https://mlsanity.com/paper/2502.19317/) (2025)
- [Trading-Off Payments and Accuracy in Online Classification with Paid Stochastic Experts](https://mlsanity.com/paper/2307.00836/) (2023)
- [Bandit-Based Task Assignment for Heterogeneous Crowdsourcing](https://mlsanity.com/paper/1507.05800/) (2015)
- [Task Recommendation in Crowdsourcing Based on Learning Preferences and Reliabilities](https://mlsanity.com/paper/1807.10444/) (2018)

## Abstract (arXiv)

We study a stochastic budget-allocation problem over K tasks. At each round t, the learner chooses an allocation Xt ∈ DeltaK. Task k succeeds with probability Fk(Xt,k), where F1,dots,FK are nondecreasing budget-to-success curves, and upon success yields a random reward with unknown mean μk. The learner observes which tasks succeed, and observes a task's reward only upon success (censored semi-bandit feedback). This model captures, for instance, splitting payments across crowdsourcing workers or distributing bids across simultaneous auctions, and subsumes stochastic multi-armed bandits and semi-bandits. We design an optimism-based algorithm that operates under censored semi-bandit feedback. Our main result shows that in diminishing-returns regimes, the regret of this algorithm scales polylogarithmically with the horizon T without any ad hoc tuning. For general nondecreasing curves, we prove that the same algorithm (with the same tuning) achieves a worst-case regret upper bound of tilde O(K√T). Finally, we establish a matching worst-case regret lower bound of Omega(K√T) that holds even for full-feedback algorithms, highlighting the intrinsic hardness of our problem outside diminishing returns.