# Allocating Divisible Resources on Arms with Unknown and Random Rewards

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 46 references that are in the map.
- First posted on arXiv 28 Jun 2023.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1702.06103/) (2017)
- [Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback](https://mlsanity.com/paper/1910.12424/) (2019)
- [Prior-free and prior-dependent regret bounds for Thompson Sampling](https://mlsanity.com/paper/1304.5758/) (2013)
- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [Online Learning with Vector Costs and Bandits with Knapsacks](https://mlsanity.com/paper/2010.07346/) (2020)
- [Online Learning with Gaussian Payoffs and Side Observations](https://mlsanity.com/paper/1510.08108/) (2015)
- [Tight Lower Bounds for Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2002.05392/) (2020)
- [Lazy OCO: Online Convex Optimization on a Switching Budget](https://mlsanity.com/paper/2102.03803/) (2021)
- [Censored Semi-Bandits: A Framework for Resource Allocation with Censored Feedback](https://mlsanity.com/paper/1909.01504/) (2019)
- [Maillard Sampling: Boltzmann Exploration Done Optimally](https://mlsanity.com/paper/2111.03290/) (2021)
- [An adaptive stochastic optimization algorithm for resource allocation](https://mlsanity.com/paper/1902.04376/) (2019)
- [Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information](https://mlsanity.com/paper/2103.13059/) (2021)
- [Optimal Resource Allocation with Semi-Bandit Feedback](https://mlsanity.com/paper/1406.3840/) (2014)
- [A Better Resource Allocation Algorithm with Semi-Bandit Feedback](https://mlsanity.com/paper/1803.10415/) (2018)
- [Bandits with Side Observations: Bounded vs. Logarithmic Regret](https://mlsanity.com/paper/1807.03558/) (2018)

## Abstract (arXiv)

We consider a decision maker allocating one unit of renewable and divisible resource in each period on a number of arms. The arms have unknown and random rewards whose means are proportional to the allocated resource and whose variances are proportional to an order b of the allocated resource. In particular, if the decision maker allocates resource Ai to arm i in a period, then the reward Yi isYi(Ai)=Ai μi+Aib xii, where μi is the unknown mean and the noise xii is independent and sub-Gaussian. When the order b ranges from 0 to 1, the framework smoothly bridges the standard stochastic multi-armed bandit and online learning with full feedback. We design two algorithms that attain the optimal gap-dependent and gap-independent regret bounds for b∈ [0,1], and demonstrate a phase transition at b=1/2. The theoretical results hinge on a novel concentration inequality we have developed that bounds a linear combination of sub-Gaussian random variables whose weights are fractional, adapted to the filtration, and monotonic.