mlsanityData to 14 Oct 2026

Allocating Divisible Resources on Arms with Unknown and Random Rewards

arXiv 2306.16578 ↗First posted 28 Jun 2023cs.LG math.ST stat.MLcited by 0

Not on the map. Why?

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.

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

21 of 46 references.

References · 21

  1. 2019Introduction to Multi-Armed Banditscited by 481
  2. 2013Bandits with Knapsackscited by 164
  3. 2019Batched Multi-armed Bandits Problemcited by 98
  4. 2014Bandits with concave rewards and convex knapsackscited by 83
  5. 2015Linear Contextual Bandits with Knapsackscited by 82
  6. 2016An optimal algorithm for the Thresholding Bandit Problemcited by 62
  7. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  8. 2019Online Continuous Submodular Maximization: From Full-Information to Bandit Feedbackcited by 33
  9. 2013Prior-free and prior-dependent regret bounds for Thompson Samplingcited by 25
  10. 2021Regret Minimization in Heavy-Tailed Banditscited by 25
  11. 2020Online Learning with Vector Costs and Bandits with Knapsackscited by 20
  12. 2015Online Learning with Gaussian Payoffs and Side Observationscited by 15
9 more
  1. 2020Tight Lower Bounds for Combinatorial Multi-Armed Banditscited by 15
  2. 2021Lazy OCO: Online Convex Optimization on a Switching Budgetcited by 14
  3. 2019Censored Semi-Bandits: A Framework for Resource Allocation with Censored Feedbackcited by 13
  4. 2021Maillard Sampling: Boltzmann Exploration Done Optimallycited by 13
  5. 2019An adaptive stochastic optimization algorithm for resource allocationcited by 11
  6. 2021Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Informationcited by 11
  7. 2014Optimal Resource Allocation with Semi-Bandit Feedbackcited by 6
  8. 2018A Better Resource Allocation Algorithm with Semi-Bandit Feedbackcited by 5
  9. 2018Bandits with Side Observations: Bounded vs. Logarithmic Regretcited by 4

Built on by

Not cited yet.