From Novice to Expert: Cost-Aware Bandits for Evolving Worker Performance in Crowdsensing

# From Novice to Expert: Cost-Aware Bandits for Evolving Worker Performance in Crowdsensing
Source: [https://arxiv.org/html/2607.13546](https://arxiv.org/html/2607.13546)
Yin Huang Qingsong Liu Jie XuY\. Huang and J\. Xu are with the Department of Electrical and Computer Engineering, University of Florida\. Email: \{yin\.huang, jie\.xu\}@ufl\.edu\. Q\. Liu is with the Manning College of Information and Computer Sciences, University of Massachusetts Amherst\. Email: qingsongliu@umass\.edu\.

###### Abstract

Mobile crowdsensing \(MC\) recruits mobile users to perform sensing tasks using their smartphones, enabling large\-scale applications such as traffic monitoring and environmental sensing\. A fundamental challenge is online worker recruitment under uncertainty, where the platform must learn workers’ sensing performance while operating with a limited budget\. Existing learning\-based MC recruitment methods typically assume that each worker’s sensing quality is stationary with a fixed mean over time\. In practice, however, worker performance often improves with experience and eventually stabilizes, while the incurred sensing cost can be unknown in advance due to time\-varying device and context states\. In this paper, we study a budget\-constrained online recruitment problem in which the platform selects one worker in each round, observes the sensing quality and incurred cost, where the expected sensing quality of each worker increases with experience and eventually converges to a plateau, and repeats until the budget is exhausted\. We formulate this problem as a structured bandit model where each worker’s expected reward evolves according to an unknown increasing\-then\-converging function of its participation count, and each worker has an unknown expected cost\. We develop a cost\-aware online learning framework that jointly learns evolving reward trajectories and heterogeneous costs, detects performance saturation, and allocates the limited budget to maximize long\-term sensing utility\. We provide theoretical performance guarantees and validate the proposed approach through extensive experiments, demonstrating consistent improvements over baselines that ignore experience\-driven dynamics or assume known costs\.

###### Index Terms:

Crowdsourcing, Multi\-armed Bandits, Worker Selection, Budget Constraints\.

## 1Introduction

Mobile crowdsensing \(MC\) has emerged as a powerful paradigm for collecting data from widespread locations via everyday mobile devices\[[25](https://arxiv.org/html/2607.13546#bib.bib63)\]\. By leveraging the sensors and connectivity of ubiquitous smartphones, MC enables large\-scale sensing applications that would be infeasible for any single user\. For instance, MC platforms have been used to monitor city traffic, measure urban noise and pollution levels, and map wireless network coverage\. In a typical MC system, a central platform recruits a crowd of smartphone users \(workers\) to perform sensing tasks, aggregating their contributions to build rich spatiotemporal datasets\. The success of such applications hinges on effective worker recruitment, selecting the right participants to maximize data quality under practical constraints like limited budgets and heterogeneous device capabilities\.

Despite extensive research on MC recruitment and task allocation algorithms, most prior models assume that each worker’s sensing performance is fixed or stationary over time\. In reality, however, participant performance can evolve as they gain experience\. Just as crowdworkers on online platforms learn and improve with each task completed, MC participants may become more proficient at sensing tasks through repeated participation\. Empirical evidence from crowdsourcing supports this learning effect: for example, the accuracy of Topcoder developers\[[39](https://arxiv.org/html/2607.13546#bib.bib58)\]was observed to increase significantly with the number of tasks completed before eventually stabilizing at a high level\. We model this behavior by assuming that each worker’s expected reward follows an*increasing\-then\-converging*trajectory, a structure that captures both early\-stage learning and eventual performance saturation\. This suggests a crucial gap in current crowdsensing frameworks: worker improvement dynamics are largely ignored\. Failing to account for learning means existing approaches may undervalue novice workers who could become top\-performers with more experience, or overcommit to individuals who have already reached their performance plateau\.

While prior work has leveraged multi\-armed bandit \(MAB\) frameworks for modeling worker selection in MC systems\[[9](https://arxiv.org/html/2607.13546#bib.bib86),[34](https://arxiv.org/html/2607.13546#bib.bib71),[42](https://arxiv.org/html/2607.13546#bib.bib72)\], these formulations typically assume that each worker’s quality is stationary and represented by a fixed, unknown reward parameter\. In this work, we consider a mobile crowdsensing system with a small, fixed pool of participants in which each task is assigned to one worker, a setting motivated by short\-term campaigns built from location\-specific microtasks, such as street\-issue verification \(e\.g\., potholes or broken street lights\), in\-store retail audits \(e\.g\., price checks or on\-shelf availability checks\), and localized environmental measurements \(e\.g\., noise or air\-quality readings\), where the platform naturally operates over a bounded set of currently available participants and each assignment corresponds to a single report, visit, or measurement\[[22](https://arxiv.org/html/2607.13546#bib.bib81),[8](https://arxiv.org/html/2607.13546#bib.bib74),[26](https://arxiv.org/html/2607.13546#bib.bib75),[37](https://arxiv.org/html/2607.13546#bib.bib84),[9](https://arxiv.org/html/2607.13546#bib.bib86)\]\. In each round, the platform assigns the sensing task to a worker, observes the obtained sensing quality and the incurred cost, and then updates its recruitment policy for subsequent rounds; the process terminates when the cumulative cost exhausts the total budget\. Under this sequential decision process, the platform must balance exploration and exploitation since both workers’ sensing quality and recruitment cost are initially unknown\. The budget constraint further amplifies the cost of exploration because every trial consumes limited resources\. Moreover, workers’ sensing quality is non\-stationary and personalized: a worker may improve with experience during early participation and then gradually stabilize, while different workers can exhibit different learning speeds and plateau levels\. Finally, we also consider unknown costs in a realistic manner\. In practice, a worker’s effective sensing cost depends on its instantaneous device and context state, such as battery level, network conditions, and surrounding environment; thus, even if the platform adopts a pre\-specified cost function, the worker\-specific cost parameter is not known a priori and is estimated by the worker in each round based on these factors, making the platform learn the expected cost online\.

In this paper, we formulate the online worker selection problem as a structured bandit setting in which each worker’s expected sensing quality evolves according to an unknown, increasing\-then\-converging function, and expected cost incurs a fixed but unknown cost\. The goal is to allocate a finite task budget across workers to maximize the cumulative qualities obtained\. This setting requires not only resolving uncertainty and learning heterogeneous costs, but also modeling each worker’s full learning trajectory, including their initial skill level, rate of improvement, and convergence point\. To address this, we develop a cost\-sensitive extension of the*Time\-Increasing Upper Confidence Bound*\(TI\-UCB\) algorithm, called CATI\-UCB, which is designed to operate under structured reward dynamics and budget constraints\. CATI\-UCB combines three core components: it uses a reward\-cost ratio to guide exploration and exploitation; it fits an online linear model to estimate each worker’s early learning behavior; and it employs change\-point detection to identify when learning saturates\. These components work together to adaptively prioritize workers based on their long\-term efficiency rather than short\-term reward\. We prove that CATI\-UCB achieves sublinear regret relative to the optimal policy, and we empirically demonstrate that it significantly outperforms existing baselines that ignore temporal reward structure or assume stationarity\.

In summary, our main contributions are as follows:

- •We formulate a new online worker selection problem in crowdsourcing where each worker’s expected reward follows an unknown, increasing\-then\-converging function, and expected cost incurs a fixed but unknown cost\. This setting captures realistic worker learning dynamics and introduces new algorithmic challenges beyond standard stationary bandit models\.
- •We propose CATI\-UCB, a structured bandit algorithm that jointly addresses uncertainty, cost\-awareness, and non\-stationary reward dynamics\. The algorithm estimates each worker’s learning curve via online linear regression, detects performance saturation through change\-point detection, and selects workers based on an upper confidence bound of the reward\-to\-cost ratio\.
- •We prove that CATI\-UCB achieves logarithmic regret compared with the optimal policy under non\-stationary rewards\.
- •We evaluate CATI\-UCB through extensive synthetic experiments that model realistic worker learning patterns\. The results show that CATI\-UCB consistently outperforms baseline methods\.

## 2Related work

Mobile Crowdsensing and worker recruitment:Mobile crowdsensing \(MC\) studies how to recruit mobile users to perform sensing tasks under uncertainty, and a large body of work has formulated worker recruitment as an online learning problem using multi\-armed bandits or related frameworks to handle unknown worker quality, limited budget, and incentive constraints\[[13](https://arxiv.org/html/2607.13546#bib.bib68),[12](https://arxiv.org/html/2607.13546#bib.bib70),[41](https://arxiv.org/html/2607.13546#bib.bib69),[34](https://arxiv.org/html/2607.13546#bib.bib71),[42](https://arxiv.org/html/2607.13546#bib.bib72),[35](https://arxiv.org/html/2607.13546#bib.bib87),[28](https://arxiv.org/html/2607.13546#bib.bib92),[33](https://arxiv.org/html/2607.13546#bib.bib91)\]\. Recent studies have further broadened the scope of MC recruitment, for example by addressing insufficient participation through social\-network\-assisted recruitment\[[38](https://arxiv.org/html/2607.13546#bib.bib85)\]or by studying dynamic online dispatch under time\-varying resource\-quality tradeoffs\[[9](https://arxiv.org/html/2607.13546#bib.bib86)\]\. This line of work typically studies sequential server\-assigned recruitment under newly observed feedback, which is also the setting considered in this paper\. However, most existing learning\-based MC formulations either assume stationary worker quality or focus on other uncertainties such as truth discovery, trust/reputation, requester\-side uncertainty, or incentive design\[[13](https://arxiv.org/html/2607.13546#bib.bib68),[12](https://arxiv.org/html/2607.13546#bib.bib70),[35](https://arxiv.org/html/2607.13546#bib.bib87),[28](https://arxiv.org/html/2607.13546#bib.bib92),[33](https://arxiv.org/html/2607.13546#bib.bib91)\]\. In contrast, our work focuses on a different source of non\-stationarity: a worker’s expected sensing reward improves with repeated participation and eventually saturates\. Motivated by empirical evidence on skill improvement\[[39](https://arxiv.org/html/2607.13546#bib.bib58)\], we model each worker’s expected reward as an*increasing\-then\-converging*function of participation count, while simultaneously learning worker costs online under a finite budget\.

Non\-stationary Bandits:The increasing\-then\-converging reward trend studied in our work is closely related to the non\-stationary bandit literature, which addresses changing reward distributions over time\[[18](https://arxiv.org/html/2607.13546#bib.bib93),[19](https://arxiv.org/html/2607.13546#bib.bib95)\]\. Existing approaches typically assume either piecewise\-stationary\[[14](https://arxiv.org/html/2607.13546#bib.bib48),[7](https://arxiv.org/html/2607.13546#bib.bib50),[6](https://arxiv.org/html/2607.13546#bib.bib52)\]or smoothly\-varying\[[6](https://arxiv.org/html/2607.13546#bib.bib52),[30](https://arxiv.org/html/2607.13546#bib.bib53)\]rewards, and adapt through sliding windows, change\-point detection, or discounting techniques\. More recently, rested bandits\[[36](https://arxiv.org/html/2607.13546#bib.bib12),[31](https://arxiv.org/html/2607.13546#bib.bib8),[21](https://arxiv.org/html/2607.13546#bib.bib7)\]have been proposed, where rewards depend on how often an arm is pulled, capturing trends like skill acquisition\. Some works model monotonic or increasing reward patterns\[[15](https://arxiv.org/html/2607.13546#bib.bib11),[27](https://arxiv.org/html/2607.13546#bib.bib15)\], but most of these methods assume simplified or deterministic trends and do not explicitly model the increasing\-then\-converging pattern observed in skill\-based tasks\. The recent work\[[40](https://arxiv.org/html/2607.13546#bib.bib4)\]considers an increasing\-then\-converging structure similar to ours, but focuses on model selection and does not address budget constraints\. In contrast, our work integrates the increasing\-then\-converging structure with cost\-sensitive online learning under a finite budget, enabling more efficient resource allocation\.

Bandits with Knapsack:“Bandits with knapsack” \(BwK\) extends the multi\-armed bandit problem to settings with limited resources, aiming to maximize total rewards under a budget constraint\[[4](https://arxiv.org/html/2607.13546#bib.bib39),[5](https://arxiv.org/html/2607.13546#bib.bib40),[17](https://arxiv.org/html/2607.13546#bib.bib94)\]\. Applications include dynamic pricing\[[3](https://arxiv.org/html/2607.13546#bib.bib41)\], procurement\[[32](https://arxiv.org/html/2607.13546#bib.bib42)\], and pay\-per\-click ad allocation\[[10](https://arxiv.org/html/2607.13546#bib.bib43)\]\. BwK research can be broadly categorized into stochastic and adversarial settings\. In the stochastic case, where each arm follows a fixed but unknown distribution\[[4](https://arxiv.org/html/2607.13546#bib.bib39),[2](https://arxiv.org/html/2607.13546#bib.bib44),[1](https://arxiv.org/html/2607.13546#bib.bib45),[23](https://arxiv.org/html/2607.13546#bib.bib13)\], optimal regret bounds have been achieved by successive elimination\[[4](https://arxiv.org/html/2607.13546#bib.bib39)\], UcbBwK\[[2](https://arxiv.org/html/2607.13546#bib.bib44)\], and primal\-dual algorithms\[[23](https://arxiv.org/html/2607.13546#bib.bib13)\]\. In the adversarial case, rewards can be manipulated by an adversary\[[20](https://arxiv.org/html/2607.13546#bib.bib46),[29](https://arxiv.org/html/2607.13546#bib.bib47)\]\. Recent work also explores non\-stationary BwK\[[24](https://arxiv.org/html/2607.13546#bib.bib21)\]\. However, these methods generally do not account for the increasing\-then\-converging patterns observed in skill\-based tasks, leading to suboptimal performance\. In contrast, our CATI\-UCB explicitly models this trend and adaptively detects convergence points under budget constraint, outperforming prior approaches both theoretically and empirically in online worker recruitment\.

## 3System Model

We consider a mobile crowdsensing \(MC\) setting in which a requester launches a short\-term sensing campaign with a fixed budget, and a platform is responsible for coordinating task assignments among a fixed pool ofKKcommitted and currently available mobile workers, as illustrated in Fig\.[1](https://arxiv.org/html/2607.13546#S3.F1)\. The campaign proceeds in rounds\. In each round, the platform selects one worker to execute one sensing job \(e\.g\., capturing traffic photos at an intersection, measuring ambient noise, or collecting WiFi fingerprints\), based on the feedback accumulated from previous assignments\. After the selected worker completes the sensing job and uploads the sensed data, the platform evaluates the outcome and observes two signals: a reward that reflects the worker’s current sensing performance \(e\.g\., data validity, clarity, timeliness, or compliance with task requirements\), and the incurred cost\. In our primary interpretation, this cost represents the realized execution delay \(or task completion time\), normalized to\[0,1\]\[0,1\]; more generally, it can also absorb other execution\-related burdens such as network usage through a scalar cost definition\. The platform then updates its internal selection strategy and proceeds to the next round\. This interactive process continues until the total budget is exhausted\. Under this interpretation, the budget can be viewed as a deadline\-like cumulative delay budget, and the platform’s objective is to allocate the limited budget across workers over time so as to maximize the cumulative sensing utility before this budget is consumed\. We do not explicitly model worker refusals, arrivals, or departures in this paper; instead, we focus on a fixed worker pool so as to isolate the online learning problem induced by evolving worker performance and unknown costs\. This setup captures practical scenarios such as sustained urban monitoring, iterative participant onboarding and calibration, and continuous improvement of sensing quality on real\-world MC platforms\.

![Refer to caption](https://arxiv.org/html/2607.13546v1/x1.png)

Figure 1:Illustration of the main procedures in the mobile crowdsensing platformOnline Worker Recruitment:The online worker recruitment involves a finite set of candidate workers denoted by\{1,2,…,K\}\\\{1,2,\\dots,K\\\}, where workeriidenotes theii\-th participant amongKKworkers\. Time is slotted into rounds indexed byt=1,2,…t=1,2,\\dots\. In each roundtt, the platform assigns the sensing job to exactly one workerAt∈\[K\]A\_\{t\}\\in\[K\]based on the feedback accumulated from previous assignments \(i\.e\., observed sensing quality and incurred cost\), and then updates its selection strategy for subsequent rounds\.

Reward & Cost Feedback:After workerAtA\_\{t\}completes the sensing job and uploads the sensed data, the platform evaluates the returned data using a quality assessment pipeline \(e\.g\., completeness, timeliness, and cross\-validation with redundant measurements when available\), and obtains a normalized quality scorerAt,t∈\[0,1\]r\_\{A\_\{t\},t\}\\in\[0,1\]as the reward\. Meanwhile, the platform observes the realized costYAt,t∈\[0,1\]Y\_\{A\_\{t\},t\}\\in\[0,1\]associated with recruiting workerAtA\_\{t\}, which primarily represents realized execution delay, and more generally may also absorb other execution\-related burdens such as bandwidth consumption through a scalar cost definition\.

We model\(ri,t,Yi,t\)\(r\_\{i,t\},Y\_\{i,t\}\)as stochastic feedback\. Specifically, conditional on workerii’s experience level, the reward observations are independent draws from an unknown distribution with a mean that evolves with experience\. LetNi,t=∑s=1t𝟏​\{As=i\}N\_\{i,t\}=\\sum\_\{s=1\}^\{t\}\\mathbf\{1\}\\\{A\_\{s\}=i\\\}denote the number of times workeriihas been selected up to the end of roundtt\. We write the expected reward asμi​\(t\)=μ~i​\(Ni,t\)\\mu\_\{i\}\(t\)=\\tilde\{\\mu\}\_\{i\}\(N\_\{i,t\}\), where the unknown functionμ~i​\(n\)\\tilde\{\\mu\}\_\{i\}\(n\)is nondecreasing innnand converges to a plateau, capturing the learning\-by\-doing effect commonly observed in crowd work settings\[[39](https://arxiv.org/html/2607.13546#bib.bib58)\]\.

For the cost, we assume that workeriihas an unknown, worker\-specific expected costcic\_\{i\}, and the observed costs\{Yi,t\}\\\{Y\_\{i,t\}\\\}are independent draws from an unknown distribution with meancic\_\{i\}and support in\[0,1\]\[0,1\]\. This captures practical MC deployments where the realized sensing cost depends on the worker’s instantaneous device/context state \(e\.g\., battery level, network condition, and environment factors\)\. As a result, even if the platform specifies a cost model, the effective cost parameter is not known a priori and must be learned online from observations\.

We denote byνi\\nu\_\{i\}the*convergence point*of workerii, representing the number of tasks needed for the worker’s performance to stabilize, and byμi∗\\mu\_\{i\}^\{\*\}the corresponding*expected converged reward*, equal toμ~i​\(νi\)\\tilde\{\\mu\}\_\{i\}\(\\nu\_\{i\}\)\. The value ofνi\\nu\_\{i\}varies across workers, reflecting different learning rates\. The shape of the reward trajectoryμ~i​\(n\)\\tilde\{\\mu\}\_\{i\}\(n\)may vary in form and can be approximated using different function classes\. In our work, we adopt a*piece\-wise linear*approximation ofμ~i​\(n\)\\tilde\{\\mu\}\_\{i\}\(n\)to preserve the structure of increasing\-then\-converging reward while enabling efficient analysis and algorithmic design, which is shown as Fig 2\. Specifically, we assume that each worker’s reward initially increases linearly with the number of tasks, then stabilizes atμi∗\\mu\_\{i\}^\{\*\}once learning saturates within the budget\. This approximation is characterized by three parameters:\(1\) the initial reward level \(reflecting prior ability\),μ~i​\(0\)\\tilde\{\\mu\}\_\{i\}\(0\), \(2\) the convergence pointνi\\nu\_\{i\}\(when learning plateaus\), and \(3\) the learning rate \(how quickly performance improves\)μi∗−μ~i​\(0\)νi\\frac\{\\mu\_\{i\}^\{\*\}\-\\tilde\{\\mu\}\_\{i\}\(0\)\}\{\\nu\_\{i\}\}\. This model captures key trends in worker learning behavior\. Furthermore, our experiments show that the algorithm performs well even when the true reward follows other forms \(e\.g\.,negative exponential\), outperforming baselines across settings\.

![Refer to caption](https://arxiv.org/html/2607.13546v1/x2.png)Figure 2:Piece\-wise Linear FunctionBudget Constraint:After observing the reward cost pairs\(rAt,t,YAt,t\)\{\(r\_\{A\_\{t\},t\},Y\_\{A\_\{t\},t\}\)\}, the platform then correspondingly updates its selection policy for the next round of worker selection and the total budget is decreased by the cost produced by the selected worker\. DenoteBBas the total budget, then the stopping timeT𝒜,B\{T\_\{\\mathcal\{A\},B\}\}for the selecting algorithm𝒜\\mathcal\{A\}can be characterized by:∑t=1T𝒜,B−1YAt,t≤B<∑t=1T𝒜,BYAt,t\.\\sum\_\{t=1\}^\{T\_\{\\mathcal\{A\},B\}\-1\}Y\_\{A\_\{t\},t\}\\leq B<\\sum\_\{t=1\}^\{T\_\{\\mathcal\{A\},B\}\}Y\_\{A\_\{t\},t\}\.

Objective:The goal of the platform is to efficiently select the most suitable worker being selected, i\.e\., yielding the highest cumulative reward until the budget is exhausted\. Specifically, let the total reward accumulated by the selection algorithm𝒜\\mathcal\{A\}up to timeT𝒜,BT\_\{\\mathcal\{A\},B\}be denoted asR𝒜,B=∑t=1T𝒜,BrAt,tR\_\{\\mathcal\{A\},B\}=\\sum\_\{t=1\}^\{T\_\{\\mathcal\{A\},B\}\}r\_\{A\_\{t\},t\}, the platform’s goal can be formulated as follows:

max⁡R𝒜,B=∑t=1T𝒜,BrAt,ts\.t\.∑t=1T𝒜,B−1YAt,t≤B<∑t=1T𝒜,BYAt,t\.\\displaystyle\\max R\_\{\\mathcal\{A\},B\}=\\sum\_\{t=1\}^\{T\_\{\\mathcal\{A\},B\}\}r\_\{A\_\{t\},t\}\\quad s\.t\.\\sum\_\{t=1\}^\{T\_\{\\mathcal\{A\},B\}\-1\}Y\_\{A\_\{t\},t\}\\leq B<\\sum\_\{t=1\}^\{T\_\{\\mathcal\{A\},B\}\}Y\_\{A\_\{t\},t\}\.Let\{qi,B\}i=1K\\\{q\_\{i,B\}\\\}\_\{i=1\}^\{K\}be a valid worker\-selection allocation under budgetBBsuch that∑i=1Kci​qi,B≤B\\sum\_\{i=1\}^\{K\}c\_\{i\}q\_\{i,B\}\\leq Bwhereqi,Bq\_\{i,B\}is the number of times workeriiis selected\. Then the total reward for this allocation isR=∑i=1K∑t=1qi,Bμi​\(t\)R=\\sum\_\{i=1\}^\{K\}\\sum\_\{t=1\}^\{q\_\{i,B\}\}\\mu\_\{i\}\(t\)\. Therefore, the optimal expected rewardR∗​\(B\)R^\{\*\}\(B\)under known reward and cost functions is the solution to the following combinatorial optimization problem:

R∗​\(B\):=max\{qi,B≥0\}i=1K⁡\{∑i=1K∑n=1qi,Bμ~i​\(n\)\|∑i=1Kci​qi,B≤B\}\.R^\{\*\}\(B\):=\\max\_\{\\\{q\_\{i,B\}\\geq 0\\\}\_\{i=1\}^\{K\}\}\\left\\\{\\sum\_\{i=1\}^\{K\}\\sum\_\{n=1\}^\{q\_\{i,B\}\}\\tilde\{\\mu\}\_\{i\}\(n\)\\;\\middle\|\\;\\sum\_\{i=1\}^\{K\}c\_\{i\}q\_\{i,B\}\\leq B\\right\\\}\.\(1\)This formulation characterizes the best achievable cumulative reward when full knowledge of reward trajectories and costs is available, and switching between workers is allowed\. We use expected regret to evaluate the performance of the algorithm𝒜\\mathcal\{A\}, which is defined below\.

Regret​\(𝒜,B\)\\displaystyle\\textsc\{Regret\}\(\\mathcal\{A\},B\)=R∗​\(B\)−𝔼​\[R𝒜,B\]\\displaystyle=R^\{\*\}\(B\)\-\\mathbb\{E\}\[R\_\{\\mathcal\{A\},B\}\]=R∗−∑i=1K𝔼​\[∑s=1Ni,T𝒜,Bμi,s\],\\displaystyle=R^\{\*\}\-\\sum\_\{i=1\}^\{K\}\\mathbb\{E\}\[\\sum\_\{s=1\}^\{N\_\{i,T\_\{\\mathcal\{A\},B\}\}\}\\mu\_\{i,s\}\],\(2\)whereNi,T𝒜,BN\_\{i,T\_\{\\mathcal\{A\},B\}\}is the actual number of times that workeriihas been selected by the platform till ending time stepT𝒜,BT\_\{\\mathcal\{A\},B\},μi,s\\mu\_\{i,s\}denotes the expected reward of workeriiat itsss\-th selection/pull, and the𝔼\\mathbb\{E\}is taken over the randomness of rewards, costs, and the selecting algorithm\.

In our setting, the values ofμ~i​\(n\)\\tilde\{\\mu\}\_\{i\}\(n\),νi\\nu\_\{i\},μi∗\\mu\_\{i\}^\{\*\}, and the costcic\_\{i\}of selecting workeriiare unknown and must be learned online\. This departs from classical bandit models in crowdsourcing, which assume stationary rewards and represent each worker with a single scalar\. Such simplifications overlook the non\-stationary, structured reward evolution of real workers, whose performance improves then stabilizes\. Capturing this increasing\-then\-converging behavior poses new challenges: the platform must identify high\-performing workers, anticipate their learning, detect convergence, and account for heterogeneous costs under a finite budget\. Existing algorithms that assume stationarity or ignore this non\-stationary trend are thus inadequate, motivating a structured, cost\-sensitive, non\-stationary framework\.

Remark:We focus on tasks from the same category/type in this work, but our framework can be extended to heterogeneous tasks by incorporating task types/features \(e\.g\., letting reward/cost depend on the current task context\)\. For a finite number of task types, one can maintain separate learning\-curve/cost estimates per \(worker, type\) and apply the same cost\-aware UCB selection rule conditioned on the task type\.

Before we dive into the learning algorithm development, let us have a better understanding of the optimal offline policy\.

###### Lemma 1\(Asymptotic structure of the offline optimum\)\.

Let

ρ⋆:=maxi∈\[K\]⁡μi⋆ci,i†∈arg⁡maxi∈\[K\]⁡μi⋆ci\.\\rho^\{\\star\}:=\\max\_\{i\\in\[K\]\}\\frac\{\\mu\_\{i\}^\{\\star\}\}\{c\_\{i\}\},\\qquad i^\{\\dagger\}\\in\\arg\\max\_\{i\\in\[K\]\}\\frac\{\\mu\_\{i\}^\{\\star\}\}\{c\_\{i\}\}\.Then there exists a constantC0\>0C\_\{0\}\>0, independent of the budgetBB, such that

ρ⋆​B−C0≤R⋆​\(B\)≤ρ⋆​B,∀B≥0\.\\rho^\{\\star\}B\-C\_\{0\}\\leq R^\{\\star\}\(B\)\\leq\\rho^\{\\star\}B,\\qquad\\forall B\\geq 0\.In particular,R⋆​\(B\)=ρ⋆​B\+O​\(1\)\.R^\{\\star\}\(B\)=\\rho^\{\\star\}B\+O\(1\)\.Moreover, the single\-worker policy that allocates all available budget to workeri†i^\{\\dagger\}is optimal up to an additive constant independent ofBB\.

###### Proof\.

Recall that

R⋆​\(B\)=max\{qi∈ℤ≥0\}i=1K⁡\{∑i=1K∑n=1qiμ~i​\(n\)\|∑i=1Kci​qi≤B\}\.R^\{\\star\}\(B\)=\\max\_\{\\\{q\_\{i\}\\in\\mathbb\{Z\}\_\{\\geq 0\}\\\}\_\{i=1\}^\{K\}\}\\left\\\{\\sum\_\{i=1\}^\{K\}\\sum\_\{n=1\}^\{q\_\{i\}\}\\tilde\{\\mu\}\_\{i\}\(n\)\\,\\middle\|\\,\\sum\_\{i=1\}^\{K\}c\_\{i\}q\_\{i\}\\leq B\\right\\\}\.We first prove the upper bound\. For any feasible allocation\{qi\}i=1K\\\{q\_\{i\}\\\}\_\{i=1\}^\{K\}, sinceμ~i​\(n\)≤μi⋆\\tilde\{\\mu\}\_\{i\}\(n\)\\leq\\mu\_\{i\}^\{\\star\}for alliiandnn, we have

∑i=1K∑n=1qiμ~i​\(n\)≤∑i=1Kμi⋆​qi=∑i=1Kμi⋆ci​ci​qi≤ρ⋆​∑i=1Kci​qi≤ρ⋆​B\.\\sum\_\{i=1\}^\{K\}\\sum\_\{n=1\}^\{q\_\{i\}\}\\tilde\{\\mu\}\_\{i\}\(n\)\\leq\\sum\_\{i=1\}^\{K\}\\mu\_\{i\}^\{\\star\}q\_\{i\}=\\sum\_\{i=1\}^\{K\}\\frac\{\\mu\_\{i\}^\{\\star\}\}\{c\_\{i\}\}c\_\{i\}q\_\{i\}\\leq\\rho^\{\\star\}\\sum\_\{i=1\}^\{K\}c\_\{i\}q\_\{i\}\\leq\\rho^\{\\star\}B\.Taking the maximum over all feasible allocations yieldsR⋆​\(B\)≤ρ⋆​B\.R^\{\\star\}\(B\)\\leq\\rho^\{\\star\}B\.Next, we prove the lower bound by considering the policy that allocates the budget only to workeri†i^\{\\dagger\}\. Letq†:=⌊Bci†⌋\.q^\{\\dagger\}:=\\left\\lfloor\\frac\{B\}\{c\_\{i^\{\\dagger\}\}\}\\right\\rfloor\.This is feasible sinceci†​q†≤Bc\_\{i^\{\\dagger\}\}q^\{\\dagger\}\\leq B\. Under the piecewise linear increasing\-then\-converging model, workeri†i^\{\\dagger\}reaches the plateauμi†⋆\\mu\_\{i^\{\\dagger\}\}^\{\\star\}afterνi†\\nu\_\{i^\{\\dagger\}\}selections, and hence

μ~i†​\(n\)=μi†⋆,∀n≥νi†\.\\tilde\{\\mu\}\_\{i^\{\\dagger\}\}\(n\)=\\mu\_\{i^\{\\dagger\}\}^\{\\star\},\\qquad\\forall n\\geq\\nu\_\{i^\{\\dagger\}\}\.Therefore, we have∑n=1q†μ~i†​\(n\)≥μi†⋆​\(q†−νi†\)\+\.\\sum\_\{n=1\}^\{q^\{\\dagger\}\}\\tilde\{\\mu\}\_\{i^\{\\dagger\}\}\(n\)\\geq\\mu\_\{i^\{\\dagger\}\}^\{\\star\}\(q^\{\\dagger\}\-\\nu\_\{i^\{\\dagger\}\}\)\_\{\+\}\.Usingq†≥Bci†−1q^\{\\dagger\}\\geq\\frac\{B\}\{c\_\{i^\{\\dagger\}\}\}\-1, we obtain

∑n=1q†μ~i†​\(n\)≥μi†⋆​\(Bci†−1−νi†\)=ρ⋆​B−μi†⋆​\(1\+νi†\)\.\\sum\_\{n=1\}^\{q^\{\\dagger\}\}\\tilde\{\\mu\}\_\{i^\{\\dagger\}\}\(n\)\\geq\\mu\_\{i^\{\\dagger\}\}^\{\\star\}\\left\(\\frac\{B\}\{c\_\{i^\{\\dagger\}\}\}\-1\-\\nu\_\{i^\{\\dagger\}\}\\right\)=\\rho^\{\\star\}B\-\\mu\_\{i^\{\\dagger\}\}^\{\\star\}\(1\+\\nu\_\{i^\{\\dagger\}\}\)\.Since this reward is achievable by a feasible policy, it follows thatR⋆​\(B\)≥ρ⋆​B−μi†⋆​\(1\+νi†\)\.R^\{\\star\}\(B\)\\geq\\rho^\{\\star\}B\-\\mu\_\{i^\{\\dagger\}\}^\{\\star\}\(1\+\\nu\_\{i^\{\\dagger\}\}\)\.

Thus, by settingC0:=μi†⋆​\(1\+νi†\),C\_\{0\}:=\\mu\_\{i^\{\\dagger\}\}^\{\\star\}\(1\+\\nu\_\{i^\{\\dagger\}\}\),we conclude that

ρ⋆​B−C0≤R⋆​\(B\)≤ρ⋆​B,∀B≥0\.\\rho^\{\\star\}B\-C\_\{0\}\\leq R^\{\\star\}\(B\)\\leq\\rho^\{\\star\}B,\\qquad\\forall B\\geq 0\.Hence,

R⋆​\(B\)=ρ⋆​B\+O​\(1\)\.R^\{\\star\}\(B\)=\\rho^\{\\star\}B\+O\(1\)\.The last statement follows immediately from the lower\-bound construction above\. ∎

Remark:Lemma 1 provides a uniform finite\-budget characterization of the offline optimum and does not require all workers to reach their plateaus before the budget is exhausted\. The upper bound only relies onμ~i​\(n\)≤μi⋆\\tilde\{\\mu\}\_\{i\}\(n\)\\leq\\mu\_\{i\}^\{\\star\}for alliiandnn\. For the lower\-bound construction, letq†=⌊Bci†⌋\.q^\{\\dagger\}=\\left\\lfloor\\frac\{B\}\{c\_\{i^\{\\dagger\}\}\}\\right\\rfloor\.Ifq†<νi†q^\{\\dagger\}<\\nu\_\{i^\{\\dagger\}\}, then\(q†−νi†\)\+=0\(q^\{\\dagger\}\-\\nu\_\{i^\{\\dagger\}\}\)\_\{\+\}=0, and hence the lower bound remains valid, although it may be loose\. Thus, no assumption of the formνi≪T𝒜,B\\nu\_\{i\}\\ll T\_\{\\mathcal\{A\},B\}is required\.

The additive constantC0C\_\{0\}accounts for the finite reward deficit incurred during the pre\-convergence phase\. Consequently,R⋆​\(B\)=ρ⋆​B\+O​\(1\),ρ⋆=maxi∈\[K\]⁡μi⋆ci\.R^\{\\star\}\(B\)=\\rho^\{\\star\}B\+O\(1\),\\qquad\\rho^\{\\star\}=\\max\_\{i\\in\[K\]\}\\frac\{\\mu\_\{i\}^\{\\star\}\}\{c\_\{i\}\}\.Therefore, allocating the budget to any workeri†∈arg⁡maxi∈\[K\]⁡μi⋆cii^\{\\dagger\}\\in\\arg\\max\_\{i\\in\[K\]\}\\frac\{\\mu\_\{i\}^\{\\star\}\}\{c\_\{i\}\}is asymptotically optimal up to an additive constant\. This large\-budget interpretation is a consequence of Lemma 1 rather than an additional assumption required by the lemma\.

## 4Algorithm Design

In Section[4\.2](https://arxiv.org/html/2607.13546#S4.SS2), we propose the Cost\-aware Time\-increasing UCB \(CATI\-UCB\) algorithm for the online worker recruitment problem formulated in Section[3](https://arxiv.org/html/2607.13546#S3)\.

### 4\.1Overview of the CATI\-UCB Algorithm

To address the challenges of unknown, non\-stationary rewards and heterogeneous costs, we propose the CATI\-UCB \(Algorithm[1](https://arxiv.org/html/2607.13546#alg1)\)\. Unlike standard bandit approaches that model each worker with a fixed reward parameter, our setting explicitly accounts for each worker’s initial skill, learning rate, and convergence pointνi\\nu\_\{i\}, defining the increasing\-then\-converging reward trajectoryμ~i​\(n\)\\tilde\{\\mu\}\_\{i\}\(n\)\. Combined with the unknown costcic\_\{i\}, these attributes determine each worker’s long\-term efficiency under budget constraints\. CATI\-UCB leverages this structure through three components: \(i\) modeling the increasing reward trend with online piecewise linear regression to predict short\-term improvement; \(ii\) detecting when learning stabilizes via change\-point detection; and \(iii\) selecting workers based on cost\-aware upper\-confidence estimates of their reward\-to\-cost ratio\. These components interact in a loop to dynamically balance exploration and exploitation until the budget is exhausted, prioritizing long\-term over short\-term gains\.

### 4\.2CATI\-UCB Algorithm

At the initial phase of the CATI\-UCB, each worker is selected once to get the initial estimation value of the reward and cost\.

#### 4\.2\.1Increasing Reward Prediction

To estimate a worker’s initial skill and learning rate, CATI\-UCB models the early\-stage reward trajectory using a simple linear approximation:

μ¯i,Ni,t=a^i,Ni,t⋅Ni,t\+b^i,Ni,t\\bar\{\\mu\}\_\{i,N\_\{i,t\}\}=\\hat\{a\}\_\{i,N\_\{i,t\}\}\\cdot N\_\{i,t\}\+\\hat\{b\}\_\{i,N\_\{i,t\}\}\(3\)whereNi,tN\_\{i,t\}is the number of times workeriihas been selected up to timett, and the parametersa^i,Ni,t\\hat\{a\}\_\{i,N\_\{i,t\}\}andb^i,Ni,t\\hat\{b\}\_\{i,N\_\{i,t\}\}are updated via least squares regression over historical reward observations\. Here,b^i,Ni,t\\hat\{b\}\_\{i,N\_\{i,t\}\}captures the estimated initial reward \(reflecting the worker’s prior ability\), whilea^i,Ni,t\\hat\{a\}\_\{i,N\_\{i,t\}\}estimates the rate of improvement over time \(reflecting the worker’s learning rate\)\.

This predictive model enables the algorithm to anticipate future rewards based on early performance, allowing more informed exploration decisions\. When a worker is detected to have converged \(as indicated in line 11 of Algorithm 1\), the model fit is reset by settingNi,t=1N\_\{i,t\}=1and restarting the collection of data points used to estimatea^i,Ni,t\\hat\{a\}\_\{i,N\_\{i,t\}\}andb^i,Ni,t\\hat\{b\}\_\{i,N\_\{i,t\}\}\. This ensures that the linear model continues to reflect only the pre\-convergence trend, maintaining an accurate and adaptive estimate of each worker’s learning dynamics\.

#### 4\.2\.2Worker Selection Design

We rank workeriiby the ratio of the upper confidence bound \(UCB\) of its estimated reward to the lower confidence bound \(LCB\) of its estimated cost:μ^i,tc^i,t\\frac\{\\hat\{\\mu\}\_\{i,t\}\}\{\\hat\{c\}\_\{i,t\}\}, following the Optimism in the Face of Uncertainty \(OFU\) principle\. Although UCB is a biased estimator, it converges asymptotically\. At steptt, the confidence padding term isϵi,t=16​2​ln⁡\(1/δ\)Ni,t\\epsilon\_\{i,t\}=16\\sqrt\{\\frac\{2\\ln\(1/\\delta\)\}\{N\_\{i,t\}\}\}, yieldingμ^i,t=μ¯i,t\+ϵi,t\\hat\{\\mu\}\_\{i,t\}=\\bar\{\\mu\}\_\{i,t\}\+\\epsilon\_\{i,t\}andc^i,t=c¯i,t−ϵi,t\\hat\{c\}\_\{i,t\}=\\bar\{c\}\_\{i,t\}\-\\epsilon\_\{i,t\}\. Here,μ¯i,t\\bar\{\\mu\}\_\{i,t\}is computed via Eq\.\([3](https://arxiv.org/html/2607.13546#S4.E3)\), andc¯i,t\\bar\{c\}\_\{i,t\}is the average cost\.

With the prediction of the increasing reward, CATI\-UCB seeks to balance exploration and exploitation by adding an uncertainty term to the predicted reward of each worker as Line 5 of Algorithm[1](https://arxiv.org/html/2607.13546#alg1)\. The algorithm then selects the worker with the maximum value ofμ^i,tc^i,t\\frac\{\\hat\{\\mu\}\_\{i,t\}\}\{\\hat\{c\}\_\{i,t\}\}to play, receives a rewardrAt,tr\_\{A\_\{t\},t\}and costYAt,tY\_\{A\_\{t\},t\}and update the observation records of workeriias described in Line 6\-8 of Algorithm[1](https://arxiv.org/html/2607.13546#alg1)\.

The concentration level of the reward’s uncertainty term follows Eq\. \([4](https://arxiv.org/html/2607.13546#S4.E4)\)\. To simplify the notation, we useμ^i,Ni,t\\hat\{\\mu\}\_\{i,N\_\{i,t\}\}asμ^i​\(t\)\\hat\{\\mu\}\_\{i\}\(t\), andμ¯i,Ni,t\\bar\{\\mu\}\_\{i,N\_\{i,t\}\}asμ¯i​\(t\)\\bar\{\\mu\}\_\{i\}\(t\)in the rest of the paper\. Then we adopt the following confidence bound:

μ^i\(t−1\)=\{∞,if​Ni,t−1=0μ¯i​\(t−1\)\+16​2​ln⁡\(1/δ\)Ni,t−1,otherwise,\\hat\{\\mu\}\_\{i\}\(t\-1\)=\\left\\\{\\begin\{aligned\} &\\infty,&&\{\\text\{if \}\\,N\_\{i,t\-1\}=0\}\\,\\\\ &\\bar\{\\mu\}\_\{i\}\(t\-1\)\+16\\sqrt\{\\frac\{2\\ln\(1/\\delta\)\}\{N\_\{i,t\-1\}\}\},&&\{\\text\{otherwise,\}\}\\end\{aligned\}\\right\.\(4\)
According to Proposition 1 of\[[40](https://arxiv.org/html/2607.13546#bib.bib4)\], for anyδ∈\(0,1\)\\delta\\in\(0,1\),μi​\(t\)≤μ¯i​\(t\)\+16​2​ln⁡\(1/δ\)Ni,t\\mu\_\{i\}\(t\)\\leq\\bar\{\\mu\}\_\{i\}\(t\)\+16\\sqrt\{\\frac\{2\\ln\(1/\\delta\)\}\{N\_\{i,t\}\}\}holds with probability at least1−δ1\-\\delta\.

#### 4\.2\.3Change Detection

To identify when a worker’s learning has saturated, CATI\-UCB incorporates a change detection module to estimate the convergence pointνi\\nu\_\{i\}for each workerii\. After a certain number of selections, different workers stabilize at distinct time steps, each reaching a steady reward levelμi∗\\mu\_\{i\}^\{\*\}fori∈\[K\]i\\in\[K\]\. To estimate the convergence pointνi\\nu\_\{i\}from the observed rewards of each workerii, we track their temporal evolution using two overlapping windows of lengthω\\omega\. The windows slide as more rewards are collected for workerii\.

At timet\+1t\+1, we compare the average rewards in the two windows: the previous windoww1=\[Ni,t−2​ω\+1,Ni,t−ω\]w\_\{1\}=\[N\_\{i,t\}\-2\\omega\+1,N\_\{i,t\}\-\\omega\]and the current windoww2=\[Ni,t−ω\+1,Ni,t\]w\_\{2\}=\[N\_\{i,t\}\-\\omega\+1,N\_\{i,t\}\], denoted byμ¯w1,i​\(t\+1\)\\bar\{\\mu\}\_\{w\_\{1\},i\}\(t\+1\)andμ¯w2,i​\(t\+1\)\\bar\{\\mu\}\_\{w\_\{2\},i\}\(t\+1\)\. If their difference exceedsγ/2\\gamma/2\(Line 10, Algorithm[1](https://arxiv.org/html/2607.13546#alg1)\), a change pointτi\\tau\_\{i\}is detected, the observations for workeriiare reset, and the current time stepτi\\tau\_\{i\}is recorded\. Otherwise, the algorithm proceeds to select workers and monitor new rewards\. This mechanism adaptively distinguishes learning from stabilization, ensuring that the linear model in the increasing phase remains accurate and up\-to\-date\. The statistical guarantee is given in Proposition[1](https://arxiv.org/html/2607.13546#Thmproposition1)\.

###### Proposition 1\.

\(Proposition 2 of\[[40](https://arxiv.org/html/2607.13546#bib.bib4)\]\) The reward change point of workeriiis considered to be reached, if

\|μ¯w1,i​\(t\+1\)−μ¯w2,i​\(t\+1\)\|\>γ/2,\|\\bar\{\\mu\}\_\{w\_\{1\},i\}\(t\+1\)\-\\bar\{\\mu\}\_\{w\_\{2\},i\}\(t\+1\)\|\>\{\\gamma\}/\{2\}\\;,whereμ¯w1,i​\(t\+1\)\\bar\{\\mu\}\_\{w\_\{1\},i\}\(t\+1\)andμ¯w2,i​\(t\+1\)\\bar\{\\mu\}\_\{w\_\{2\},i\}\(t\+1\)are the predicted rewards for workeriiat timet\+1t\+1calculated by observations in the windoww1=\[Ni,t−2​ω\+1,Ni,t−ω\]w\_\{1\}=\\left\[N\_\{i,t\}\-2\\omega\+1,N\_\{i,t\}\-\\omega\\right\], and by observations in the windoww2=\[Ni,t−ω\+1,Ni,t\]w\_\{2\}=\\left\[N\_\{i,t\}\-\\omega\+1,N\_\{i,t\}\\right\]\. Withγ≤2ω​\(14\+12\|ω−1\|\)2​ln⁡\(2δ\)\\gamma\\leq\\sqrt\{\\frac\{2\}\{\\omega\}\(14\+\\frac\{12\}\{\|\\omega\-1\|\}\)^\{2\}\\ln\(\\frac\{2\}\{\\delta\}\)\}, the above change detection inequality is valid with probability1−δ1\-\\delta\.

Algorithm 1CATI\-UCB1:Input:

K,δ,window sizeK,\\delta,\\text\{window size\}ω,t=0\\omega,t=0,\.

2:Initialization: Select each worker

iionce, observe the

XiX\_\{i\}and

YiY\_\{i\}to predict the

μ^i,t\\hat\{\\mu\}\_\{i,t\}and

c^i,t\\hat\{c\}\_\{i,t\}\.

3:while

∑τ=1tcAτ,τ≤B\\sum\_\{\\tau=1\}^\{t\}c\_\{A\_\{\\tau\},\\tau\}\\leq Bdo

4:

t=t\+1,ϵi,t=16​2​log⁡1/δNi,tt=t\+1,\\epsilon\_\{i,t\}=16\\sqrt\{\\frac\{2\\log 1/\\delta\}\{N\_\{i,t\}\}\}
5:

At=arg⁡maxi⁡\{μ^i,t\+ϵi,tmax⁡\{c^i,t−ϵi,t,0\.001\}\},\\displaystyle A\_\{t\}=\\arg\\max\_\{i\}\\\{\\frac\{\\hat\{\\mu\}\_\{i,t\}\+\\epsilon\_\{i,t\}\}\{\\max\\\{\\hat\{c\}\_\{i,t\}\-\\epsilon\_\{i,t\},0\.001\\\}\}\\\},
6:Choose worker

AtA\_\{t\}, and Observe reward

XAt,t,YAt,tX\_\{A\_\{t\},t\},Y\_\{A\_\{t\},t\}\.

7:Update reward estimation

μ^At,NAt,t\\hat\{\\mu\}\_\{A\_\{t\},N\_\{A\_\{t\},t\}\}, and cost estimation

c^At,NAt,t\\hat\{c\}\_\{A\_\{t\},N\_\{A\_\{t\},t\}\}\.

8:

NAt,t=NAt,t\+1N\_\{A\_\{t\},t\}=N\_\{A\_\{t\},t\}\+1\.

9:if

NAt,t≥2​wN\_\{A\_\{t\},t\}\\geq 2wthen

10:if

\|μ^At,w1−μ^At,w2\|≥12​2w​\(14\+12\|w−1\|\)2​log⁡\(2/δ\)\|\\hat\{\\mu\}\_\{A\_\{t\},w\_\{1\}\}\-\\hat\{\\mu\}\_\{A\_\{t\},w\_\{2\}\}\|\\geq\\frac\{1\}\{2\}\\sqrt\{\\frac\{2\}\{w\}\{\(14\+\\frac\{12\}\{\|w\-1\|\}\)\}^\{2\}\\log\(2/\\delta\)\}then

11:

τAt=t,NAt,t=1\\tau\_\{A\_\{t\}\}=t,N\_\{A\_\{t\},t\}=1
12:endif

13:endif

14:endwhile

## 5Regret Analysis

In this section, we provide the regret upper bound of CATI\-UCB in a typical increasing\-then\-converging reward within a given constrained budget setting\.

Define the optimal worker asarg⁡maxi∈\[K\]⁡μi∗ci\\arg\\max\_\{i\\in\[K\]\}\\frac\{\\mu\_\{i\}^\{\*\}\}\{c\_\{i\}\}, assuming all workers have true costs abovecminc\_\{\\min\}\. The suboptimal gap for workeriiisΔi=μi†∗ci†−μi∗ci\\Delta\_\{i\}=\\frac\{\\mu\_\{i^\{\\dagger\}\}^\{\*\}\}\{c\_\{i^\{\\dagger\}\}\}\-\\frac\{\\mu\_\{i\}^\{\*\}\}\{c\_\{i\}\}\. Then, by Eq\.[2](https://arxiv.org/html/2607.13546#S3.E2), the regret of the increasing\-then\-converging bandit under budget constraint using algorithm𝒜\\mathcal\{A\}can be rewritten as in Lemma \([2](https://arxiv.org/html/2607.13546#Thmlemma2)\)\.

###### Lemma 2\.

The expected regret can be characterized by

Regret​\(𝒜,B\)≤∑i≠i†ci​Δi​𝔼​\[Ni,T𝒜,B\]\+μi†∗/ci†\+∑i∈\[N\]νi​μi∗\.\\displaystyle\\textsc\{Regret\}\(\\mathcal\{A\},B\)\\leq\\sum\_\{i\\neq i^\{\\dagger\}\}c\_\{i\}\\Delta\_\{i\}\\mathbb\{E\}\[N\_\{i,T\_\{\\mathcal\{A\},B\}\}\]\+\\mu^\{\*\}\_\{i^\{\\dagger\}\}/c\_\{i^\{\\dagger\}\}\+\\sum\_\{i\\in\[N\]\}\\nu\_\{i\}\\mu^\{\*\}\_\{i\}\.

###### Proof\.

Note that the stopping timeT𝒜,BT\_\{\\mathcal\{A\},B\}, defined by∑t=1T𝒜,B−1YAt,t≤B<∑t=1T𝒜,BYAt,t\\sum\_\{t=1\}^\{T\_\{\\mathcal\{A\},B\}\-1\}Y\_\{A\_\{t\},t\}\\leq B<\\sum\_\{t=1\}^\{T\_\{\\mathcal\{A\},B\}\}Y\_\{A\_\{t\},t\}, is a random variable depending onBB\. Then the proof of Lemma 2 consists of two steps:

Step 1\.LetBtB\_\{t\}denote the remaining budget at roundtt, and𝐈​\(Bt≥0\)\\mathbf\{I\}\(B\_\{t\}\\geq 0\)the indicator of a valid round\. Letℳ\\mathcal\{M\}be the optimal policy that achievesR∗R^\{\*\}, the optimal expected total reward with known reward and cost distributions, and letAt∗A\_\{t\}^\{\*\}denote its selected action\. We first show thatR∗≤\(B\+1\)​μi†∗ci†R^\{\*\}\\leq\(B\+1\)\\frac\{\\mu^\{\*\}\_\{i^\{\\dagger\}\}\}\{c\_\{i^\{\\dagger\}\}\}\.

R∗\\displaystyle R^\{\*\}=𝔼​\[∑t=1∞rAt∗,t​𝐈​\(Bt≥0\)\]≤𝔼​\[∑t=1∞μAt∗∗​𝐈​\(Bt≥0\)\]\\displaystyle=\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{\\infty\}r\_\{A^\{\*\}\_\{t\},t\}\\mathbf\{I\}\(B\_\{t\}\\geq 0\)\\right\]\\leq\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{\\infty\}\\mu\_\{A\_\{t\}^\{\*\}\}^\{\*\}\\mathbf\{I\}\(B\_\{t\}\\geq 0\)\\right\]≤𝔼​\[∑t=1∞cAt∗​μi†∗ci†​𝐈​\(Bt≥0\)\]=μi†∗ci†​𝔼​\[∑t=1∞cAt∗​𝐈​\(Bt≥0\)\]\\displaystyle\\leq\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{\\infty\}c\_\{A\_\{t\}^\{\*\}\}\\frac\{\\mu\_\{i^\{\\dagger\}\}^\{\*\}\}\{c\_\{i^\{\\dagger\}\}\}\\mathbf\{I\}\(B\_\{t\}\\geq 0\)\\right\]=\\frac\{\\mu\_\{i^\{\\dagger\}\}^\{\*\}\}\{c\_\{i^\{\\dagger\}\}\}\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{\\infty\}c\_\{A\_\{t\}^\{\*\}\}\\mathbf\{I\}\(B\_\{t\}\\geq 0\)\\right\]=μi†∗ci†​𝔼​\[∑t=1∞cAt∗,t​𝐈​\(Bt≥0\)\]≤\(B\+1\)​μi†∗ci†,\\displaystyle=\\frac\{\\mu\_\{i^\{\\dagger\}\}^\{\*\}\}\{c\_\{i^\{\\dagger\}\}\}\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{\\infty\}c\_\{A\_\{t\}^\{\*\},t\}\\mathbf\{I\}\(B\_\{t\}\\geq 0\)\\right\]\\leq\(B\+1\)\\frac\{\\mu\_\{i^\{\\dagger\}\}^\{\*\}\}\{c\_\{i^\{\\dagger\}\}\},where the first inequality holds sinceμi,t≤μi∗\\mu\_\{i,t\}\\leq\\mu\_\{i\}^\{\*\}and the second follows from the suboptimal worker definition:μAt∗∗cAt∗≤μi†∗ci†\\frac\{\\mu\_\{A^\{\*\}\_\{t\}\}^\{\*\}\}\{c\_\{A^\{\*\}\_\{t\}\}\}\\leq\\frac\{\\mu\_\{i^\{\\dagger\}\}^\{\*\}\}\{c\_\{i^\{\\dagger\}\}\}\.

Step 2\.According to step 1, the optimal reward can be upper bounded asR∗≤\(B\+1\)​μi†∗ci†<𝔼​\[∑t=1T𝒜,BcAt,t\+1\]​μi†∗ci†\.R^\{\*\}\\leq\(B\+1\)\\frac\{\\mu^\{\*\}\_\{i^\{\\dagger\}\}\}\{c\_\{i^\{\\dagger\}\}\}<\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\_\{\\mathcal\{A\},B\}\}c\_\{A\_\{t\},t\}\+1\\right\]\\frac\{\\mu^\{\*\}\_\{i^\{\\dagger\}\}\}\{c\_\{i^\{\\dagger\}\}\}\.Accordingly, the regret can be bounded as

Regret​\(𝒜,B\)≤𝔼​\[∑t=1T𝒜,BcAt,t\+1\]​μi†∗ci†−𝔼​\[∑t=1T𝒜,BrAt,t\]\\displaystyle\\text\{Regret\}\(\\mathcal\{A\},B\)\\leq\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\_\{\\mathcal\{A\},B\}\}c\_\{A\_\{t\},t\}\+1\\right\]\\frac\{\\mu^\{\*\}\_\{i^\{\\dagger\}\}\}\{c\_\{i^\{\\dagger\}\}\}\-\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\_\{\\mathcal\{A\},B\}\}r\_\{A\_\{t\},t\}\\right\]=𝔼​\[∑t=1T𝒜,B\(μi†∗ci†​cAt,t−rAt,t\)\]\+μi†∗ci†\\displaystyle=\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\_\{\\mathcal\{A\},B\}\}\\left\(\\frac\{\\mu^\{\*\}\_\{i^\{\\dagger\}\}\}\{c\_\{i^\{\\dagger\}\}\}c\_\{A\_\{t\},t\}\-r\_\{A\_\{t\},t\}\\right\)\\right\]\+\\frac\{\\mu^\{\*\}\_\{i^\{\\dagger\}\}\}\{c\_\{i^\{\\dagger\}\}\}≤𝔼​\[∑t=1T𝒜,B\(μi†∗ci†​cAt−μAt∗\)\]\+∑i∈\[N\]νi​μi∗\+μi†∗ci†\\displaystyle\\leq\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\_\{\\mathcal\{A\},B\}\}\\left\(\\frac\{\\mu^\{\*\}\_\{i^\{\\dagger\}\}\}\{c\_\{i^\{\\dagger\}\}\}c\_\{A\_\{t\}\}\-\\mu^\{\*\}\_\{A\_\{t\}\}\\right\)\\right\]\+\\sum\_\{i\\in\[N\]\}\\nu\_\{i\}\\mu^\{\*\}\_\{i\}\+\\frac\{\\mu^\{\*\}\_\{i^\{\\dagger\}\}\}\{c\_\{i^\{\\dagger\}\}\}=∑i≠i†ci​Δi​𝔼​\[Ni,T𝒜,B\]\+μi†∗ci†\+∑i∈\[N\]νi​μi∗,\\displaystyle=\\sum\_\{i\\neq i^\{\\dagger\}\}c\_\{i\}\\Delta\_\{i\}\\mathbb\{E\}\[N\_\{i,T\_\{\\mathcal\{A\},B\}\}\]\+\\frac\{\\mu^\{\*\}\_\{i^\{\\dagger\}\}\}\{c\_\{i^\{\\dagger\}\}\}\+\\sum\_\{i\\in\[N\]\}\\nu\_\{i\}\\mu^\{\*\}\_\{i\},where the inequality is due to

𝔼​\[∑t=1T𝒜,BrAt,t\]\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\_\{\\mathcal\{A\},B\}\}r\_\{A\_\{t\},t\}\\right\]=𝔼​\[∑i=1K∑l=0Ni,T𝒜,Bμi​\(l\)\]\\displaystyle=\\mathbb\{E\}\\left\[\\sum\_\{i=1\}^\{K\}\\sum\_\{l=0\}^\{N\_\{i,T\_\{\\mathcal\{A\},B\}\}\}\\mu\_\{i\}\(l\)\\right\]=𝔼​\[∑i=1K∑l=0Ni,T𝒜,Bμi∗\]−νi​μi∗\+∑l=0νiμi​\(l\)\\displaystyle=\\mathbb\{E\}\\left\[\\sum\_\{i=1\}^\{K\}\\sum\_\{l=0\}^\{N\_\{i,T\_\{\\mathcal\{A\},B\}\}\}\\mu\_\{i\}^\{\*\}\\right\]\-\\nu\_\{i\}\\mu\_\{i\}^\{\*\}\+\\sum\_\{l=0\}^\{\\nu\_\{i\}\}\\mu\_\{i\}\(l\)≥𝔼​\[∑i=1K∑l=0Ni,T𝒜,Bμi∗\]−νi​μi∗\.∎\\displaystyle\\geq\\mathbb\{E\}\\left\[\\sum\_\{i=1\}^\{K\}\\sum\_\{l=0\}^\{N\_\{i,T\_\{\\mathcal\{A\},B\}\}\}\\mu\_\{i\}^\{\*\}\\right\]\-\\nu\_\{i\}\\mu\_\{i\}^\{\*\}\.\{\\qed\}∎

We next only focus on the expected selecting time of each suboptimal worker\. Define two events thatFi=\{τi≥νi\}F\_\{i\}=\\\{\\tau\_\{i\}\\geq\\nu\_\{i\}\\\}andDi=\{τi≤νi\+ω\}D\_\{i\}=\\\{\\tau\_\{i\}\\leq\\nu\_\{i\}\+\\omega\\\}\.FiF\_\{i\}implies that theii\-th change point can only be detected by the algorithm after the change occurs\. DenoteFicF\_\{i\}^\{c\}andDicD\_\{i\}^\{c\}as the complementary event ofFiF\_\{i\}andDiD\_\{i\}\. This leads to the following result:

###### Lemma 3\.

Letγ=2​2ω​\(14\+12\|ω−1\|\)2​ln⁡\(B\)\\gamma=2\\sqrt\{\\frac\{2\}\{\\omega\}\(14\+\\frac\{12\}\{\|\\omega\-1\|\}\)^\{2\}\\ln\(B\)\}, then𝐏​\(Fi​Di\)\>1−1B\\mathbf\{P\}\(F\_\{i\}D\_\{i\}\)\>1\-\\frac\{1\}\{B\}\.

###### Proof\.

𝐏​\(Fi​Di\)=𝐏​\(vi<τ1<vi\+ω\)\\mathbf\{P\}\(F\_\{i\}D\_\{i\}\)=\\mathbf\{P\}\(v\_\{i\}<\\tau\_\{1\}<v\_\{i\}\+\\omega\), which means that if a change occurs, the algorithm detects it within the windowω\\omega\. By inequality \(8\) in\[[40](https://arxiv.org/html/2607.13546#bib.bib4)\],

𝐏​\(Fi​Di\)\\displaystyle\\mathbf\{P\}\(F\_\{i\}D\_\{i\}\)=𝐏​\(\|μ^w1,i​\(t\+1\)−μ^w2,i​\(t\+1\)\|\>γ2\)\\displaystyle=\\mathbf\{P\}\(\|\\hat\{\\mu\}\_\{w\_\{1\},i\}\(t\+1\)\-\\hat\{\\mu\}\_\{w\_\{2\},i\}\(t\+1\)\|\>\\frac\{\\gamma\}\{2\}\)\>1−exp⁡\{−ω​\(γ2\)22​\(14\+12\|ω−1\|\)2\}\.\\displaystyle\>1\-\\exp\\\{\-\\frac\{\\omega\(\\frac\{\\gamma\}\{2\}\)^\{2\}\}\{2\(14\+\\frac\{12\}\{\|\\omega\-1\|\}\)^\{2\}\}\\\}\.Then substituteγ=2​2ω​\(14\+12\|ω−1\|\)2​ln⁡\(B\)\\gamma=2\\sqrt\{\\frac\{2\}\{\\omega\}\(14\+\\frac\{12\}\{\|\\omega\-1\|\}\)^\{2\}\\ln\(B\)\}to1−exp⁡\{−ω​\(γ2\)22​\(14\+12\|ω−1\|\)2\}1\-\\exp\\\{\-\\frac\{\\omega\(\\frac\{\\gamma\}\{2\}\)^\{2\}\}\{2\(14\+\\frac\{12\}\{\|\\omega\-1\|\}\)^\{2\}\}\\\}, we have𝐏​\(Fi​Di\)\>1−1B\\mathbf\{P\}\(F\_\{i\}D\_\{i\}\)\>1\-\\frac\{1\}\{B\}\. ∎

Then, we introduce two notations as follows,

T0=⌊2​Bcmin⌋,N0=2​log⁡B⋅1min2⁡\{Δi​\(ci\)28​\(μi∗\+ci\),ci4\}\.\\displaystyle T\_\{0\}=\\lfloor\\frac\{2B\}\{c\_\{\\min\}\}\\rfloor,\\quad\\quad N\_\{0\}=2\\log B\\cdot\\frac\{1\}\{\{\\min\}^\{2\}\\\{\\frac\{\\Delta\_\{i\}\(c\_\{i\}\)^\{2\}\}\{8\(\\mu^\{\*\}\_\{i\}\+c\_\{i\}\)\},\\frac\{c\_\{i\}\}\{4\}\\\}\}\.
###### Lemma 4\.

For anyt≥T0t\\geq T\_\{0\}, we have𝐏​\(Bt\+1≥0\)≤exp⁡\(−2​\(B−t​cmin\)2/t\)\\mathbf\{P\}\(B\_\{t\+1\}\\geq 0\)\\leq\\exp\(\-2\(B\-tc\_\{\\min\}\)^\{2\}/t\)\.

###### Proof\.

Recall that the cost incurred at roundttisctc\_\{t\}\. Whent≥T0t\\geq T\_\{0\}we have𝔼​\[c1\]\+⋯\+𝔼​\[ct\]≥t⋅cmin≥2​B\>B\\mathbb\{E\}\[c\_\{1\}\]\+\\cdots\+\\mathbb\{E\}\[c\_\{t\}\]\\geq t\\cdot c\_\{\\min\}\\geq 2B\>B\. Accordingly, it holds that

𝐏​\(Bt\+1≥0\)\\displaystyle\\mathbf\{P\}\(B\_\{t\+1\}\\geq 0\)=𝐏​\(c1\+⋯\+ct≤B\)\\displaystyle=\\mathbf\{P\}\(c\_\{1\}\+\\cdots\+c\_\{t\}\\leq B\)≤𝐏\(c1\+⋯\+ct−𝔼\[c1\]−⋯−𝔼\[ct\]\\displaystyle\\leq\\mathbf\{P\}\(c\_\{1\}\+\\cdots\+c\_\{t\}\-\\mathbb\{E\}\[c\_\{1\}\]\-\\cdots\-\\mathbb\{E\}\[c\_\{t\}\]≤B−𝐄\[c1\]−⋯−𝔼\[ct\]\)\\displaystyle\\qquad\\qquad\\leq B\-\\mathbf\{E\}\[c\_\{1\}\]\-\\cdots\-\\mathbb\{E\}\[c\_\{t\}\]\)≤exp⁡\{−2​\(B−𝔼​\[c1\]−⋯−𝔼​\[ct\]\)2t\}\\displaystyle\\leq\\exp\\\{\-\\frac\{2\(B\-\\mathbb\{E\}\[c\_\{1\}\]\-\\cdots\-\\mathbb\{E\}\[c\_\{t\}\]\)^\{2\}\}\{t\}\\\}≤exp⁡\{−2​\(B−t​cmin\)2t\},\\displaystyle\\leq\\exp\\\{\-\\frac\{2\(B\-tc\_\{\\min\}\)^\{2\}\}\{t\}\\\},where the second inequality holds due to the Hoeffding inequality\. ∎

Here, denote that algorithm CATI\-UCB as𝒞\\mathcal\{C\}, we are ready to have a regret bound for our algorithm:

###### Theorem 1\.

Letγ=2​2ω​\(14\+12\|ω−1\|\)2​ln⁡\(B\)\\gamma=2\\sqrt\{\\frac\{2\}\{\\omega\}\(14\+\\frac\{12\}\{\|\\omega\-1\|\}\)^\{2\}\\ln\(B\)\}, the regret of our algorithm CATI\-UCB can be bounded by :

Regret​\(𝒞,B\)\\displaystyle\\text\{Regret\}\(\\mathcal\{C\},B\)≤∑i≠i†ciΔi⋅\(N0\+4​T0B2\+ℱ\(B,cmin\)\+2ω\+\\displaystyle\\leq\\sum\_\{i\\neq i^\{\\dagger\}\}c\_\{i\}\\Delta\_\{i\}\\cdot\(N\_\{0\}\+\\frac\{4T\_\{0\}\}\{B^\{2\}\}\+\\mathcal\{F\}\(B,c\_\{\\min\}\)\+2\\omega\+νi\+2​Bcmin\+1\+ℱ​\(B,cmin\)B\)\+μi†∗ci†\+∑i∈\[N\]νiμ∗i,\\displaystyle\\;\\nu\_\{i\}\+\\frac\{\\frac\{2B\}\{c\_\{\\min\}\}\+1\+\\mathcal\{F\}\(B,c\_\{\\min\}\)\}\{B\}\)\+\\frac\{\\mu^\{\*\}\_\{i^\{\\dagger\}\}\}\{c\_\{i^\{\\dagger\}\}\}\+\\sum\_\{i\\in\[N\]\}\\nu\_\{i\}\\mu^\{\*\}\_\{i\},where

T0\\displaystyle T\_\{0\}=⌊2​Bcmin⌋,N0=2​log⁡Bmin2⁡\{Δi​\(ci\)28​\(μi∗\+ci\),ci4\},and\\displaystyle=\\lfloor\\frac\{2B\}\{c\_\{\\min\}\}\\rfloor,\\qquad N\_\{0\}=\\frac\{2\\log B\}\{\{\\min\}^\{2\}\\left\\\{\\frac\{\\Delta\_\{i\}\(c\_\{i\}\)^\{2\}\}\{8\(\\mu^\{\*\}\_\{i\}\+c\_\{i\}\)\},\\frac\{c\_\{i\}\}\{4\}\\right\\\}\},\\;\\text\{and\}ℱ​\(B,cmin\)=exp⁡\{−2​\(B−1\)22​Bcmin\+1⋅11−exp⁡−4​\(B−1\)​cmin2​Bcmin\+1\}\\displaystyle\\mathcal\{F\}\(B,c\_\{\\min\}\)=\\exp\\left\\\{\\frac\{\-2\{\(B\-1\)\}^\{2\}\}\{\\frac\{2B\}\{c\_\{\\min\}\}\+1\}\\cdot\\frac\{1\}\{1\-\\exp\{\\frac\{\-4\{\(B\-1\)\}c\_\{\\min\}\}\{\\frac\{2B\}\{c\_\{\\min\}\}\+1\}\}\}\\right\\\}\+exp⁡\{−cmin​\(B−cmin\)2B\}\+∑ℓ=T0\+1∞exp⁡\{−ℓ​\(cmin\)2\}\\displaystyle\+\\exp\\left\\\{\-\\frac\{c\_\{\\min\}\(B\-c\_\{\\min\}\)^\{2\}\}\{B\}\\right\\\}\+\\sum\_\{\\ell=T\_\{0\}\+1\}^\{\\infty\}\\exp\\left\\\{\-\\ell\(c\_\{\\min\}\)^\{2\}\\right\\\}

Remark:The termℱ​\(B,cmin\)\\mathcal\{F\}\(B,c\_\{\\min\}\)tends to zero asBBtends to infinity,N0N\_\{0\}is a logarithmic relationship with respect toBB, and the remaining terms are constant terms, therefore, we can get the regret upper bound of CATI\-UCB ofO​\(log⁡\(B\)\)O\(\\log\(B\)\), which implies a fast convergence rate\.

###### Proof\.

The right side of Lemma \([2](https://arxiv.org/html/2607.13546#Thmlemma2)\) shows that the regret of our algorithm is related to the number of selects for each suboptimalii, it can be characterized by

𝔼​\[Ni,T𝒞,B\]\\displaystyle\\mathbb\{E\}\[N\_\{i,T\_\{\\mathcal\{C\},B\}\}\]=𝔼​\[Ni,T𝒞,B−νi\]\+νi\\displaystyle=\\mathbb\{E\}\[N\_\{i,T\_\{\\mathcal\{C\},B\}\}\-\\nu\_\{i\}\]\+\\nu\_\{i\}≤𝔼​\[Ni,T𝒞,B−τi\|Fi​Di\]\+𝔼​\[τi−νi\|Fi​Di\]\\displaystyle\\leq\\mathbb\{E\}\[N\_\{i,T\_\{\\mathcal\{C\},B\}\}\-\\tau\_\{i\}\|F\_\{i\}D\_\{i\}\]\+\\mathbb\{E\}\[\\tau\_\{i\}\-\\nu\_\{i\}\|F\_\{i\}D\_\{i\}\]\+𝔼​\[T𝒞,B\|Fic​Dic\]⋅\(1−𝐏​\(Fi​Di\)\)\+νi\\displaystyle\\qquad\\qquad\+\\mathbb\{E\}\[T\_\{\\mathcal\{C\},B\}\|F^\{c\}\_\{i\}D^\{c\}\_\{i\}\]\\cdot\(1\-\\mathbf\{P\}\(F\_\{i\}D\_\{i\}\)\)\+\\nu\_\{i\}≤𝔼​\[Ni,T𝒞,B−τi\|Fi​Di\]⏟\(i\)\+𝔼​\[τi−νi\|Fi​Di\]⏟\(ii\)\\displaystyle\\leq\\underbrace\{\\mathbb\{E\}\[N\_\{i,T\_\{\\mathcal\{C\},B\}\}\-\\tau\_\{i\}\|F\_\{i\}D\_\{i\}\]\}\_\{\\textbf\{\(i\)\}\}\+\\underbrace\{\\mathbb\{E\}\[\\tau\_\{i\}\-\\nu\_\{i\}\|F\_\{i\}D\_\{i\}\]\}\_\{\\textbf\{\(ii\)\}\}\+𝔼​\[T𝒞,B\]​\(1−𝐏​\(Fi​Di\)\)⏟\(iii\)\+νi,\\displaystyle\\qquad\\qquad\+\\underbrace\{\\mathbb\{E\}\[T\_\{\\mathcal\{C\},B\}\]\(1\-\\mathbf\{P\}\(F\_\{i\}D\_\{i\}\)\)\}\_\{\\textbf\{\(iii\)\}\}\+\\nu\_\{i\},where the first inequality is due toNi,T𝒞,B≤T𝒞,BN\_\{i,T\_\{\\mathcal\{C\},B\}\}\\leq T\_\{\\mathcal\{C\},B\}and𝐏​\(Fi​Di\)≤1\\mathbf\{P\}\(F\_\{i\}D\_\{i\}\)\\leq 1\.

To bound part \(i\), it can be decomposed as follows,

𝔼​\[Ni,T𝒞,B−τi\|Fi​Di\]≤𝔼​\[Ni,T𝒞,B\|Fi​Di\]\\displaystyle\\mathbb\{E\}\[N\_\{i,T\_\{\\mathcal\{C\},B\}\}\-\\tau\_\{i\}\|F\_\{i\}D\_\{i\}\]\\leq\\mathbb\{E\}\[N\_\{i,T\_\{\\mathcal\{C\},B\}\}\|F\_\{i\}D\_\{i\}\]≤\\displaystyle\\leq𝔼​\[∑t=1T0𝐈​\{At=i,Fi​Di\}\]\+𝔼​\[∑T0\+1∞𝐈​\{Bt≥0\}\]\\displaystyle\\mathbb\{E\}\\left\[\\sum^\{T\_\{0\}\}\_\{t=1\}\\mathbf\{I\}\\\{A\_\{t\}=i,F\_\{i\}D\_\{i\}\\\}\\right\]\+\\mathbb\{E\}\\left\[\\sum^\{\\infty\}\_\{T\_\{0\}\+1\}\\mathbf\{I\}\\\{B\_\{t\}\\geq 0\\\}\\right\]≤\\displaystyle\\leqN0\+τi\+𝔼​\[∑t=1T0𝐈​\{At=i,Ni,t≥N0\+τi,Fi​Di\}\]\\displaystyle N\_\{0\}\+\\tau\_\{i\}\+\\mathbb\{E\}\\left\[\\sum^\{T\_\{0\}\}\_\{t=1\}\\mathbf\{I\}\\\{A\_\{t\}=i,N\_\{i,t\}\\geq N\_\{0\}\+\\tau\_\{i\},F\_\{i\}D\_\{i\}\\\}\\right\]\+𝔼​\[∑T0\+1∞𝐈​\{Bt≥0\}\]\.\\displaystyle\\qquad\\qquad\+\\mathbb\{E\}\\left\[\\sum^\{\\infty\}\_\{T\_\{0\}\+1\}\\mathbf\{I\}\\\{B\_\{t\}\\geq 0\\\}\\right\]\.For notational convenience, denoteEtE\_\{t\}as the event𝐈​\{At=i,Ni,t≥N0\+νi,Fi​Di\}\\mathbf\{I\}\\\{A\_\{t\}=i,N\_\{i,t\}\\geq N\_\{0\}\+\\nu\_\{i\},F\_\{i\}D\_\{i\}\\\}\. Sinceμi†∗/ci†=μi∗/ci\+Δi\\mu^\{\*\}\_\{i^\{\\dagger\}\}/c\_\{i^\{\\dagger\}\}=\\mu^\{\*\}\_\{i\}/c\_\{i\}\+\\Delta\_\{i\}, ifEtE\_\{t\}holds, which means that workeriiis selected at timett, then at least one of the following two events must happen:

Et1:\\displaystyle E^\{1\}\_\{t\}:μ^i†c^i†≤μi†∗ci†−Δi2,Ni,t≥N0\+τi,Fi​Di,\\displaystyle\\frac\{\\hat\{\\mu\}\_\{i^\{\\dagger\}\}\}\{\\hat\{c\}\_\{i^\{\\dagger\}\}\}\\leq\\frac\{\\mu^\{\*\}\_\{i^\{\\dagger\}\}\}\{c\_\{i^\{\\dagger\}\}\}\-\\frac\{\\Delta\_\{i\}\}\{2\},N\_\{i,t\}\\geq N\_\{0\}\+\\tau\_\{i\},F\_\{i\}D\_\{i\},Et2:\\displaystyle E^\{2\}\_\{t\}:μ^ic^i\>μi∗ci\+Δi2,Ni,t≥N0\+τi,Fi​Di\.\\displaystyle\\frac\{\\hat\{\\mu\}\_\{i\}\}\{\\hat\{c\}\_\{i\}\}\>\\frac\{\\mu^\{\*\}\_\{i\}\}\{c\_\{i\}\}\+\\frac\{\\Delta\_\{i\}\}\{2\},N\_\{i,t\}\\geq N\_\{0\}\+\\tau\_\{i\},F\_\{i\}D\_\{i\}\.Otherwise, let\{Et1\}c\\\{E^\{1\}\_\{t\}\\\}^\{c\}and\{Et2\}c\\\{E^\{2\}\_\{t\}\\\}^\{c\}denote the complements event ofEt1E^\{1\}\_\{t\}andEt2E^\{2\}\_\{t\}\. If both occur simultaneously, then:

\{Et1\}c⇒μ^i†c^i†\\displaystyle\\\{E^\{1\}\_\{t\}\\\}^\{c\}\\Rightarrow\\frac\{\\hat\{\\mu\}\_\{i^\{\\dagger\}\}\}\{\\hat\{c\}\_\{i^\{\\dagger\}\}\}\>μi∗ci\+Δi−Δi2=μi∗ci∗\+Δi2≥μ^ic^i,\\displaystyle\>\\frac\{\\mu^\{\*\}\_\{i\}\}\{c\_\{i\}\}\+\\Delta\_\{i\}\-\\frac\{\\Delta\_\{i\}\}\{2\}=\\frac\{\\mu\_\{i\}^\{\*\}\}\{c\_\{i\}^\{\*\}\}\+\\frac\{\\Delta\_\{i\}\}\{2\}\\geq\\frac\{\\hat\{\\mu\}\_\{i\}\}\{\\hat\{c\}\_\{i\}\},where the last inequality corresponds to\{Et2\}c\\\{E^\{2\}\_\{t\}\\\}^\{c\}\. Thus, we haveμ^i†c^i†\>μ^ic^i\\frac\{\\hat\{\\mu\}\_\{i^\{\\dagger\}\}\}\{\\hat\{c\}\_\{i^\{\\dagger\}\}\}\>\\frac\{\\hat\{\\mu\}\_\{i\}\}\{\\hat\{c\}\_\{i\}\}, which contradicts the fact that workeriiwas selected in roundtt\.

By the concentration inequality \(setδ=1/B\\delta=1/B\),

𝐏​\(μ^i†\>μi†∗\|Ni,t≥N0\+τi\)≥1−1B2,\\displaystyle\\mathbf\{P\}\\left\(\\hat\{\\mu\}\_\{i^\{\\dagger\}\}\>\\mu^\{\*\}\_\{i^\{\\dagger\}\}\|N\_\{i,t\}\\geq N\_\{0\}\+\\tau\_\{i\}\\right\)\\geq 1\-\\frac\{1\}\{B^\{2\}\},𝐏​\(c^i†​<ci†\|​Ni,t≥N0\+τi\)≥1−1B2,\\displaystyle\\mathbf\{P\}\\left\(\\hat\{c\}\_\{i^\{\\dagger\}\}<c\_\{i^\{\\dagger\}\}\|N\_\{i,t\}\\geq N\_\{0\}\+\\tau\_\{i\}\\right\)\\geq 1\-\\frac\{1\}\{B^\{2\}\},which gives𝐏​\(Et1\)≤2B2\\mathbf\{P\}\\left\(E^\{1\}\_\{t\}\\right\)\\leq\\frac\{2\}\{B^\{2\}\}\. Similarly, with probability at least1−2B21\-\\frac\{2\}\{B^\{2\}\},

μ^ic^i\\displaystyle\\frac\{\\hat\{\\mu\}\_\{i\}\}\{\\hat\{c\}\_\{i\}\}≤μi∗\+2​ϵi,tmax⁡\{ci−2​ϵi,t,η\}​≤\(a\)​μi∗\+2​ϵi,tci−2​ϵi,t=μi∗ci\+2​ϵi,t​\(μi∗\+ci\)ci​\(ci−2​ϵi,t\)\\displaystyle\\leq\\frac\{\\mu^\{\*\}\_\{i\}\+2\\epsilon\_\{i,t\}\}\{\\max\\\{c\_\{i\}\-2\\epsilon\_\{i,t\},\\eta\\\}\}\\overset\{\(a\)\}\{\\leq\}\\frac\{\\mu^\{\*\}\_\{i\}\+2\\epsilon\_\{i,t\}\}\{c\_\{i\}\-2\\epsilon\_\{i,t\}\}=\\frac\{\\mu^\{\*\}\_\{i\}\}\{c\_\{i\}\}\+\\frac\{2\\epsilon\_\{i,t\}\(\\mu^\{\*\}\_\{i\}\+c\_\{i\}\)\}\{c\_\{i\}\(c\_\{i\}\-2\\epsilon\_\{i,t\}\)\}≤\(b\)​μi∗ci\+4​ϵi,t​\(μi∗\+ci\)\(ci\)2​≤\(c\)​μi∗ci\+Δi2\.\\displaystyle\\overset\{\(b\)\}\{\\leq\}\\frac\{\\mu^\{\*\}\_\{i\}\}\{c\_\{i\}\}\+\\frac\{4\\epsilon\_\{i,t\}\(\\mu^\{\*\}\_\{i\}\+c\_\{i\}\)\}\{\(c\_\{i\}\)^\{2\}\}\\overset\{\(c\)\}\{\\leq\}\\frac\{\\mu^\{\*\}\_\{i\}\}\{c\_\{i\}\}\+\\frac\{\\Delta\_\{i\}\}\{2\}\.where the inequalities \(a\), \(b\), and \(c\) hold sinceNi,t≥N0N\_\{i,t\}\\geq N\_\{0\}ensures that2​ϵi,t≤0\.5​ci2\\epsilon\_\{i,t\}\\leq 0\.5c\_\{i\}andϵi,t≤Δi​\(ci\)28​\(μi∗\+ci\)\\epsilon\_\{i,t\}\\leq\\frac\{\\Delta\_\{i\}\(c\_\{i\}\)^\{2\}\}\{8\(\\mu^\{\*\}\_\{i\}\+c\_\{i\}\)\}\. Therefore,𝐏​\(At2\)≤2B2\\mathbf\{P\}\(A^\{2\}\_\{t\}\)\\leq\\frac\{2\}\{B^\{2\}\}, and thus

𝔼​\[Ni,T𝒞,B−τi\|Fi​Di\]\\displaystyle\\mathbb\{E\}\[N\_\{i,T\_\{\\mathcal\{C\},B\}\}\-\\tau\_\{i\}\|F\_\{i\}D\_\{i\}\]≤\\displaystyle\\leqN0\+∑t=N0\+τi\+1T0𝐈​\{At\}\+∑T0\+1∞𝐈​\{Bt≥0\}\\displaystyle N\_\{0\}\+\\sum^\{T\_\{0\}\}\_\{t=N\_\{0\}\+\\tau\_\{i\}\+1\}\\mathbf\{I\}\\\{A\_\{t\}\\\}\+\\sum^\{\\infty\}\_\{T\_\{0\}\+1\}\\mathbf\{I\}\\\{B\_\{t\}\\geq 0\\\}≤\\displaystyle\\leqN0\+4​T0B2\+∑T0\+1∞𝐈​\{Bt≥0\}\+νi\+w\.\\displaystyle N\_\{0\}\+\\frac\{4T\_\{0\}\}\{B^\{2\}\}\+\\sum^\{\\infty\}\_\{T\_\{0\}\+1\}\\mathbf\{I\}\\\{B\_\{t\}\\geq 0\\\}\+\\nu\_\{i\}\+w\.Accroding to the Lemma 4, for anyt≥T0t\\geq T\_\{0\}, we have𝐏​\(Bt\+1≥0\)≤exp⁡\(−2​\(B−t​cmin\)2/t\)\\mathbf\{P\}\(B\_\{t\+1\}\\geq 0\)\\leq\\exp\(\-2\(B\-tc\_\{\\min\}\)^\{2\}/t\)\. Now we are going to bound∑t=T0\+1∞𝐏​\(Bt≥0\)\\sum\_\{t=T\_\{0\}\+1\}^\{\\infty\}\\mathbf\{P\}\(B\_\{t\}\\geq 0\)\. It holds that

∑t=T0\+1∞𝐏​\(Bt≥0\)≤∑t=T0∞𝐏​\(Bt\+1≥0\)\\displaystyle\\sum\_\{t=T\_\{0\}\+1\}^\{\\infty\}\\mathbf\{P\}\(B\_\{t\}\\geq 0\)\\leq\\sum\_\{t=T\_\{0\}\}^\{\\infty\}\\mathbf\{P\}\(B\_\{t\+1\}\\geq 0\)=\\displaystyle=exp⁡\{−cmin​\(B−cmin\)2B\}\+∑t=T0\+1∞𝐏​\(Bt\+1≥0\)\\displaystyle\\exp\\left\\\{\-\\frac\{c\_\{\\min\}\(B\-c\_\{\\min\}\)^\{2\}\}\{B\}\\right\\\}\+\\sum\_\{t=T\_\{0\}\+1\}^\{\\infty\}\\mathbf\{P\}\(B\_\{t\+1\}\\geq 0\)=\\displaystyle=X\+∑ℓ=1∞exp⁡\{−2​\(B−T0⋅cmin−ℓ⋅cmin\)2ℓ\+T0\}\\displaystyle X\+\\sum\_\{\\ell=1\}^\{\\infty\}\\exp\\left\\\{\-\\frac\{2\(B\-T\_\{0\}\\cdot c\_\{\\min\}\-\\ell\\cdot c\_\{\\min\}\)^\{2\}\}\{\\ell\+T\_\{0\}\}\\right\\\}≤\\displaystyle\\leqX\+∑ℓ=1∞exp⁡\{−2​\(B−cmin\+ℓ⋅cmin\)2ℓ\+T0\}\\displaystyle X\+\\sum\_\{\\ell=1\}^\{\\infty\}\\exp\\left\\\{\-\\frac\{2\(B\-c\_\{\\min\}\+\\ell\\cdot c\_\{\\min\}\)^\{2\}\}\{\\ell\+T\_\{0\}\}\\right\\\}≤\\displaystyle\\leqX\+∑ℓ=1∞exp⁡\{−2​\(B−cmin\+ℓ⋅cmin\)22​Bcmin\+ℓ\}\\displaystyle X\+\\sum\_\{\\ell=1\}^\{\\infty\}\\exp\\left\\\{\-\\frac\{2\(B\-c\_\{\\min\}\+\\ell\\cdot c\_\{\\min\}\)^\{2\}\}\{\\frac\{2B\}\{c\_\{\\min\}\}\+\\ell\}\\right\\\}≤\\displaystyle\\leqX\+∑ℓ=1T0exp⁡\{−2​\(B−cmin\+ℓ⋅cmin\)22​Bcmin\+ℓ\}\\displaystyle X\+\\sum\_\{\\ell=1\}^\{T\_\{0\}\}\\exp\\left\\\{\-\\frac\{2\(B\-c\_\{\\min\}\+\\ell\\cdot c\_\{\\min\}\)^\{2\}\}\{\\frac\{2B\}\{c\_\{\\min\}\}\+\\ell\}\\right\\\}\+∑ℓ=T0\+1∞exp⁡\{−2​\(B−cmin\+ℓ⋅cmin\)22​Bcmin\+ℓ\}\\displaystyle\\quad\+\\sum\_\{\\ell=T\_\{0\}\+1\}^\{\\infty\}\\exp\\left\\\{\-\\frac\{2\(B\-c\_\{\\text\{min\}\}\+\\ell\\cdot c\_\{\\min\}\)^\{2\}\}\{\\frac\{2B\}\{c\_\{\\min\}\}\+\\ell\}\\right\\\}≤\\displaystyle\\leqX\+Z\+∑ℓ=T0\+1∞exp⁡\{−ℓ​\(cmin\)2\},\\displaystyle X\+Z\+\\sum\_\{\\ell=T\_\{0\}\+1\}^\{\\infty\}\\exp\\left\\\{\-\\ell\(c\_\{\\min\}\)^\{2\}\\right\\\},where the second equality substituteexp⁡\{−cmin​\(B−cmin\)2B\}\\exp\\left\\\{\-\\frac\{c\_\{\\min\}\(B\-c\_\{\\min\}\)^\{2\}\}\{B\}\\right\\\}to X, the second and third inequalities are due to the definition ofT0T\_\{0\}, the forth inequality usesZZto substitute∑ℓ=1T0exp⁡\{−2​\(B−cmin\+ℓ⋅cmin\)22​Bcmin\+ℓ\}\\sum\_\{\\ell=1\}^\{T\_\{0\}\}\\exp\\left\\\{\-\\frac\{2\(B\-c\_\{\\min\}\+\\ell\\cdot c\_\{\\min\}\)^\{2\}\}\{\\frac\{2B\}\{c\_\{\\min\}\}\+\\ell\}\\right\\\}, and this term can be bounded byexp⁡\{−2​\(B−1\)22​Bcmin\+1⋅11−exp⁡−4​\(B−1\)​cmin2​Bcmin\+1\}\\exp\\left\\\{\\frac\{\-2\{\(B\-1\)\}^\{2\}\}\{\\frac\{2B\}\{c\_\{\\text\{min\}\}\}\+1\}\\cdot\\frac\{1\}\{1\-\\exp\{\\frac\{\-4\{\(B\-1\)\}c\_\{\\text\{min\}\}\}\{\\frac\{2B\}\{c\_\{\\text\{min\}\}\}\+1\}\}\}\\right\\\}\. We useℱ​\(B,cmin\)\\mathcal\{F\}\(B,c\_\{\\text\{min\}\}\)to bound the right side of the above inequality\. Please note thatℱ​\(B,cmin\)\\mathcal\{F\}\(B,c\_\{\\text\{min\}\}\)tends to zero asBBtends to infinity\.

Combining all things together we obtain for anyi≠i†i\\neq i^\{\\dagger\},

𝔼​\[Ni,T𝒞,B−τi\|Fi​Di\]≤N0\+4​T0B2\+ℱ​\(B,cmin\)\+ω\+νi\.\\mathbb\{E\}\[N\_\{i,T\_\{\\mathcal\{C\},B\}\}\-\\tau\_\{i\}\|F\_\{i\}D\_\{i\}\]\\leq N\_\{0\}\+\\frac\{4T\_\{0\}\}\{B^\{2\}\}\+\\mathcal\{F\}\(B,c\_\{\\min\}\)\+\\omega\+\\nu\_\{i\}\.\(5\)For the part \(ii\), it can be bounded by

𝔼​\[τi−νi\|Fi​Di\]≤ω\.\\mathbb\{E\}\[\\tau\_\{i\}\-\\nu\_\{i\}\|F\_\{i\}D\_\{i\}\]\\leq\\omega\.\(6\)According to the Lemma 3, the part \(iii\) can be bound by:

𝔼​\[T𝒞,B\]​\(1−𝐏​\(Fi​Di\)\)\\displaystyle\\mathbb\{E\}\[T\_\{\\mathcal\{C\},B\}\]\(1\-\\mathbf\{P\}\(F\_\{i\}D\_\{i\}\)\)≤T0\+𝔼​\[∑T0\+1∞𝐈​\{Bt≥0\}\]B\\displaystyle\\leq\\frac\{T\_\{0\}\+\\mathbb\{E\}\\left\[\\sum^\{\\infty\}\_\{T\_\{0\}\+1\}\\mathbf\{I\}\\\{B\_\{t\}\\geq 0\\\}\\right\]\}\{B\}≤2​Bcmin\+1\+ℱ​\(B,cmin\)B\.\\displaystyle\\leq\\frac\{\\frac\{2B\}\{c\_\{\\min\}\}\+1\+\\mathcal\{F\}\(B,c\_\{\\min\}\)\}\{B\}\.\(7\)
Combining \([5](https://arxiv.org/html/2607.13546#S5.E5)\), \([6](https://arxiv.org/html/2607.13546#S5.E6)\) and \([5](https://arxiv.org/html/2607.13546#S5.Ex64)\), we bound𝔼​\[Ni,Tc,B\]\\mathbb\{E\}\[N\_\{i,T\_\{c\},B\}\]as:

𝔼​\[Ni,T𝒞,B\]\\displaystyle\\mathbb\{E\}\[N\_\{i,T\_\{\\mathcal\{C\},B\}\}\]≤N0\+4​T0B2\+ℱ​\(B,cmin\)\+2​ω\\displaystyle\\leq N\_\{0\}\+\\frac\{4T\_\{0\}\}\{B^\{2\}\}\+\\mathcal\{F\}\(B,c\_\{\\min\}\)\+2\\omega\+νi\+2​Bcmin\+1\+ℱ​\(B,cmin\)B\.\\displaystyle\\qquad\\qquad\+\\nu\_\{i\}\+\\frac\{\\frac\{2B\}\{c\_\{\\min\}\}\+1\+\\mathcal\{F\}\(B,c\_\{\\min\}\)\}\{B\}\.
By Lemma[2](https://arxiv.org/html/2607.13546#Thmlemma2), the regret of CATI\-UCB can be bound by:

Regret​\(𝒞,B\)≤∑i≠i†ci​Δi​𝔼​\[Ni,T𝒞,B\]\+μi†∗ci†\+∑i∈\[N\]νi​μi∗\\displaystyle\\text\{Regret\}\(\\mathcal\{C\},B\)\\leq\\sum\_\{i\\neq i^\{\\dagger\}\}c\_\{i\}\\Delta\_\{i\}\\mathbb\{E\}\[N\_\{i,T\_\{\\mathcal\{C\},B\}\}\]\+\\frac\{\\mu^\{\*\}\_\{i^\{\\dagger\}\}\}\{c\_\{i^\{\\dagger\}\}\}\+\\sum\_\{i\\in\[N\]\}\\nu\_\{i\}\\mu^\{\*\}\_\{i\}≤∑i≠i†ciΔi⋅\(N0\+4​T0B2\+ℱ\(B,cmin\)\+2ω\+νi\+\\displaystyle\\qquad\\leq\\sum\_\{i\\neq i^\{\\dagger\}\}c\_\{i\}\\Delta\_\{i\}\\cdot\(N\_\{0\}\+\\frac\{4T\_\{0\}\}\{B^\{2\}\}\+\\mathcal\{F\}\(B,c\_\{\\min\}\)\+2\\omega\+\\nu\_\{i\}\+2​Bcmin\+1\+ℱ​\(B,cmin\)B\)\+μi†∗ci†\+∑i∈\[N\]νiμ∗i\.∎\\displaystyle\\qquad\\frac\{\\frac\{2B\}\{c\_\{\\min\}\}\+1\+\\mathcal\{F\}\(B,c\_\{\\min\}\)\}\{B\}\)\+\\frac\{\\mu^\{\*\}\_\{i^\{\\dagger\}\}\}\{c\_\{i^\{\\dagger\}\}\}\+\\sum\_\{i\\in\[N\]\}\\nu\_\{i\}\\mu^\{\*\}\_\{i\}\.\\qed

Remark 1: Extension to Multiple Task Types\.CATI\-UCB also extends to multiple task types\. Instead of maintaining one set of statistics for each worker, we maintain separate statistics for each\(worker,task type\)\(\\text\{worker\},\\text\{task type\}\)pair\. Specifically, for each workeriiand task typemm, we maintain: \(i\) the type\-dependent participation countNi,mN\_\{i,m\}, \(ii\) the type\-dependent reward\-learning curve parameters used in the online linear prediction module, \(iii\) the type\-dependent cost estimate, and \(iv\) the corresponding change\-detection statistics for convergence identification\. Then, when a task of typemtm\_\{t\}arrives at roundtt, CATI\-UCB applies exactly the same cost\-aware UCB rule, but conditioned on the statistics associated with typemtm\_\{t\}\. After observing the reward and cost, only the selected\(i,mt\)\(i,m\_\{t\}\)pair is updated\. Hence, the core mechanism of CATI\-UCB remains unchanged; the extension simply refines the estimation granularity from worker\-level to worker\-type\-level\.

This extension is algorithmically straightforward, but its statistical efficiency decreases as the number of task types grows\. Under a fixed budget, each pair is observed less frequently, so its confidence radius,O​\(log⁡BNi,m\),O\\\!\\left\(\\sqrt\{\\frac\{\\log B\}\{N\_\{i,m\}\}\}\\right\),shrinks more slowly, while at least2​ω2\\omegaobservations are required before change detection can be performed\. Thus, infrequent task types lead to slower reward and cost estimation, delayed convergence detection, and potentially larger regret\. The current analysis therefore treats the heterogeneous\-task extension as an applicability result for a finite and relatively small number of task types; deriving an explicit task\-type\-dependent regret bound is left for future work\.

Remark 2: Extension to Combinatorial Selection\.CATI\-UCB can also be extended to a combinatorial setting in which up tommworkers are selected in each round\. In the simplest additive case, the algorithm still maintains worker\-level reward\-learning, cost\-estimation, and change\-detection statistics as in the single\-worker setting, while the action in each round becomes the selection of a feasible subset\. Then, instead of choosing the single worker with the largest estimated reward\-cost ratio, the platform chooses the subset of up tommworkers with the largest estimated reward\-cost ratios\. If the optimal subset is denoted byS∗S^\{\*\}, then for any candidate subsetSSone may define the gapΔS=∑i∈S∗μi∗−∑i∈Sμi∗,\\Delta\_\{S\}=\\sum\_\{i\\in S^\{\*\}\}\\mu\_\{i\}^\{\*\}\-\\sum\_\{i\\in S\}\\mu\_\{i\}^\{\*\},which leads to a regret decomposition of the formRegret≤∑S≠S∗ΔS​𝔼​\[NS\]\+O​\(1\)\.\\mathrm\{Regret\}\\leq\\sum\_\{S\\neq S^\{\*\}\}\\Delta\_\{S\}\\,\\mathbb\{E\}\[N\_\{S\}\]\+O\(1\)\.Since every suboptimal subset must contain at least one suboptimal worker, the number of selections of such subsets can be bounded through the number of pulls of suboptimal workers\. Thus, the same high\-level proof idea still yields a regret upper bound\.

## 6Experiment

In this section, we first evaluate CATI\-UCB on synthetic data under piecewise linear and negative exponential reward functions to validate its performance and robustness\. We then present additional experiments on hyperparameter sensitivity, heterogeneous task types, and trace\-driven real\-world data to further demonstrate the effectiveness of the proposed framework\.

### 6\.1Experimental Setup

We first introduce the baselines and experimental settings, and then describe the evaluation metrics\.

#### 6\.1\.1Baselines

We compare our proposed algorithm against the following baseline algorithms and methods:

- •Primal\-Dual\[[11](https://arxiv.org/html/2607.13546#bib.bib5)\]: a primal\-dual algorithm designed for constrained budget bandits problem\.
- •TIUCB\[[40](https://arxiv.org/html/2607.13546#bib.bib4)\]: a model selection algorithm designed for time\-increasing bandits problem\.
- •Budget\-TIUCB: a time\-increasing bandit algorithm that takes into account the constraint budget during the process, which is adapted based on\[[40](https://arxiv.org/html/2607.13546#bib.bib4)\]\.
- •UCBc\\text\{UCB\}\_\{c\}\[[16](https://arxiv.org/html/2607.13546#bib.bib14)\]: A bandit algorithm that maximizes total reward under a budget constraint by dividing the reward’s upper bound by the cost’s lower bound\.

#### 6\.1\.2Parameter Setting and Metric\.

For our proposed CATI\-UCB algorithm, we set the change detection windowω=16\\omega=16and thresholdγ=0\.2\\gamma=0\.2in all experiments\. To introduce the variability, random noise is uniformly sampled from\[−0\.05,0\.05\]\[\-0\.05,0\.05\]for the synthetic simulations and is added to both the realized reward and cost at each round\. All experiments are conducted under budget constraintsB∈\{50,100,200,400\}B\\in\\\{50,100,200,400\\\}, and each setting is repeated 20 times with independent random seeds to ensure robustness and reliability\. The reported regret is computed with respect to the same offline oracle under the corresponding budget setting, i\.e\.,

Regret​\(A,B\)=R∗​\(B\)−𝔼​\[RA,B\],\\mathrm\{Regret\}\(A,B\)=R^\{\*\}\(B\)\-\\mathbb\{E\}\[R\_\{A,B\}\],whereR∗​\(B\)R^\{\*\}\(B\)denotes the optimal expected cumulative reward achieved by an oracle that knows the reward trajectories and expected costs in advance\. Hence, the regret values quantify the gap between each online policy and the best achievable expected utility under the same budget\. We also report the mean reward, mean cost, reward\-cost ratio, stopping time, and optimal\-selection percentage for interpretability\. According to the Lemma 1, the optimal strategy is to allocate all budget to the worker with highest reward\-cost ratio\.

### 6\.2Piecewise Linear Function Data

![Refer to caption](https://arxiv.org/html/2607.13546v1/x3.png)

\(a\)Reward Functions
![Refer to caption](https://arxiv.org/html/2607.13546v1/x4.png)

\(b\)Cumulative Regret

Figure 3:Performance of Piecewise Linear FunctionTABLE I:Statistics of the Piecewise Linear Function \(Budget = 200\)r¯\\bar\{r\}c¯\\bar\{c\}r¯c¯\\frac\{\\bar\{r\}\}\{\\bar\{c\}\}τ¯\\bar\{\\tau\}\(%\)optCATI\-UCB0\.7410\.6021\.231357\.469\.66Primal\-Dual0\.7490\.6821\.097314\.858\.57TIUCB0\.7490\.6841\.095314\.258\.62Budget\-TIUCB0\.7530\.6761\.114318\.062\.26UCBc\\text\{UCB\}\_\{c\}0\.7550\.6711\.125320\.655\.95We consider a synthetic setting where each worker’s reward increases linearly and then plateaus\. As shown in Fig[3\(a\)](https://arxiv.org/html/2607.13546#S6.F3.sf1), Worker 1 starts atμ1​\(0\)=0\.55\\mu\_\{1\}\(0\)=0\.55and reachesμ1⋆=0\.70\\mu\_\{1\}^\{\\star\}=0\.70afterν1=25\\nu\_\{1\}=25selects, while Worker 2 starts atμ2​\(0\)=0\.45\\mu\_\{2\}\(0\)=0\.45and surpasses Worker 1 by reachingμ2⋆=0\.80\\mu\_\{2\}^\{\\star\}=0\.80afterν2=50\\nu\_\{2\}=50selects\. For anyi∈\{1,2\}i\\in\\\{1,2\\\}, the reward function isμi​\(t\)=μi​\(0\)\+μi⋆−μi​\(0\)νi​t\\mu\_\{i\}\(t\)=\\mu\_\{i\}\(0\)\+\\frac\{\\mu\_\{i\}^\{\\star\}\-\\mu\_\{i\}\(0\)\}\{\\nu\_\{i\}\}tfort<νit<\\nu\_\{i\}andμi​\(t\)=μi⋆\\mu\_\{i\}\(t\)=\\mu\_\{i\}^\{\\star\}fort≥νit\\geq\\nu\_\{i\}\.

To evaluate the change\-point detection module inCATI\-UCB, we also visualize the estimated reward curves under two window sizes \(w1,w2\)\. When the difference between these two estimates exceeds a detection threshold, the algorithm detects a change point, which is marked by the red dot\. After detection, the algorithm resets the selecting statistics, resulting in a sharp spike in the estimated reward due to setting the countNi,t=1N\_\{i,t\}=1\. As more observations accumulate, the estimate stabilizes and gradually converges to the true post\-change value\. A similar pattern is observed for Worker 2, showing the robustness of our change\-point detection scheme\.

Fig[3\(b\)](https://arxiv.org/html/2607.13546#S6.F3.sf2)reports the cumulative regret with 2 workers as budget increases\.CATI\-UCBconsistently outperforms all baselines and achieves sublinear regret\. Except for TIUCB, all other algorithms can achieve sublinear regret because they are also designed to balance reward and cost\. Note that none of these algorithms have theoretical guarantees under the increasing\-then\-converge with budget constraint bandit problem\. WhileUCBc\\text\{UCB\}\_\{c\}performs well due to cost\-awareness, it fails to model reward dynamics and underperforms our method\. TIUCB performs worst, as it disregards budget constraints and tends to select high\-cost workers with large empirical rewards, exhausting budget prematurely\.

We further report mean rewardr¯\\bar\{r\}, mean costc¯\\bar\{c\}, reward\-cost ratior¯/c¯\\bar\{r\}/\\bar\{c\}, stopping timeτ\\tau, and optimal selecting percentage \(%opt\) forB=200B=200in Table[I](https://arxiv.org/html/2607.13546#S6.T1)\. Table[I](https://arxiv.org/html/2607.13546#S6.T1)shows that TIUCB has the largest mean costs for selecting the worker of these algorithms, which leads to the smallest termination time\.CATI\-UCBachieves the bestr¯/c¯\\bar\{r\}/\\bar\{c\}, the longest task horizon, and the highest optimal selection rate, showing its ability to balance reward and cost while adapting to worker quality\.

### 6\.3Negative Exponential Function Data

Beyond the piecewise linear setting, prior studies have suggested that a worker’s learning curve can also be well captured by a negative exponential function\[[39](https://arxiv.org/html/2607.13546#bib.bib58)\]\. To validate the robustness of our algorithm under alternative reward structures, we conduct additional experiments where each worker’s expected reward follows the negative exponential function\.

We use two sets of synthetic reward functions to simulate models with increasing\-then\-converging performance patterns\. The formats of two functions are as follows:

Fexp=\{f​\(t\)=c​\(1−e−a​t\)\}, and\\displaystyle F\_\{\\text\{exp\}\}=\\\{f\(t\)=c\(1\-e^\{\-at\}\)\\\}\\quad\\text\{, and\}Fpoly=\{f​\(t\)=c​\(1−b​\(t\+b1/ρ\)−ρ\)\}\.\\displaystyle F\_\{\\text\{poly\}\}=\\\{f\(t\)=c\(1\-b\{\(t\+b^\{1/\\rho\}\)\}^\{\-\\rho\}\)\\\}\.These two families of functions are able to represent the general increasing\-then\-converging pattern of different shapes\[[27](https://arxiv.org/html/2607.13546#bib.bib15),[40](https://arxiv.org/html/2607.13546#bib.bib4)\], where functions originating fromFexpF\_\{\\text\{exp\}\}exhibit a rapid increase before converging, while those fromFpolyF\_\{\\text\{poly\}\}may display much slower growth rates\.

![Refer to caption](https://arxiv.org/html/2607.13546v1/x5.png)

\(a\)Reward Functions
![Refer to caption](https://arxiv.org/html/2607.13546v1/x6.png)

\(b\)Cumulative Regret

Figure 4:Performance of Negative Exponential FunctionTABLE II:Statistics of The Negative Exponential Function \(Budget = 200\)r¯\\bar\{r\}c¯\\bar\{c\}r¯c¯\\frac\{\\bar\{r\}\}\{\\bar\{c\}\}τ¯\\bar\{\\tau\}\(%\)optCATI\-UCB0\.5840\.3561\.643562\.285\.80Primal\-Dual0\.6450\.4941\.305404\.851\.43TIUCB0\.6520\.5081\.282393\.047\.63Budget\-TIUCB0\.6710\.5451\.231367\.238\.77UCBc\\text\{UCB\}\_\{c\}0\.6010\.3961\.518504\.875\.79![Refer to caption](https://arxiv.org/html/2607.13546v1/x7.png)

\(a\)Reward Functions
![Refer to caption](https://arxiv.org/html/2607.13546v1/x8.png)

\(b\)Cumulative Regret

Figure 5:Performance of 12\-worker BanditsTABLE III:Statistics of the 12\-worker Time increasing Bandit \(Budget = 200\)r¯\\bar\{r\}c¯\\bar\{c\}r¯c¯\\frac\{\\bar\{r\}\}\{\\bar\{c\}\}τ¯\\bar\{\\tau\}\(%\)optCATI\-UCB0\.4570\.3791\.204784\.034\.29Primal\-Dual0\.3030\.2731\.108732\.420\.56TIUCB0\.4340\.3841\.131520\.29\.57Budget\-TIUCB0\.2710\.2551\.065527\.418\.29UCBc\\text\{UCB\}\_\{c\}0\.4180\.3791\.106528\.430\.02#### 6\.3\.12\-worker Bandits

We conducted a two\-worker bandit experiment witha,b,c,βa,b,c,\\betaset to0\.0001,1\.0,0\.80\.0001,1\.0,0\.8and0\.10\.1, and the reward values shown in Fig[4\(a\)](https://arxiv.org/html/2607.13546#S6.F4.sf1)\. To test the trade\-off between reward and cost, we assigned the exponential worker a high stable reward and 0\.7 cost, and the polynomial worker a lower reward and 0\.3 cost\. Although the reward is no longer piecewise linear, CATI\-UCB can still track the dynamics by fitting early\-stage observations and applying change\-point detection\. As shown in the left panel, the algorithm identifies convergence points when estimates from two window sizes diverge, triggering a reset\. This causes a brief spike due toNi,t=1N\_\{i,t\}=1, which quickly stabilizes with more samples\.

Fig\.[4\(b\)](https://arxiv.org/html/2607.13546#S6.F4.sf2)and Table[II](https://arxiv.org/html/2607.13546#S6.T2)also shows that our findings are consistent with the piecewise linear case: CATI\-UCB consistently achieves the lowest cumulative regret across all budget levels, especially when the budget is large and the full learning dynamics unfold\. Compared toUCBc\\text\{UCB\}\_\{c\}, which balances reward and cost but cannot adapt to time\-evolving reward structures, CATI\-UCB benefits from modeling the non\-stationary growth and transitions\. TIUCB again performs worst, as it does not account for budget constraints and tends to over\-select costly workers based on short\-term empirical averages\. Due to the smoother reward transitions and slower initial growth, all algorithms exhibit slightly higher regret compared to the piecewise case\. Nonetheless, CATI\-UCB retains a clear advantage under this more realistic and challenging reward evolution\.

![Refer to caption](https://arxiv.org/html/2607.13546v1/x9.png)

\(a\)Window sizeww
![Refer to caption](https://arxiv.org/html/2607.13546v1/x10.png)

\(b\)Thresholdγ\\gamma

Figure 6:Sensitivity of CATI\-UCB to Hyperparameters
#### 6\.3\.212\-worker Bandits

In order to generalize the effectiveness of our experimental results, we also compare the performance of each algorithm on 12 workers\. Then the value ofa,c,ρ∈\(0,1\]a,c,\\rho\\in\(0,1\]andb∈ℝ≥0b\\in\\mathbb\{R\}\\geq 0are selected randomly and the results are shown in Fig[5\(b\)](https://arxiv.org/html/2607.13546#S6.F5.sf2)and Table[III](https://arxiv.org/html/2607.13546#S6.T3)\. As the number of workers increases, each algorithm needs to spend more cost to explore the worker, resulting in a larger regret, so the total regret is divided by 10 to better show the performance of each model\. Table[III](https://arxiv.org/html/2607.13546#S6.T3)shows that the selecting percentage of the optimal \(%opt\) of each algorithm decreases than that of 2\-worker bandit setting, further verifying that as the number of workers increases, the algorithm spends more cost to learn the suboptimal worker\. However, CATI\-UCB still achieves the highest percentage of selecting the optimal worker and the highestr¯c¯\\frac\{\\bar\{r\}\}\{\\bar\{c\}\}\. TIUCB achieves the smallest percentage of selecting the optimal worker and the smallestr¯c¯\\frac\{\\bar\{r\}\}\{\\bar\{c\}\}, which is consistent with the CATI\-UCB outperform all baselines in Fig[5\(b\)](https://arxiv.org/html/2607.13546#S6.F5.sf2)\.

### 6\.4Sensitivity to Change\-Detection Hyperparameters

We next examine the sensitivity of CATI\-UCB to the two hyperparameters in the change\-detection module, namely the window sizeω\\omegaand the thresholdγ\\gamma\. Unless otherwise specified, all sensitivity experiments in this subsection are conducted under the same*12\-arm synthetic setting*as in the main experiments\. We report the average final regret over repeated runs\.

Fig\.[6\(a\)](https://arxiv.org/html/2607.13546#S6.F6.sf1)shows the effect of varying the window size overω∈\{22,23,…,27\}\\omega\\in\\\{2^\{2\},2^\{3\},\\ldots,2^\{7\}\\\}\. The result exhibits a clear non\-monotonic pattern\. Whenω\\omegais too small, the detector becomes overly sensitive to local fluctuations, which leads to unstable resets and higher regret\. Whenω\\omegais too large, detection becomes delayed, so the algorithm adapts too slowly after the reward trend changes\. The best result in this experiment is achieved aroundω=25\\omega=2^\{5\}, while moderate window sizes such asω∈\{16,32\}\\omega\\in\\\{16,32\\\}clearly outperform the extreme choices\. In the main experiments, we useω=16\\omega=16as a representative moderate setting that performs competitively while preserving a shorter reaction horizon\.

Fig\.[6\(b\)](https://arxiv.org/html/2607.13546#S6.F6.sf2)reports the effect of varying the threshold overγ∈\{0\.01,0\.02,0\.05,0\.1,0\.2,0\.4\}\\gamma\\in\\\{0\.01,0\.02,0\.05,0\.1,0\.2,0\.4\\\}\. Compared with the window\-size study, the regret varies only mildly across a broad range of threshold values, indicating that CATI\-UCB is fairly robust to the exact choice ofγ\\gammaonce it is set in a reasonable interval\. This is also consistent with the algorithmic mechanism: since the detection decision is based on averaged statistics from two windows, the smoothing induced byω\\omegaalready stabilizes the detector, making performance less sensitive to the precise threshold value\. In our experiment, moderate thresholds aroundγ∈\[0\.1,0\.2\]\\gamma\\in\[0\.1,0\.2\]provide slightly better performance, which is why we useγ=0\.2\\gamma=0\.2in the main text\.

### 6\.5Heterogeneous Task Types

To validate that CATI\-UCB extends naturally beyond the homogeneous\-task setting, we further consider a heterogeneous\-task scenario with two task types\. In this setting, each worker has task\-type\-dependent reward dynamics, so the algorithm maintains separate reward\-learning, cost\-estimation, and change\-detection statistics for each\(worker,task type\)\(\\text\{worker\},\\text\{task type\}\)pair, as discussed in the above remark on multiple task types\.

We first consider a toy setting with22workers and22task types\. Fig\.[7](https://arxiv.org/html/2607.13546#S6.F7)shows representative type\-specific reward trajectories under both exponential\-growth and polynomial\-growth patterns\. The figure also illustrates the two window\-based prediction curves and the detected turning point for each worker–task pair\. We observe that CATI\-UCB still tracks the reward evolution accurately and successfully detects the transition from the growth phase to the saturation phase for different task types\. Then we consider a larger setting with1212workers and22task types\. The corresponding type\-specific reward trajectories are shown in Fig\.[8](https://arxiv.org/html/2607.13546#S6.F8)\. Compared with the22\-worker case, the platform now needs to learn many more worker–task pairs, so the exploration burden is higher under the same budget\.

Since, in the heterogeneous\-task setting, the realized reward depends on the task\-type sequence and each worker has type\-dependent reward functions, we report cumulative reward instead of a single regret quantity\. Fig\.[9](https://arxiv.org/html/2607.13546#S6.F9)shows the cumulative reward for both settings\. CATI\-UCB achieves the highest cumulative reward in both cases\. At the same time, the overall reward in the1212\-worker case is lower than that in the22\-worker case under the same budget, since more budget must be spent on exploration to learn the task\-type\-dependent reward functions\. These results show that the proposed framework remains effective beyond the homogeneous\-task case and continues to outperform the baselines in heterogeneous\-task settings\.

![Refer to caption](https://arxiv.org/html/2607.13546v1/x11.png)Figure 7:Type\-Specific Reward Trajectories in the 2\-Arm Setting![Refer to caption](https://arxiv.org/html/2607.13546v1/x12.png)Figure 8:Type\-Specific Reward Trajectories in the 12\-Arm Setting![Refer to caption](https://arxiv.org/html/2607.13546v1/x13.png)

\(a\)2\-Arm Setting
![Refer to caption](https://arxiv.org/html/2607.13546v1/x14.png)

\(b\)12\-Arm Setting

Figure 9:Cumulative Reward in the Heterogeneous Task\-Types Setting
### 6\.6Trace\-Driven Evaluation Based on a Real\-World Dataset

![Refer to caption](https://arxiv.org/html/2607.13546v1/x15.png)

\(a\)Empirical Reward Trajectories
![Refer to caption](https://arxiv.org/html/2607.13546v1/x16.png)

\(b\)Cumulative Regret

Figure 10:Trace\-Driven Evaluation Based on the Topcoder DatasetTo complement the synthetic experiments, we construct a trace\-driven benchmark based on a real\-world Topcoder dataset\[[39](https://arxiv.org/html/2607.13546#bib.bib58)\]\. Since the original raw records are not publicly available, we follow the skill\-improvement pipeline in\[[39](https://arxiv.org/html/2607.13546#bib.bib58)\]and build empirical reward trajectories from the published performance trends\. Specifically, we use the reported worker\-performance curves to fit representative reward traces, and then sort each worker’s scores chronologically to form an empirical reward trajectory\.

Fig\. 7\(a\) shows representative empirical reward trajectories for two workers\. The blue circles denote empirical reward observations, while the pink and gray dashed curves denote least\-squares prediction trajectories under two detection windows\. The orange dots mark the turning points detected by CATI\-UCB\. Compared with the synthetic setting, these real\-data\-driven traces are substantially noisier and may contain multiple local turning points, which makes convergence detection more challenging\.

Fig\. 7\(b\) reports the corresponding budgeted online\-selection result\. CATI\-UCB achieves the smallest regret for moderate and large budgets, indicating that the proposed framework remains effective when the reward process is derived from real worker\-performance data\. At the smallest budget, the empirical reward sequence is still highly unstable and the detector has limited history, so CATI\-UCB is slightly less favorable than some baselines\. As the budget increases and more sequential observations become available, CATI\-UCB becomes consistently superior\. These trace\-driven experiments thus provide direct evidence that CATI\-UCB is not limited to purely synthetic environments\.

## 7Conclusion

In this paper, we studied budget\-constrained task allocation under structured worker learning, where each worker’s reward follows an unknown, increasing\-then\-converging trajectory with fixed costs\. To address this, we proposed CATI\-UCB, a cost\-aware algorithm that estimates reward and cost, detects learning convergence via change\-point detection, and adaptively allocates budget\. We provide theoretical guarantees and show that CATI\-UCB achieves sublinear regret and outperforms baselines across synthetic and real\-world settings\. An important direction for future work is to characterize the regret dependence on the number and arrival frequencies of task types, and to improve statistical scalability through parameter sharing or contextual generalization across related task types\.

## References

- \[1\]\(2016\)An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives\.InConference on Learning Theory,pp\. 4–18\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p3.1)\.
- \[2\]S\. Agrawal and N\. R\. Devanur\(2014\)Bandits with concave rewards and convex knapsacks\.InProceedings of the fifteenth ACM conference on Economics and computation,pp\. 989–1006\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p3.1)\.
- \[3\]M\. Babaioff, S\. Dughmi, R\. Kleinberg, and A\. Slivkins\(2015\)Dynamic pricing with limited supply\.ACM New York, NY, USA\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p3.1)\.
- \[4\]A\. Badanidiyuru, R\. Kleinberg, and Y\. Singer\(2012\)Learning on a budget: posted price mechanisms for online procurement\.InProceedings of the 13th ACM conference on electronic commerce,pp\. 128–145\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p3.1)\.
- \[5\]A\. Badanidiyuru, R\. Kleinberg, and A\. Slivkins\(2018\)Bandits with knapsacks\.Journal of the ACM \(JACM\)65\(3\),pp\. 1–55\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p3.1)\.
- \[6\]O\. Besbes, Y\. Gur, and A\. Zeevi\(2014\)Stochastic multi\-armed\-bandit problem with non\-stationary rewards\.Advances in neural information processing systems27\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p2.1)\.
- \[7\]Y\. Cao, Z\. Wen, B\. Kveton, and Y\. Xie\(2019\)Nearly optimal adaptive procedure with change detection for piecewise\-stationary bandit\.InThe 22nd International Conference on Artificial Intelligence and Statistics,pp\. 418–427\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p2.1)\.
- \[8\]F\. Carrera, S\. Guerin, and J\. Thorp\(2013\)By the people, for the people: the crowdsourcing of” streetbump”: an automatic pothole mapping app\.The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences40,pp\. 19–23\.Cited by:[§1](https://arxiv.org/html/2607.13546#S1.p3.1)\.
- \[9\]Y\. Chen, S\. Zhang, Y\. Jin, Z\. Qian, M\. Xiao, N\. Chen, and Z\. Ma\(2022\)Learning for crowdsourcing: online dispatch for video analytics with guarantee\.InIEEE INFOCOM 2022\-IEEE Conference on Computer Communications,pp\. 1908–1917\.Cited by:[§1](https://arxiv.org/html/2607.13546#S1.p3.1),[§2](https://arxiv.org/html/2607.13546#S2.p1.1)\.
- \[10\]R\. Combes, C\. Jiang, and R\. Srikant\(2015\)Bandits with budgets: regret lower bounds and optimal algorithms\.ACM SIGMETRICS Performance Evaluation Review43\(1\),pp\. 245–257\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p3.1)\.
- \[11\]P\. R\. Diaz, J\. A\. Killian, L\. Xu, A\. S\. Suggala, A\. Taneja, and M\. Tambe\(2023\)Flexible budgets in restless bandits: a primal\-dual algorithm for efficient budget allocation\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.37,pp\. 12103–12111\.Cited by:[1st item](https://arxiv.org/html/2607.13546#S6.I1.i1.p1.1)\.
- \[12\]G\. Gao, H\. Huang, M\. Xiao, J\. Wu, Y\. Sun, and Y\. Du\(2021\)Budgeted unknown worker recruitment for heterogeneous crowdsensing using cmab\.IEEE Transactions on Mobile Computing21\(11\),pp\. 3895–3911\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p1.1)\.
- \[13\]G\. Gao, J\. Wu, Z\. Yan, M\. Xiao, and G\. Chen\(2019\)Unknown worker recruitment with budget and covering constraints for mobile crowdsensing\.In2019 IEEE 25th International Conference on Parallel and Distributed Systems \(ICPADS\),pp\. 539–547\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p1.1)\.
- \[14\]A\. Garivier and E\. Moulines\(2011\)On upper\-confidence bound policies for switching bandit problems\.InInternational conference on algorithmic learning theory,pp\. 174–188\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p2.1)\.
- \[15\]H\. Heidari, M\. J\. Kearns, and A\. Roth\(2016\)Tight policy regret bounds for improving and decaying bandits\.\.InIJCAI,pp\. 1562–1570\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p2.1)\.
- \[16\]M\. Heyden, V\. Arzamasov, E\. Fouché, and K\. Böhm\(2024\)Budgeted multi\-armed bandits with asymmetric confidence intervals\.InProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,pp\. 1073–1084\.Cited by:[4th item](https://arxiv.org/html/2607.13546#S6.I1.i4.p1.1)\.
- \[17\]Y\. Huang, Q\. Liu, and J\. Xu\(2024\)Adversarial combinatorial bandits with switching cost and arm selection constraints\.InIEEE INFOCOM 2024\-IEEE Conference on Computer Communications,pp\. 371–380\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p3.1)\.
- \[18\]Y\. Huang, L\. Zhang, and J\. Xu\(2023\)Adversarial group linear bandits and its application to collaborative edge inference\.InIEEE INFOCOM 2023\-IEEE Conference on Computer Communications,pp\. 1–10\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p2.1)\.
- \[19\]Y\. Huang, L\. Zhang, and J\. Xu\(2025\)Learning the optimal path and dnn partition for collaborative edge inference\.IEEE Transactions on Mobile Computing\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p2.1)\.
- \[20\]N\. Immorlica, K\. Sankararaman, R\. Schapire, and A\. Slivkins\(2022\)Adversarial bandits with knapsacks\.Journal of the ACM69\(6\),pp\. 1–47\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p3.1)\.
- \[21\]N\. Levine, K\. Crammer, and S\. Mannor\(2017\)Rotting bandits\.Advances in neural information processing systems30\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p2.1)\.
- \[22\]X\. Li, Y\. Zhao, X\. Zhou, and K\. Zheng\(2020\)Consensus\-based group task assignment with social impact in spatial crowdsourcing\.Data Science and Engineering5\(4\),pp\. 375–390\.Cited by:[§1](https://arxiv.org/html/2607.13546#S1.p3.1)\.
- \[23\]X\. Li, C\. Sun, and Y\. Ye\(2021\)The symmetry between arms and knapsacks: a primal\-dual approach for bandits with knapsacks\.InInternational Conference on Machine Learning,pp\. 6483–6492\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p3.1)\.
- \[24\]S\. Liu, J\. Jiang, and X\. Li\(2022\)Non\-stationary bandits with knapsacks\.Advances in Neural Information Processing Systems35,pp\. 16522–16532\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p3.1)\.
- \[25\]H\. Ma, D\. Zhao, and P\. Yuan\(2014\)Opportunities in mobile crowd sensing\.IEEE Communications Magazine52\(8\),pp\. 29–35\.Cited by:[§1](https://arxiv.org/html/2607.13546#S1.p1.1)\.
- \[26\]N\. Maisonneuve, M\. Stevens, M\. E\. Niessen, and L\. Steels\(2009\)NoiseTube: measuring and mapping noise pollution with mobile phones\.InInformation Technologies in Environmental Engineering: Proceedings of the 4th International ICSC Symposium Thessaloniki, Greece, May 28\-29, 2009,pp\. 215–228\.Cited by:[§1](https://arxiv.org/html/2607.13546#S1.p3.1)\.
- \[27\]A\. M\. Metelli, F\. Trovo, M\. Pirola, and M\. Restelli\(2022\)Stochastic rising bandits\.InInternational Conference on Machine Learning,pp\. 15421–15457\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p2.1),[§6\.3](https://arxiv.org/html/2607.13546#S6.SS3.p2.2)\.
- \[28\]Y\. Ouyang, F\. Zeng, N\. N\. Xiong, A\. Liu, and W\. Pedrycz\(2025\)MWRS: a mab\-based worker recruitment scheme with tripartite stackelberg game for reliable mobile crowdsensing\.IEEE Transactions on Mobile Computing24\(7\),pp\. 5665–5680\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p1.1)\.
- \[29\]A\. Rangi, M\. Franceschetti, and L\. Tran\-Thanh\(2018\)Unifying the stochastic and the adversarial bandits with knapsack\.arXiv preprint arXiv:1811\.12253\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p3.1)\.
- \[30\]Y\. Russac, C\. Vernade, and O\. Cappé\(2019\)Weighted linear bandits for non\-stationary environments\.Advances in Neural Information Processing Systems32\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p2.1)\.
- \[31\]J\. Seznec, P\. Menard, A\. Lazaric, and M\. Valko\(2020\)A single algorithm for both restless and rested rotting bandits\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 3784–3794\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p2.1)\.
- \[32\]A\. Singla and A\. Krause\(2013\)Truthful incentives in crowdsourcing tasks using regret minimization mechanisms\.InProceedings of the 22nd international conference on World Wide Web,pp\. 1167–1178\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p3.1)\.
- \[33\]H\. Song, P\. Li, R\. Du, H\. Yu, W\. Huang, L\. Nie, H\. Bao, and Q\. Liu\(2025\)Unknown task selection and worker recruitment using two\-stage multi\-armed bandit in crowdsensing\.IEEE Internet of Things Journal\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p1.1)\.
- \[34\]S\. Su, L\. Wang, Z\. Yu, X\. Xia, L\. Ma, F\. Xiong, Y\. Zhang, and B\. Guo\(2025\)Crowdsensing for emergency response in unknown environments: a rapid strategic sensing approach\.IEEE Transactions on Mobile Computing\.Cited by:[§1](https://arxiv.org/html/2607.13546#S1.p3.1),[§2](https://arxiv.org/html/2607.13546#S2.p1.1)\.
- \[35\]J\. Tang, K\. Fan, W\. Xie, F\. Han, Z\. Qu, A\. Liu, N\. N\. Xiong, S\. Zhang, and T\. Wang\(2023\)BTV\-cmab: a bi\-directional trust verification\-based combinatorial multiarmed bandit scheme for mobile crowdsourcing\.IEEE Internet of Things Journal11\(2\),pp\. 1925–1938\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p1.1)\.
- \[36\]C\. Tekin and M\. Liu\(2012\)Online learning of rested and restless bandits\.IEEE Transactions on Information Theory58\(8\),pp\. 5588–5611\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p2.1)\.
- \[37\]Y\. Tong, J\. She, B\. Ding, L\. Wang, and L\. Chen\(2016\)Online mobile micro\-task allocation in spatial crowdsourcing\.In2016 IEEE 32Nd international conference on data engineering \(ICDE\),pp\. 49–60\.Cited by:[§1](https://arxiv.org/html/2607.13546#S1.p3.1)\.
- \[38\]Z\. Wang, Y\. Huang, X\. Wang, J\. Ren, Q\. Wang, and L\. Wu\(2020\)Socialrecruiter: dynamic incentive mechanism for mobile crowdsourcing worker recruitment with social networks\.IEEE Transactions on Mobile Computing20\(5\),pp\. 2055–2066\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p1.1)\.
- \[39\]Z\. Wang, H\. Sun, Y\. Fu, and L\. Ye\(2017\)Recommending crowdsourced software developers in consideration of skill improvement\.InProceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering \(ASE\),pp\. 717–728\.Cited by:[§1](https://arxiv.org/html/2607.13546#S1.p2.1),[§2](https://arxiv.org/html/2607.13546#S2.p1.1),[§3](https://arxiv.org/html/2607.13546#S3.p4.8),[§6\.3](https://arxiv.org/html/2607.13546#S6.SS3.p1.1),[§6\.6](https://arxiv.org/html/2607.13546#S6.SS6.p1.1)\.
- \[40\]Y\. Xia, F\. Kong, T\. Yu, L\. Guo, R\. A\. Rossi, S\. Kim, and S\. Li\(2024\)Which llm to play? convergence\-aware online model selection with time\-increasing bandits\.InProceedings of the ACM on Web Conference 2024,pp\. 4059–4070\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p2.1),[§4\.2\.2](https://arxiv.org/html/2607.13546#S4.SS2.SSS2.p4.3),[§5](https://arxiv.org/html/2607.13546#S5.4.p1.2),[2nd item](https://arxiv.org/html/2607.13546#S6.I1.i2.p1.1),[3rd item](https://arxiv.org/html/2607.13546#S6.I1.i3.p1.1),[§6\.3](https://arxiv.org/html/2607.13546#S6.SS3.p2.2),[Proposition 1](https://arxiv.org/html/2607.13546#Thmproposition1.p1.1.1)\.
- \[41\]H\. Zhao, M\. Xiao, J\. Wu, Y\. Xu, H\. Huang, and S\. Zhang\(2020\)Differentially private unknown worker recruitment for mobile crowdsensing using multi\-armed bandits\.IEEE Transactions on Mobile Computing20\(9\),pp\. 2779–2794\.Cited by:[§2](https://arxiv.org/html/2607.13546#S2.p1.1)\.
- \[42\]Q\. Zhou, X\. Zhang, and Z\. Yang\(2024\)Unknown worker recruitment with long\-term incentive in mobile crowdsensing\.IEEE Transactions on Mobile Computing\.Cited by:[§1](https://arxiv.org/html/2607.13546#S1.p3.1),[§2](https://arxiv.org/html/2607.13546#S2.p1.1)\.