2025/08/07 by Bachoc, François, Cesa-Bianchi, Nicolò, Cesari, Tommaso +1
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.2508.05844
Motivated by applications in crowdsourcing, where a fixed sum of money is split among K workers, and autobidding, where a fixed budget is used to bid in K simultaneous auctions, we define a stochastic bandit model where arms belong to the K-dimensional probability simplex and represent the fraction of budget allocated to each task/auction. The reward in each round is the sum of K stochastic rewards, where each of these rewards is unlocked with a probability that varies with the fraction of the budget allocated to that task/auction. We design an algorithm whose expected regret after T steps is of order K√(T) (up to log factors) and prove a matching lower bound. Improved bounds of order K (log T)2 are shown when the function mapping budget to probability of unlocking the reward (i.e., terminating the task or winning the auction) satisfies additional diminishing-returns conditions.