Stochastic Bandits for Crowdsourcing and Multi-Platform Autobidding

François Bachoc, Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni · 2025

Read Stochastic Bandits for Crowdsourcing and Multi-Platform Autobidding by François Bachoc, Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-05844.txt.

Introduction

François Bachoc and three co-authors allocate budgets under uncertainty in twenty twenty-five. A learner must split a budget across many tasks each round. Each task succeeds with a probability that grows with its funding in an unknown way. Success brings a random reward, but the reward is visible only when the task succeeds.

That censored semi-bandit feedback models real settings. Splitting payments among crowdsourcing workers is one example. Distributing bids across simultaneous auctions is another. The authors design an optimism-based algorithm for the setting. In diminishing-returns regimes, its regret grows only polylogarithmically with time, without ad hoc tuning. General curves get their own analysis. Readers get a principled way to fund many uncertain tasks at once.

Catalog record

CREATORFrançois Bachoc, Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE82 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-05844

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Stochastic Bandits for Crowdsourcing and Multi-Platform Autobidding François Bachoc, Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni Abstract Motivated by applications in crowdsourcing, where a fixed sum of money is split among K K workers, and autobidding, where a fixed budget is used to bid in K K simultaneous auctions, we define a stochastic bandit model where arms belong to the K 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 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 T steps is of order K ​ T K\sqrt{T} (up to log factors) and prove a matching lower bound. Improved bounds of order K ​ ( log ⁡ T ) 2 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. 1 Introduction The multi-armed bandit, a mathematical model for sequential decision-making with partial feedback, has been applied to a wide range of domains, including clinical trials, product recommendation, online advertising, digital markets, and process optimization. A multi-armed bandit consists of an action space and an unknown reward process associated with each action. At every decision round, a bandit algorithm selects an action and observes the reward produced at that round by the process associated with the chosen action. In this work we focus on a setting where rewards are stochastic and actions have a linear structure. However, unlike the classical linear bandit model—where the expected reward is a linear function of the selected action x —in our setting the expected reward is \bigl\langle\mu,F(x)\bigr\rangle , where \mu\in[0,1]^{K} are unknown coefficients and F\colon\mathbb{R}^{K}\to[0,1]^{K} is some (possibly nonlinear) function. More specifically, we assume that actions x are elements of the K -dimensional probability simplex and F(x) are the means of K Bernoulli random variables. The realizations of these random variables, which the algorithm observes after each round, tell us which of the K components of our action contributed to the total reward in that round. This simple variant of linear bandits allows us to analyze new interesting scenarios that were not fully captured by previous analyses: • A platform for crowdsourcing splits in each round a fixed sum of money among K workers who must complete a set of tasks. Workers will accept and complete their tasks only with a certain probability, defined by the vector F(x)=\big(F_{1}(x_{1}),\ldots,F_{K}(x_{K})\big) and depending on each worker’s preferences and reliability that are being affected by the payments x=(x_{1},\ldots,x_{K}) , where x_{k} is the fraction of money received by the k -th worker. The platform’s expected reward in that round, \bigl\langle\mu,F(x)\bigr\rangle , depends on the productivity of each worker modeled via K random variables with means \mu\in[0,1]^{K} . • An autobidding agent spends in each round a fixed budget to bid in K simultaneous auctions. Auctions are won with probabilities F(x)=\big(F_{1}(x_{1}),\ldots,F_{K}(x_{K})\big) depending on the agent’s bids x=(x_{1},\ldots,x_{K}) and the competing bids in each auction. The agent’s expected reward in the round, \bigl\langle\mu,F(x)\bigr\rangle , depends on the unknown value of each auctioned item, which is modeled via K random variables with means \mu\in[0,1]^{K} . Other applications include online model selection, where a computing time budget is split among several instances of a learning system (e.g., a LLM trained with different hyperparameter values) and the expected reward is computed based on the quality of the output produced by those instances that terminated training (or inference) within the allocated time—see, e.g., xia2024llm for work along these lines. 1.1 Related works Our model is a variant of stochastic linear bandits—see, e.g., ( lattimore2020bandit , Chapter 19) . In that setting, the expected reward at step t is \left\langle\mu,x_{t}\right\rangle , and the feedback observed by the algorithm is the realized reward \left\langle\mu,x_{t}\right\rangle+\eta_{t} , where \mu is the latent parameter and \eta_{t} is a zero-mean subgaussian random variable. While this setting has been originally formulated with x and \mu both lying in Euclidean balls— (\ell_{2},\ell_{2}) geometry for short—regret bounds for arbitrary (\ell_{p},\ell_{q}) geometries have been shown in ( bubeck2012towards ; bubeck2018sparsity ) . In the bandits with experts adversarial model of auer2002nonstochastic , the geometry is (\ell_{1},\ell_{\infty}) just like in our setting. However, unlike our setting, the feedback in that model is \theta_{t,I_{t}} where \theta_{t} is the adversarial reward at time t and I_{t}\in[K] is drawn according to the action x_{t} in the K -dimensional simplex selected at time t . Our model is also reminiscent of the binary classification model with paid experts studied in ( van2023trading ) , see also ( zhang2015bandit ) for earlier results along these lines. The work on paid experts uses a (\ell_{\infty},\ell_{\infty}) geometry mapping payments x\in[0,1]^{K} to (\varepsilon_{1},\ldots,\varepsilon_{K})\in[0,1]^{K} , where \varepsilon_{k}=F_{k}(x_{k}) for unknown Lipschitz functions F_{1},\ldots,F_{K} . Here \varepsilon_{k} is the probability that the k -th expert correctly classifies the t -th bit of an unknown bit sequence. The expected reward, however, is not a function of \bigl\langle x,F(x)\bigr\rangle , which implies that we cannot directly apply those results to our problem. Previous works applying bandits to crowdsourcing ( tran2014efficient ) , multi-platform autobidding ( aggarwal2025multi ) , and multi-channel advertising ( avadhanula2021stochastic ; deng2023multi ) use global (across T time steps) constraints on budget. Unlike our setting, which considers per-step budget constraints, the presence of global (knapsack) constraints changes the nature of the problem making it more similar to constrained online optimization (with bandit feedback). Note that per-step budget constraints capture certain applications better than global constraints. For example, in cost-efficient inference for LLMs ( li2025llm ; nguyen2024metallm ) , we optimize the choice of which LLM to use via a trade-off between generation cost and model quality for each input prompt. In crowdsourcing, stochastic models of acceptance probability and reliability were investigated in ( ul2016efficient ) without providing a mathematical guarantee on the algorithm’s performance. A setting similar to ours is studied in ( kang2020task ) , where F_{1},\ldots,F_{K} are restricted to be linear functions. These linear functions are known only for some k\in[K] , and the algorithm is unable to observe whether the tasks with unknown F_{k} were successfully completed. A regret bound of order \sqrt{T} is proven for a notion of reward different from ours. 1.2 Setting For any n\in\mathbb{N} , we let [n] be the set \{1,\dots,n\} . The action space is the K -dimensional simplex \Delta_{K}\coloneqq\{x\in[0,1]^{K}:\sum_{k\in[K]}x_{k}=1\} , for some K\in\mathbb{N} , which we fix for the remaining of this work. Let G_{t,k} be the stochastic reward associated with the completion of task k\in[K] at time t , where for each k\in[K] , (G_{t,k})_{t\in\mathbb{N}} is an unknown i.i.d. sequence of [0,1] -valued random variables with unknown expectation \mu_{k} . If we allocate a budget x_{k}\in[0,1] on a task k\in[K] , then the probability of completing the task k is F_{k}(x_{k}) , where F_{1},\dots,F_{K}\colon[0,1]\to[0,1] are non-decreasing functions. Also, we let B_{t,k}(x_{k}) be the Bernoulli random variable that indicates the completion of the task k at time t , so that \mathbb{E}\bigl[B_{t,k}(x_{k})\bigr]=F_{k}(x_{k}) , where, for each k\in[K] , \bigl(B_{t,k}(x_{k})\bigr)_{t\in\mathbb{N},x_{k}\in[0,1]} is an unknown independent family of Bernoulli random variables, independent

Read the complete text