Learning When to Automate: Queue Control in Human-AI Service Systems

# Learning When to Automate: Queue Control in Human-AI Service Systems
Source: [https://arxiv.org/html/2607.06017](https://arxiv.org/html/2607.06017)
Giovanni MontanariMarco ScarsiniDepartment of Economics and Financial Markets, Luiss UniversityVianney PerchetFairPlay Joint Team, Inria, FranceCriteo AI Lab, Paris, FranceCREST, ENSAE, Institut Polytechnique de Paris

###### Abstract

We study a human\-AI service system in which tasks arrive sequentially and are processed through a two\-stage architecture: an automated chatbot followed, when necessary, by a human agent\. We considerTTsequentially arriving tasks, each belonging to one ofKKheterogeneous types\. For each task the decision maker chooses how many resources to allocate to the chatbot, whose type\-dependent success probabilities are initially unknown\. Tasks not resolved by the chatbot enter type\-dependent human\-service queues, where they are processed by a human agent with unknown service rates\. This model captures a central tradeoff in hybrid service systems: relying more on automation reduces human congestion but increases chatbot costs, while insufficient automation may overload the human agent\. We propose theUCB\-DPPpolicy, which combines Upper Confidence Bounds with Drift\-Plus\-Penalty control to learn the unknown parameters of the system while making queue\-aware decisions\. We prove thatUCB\-DPPachieves regret𝒪~​\(K​T\)\\widetilde\{\\mathcal\{O\}\}\(K\\sqrt\{T\}\)and guarantees mean\-rate stability of the human\-service queues\. Simulations on synthetic instances show that the proposed policy outperforms natural baselines\.

## 1Introduction

The increasing deployment of large language models \(LLMs\) in service systems raises a fundamental question: how should automated agents and human operators be jointly coordinated? In many practical settings, an LLM\-based assistant can resolve part of the incoming workload quickly, but its performance depends on the amount of computational or operational resources allocated to it and it may still fail on difficult requests\. Human agents, on the other hand, are often more reliable but slower and capacity\-constrained\. A central challenge is therefore to exploit automation while controlling both operational costs and congestion in the human\-service system\.

We study this challenge through an online learning and queueing\-control model for human\-AI service systems\. Tasks arrive sequentially over a finite horizonTTand belong to one ofKKheterogeneous types, representing different levels of difficulty or service requirements\. Each task is first processed by a chatbot\. The decision maker chooses a cost level for the chatbot, interpreted as the amount of resources devoted to automated resolution\. A higher cost increases the probability that the chatbot resolves the task, while tasks not resolved automatically are routed to a type\-dependent human queue\. The human agent can serve only one queue at a time, so the controller must also decide how to allocate limited human service capacity across task types\.

The key feature of this setting is that automation and human scheduling control two different sides of the queueing system\. The chatbot cost decisions shape the arrival process of the human queues: using more automation reduces future human workload but increases immediate chatbot costs\. Scheduling decisions, instead, determine the departure process by allocating human service capacity across queues\. Thus, automation and human service cannot be optimized independently: they must be coordinated over time in response to the current congestion state\.

Another key difficulty is that the platform typically does not know in advance how different task types will be handled by the chatbot and by the human agent\. Empirical evidence suggests that the relative effectiveness of AI and human service depends on task complexity\[[33](https://arxiv.org/html/2607.06017#bib.bib36)\], while recent work on generative AI highlights that model performance may vary sharply across tasks that appear similar\[[7](https://arxiv.org/html/2607.06017#bib.bib37)\]\. These observations motivate treating chatbot effectiveness and human service rates as task\-dependent and initially unknown\. The platform must therefore learn them from experience while simultaneously deciding how much to rely on automation and how to allocate limited human service capacity\.

### 1\.1Motivation

The proposed framework is motivated by a broad class of human\-AI service platforms in which automation and human intervention coexist\. A canonical example is customer support, where incoming requests are first handled by a chatbot and escalated to a human operator only when the automated response is insufficient\. This hybrid architecture is increasingly relevant in practice: chatbot\-based customer service can generate economic value for firms\[[9](https://arxiv.org/html/2607.06017#bib.bib10)\], but empirical studies also show that user adoption and satisfaction depend on factors such as communication quality, trust, privacy concerns, anthropomorphism, and the quality of the interaction in failure scenarios\[[27](https://arxiv.org/html/2607.06017#bib.bib11),[28](https://arxiv.org/html/2607.06017#bib.bib12),[14](https://arxiv.org/html/2607.06017#bib.bib13),[15](https://arxiv.org/html/2607.06017#bib.bib14),[6](https://arxiv.org/html/2607.06017#bib.bib15),[3](https://arxiv.org/html/2607.06017#bib.bib16),[13](https://arxiv.org/html/2607.06017#bib.bib17)\]\. These findings suggest that replacing human service entirely with automation is often not desirable; instead, effective systems should decide when to rely on the chatbot and when to route unresolved requests to human agents\.

The same two\-stage structure appears beyond customer support\. In corporate IT helpdesks, automated assistants may resolve routine access or software issues, while more complex tickets are routed to human technicians\. In fraud detection, automated screening systems may clear routine transactions, whereas uncertain cases are forwarded to human analysts for manual review\. In all these examples, the platform must jointly determine how much to rely on automation and how to allocate limited human service capacity across heterogeneous queues, while learning the effectiveness of both components online\.

### 1\.2Contributions

The first contribution is a queueing model for human\-AI service platforms in which automation decisions and human scheduling decisions are coupled\. Chatbot decisions endogenously control the residual arrival process into the human queues, while scheduling decisions determine how the human agent serves the resulting queues\. This two\-stage structure captures a common workflow in modern service systems and differs from standard queueing\-control models in which the arrival process is typically exogenous\.

The second contribution is algorithmic\. We propose theUCB\-DPPpolicy, which combines Upper Confidence Bounds \(UCB\) with Drift\-Plus\-Penalty \(DPP\) control\. The policy uses optimistic estimates of the unknown chatbot success probabilities and human service rates, while making queue\-aware decisions through a weighted drift\-plus\-penalty objective\. A key difficulty is that DPP is traditionally used to obtain asymptotic stability and time\-average optimality guarantees, whereas here it must be adapted to a finite\-horizon regret analysis\. Moreover, learning errors affect both the arrival and the service sides of the queueing system\.

The third contribution is theoretical\. We prove thatUCB\-DPPachieves a sublinear regret bound of order𝒪~​\(K​T\)\\widetilde\{\\mathcal\{O\}\}\(K\\sqrt\{T\}\)and ensures mean\-rate stability of the human\-service queues\. The analysis combines UCB concentration bounds with Lyapunov\-drift arguments and controls estimation errors weighted by the queue backlog\. Finally, we complement the theoretical results with simulations on synthetic instances, showing thatUCB\-DPPoutperforms natural baseline policies\.

### 1\.3Related Work

##### Human\-AI service systems and chatbot escalation\.

A growing literature studies service systems in which automated agents and human operators jointly handle customer requests\. Hybrid customer\-service architectures combining virtual agents and human operators have been proposed and analyzed from empirical and multidisciplinary perspectives\[[17](https://arxiv.org/html/2607.06017#bib.bib1),[26](https://arxiv.org/html/2607.06017#bib.bib2)\]\. Closer to the service\-operations literature, human\-AI service systems have been studied in settings with strategic customers, with a focus on whether the use of AI should be mandated\[[34](https://arxiv.org/html/2607.06017#bib.bib3)\]\. Related work also analyzes human\-AI interaction in congested service systems, but in settings where AI assists human decision\-making rather than acting as a first\-stage service channel\[[21](https://arxiv.org/html/2607.06017#bib.bib4)\]\.

A related line of work studies the machine–human handoff problem in dialogue systems\. This literature considers the task of predicting when a chatbot conversation should be transferred to a human agent\[[22](https://arxiv.org/html/2607.06017#bib.bib5)\], jointly models handoff prediction and service satisfaction\[[23](https://arxiv.org/html/2607.06017#bib.bib6)\], and incorporates cost\-aware considerations into handoff decisions\[[37](https://arxiv.org/html/2607.06017#bib.bib7)\]\. Other works study intent recognition mechanisms for identifying requests to switch from chatbot to human service\[[31](https://arxiv.org/html/2607.06017#bib.bib8)\]\. Recent field evidence from large\-scale customer\-service operations further highlights the operational importance of human\-in\-the\-loop interventions in agentic AI systems\[[32](https://arxiv.org/html/2607.06017#bib.bib9)\]\.

This work takes a different perspective by combining online learning with queue control in a human\-AI service model\. The platform must jointly minimize chatbot costs and stabilize the human\-service queues, while learning both the chatbot success probabilities and the human service rates across task types\. We propose a learning policy for this setting and provide a finite\-time regret analysis, showing how automation decisions and human\-capacity allocation can be optimized jointly under uncertainty\.

##### Queueing control and DPP\.

The present work is also related to the classical literature on queueing control and Lyapunov\-based scheduling\. A central line of work studies queue\-length\-based scheduling policies, such as MaxWeight and backpressure, which select service actions according to the current congestion state of the system\. These policies originate from the seminal work on stability and maximum\-throughput scheduling in constrained queueing networks\[[30](https://arxiv.org/html/2607.06017#bib.bib18)\], and have been further analyzed in generalized switch and heavy\-traffic regimes\[[29](https://arxiv.org/html/2607.06017#bib.bib19)\]\. More broadly, queue\-length\-based scheduling and resource\-allocation rules have become standard tools for the control of stochastic networks\[[12](https://arxiv.org/html/2607.06017#bib.bib21),[8](https://arxiv.org/html/2607.06017#bib.bib22)\]\.

The algorithmic approach proposed in this work is particularly inspired by Lyapunov optimization and the Drift\-Plus\-Penalty methodology\[[25](https://arxiv.org/html/2607.06017#bib.bib23),[24](https://arxiv.org/html/2607.06017#bib.bib20)\]\. This framework designs online control policies by minimizing, at each time step, an upper bound on the Lyapunov drift plus a weighted penalty term\. In the analyzed setting, the drift term captures the evolution of the human\-service queues, while the penalty corresponds to the chatbot cost\. The main difference from the classical queueing\-control literature is that the relevant system parameters, namely the chatbot success probabilities and the human service rates, are unknown and must be learned online while the queues are being controlled\.

##### Online learning and bandits\.

The learning component of the model is related to the classical literature on multi\-armed bandits and online learning\. The bandit framework studies sequential decision\-making problems in which a learner must balance exploration and exploitation while minimizing regret\. Foundational results on adaptive allocation rules were established in\[[19](https://arxiv.org/html/2607.06017#bib.bib24)\], while finite\-time regret guarantees for Upper Confidence Bound algorithms were developed in\[[1](https://arxiv.org/html/2607.06017#bib.bib25)\]\. We refer to\[[2](https://arxiv.org/html/2607.06017#bib.bib26),[20](https://arxiv.org/html/2607.06017#bib.bib27)\]for broader treatments of stochastic and adversarial bandit models\.

AlthoughUCB\-DPPrelies on UCB\-type confidence bounds, the setting differs from standard bandit problems\. Observations are generated by the control decisions and the queueing state: chatbot outcomes provide information only for task types on which resources are allocated, while human service outcomes are observed only when the policy selects a nonempty queue for service\. Moreover, estimation errors are weighted by the current backlog, coupling learning with queue control\. Thus, standard bandit arguments must be combined with Lyapunov\-drift techniques\.

##### Online learning in queue control\.

Finally, the most closely related line of work studies online learning in queueing and stochastic network control systems, where control decisions must be made under unknown system parameters\. Several works combine bandit\-learning ideas with queueing objectives, including the learning of unknown service rates\[[18](https://arxiv.org/html/2607.06017#bib.bib29)\], scheduling with unknown statistics through MaxWeight and UCB\-type rules\[[35](https://arxiv.org/html/2607.06017#bib.bib30)\], and the analysis of transient congestion effects induced by learning\[[10](https://arxiv.org/html/2607.06017#bib.bib31)\]\. Related approaches combine Lyapunov\-drift methods with bandit feedback or adversarial learning in constrained scheduling and stochastic network optimization problems\[[16](https://arxiv.org/html/2607.06017#bib.bib32),[11](https://arxiv.org/html/2607.06017#bib.bib33),[4](https://arxiv.org/html/2607.06017#bib.bib34),[5](https://arxiv.org/html/2607.06017#bib.bib28)\]\.

This work is related to the literature on learning in queueing systems, but the model has a different two\-stage structure\. In standard queueing\-control problems, arrivals are typically exogenous and the controller acts mainly on the service side\. In the proposed setting, chatbot decisions endogenously shape the arrival process into the human queues, while scheduling decisions determine the departure process\. The platform must therefore learn and control both sides of the system: the chatbot layer, through unknown chatbot success probabilities, and the human\-service layer, through unknown service rates\.

## 2The Model

Task arrivalXt∈\[K\]X\_\{t\}\\in\[K\]Chatbotcostctc\_\{t\}success prob\.pXt​ctp\_\{X\_\{t\}\}c\_\{t\}ResolvedautomaticallyHuman queues\(Qt,1,…,Qt,K\)\(Q\_\{t,1\},\\dots,Q\_\{t,K\}\)Schedulingactionata\_\{t\}Human agentservice prob\.μat\\mu\_\{a\_\{t\}\}successfailure

Figure 1:Illustration of the human\-chatbot service system\.Tasks arrive sequentially over a finite time horizonTT, which is assumed to be known in advance\. At each timet∈\[T\]t\\in\[T\], a task of typeXtX\_\{t\}enters the system, where

Xt∈\[K\]:=\{1,…,K\}\.X\_\{t\}\\in\[K\]:=\\\{1,\\ldots,K\\\}\.Task types represent heterogeneous classes of requests, for instance different levels of difficulty, urgency, or complexity\.

We assume that arrivals are independent and identically distributed over time according to an unknown distribution𝝀=\(λ1,…,λK\)\\bm\{\\lambda\}=\(\\lambda\_\{1\},\\ldots,\\lambda\_\{K\}\)over the set of task types\. Thus, for everyk∈\[K\]k\\in\[K\],λk=ℙ​\(Xt=k\)\>0\\lambda\_\{k\}=\\mathbb\{P\}\(X\_\{t\}=k\)\>0, and∑k=1Kλk=1\\sum\_\{k=1\}^\{K\}\\lambda\_\{k\}=1\. The arrival distribution𝝀\\bm\{\\lambda\}is not known to the decision maker\.

##### Chatbot success probability\.

Upon arrival, each task is first routed to a chatbot\. If the task arriving at timettis of typekk, the decision maker selects a cost levelc∈\[0,1\]c\\in\[0,1\], representing the amount of resources allocated to the chatbot for handling that task\. The chatbot then succeeds in resolving the task with probabilitysk​\(c\)s\_\{k\}\(c\), and fails otherwise\. Equivalently, the chatbot outcome is a Bernoulli random variable with parametersk​\(c\)s\_\{k\}\(c\)\.

We assume that the chatbot success probability is linear in the allocated cost\. Namely, for each typek∈\[K\]k\\in\[K\], there exists an unknown parameterpk∈\(0,1\]p\_\{k\}\\in\(0,1\]such that

sk​\(c\)=pk​c,c∈\[0,1\]\.s\_\{k\}\(c\)=p\_\{k\}c,\\qquad c\\in\[0,1\]\.\(1\)Thus,pkp\_\{k\}captures the intrinsic effectiveness of the chatbot on tasks of typekk, while the control variableccmodulates the actual probability of automatic resolution\.

##### Human service mechanism\.

Tasks that are not resolved by the chatbot are routed to a human service system\. We assume that there exist unknown parameters\{μ1,…,μK\}\\\{\\mu\_\{1\},\\ldots,\\mu\_\{K\}\\\}such that, whenever the human agent works on a task of typekk, the task is completed by the end of the slot with probabilityμk∈\(0,1\]\\mu\_\{k\}\\in\(0,1\]\. Equivalently, each slot devoted to a type\-kktask produces an independent Bernoulli service attempt with success probabilityμk\\mu\_\{k\}\. Hence, conditional on the task typekk, the service timeLL\(measured in number of slots\) follows a geometric distribution and satisfies

𝔼​\[L∣k\]=1μk\.\\mathbb\{E\}\[L\\mid k\]=\\frac\{1\}\{\\mu\_\{k\}\}\.\(2\)To capture heterogeneity across task types, we considerKKseparate queues, one for each type, and introduce a scheduling decision for the human server\. At each slottt, the decision maker chooses an action

at∈\{1,…,K\}\.a\_\{t\}\\in\\\{1,\\ldots,K\\\}\.\(3\)Ifat=ka\_\{t\}=kand the corresponding queue is nonempty, then the human agent serves one type\-kktask during slottt\. We assume that scheduling is*preemptive*: the server may switch across task types from one slot to the next, interrupting the processing of a task and possibly returning to it later\. This assumption is natural in the geometric service model, where each service attempt is memoryless and the probability of completion depends only on the type currently being served\.

##### Queue dynamics\.

Let𝑸t:=\(Qt,1,…,Qt,K\)\\bm\{Q\}\_\{t\}:=\(Q\_\{t,1\},\\ldots,Q\_\{t,K\}\)denote the backlog vector at the beginning of slottt, whereQt,k∈ℕQ\_\{t,k\}\\in\\mathbb\{N\}is the number of pending type\-kktasks in the human queue\. We assume that all queues are initially empty, namelyQ1,k=0Q\_\{1,k\}=0for allk∈\[K\]k\\in\[K\]\.

At each slottt, one task of typeXt∈\[K\]X\_\{t\}\\in\[K\]arrives and is first routed to the chatbot\. After the decision maker selects the chatbot costct∈\[0,1\]c\_\{t\}\\in\[0,1\], the task either leaves the system if the chatbot succeeds, or joins the human queue corresponding to its type if the chatbot fails\. We define the per\-type arrival indicators to the human queues as

At,k:=𝟙​\{Xt=k\}​1​\{the chatbot fails at slot​t\},k∈\[K\]\.A\_\{t,k\}:=\\mathds\{1\}\\\{X\_\{t\}=k\\\}\\,\\mathds\{1\}\\\{\\text\{the chatbot fails at slot \}t\\\},\\qquad k\\in\[K\]\.\(4\)Thus, at most one human queue receives an arrival in each slot\. Moreover, conditional onXt=kX\_\{t\}=kandctc\_\{t\}, the expected arrival to queuekkis

𝔼​\[At,k∣Xt=k,ct\]=1−pk​ct,\\mathbb\{E\}\[A\_\{t,k\}\\mid X\_\{t\}=k,c\_\{t\}\]=1\-p\_\{k\}c\_\{t\},\(5\)whileAt,j=0A\_\{t,j\}=0for allj≠kj\\neq k\.

The scheduling actionat∈\[K\]a\_\{t\}\\in\[K\]determines which queue is selected for service\. Ifat=ka\_\{t\}=kand queuekkis nonempty, the human agent attempts to complete one type\-kktask during slottt\. We define the departure indicators as

Dt,k:=𝟙​\{at=k\}​1​\{Qt,k\>0\}​Zt,k,k∈\[K\],D\_\{t,k\}:=\\mathds\{1\}\\\{a\_\{t\}=k\\\}\\,\\mathds\{1\}\\\{Q\_\{t,k\}\>0\\\}\\,Z\_\{t,k\},\\qquad k\\in\[K\],\(6\)whereZt,k∼ℬ​\(μk\)Z\_\{t,k\}\\sim\\mathcal\{B\}\(\\mu\_\{k\}\)\. Hence, conditional on the current backlog and on the scheduling decision,

𝔼​\[Dt,k∣𝑸t,at\]=𝟙​\{at=k\}​𝟙​\{Qt,k\>0\}​μk\.\\mathbb\{E\}\[D\_\{t,k\}\\mid\\bm\{Q\}\_\{t\},a\_\{t\}\]=\\mathds\{1\}\\\{a\_\{t\}=k\\\}\\mathds\{1\}\\\{Q\_\{t,k\}\>0\\\}\\mu\_\{k\}\.\(7\)In particular,Dt,k=0D\_\{t,k\}=0wheneverat≠ka\_\{t\}\\neq korQt,k=0Q\_\{t,k\}=0\.

The human queues then evolve according to

Qt\+1,k=Qt,k\+At,k−Dt,k,k∈\[K\]\.Q\_\{t\+1,k\}=Q\_\{t,k\}\+A\_\{t,k\}\-D\_\{t,k\},\\qquad k\\in\[K\]\.\(8\)SinceDt,k≤𝟙​\{Qt,k\>0\}D\_\{t,k\}\\leq\\mathds\{1\}\\\{Q\_\{t,k\}\>0\\\}, the queue lengths remain nonnegative at all times\.

Following\[[25](https://arxiv.org/html/2607.06017#bib.bib23)\], we say that queuekkis*mean rate stable*if its expected backlog grows sublinearly over time, namely if

limT→∞𝔼​\[QT,k\]T=0\.\\lim\_\{T\\to\\infty\}\\frac\{\\mathbb\{E\}\[Q\_\{T,k\}\]\}\{T\}=0\.\(9\)Equivalently, the queue does not accumulate unresolved tasks at a linear rate\.

Figure[1](https://arxiv.org/html/2607.06017#S2.F1)provides a schematic illustration of the model\.

### 2\.1Cost Objective and Regret

A control policy specifies both the chatbot\-cost decision and the human\-service scheduling action over time\. Formally, an admissible policyπ\\piis a decision rule that, at each slottt, maps the current task type, the current backlog vector, and the past history into an action pair

πt:\(Xt,𝑸tπ,ℱt−1\)↦\(ctπ,atπ\),\\pi\_\{t\}:\\ \(X\_\{t\},\\bm\{Q\}\_\{t\}^\{\\pi\},\\mathcal\{F\}\_\{t\-1\}\)\\mapsto\(c\_\{t\}^\{\\pi\},a\_\{t\}^\{\\pi\}\),\(10\)wherectπ∈\[0,1\]c\_\{t\}^\{\\pi\}\\in\[0,1\]is the cost allocated to the chatbot andatπ∈\[K\]a\_\{t\}^\{\\pi\}\\in\[K\]is the queue selected for human service\. Hereℱt−1\\mathcal\{F\}\_\{t\-1\}denotes the information available up to the end of slott−1t\-1\.

Given a horizonTT, we evaluate a policy through the total cost

CTπ:=∑t=1Tctπ\+∑k=1Krk​QT\+1,kπ,C^\{\\pi\}\_\{T\}:=\\sum\_\{t=1\}^\{T\}c\_\{t\}^\{\\pi\}\+\\sum\_\{k=1\}^\{K\}r\_\{k\}\\,Q\_\{T\+1,k\}^\{\\pi\},\(11\)whererk∈\[rmin,rmax\]r\_\{k\}\\in\[r\_\{\\min\},r\_\{\\max\}\], with0<rmin<rmax0<r\_\{\\min\}<r\_\{\\max\}, is the penalty weight associated with unfinished tasks of typekk\. The first term is the cumulative chatbot cost, while the second term penalizes the residual backlog at the end of the horizon\. Thus, larger values ofrkr\_\{k\}correspond to task classes for which leaving jobs unresolved is more costly\.

Since the system parameters are unknown, the decision maker must learn them while controlling the system\. We measure the performance of a policy through regret with respect to the best admissible policy that knows the true parameters in advance\. LetΠ\\Pidenote the class of admissible policies satisfying \([10](https://arxiv.org/html/2607.06017#S2.E10)\)\. The regret of a policyπ∈Π\\pi\\in\\Piis defined as

RTπ:=𝔼​\[CTπ\]−infπ′∈Π𝔼​\[CTπ′\]\.R\_\{T\}^\{\\pi\}:=\\mathbb\{E\}\[C^\{\\pi\}\_\{T\}\]\-\\inf\_\{\\pi^\{\\prime\}\\in\\Pi\}\\mathbb\{E\}\[C^\{\\pi^\{\\prime\}\}\_\{T\}\]\.\(12\)The expectation is taken with respect to the randomness of arrivals, chatbot outcomes, service completions, and any possible randomization of the policy\. Regret therefore measures the excess expected cost incurred byπ\\pirelative to the best parameter\-aware admissible policy over the same horizon\.

### 2\.2Lower Bound via Static Optimization Problem

Characterizing the optimal policy in \([12](https://arxiv.org/html/2607.06017#S2.E12)\) is generally difficult, since such a policy may depend both on the true system parameters𝜽=\(𝝀,𝒑,𝝁\)\\bm\{\\theta\}=\(\\bm\{\\lambda\},\\bm\{p\},\\bm\{\\mu\}\)and on the current backlog state𝑸t\\bm\{Q\}\_\{t\}\. To obtain a tractable benchmark, we introduce the following*static*optimization problem:

OPT​\(𝜽\)=minck∈\[0,1\]ρk≥0\\displaystyle\\text\{OPT\}\(\\bm\{\\theta\}\)=\\min\_\{\\begin\{subarray\}\{c\}c\_\{k\}\\in\[0,1\]\\\\ \\rho\_\{k\}\\geq 0\\end\{subarray\}\}∑k=1Kλk​ck\\displaystyle\\sum\_\{k=1\}^\{K\}\\lambda\_\{k\}c\_\{k\}\(13\)s\.t\.λk​\(1−pk​ck\)≤μk​ρk,∀k∈\[K\],\\displaystyle\\lambda\_\{k\}\(1\-p\_\{k\}c\_\{k\}\)\\leq\\mu\_\{k\}\\rho\_\{k\},\\qquad\\forall k\\in\[K\],∑k=1Kρk≤1\.\\displaystyle\\sum\_\{k=1\}^\{K\}\\rho\_\{k\}\\leq 1\.Here,ckc\_\{k\}represents the chatbot cost that would be assigned to all tasks of typekkunder a static type\-dependent rule\. The quantityλk​\(1−pk​ck\)\\lambda\_\{k\}\(1\-p\_\{k\}c\_\{k\}\)is the effective rate at which type\-kktasks are not resolved by the chatbot and therefore enter the human queue\. The variableρk\\rho\_\{k\}represents the fraction of human service capacity allocated to typekk, so thatμk​ρk\\mu\_\{k\}\\rho\_\{k\}is the corresponding effective service capacity\. The constraints impose that, for each type, the human service capacity is large enough to absorb the residual arrival rate, while the total allocated human capacity cannot exceed one\.

The problem is static because the decision variables\(𝒄,𝝆\)\(\\bm\{c\},\\bm\{\\rho\}\)are fixed over time and do not depend on the instantaneous backlog of the system\. It therefore provides a parameter\-dependent benchmark, rather than a full dynamic policy\.

We assume that the optimization problem \([13](https://arxiv.org/html/2607.06017#S2.E13)\) is feasible\. Equivalently, since the residual load is minimized by takingck=1c\_\{k\}=1for allkk, feasibility is guaranteed if and only if

∑k=1Kλk​\(1−pk\)μk≤1\.\\sum\_\{k=1\}^\{K\}\\frac\{\\lambda\_\{k\}\(1\-p\_\{k\}\)\}\{\\mu\_\{k\}\}\\leq 1\.
The Lagrangian associated with the optimization problem \([13](https://arxiv.org/html/2607.06017#S2.E13)\) is

ℒ​\(𝒄,𝝆;𝒚,ν\)=∑k=1Kλk​ck\+∑k=1Kyk​\(λk​\(1−pk​ck\)−μk​ρk\)\+ν​\(∑k=1Kρk−1\),\\mathcal\{L\}\(\\bm\{c\},\\bm\{\\rho\};\\bm\{y\},\\nu\)=\\sum\_\{k=1\}^\{K\}\\lambda\_\{k\}c\_\{k\}\+\\sum\_\{k=1\}^\{K\}y\_\{k\}\\left\(\\lambda\_\{k\}\(1\-p\_\{k\}c\_\{k\}\)\-\\mu\_\{k\}\\rho\_\{k\}\\right\)\+\\nu\\left\(\\sum\_\{k=1\}^\{K\}\\rho\_\{k\}\-1\\right\),\(14\)whereyk≥0y\_\{k\}\\geq 0is the dual multiplier associated with thekk\-th balance constraint, andν≥0\\nu\\geq 0is the dual multiplier associated with the total capacity constraint\. Let\(𝒚∗,ν∗\)\(\\bm\{y\}^\{\*\},\\nu^\{\*\}\)be an optimal dual solution\.

We can now state a lower bound linking the static benchmark to the cost of the optimal admissible policy\.

###### Theorem 1\.

Assume that the terminal backlog weights satisfy

rk≥yk∗,∀k∈\[K\]\.r\_\{k\}\\geq y\_\{k\}^\{\*\},\\qquad\\forall k\\in\[K\]\.Then, for every horizonT≥1T\\geq 1,

infπ∈Π𝔼​\[CTπ\]≥T⋅OPT​\(𝜽\)\.\\inf\_\{\\pi\\in\\Pi\}\\mathbb\{E\}\[C^\{\\pi\}\_\{T\}\]\\geq T\\cdot\\text\{OPT\}\(\\bm\{\\theta\}\)\.

The multiplieryk∗y\_\{k\}^\{\*\}can be interpreted as the shadow congestion cost of an additional unit of residual type\-kkload\. The conditionrk≥yk∗r\_\{k\}\\geq y\_\{k\}^\{\*\}therefore requires the terminal penalty to be large enough to internalize the congestion cost captured by the static benchmark\. In particular, it rules out settings in which residual backlog is underpriced relative to the marginal value of service capacity\.

Let\(𝒄∗,𝝆∗\)\(\\bm\{c\}^\{\*\},\\bm\{\\rho\}^\{\*\}\)denote an optimal solution to the static optimization problem \([13](https://arxiv.org/html/2607.06017#S2.E13)\)\. The following proposition is a direct consequence of Theorem[1](https://arxiv.org/html/2607.06017#Thmtheorem1)\.

###### Proposition 1\.

For any policyπ\\pi, the regretRTπR\_\{T\}^\{\\pi\}satisfies

RTπ≤∑t=1T𝔼​\[ctπ−cXt∗\]\+∑k=1Krk​𝔼​\[QT\+1,kπ\]\.R\_\{T\}^\{\\pi\}\\leq\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[c\_\{t\}^\{\\pi\}\-c\_\{X\_\{t\}\}^\{\*\}\]\+\\sum\_\{k=1\}^\{K\}r\_\{k\}\\,\\mathbb\{E\}\[Q\_\{T\+1,k\}^\{\\pi\}\]\.

The proofs of this section are in Appendix[A](https://arxiv.org/html/2607.06017#A1)\.

## 3UCB\-DPPPolicy

The goal is to design an online policy that jointly chooses, at each slottt, the chatbot costct∈\[0,1\]c\_\{t\}\\in\[0,1\]and the human\-service scheduling actionat∈\[K\]a\_\{t\}\\in\[K\]\. The policy uses the current backlog vector𝑸t\\bm\{Q\}\_\{t\}together with the information collected about the unknown chatbot success probabilities𝒑=\(p1,…,pK\)\\bm\{p\}=\(p\_\{1\},\\ldots,p\_\{K\}\)and human service rates𝝁=\(μ1,…,μK\)\\bm\{\\mu\}=\(\\mu\_\{1\},\\ldots,\\mu\_\{K\}\)\. Its objective is to minimize cumulative chatbot costs while keeping the human queues stable in the sense of Equation \([9](https://arxiv.org/html/2607.06017#S2.E9)\)\. Throughout this section, we omit the superscriptπ\\pifrom all policy\-dependent quantities\.

##### Estimation of𝝁\\bm\{\\mu\}\.

Whenever the human agent serves a nonempty queue of typekk, the service attempt succeeds with probabilityμk\\mu\_\{k\}\. Thus, each effective service attempt on typekkproduces a Bernoulli observation\. For eachk∈\[K\]k\\in\[K\], define

Nk​\(t\):=∑s=1t𝟙​\{as=k,Qs,k\>0\},Sk​\(t\):=∑s=1tDs,k\.N\_\{k\}\(t\):=\\sum\_\{s=1\}^\{t\}\\mathds\{1\}\\\{a\_\{s\}=k,\\;Q\_\{s,k\}\>0\\\},\\qquad S\_\{k\}\(t\):=\\sum\_\{s=1\}^\{t\}D\_\{s,k\}\.\(15\)Here,Nk​\(t\)N\_\{k\}\(t\)is the number of effective service attempts on typekkup to timett, whileSk​\(t\)S\_\{k\}\(t\)is the number of successful completions of type\-kktasks\. We setNk​\(0\)=Sk​\(0\)=0N\_\{k\}\(0\)=S\_\{k\}\(0\)=0\. The empirical estimator ofμk\\mu\_\{k\}is

μ^k​\(t\):=\{0,if​Nk​\(t\)=0,Sk​\(t\)Nk​\(t\),if​Nk​\(t\)≥1\.\\hat\{\\mu\}\_\{k\}\(t\):=\\begin\{cases\}0,&\\text\{if \}N\_\{k\}\(t\)=0,\\\\\[2\.84526pt\] \\dfrac\{S\_\{k\}\(t\)\}\{N\_\{k\}\(t\)\},&\\text\{if \}N\_\{k\}\(t\)\\geq 1\.\\end\{cases\}\(16\)Given a confidence radiusβkμ​\(t\)≥0\\beta\_\{k\}^\{\\mu\}\(t\)\\geq 0, defined below, we use the optimistic estimate

μ¯k​\(t\):=min⁡\{1,μ^k​\(t\)\+βkμ​\(t\)\}\.\\bar\{\\mu\}\_\{k\}\(t\):=\\min\\left\\\{1,\\hat\{\\mu\}\_\{k\}\(t\)\+\\beta\_\{k\}^\{\\mu\}\(t\)\\right\\\}\.\(17\)

##### Estimation of𝒑\\bm\{p\}\.

When a task of typekkarrives at slotttand the chatbot costctc\_\{t\}is chosen, the chatbot succeeds with probabilitypk​ctp\_\{k\}c\_\{t\}\. LetYt:=𝟏​\{chatbot succeeds at slot​t\}Y\_\{t\}:=\\mathbf\{1\}\\\{\\text\{chatbot succeeds at slot \}t\\\}\. Conditionally on\(Xt=k,ct\)\(X\_\{t\}=k,c\_\{t\}\),

𝔼​\[Yt∣Xt=k,ct\]=pk​ct\.\\mathbb\{E\}\[Y\_\{t\}\\mid X\_\{t\}=k,c\_\{t\}\]=p\_\{k\}c\_\{t\}\.To estimatepkp\_\{k\}, for eachk∈\[K\]k\\in\[K\]we define

Mk​\(t\):=∑s=1tcs​𝟙​\{Xs=k\},Gk​\(t\):=∑s=1tYs​𝟙​\{Xs=k\}\.M\_\{k\}\(t\):=\\sum\_\{s=1\}^\{t\}c\_\{s\}\\mathds\{1\}\\\{X\_\{s\}=k\\\},\\qquad G\_\{k\}\(t\):=\\sum\_\{s=1\}^\{t\}Y\_\{s\}\\mathds\{1\}\\\{X\_\{s\}=k\\\}\.\(18\)Here,Mk​\(t\)M\_\{k\}\(t\)is the cumulative exposure of typekkto the chatbot, whileGk​\(t\)G\_\{k\}\(t\)is the cumulative number of chatbot successes on typekk\. As shown below, theUCB\-DPPcost decision is threshold\-based and therefore satisfiesct∈\{0,1\}c\_\{t\}\\in\\\{0,1\\\}\. HenceMk​\(t\)M\_\{k\}\(t\)counts the number of effective chatbot trials on typekk\. We setMk​\(0\)=Gk​\(0\)=0M\_\{k\}\(0\)=G\_\{k\}\(0\)=0\. The empirical estimator ofpkp\_\{k\}is

p^k​\(t\):=\{0,if​Mk​\(t\)=0,Gk​\(t\)Mk​\(t\),if​Mk​\(t\)\>0\.\\hat\{p\}\_\{k\}\(t\):=\\begin\{cases\}0,&\\text\{if \}M\_\{k\}\(t\)=0,\\\\\[2\.84526pt\] \\dfrac\{G\_\{k\}\(t\)\}\{M\_\{k\}\(t\)\},&\\text\{if \}M\_\{k\}\(t\)\>0\.\\end\{cases\}\(19\)Given a confidence radiusβkp​\(t\)≥0\\beta\_\{k\}^\{p\}\(t\)\\geq 0, we define

p¯k​\(t\):=min⁡\{1,p^k​\(t\)\+βkp​\(t\)\}\.\\bar\{p\}\_\{k\}\(t\):=\\min\\left\\\{1,\\hat\{p\}\_\{k\}\(t\)\+\\beta\_\{k\}^\{p\}\(t\)\\right\\\}\.\(20\)

##### Drift\-Plus\-Penalty principle\.

We use a weighted quadratic Lyapunov function,

Φ​\(𝑸t\)=12​∑k=1Krk​Qt,k2\.\\Phi\(\\bm\{Q\}\_\{t\}\)=\\frac\{1\}\{2\}\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}^\{2\}\.\(21\)Let us define the conditional drift as

Δt=𝔼​\[Φ​\(𝑸t\+1\)−Φ​\(𝑸t\)∣ℱt\]\.\\Delta\_\{t\}=\\mathbb\{E\}\\big\[\\Phi\(\\bm\{Q\}\_\{t\+1\}\)\-\\Phi\(\\bm\{Q\}\_\{t\}\)\\mid\\mathcal\{F\}\_\{t\}\\big\]\.\(22\)
The following drift bound follows directly from the queue dynamics\.

###### Lemma 1\(Drift Upper Bound\)\.

For allt∈\[T\]t\\in\[T\], it holds that

Δt≤rmax\+∑k=1Krk​Qt,k​𝔼​\[At,k−Dt,k∣ℱt\]\.\\Delta\_\{t\}\\leq r\_\{\\max\}\+\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\\,\\mathbb\{E\}\[A\_\{t,k\}\-D\_\{t,k\}\\mid\\mathcal\{F\}\_\{t\}\]\.

The proof is in Appendix[B](https://arxiv.org/html/2607.06017#A2)\.

Following the Drift\-Plus\-Penalty methodology, the control actions are chosen by minimizing an upper bound on

Δt\+V​ct,\\Delta\_\{t\}\+Vc\_\{t\},\(23\)where the parameterV\>0V\>0balances instantaneous chatbot costs against queue growth\. Larger values ofVVput more weight on cost minimization, while smaller values prioritize congestion control\.

Using Lemma[1](https://arxiv.org/html/2607.06017#Thmlemma1), we have

Δt\+V​ct≤rmax\+∑k=1Krk​Qt,k​𝔼​\[At,k−Dt,k∣ℱt\]\+V​ct\.\\Delta\_\{t\}\+Vc\_\{t\}\\leq r\_\{\\max\}\+\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\\,\\mathbb\{E\}\[A\_\{t,k\}\-D\_\{t,k\}\\mid\\mathcal\{F\}\_\{t\}\]\+Vc\_\{t\}\.\(24\)Substituting the conditional expectations of the arrival and departure processes, and dropping the constant termrmaxr\_\{\\max\}, yields the surrogate objective

Ψt​\(c,a\):=V​c\+rXt​Qt,Xt​\(1−pXt​c\)−ra​Qt,a​μa\.\\Psi\_\{t\}\(c,a\):=Vc\+r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}\(1\-p\_\{X\_\{t\}\}c\)\-r\_\{a\}Q\_\{t,a\}\\mu\_\{a\}\.\(25\)
Since the parameters𝒑\\bm\{p\}and𝝁\\bm\{\\mu\}are unknown, theUCB\-DPPpolicy replaces them with their optimistic estimates and minimizes

Ψ~t​\(c,a\):=V​c\+rXt​Qt,Xt​\(1−p¯Xt​\(t−1\)​c\)−ra​Qt,a​μ¯a​\(t−1\)\.\\widetilde\{\\Psi\}\_\{t\}\(c,a\):=Vc\+r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}\(1\-\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)c\)\-r\_\{a\}Q\_\{t,a\}\\bar\{\\mu\}\_\{a\}\(t\-1\)\.\(26\)Thus, at each slottt,

\(ct,at\)∈arg⁡minc∈\[0,1\],a∈\[K\]⁡Ψ~t​\(c,a\)\.\(c\_\{t\},a\_\{t\}\)\\in\\arg\\min\_\{c\\in\[0,1\],\\,a\\in\[K\]\}\\widetilde\{\\Psi\}\_\{t\}\(c,a\)\.\(27\)
SinceΨ~t\\widetilde\{\\Psi\}\_\{t\}is separable inccandaaand linear incc, the policy admits the explicit form

ct=\{1,rXt​p¯Xt​\(t−1\)​Qt,Xt≥V,0,otherwise,at∈arg⁡maxj∈\[K\]⁡rj​Qt,j​μ¯j​\(t−1\)\.c\_\{t\}=\\begin\{cases\}1,&r\_\{X\_\{t\}\}\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)Q\_\{t,X\_\{t\}\}\\geq V,\\\\ 0,&\\text\{otherwise,\}\\end\{cases\}\\qquad a\_\{t\}\\in\\arg\\max\_\{j\\in\[K\]\}r\_\{j\}Q\_\{t,j\}\\bar\{\\mu\}\_\{j\}\(t\-1\)\.If all queues are empty, the scheduling decision is irrelevant\.

Thus, the chatbot is activated when its weighted optimistic benefit in reducing future human backlog exceeds the cost thresholdVV, while the human server is assigned to the queue with the largest optimistic weighted service potential, as in a MaxWeight rule\.

The threshold structure of the chatbot decision follows from the linear formsk​\(c\)=pk​cs\_\{k\}\(c\)=p\_\{k\}c: since the surrogate objective is linear incc, the chatbot cost always takes values in\{0,1\}\\\{0,1\\\}, corresponding to an*on/off*decision\. Learning enters the policy through two UCB mechanisms\[[1](https://arxiv.org/html/2607.06017#bib.bib25)\]: one for the chatbot success probabilities and one for the human service rates\. The former affects the arrival process into the human queues, while the latter affects the scheduling of human service capacity\.

A complete pseudocode description of theUCB\-DPPpolicy is provided in Appendix[B](https://arxiv.org/html/2607.06017#A2)\.

## 4Regret Bound

We now show that the regret of theUCB\-DPPpolicy grows sublinearly with the horizonTT\. As a consequence of the backlog estimates used in the analysis, we also obtain mean\-rate stability of the human\-service queues\.

The first step is to decompose the regret into terms that can be controlled separately\. For everyt∈\[T\]t\\in\[T\], define the*good event*up to timettas

𝒢t=⋂s=1t⋂k=1K\(\{\|μk−μ^k​\(s−1\)\|≤βkμ​\(s−1\)\}∩\{\|pk−p^k​\(s−1\)\|≤βkp​\(s−1\)\}\)\.\\mathscr\{G\}\_\{t\}=\\bigcap\_\{s=1\}^\{t\}\\bigcap\_\{k=1\}^\{K\}\\left\(\\left\\\{\|\\mu\_\{k\}\-\\hat\{\\mu\}\_\{k\}\(s\-1\)\|\\leq\\beta\_\{k\}^\{\\mu\}\(s\-1\)\\right\\\}\\cap\\left\\\{\|p\_\{k\}\-\\hat\{p\}\_\{k\}\(s\-1\)\|\\leq\\beta\_\{k\}^\{p\}\(s\-1\)\\right\\\}\\right\)\.\(28\)On this event, all empirical estimates of the chatbot success probabilities and human service rates remain within their confidence intervals uniformly over all types and all times up tott\.

###### Lemma 2\(Regret decomposition\)\.

The regret of theUCB\-DPPpolicy satisfies

RTUCB\-DPP≤R1p​\(T\)\+R1μ​\(T\)\+R2​\(T\)\+R3​\(T\)\+R4​\(T\),R\_\{T\}^\{\\texttt\{UCB\-DPP\}\}\\leq R\_\{1\}^\{p\}\(T\)\+R\_\{1\}^\{\\mu\}\(T\)\+R\_\{2\}\(T\)\+R\_\{3\}\(T\)\+R\_\{4\}\(T\),where

- •R1p​\(T\):=1V​𝔼​\[∑t=1TrXt​Qt,Xt​ct​\(p¯Xt​\(t−1\)−pXt\)​𝟙​\{𝒢t\}\]R\_\{1\}^\{p\}\(T\):=\\frac\{1\}\{V\}\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}c\_\{t\}\\left\(\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\-p\_\{X\_\{t\}\}\\right\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\right\],
- •R1μ​\(T\):=1V​𝔼​\[∑t=1Trat​Qt,at​\(μ¯at​\(t−1\)−μat\)​𝟙​\{𝒢t\}\]R\_\{1\}^\{\\mu\}\(T\):=\\frac\{1\}\{V\}\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\left\(\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\-\\mu\_\{a\_\{t\}\}\\right\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\right\],
- •R2​\(T\):=T​ℙ​\(𝒢¯T\)R\_\{2\}\(T\):=T\\,\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}\),
- •R3​\(T\):=rmax​TVR\_\{3\}\(T\):=\\frac\{r\_\{\\max\}T\}\{V\},
- •R4​\(T\):=∑k=1Krk​𝔼​\[QT\+1,k\]R\_\{4\}\(T\):=\\sum\_\{k=1\}^\{K\}r\_\{k\}\\,\\mathbb\{E\}\[Q\_\{T\+1,k\}\]\.

We now bound the terms appearing in Lemma[2](https://arxiv.org/html/2607.06017#Thmlemma2)\.

##### Control of the bad event\.

We first control the probability of the complement of the good event\. Fixδ∈\(0,1\)\\delta\\in\(0,1\), whose value will be specified later\. We setβkμ​\(0\):=1\\beta\_\{k\}^\{\\mu\}\(0\):=1,βkp​\(0\):=1\\beta\_\{k\}^\{p\}\(0\):=1and, for everyt≥1t\\geq 1, define

βkμ​\(t\)\\displaystyle\\beta\_\{k\}^\{\\mu\}\(t\)=\{1,if​Nk​\(t\)=0,log⁡\(4​K​t/δ\)2​Nk​\(t\),if​Nk​\(t\)≥1,βkp​\(t\)\\displaystyle=\\qquad\\beta\_\{k\}^\{p\}\(t\)=\{1,if​Mk​\(t\)=0,log⁡\(4​K​t/δ\)2​Mk​\(t\),if​Mk​\(t\)≥1\.\\displaystyle=\(29\)
###### Proposition 2\.

The event𝒢T\\mathscr\{G\}\_\{T\}satisfies

ℙ​\(𝒢¯T\)≤δ​T\.\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}\)\\leq\\delta T\.

##### Control of the terminal backlog\.

We next control the backlog contributionR4​\(T\)R\_\{4\}\(T\)\. Define

Zt:=2​Φ​\(𝑸t\)=\(∑k=1Krk​Qt,k2\)1/2\.Z\_\{t\}:=\\sqrt\{2\\Phi\(\\bm\{Q\}\_\{t\}\)\}=\\left\(\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}^\{2\}\\right\)^\{1/2\}\.\(30\)
###### Lemma 3\.

Assume that there existε\>0\\varepsilon\>0and a strictly feasible point\(𝐜ε,𝛒ε\)\(\\bm\{c\}^\{\\varepsilon\},\\bm\{\\rho\}^\{\\varepsilon\}\)such that

λk​\(1−pk​ckε\)\+ε≤μk​ρkε,∀k∈\[K\]​and​∑k=1Kρkε≤1\.\\lambda\_\{k\}\(1\-p\_\{k\}c\_\{k\}^\{\\varepsilon\}\)\+\\varepsilon\\leq\\mu\_\{k\}\\rho\_\{k\}^\{\\varepsilon\},\\;\\forall k\\in\[K\]\\;\\;\\;\\text\{and\}\\;\\;\\;\\sum\_\{k=1\}^\{K\}\\rho\_\{k\}^\{\\varepsilon\}\\leq 1\.Then

𝔼​\[ZT\+1​𝟙​\{𝒢T\}\]≤𝒪​\(V\+K​log⁡\(T/δ\)\)\.\\mathbb\{E\}\[Z\_\{T\+1\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{T\}\\\}\]\\leq\\mathcal\{O\}\(V\+K\\log\(T/\\delta\)\)\.

The assumption in Lemma[3](https://arxiv.org/html/2607.06017#Thmlemma3)is a strong stability condition for the static benchmark\. It requires the existence of a type\-dependent chatbot allocation and a human\-capacity allocation such that, for every classkk, the effective service capacityμk​ρkε\\mu\_\{k\}\\rho\_\{k\}^\{\\varepsilon\}exceeds the residual arrival rateλk​\(1−pk​ckε\)\\lambda\_\{k\}\(1\-p\_\{k\}c\_\{k\}^\{\\varepsilon\}\)by a uniform marginε\\varepsilon\. This slack is used in the drift argument to obtain a negative drift when the backlog is large\. Intuitively, it rules out boundary cases in which the system is only critically loaded, where queues may be stable asymptotically but finite\-horizon backlog bounds are harder to control\. As a consequence, we obtain the following bound on the terminal backlog term\.

###### Proposition 3\(Bound onR4​\(T\)R\_\{4\}\(T\)\)\.

Under the assumptions of Lemma[3](https://arxiv.org/html/2607.06017#Thmlemma3),R4​\(T\)R\_\{4\}\(T\)satisfies

R4​\(T\)=𝒪​\(V\+K​log⁡\(T/δ\)\)\+rmax​T​ℙ​\(𝒢¯T\)\.R\_\{4\}\(T\)=\\mathcal\{O\}\(V\+K\\log\(T/\\delta\)\)\+r\_\{\\max\}T\\,\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}\)\.

##### Control of the estimation\-error terms\.

It remains to control the two terms involving estimation errors on the good event, namelyR1μ​\(T\)R\_\{1\}^\{\\mu\}\(T\)andR1p​\(T\)R\_\{1\}^\{p\}\(T\)\.

###### Proposition 4\.

The estimation\-error terms satisfy

R1μ​\(T\),R1p​\(T\)=𝒪​\(K​T​log⁡\(T/δ\)\)\.R\_\{1\}^\{\\mu\}\(T\),\\;R\_\{1\}^\{p\}\(T\)=\\mathcal\{O\}\\left\(K\\sqrt\{T\\log\(T/\\delta\)\}\\right\)\.

##### Final regret bound\.

We are now ready to combine the preceding bounds and state the main regret guarantee\.

###### Theorem 2\.

Under the assumption in Lemma[3](https://arxiv.org/html/2607.06017#Thmlemma3), by settingV=TV=\\sqrt\{T\}andδ=T−2\\delta=T^\{\-2\}, theUCB\-DPPpolicy satisfies, forT≥2T\\geq 2,

RTUCB\-DPP=𝒪​\(K​T​log⁡T\)\.R\_\{T\}^\{\\texttt\{UCB\-DPP\}\}=\\mathcal\{O\}\\left\(K\\sqrt\{T\\log T\}\\right\)\.

The proof starts from the regret decomposition in Lemma[2](https://arxiv.org/html/2607.06017#Thmlemma2)\. On the good event, optimism reduces the regret to two estimation\-error terms, corresponding to the chatbot and service parameters\. These terms are nonstandard because the estimation errors are weighted by the current queue backlog\. They are controlled by combining concentration bounds with Lyapunov\-drift arguments that keep the relevant backlog terms under control\. The remaining terms are the bad\-event probability, the drift contributionT/VT/V, and the terminal backlog, which is of orderVVup to logarithmic factors\. SettingV=TV=\\sqrt\{T\}andδ=T−2\\delta=T^\{\-2\}balances these terms and gives the stated regret bound\.

We can also observe that, as a direct consequence of Proposition[3](https://arxiv.org/html/2607.06017#Thmproposition3), choosingV=TV=\\sqrt\{T\}andδ=T−2\\delta=T^\{\-2\}gives a sublinear weighted terminal backlog\. Sincerk≥rmin\>0r\_\{k\}\\geq r\_\{\\min\}\>0for allk∈\[K\]k\\in\[K\], each human\-service queue is*mean\-rate stable*:

limT→∞𝔼​\[QT\+1,k\]T=0,∀k∈\[K\]\.\\lim\_\{T\\to\\infty\}\\frac\{\\mathbb\{E\}\[Q\_\{T\+1,k\}\]\}\{T\}=0,\\qquad\\forall k\\in\[K\]\.
The complete proofs of this section are provided in Appendix[C](https://arxiv.org/html/2607.06017#A3)\.

## 5Simulations

We test theUCB\-DPPpolicy on a synthetic instance withK=5K=5task classes, arrival rates𝝀=\(0\.32,0\.08,0\.25,0\.20,0\.15\)\\bm\{\\lambda\}=\(0\.32,0\.08,0\.25,0\.20,0\.15\), chatbot success probabilities𝒑=\(0\.82,0\.35,0\.68,0\.25,0\.9\)\\bm\{p\}=\(0\.82,0\.35,0\.68,0\.25,0\.9\), human service rates𝝁=\(0\.3,0\.85,0\.45,0\.75,0\.28\)\\bm\{\\mu\}=\(0\.3,0\.85,0\.45,0\.75,0\.28\), and terminal backlog weights𝒓=\(2\.3,0\.8,1\.5,0\.9,2\.5\)\\bm\{r\}=\(2\.3,0\.8,1\.5,0\.9,2\.5\), chosen to satisfy the assumption of Lemma[3](https://arxiv.org/html/2607.06017#Thmlemma3)\.

All simulations are run over a horizonT=30000T=30000for theUCB\-DPPplot in Figure[2\(a\)](https://arxiv.org/html/2607.06017#S5.F2.sf1)and over a horizonT=10000T=10000for the policy comparison plot in Figure[2\(b\)](https://arxiv.org/html/2607.06017#S5.F2.sf2)\. Each curve is averaged over100100independent runs, and the shaded regions represent one standard error\.

As shown in Figure[2\(a\)](https://arxiv.org/html/2607.06017#S5.F2.sf1), the cumulative regret ofUCB\-DPPgrows sublinearly over time\.

For the comparison plot, we consider three benchmark policies\. The first is a plug\-in version of DPP, which has the same decision structure asUCB\-DPPbut replaces the optimistic estimatesp¯k​\(t\)\\bar\{p\}\_\{k\}\(t\)andμ¯k​\(t\)\\bar\{\\mu\}\_\{k\}\(t\)with the empirical estimatesp^k​\(t\)\\hat\{p\}\_\{k\}\(t\)andμ^k​\(t\)\\hat\{\\mu\}\_\{k\}\(t\)\. The other two policies always set the chatbot cost to eitherc=1c=1orc=0c=0, respectively, and use a greedy scheduling rule based only on the empirical service rates:

at∈arg⁡maxk∈\[K\]⁡rk​μ^k​\(t−1\)\.a\_\{t\}\\in\\arg\\max\_\{k\\in\[K\]\}r\_\{k\}\\hat\{\\mu\}\_\{k\}\(t\-1\)\.This rule does not take the current backlog into account\. Instead, at each slot it prioritizes the task type with the largest product between terminal backlog cost and estimated service rate, namely the class that is both more costly to leave unresolved and empirically easier to serve\.

The comparison in Figure[2\(b\)](https://arxiv.org/html/2607.06017#S5.F2.sf2)therefore highlights the role of both the optimism mechanism and the queue\-aware Drift\-Plus\-Penalty structure in stabilizing the system while controlling chatbot usage\. Other simulations are provided in Appendix[D](https://arxiv.org/html/2607.06017#A4)\.

![Refer to caption](https://arxiv.org/html/2607.06017v1/Regret_UCBDPP.png)\(a\)Average cumulative regret ofUCB\-DPP\.
![Refer to caption](https://arxiv.org/html/2607.06017v1/real_comparison.png)\(b\)Average cumulative regret ofUCB\-DPPand three baselines\.

## 6Conclusion, Limitations and Open Directions

We studied an online learning and queueing\-control model for human\-AI service systems\. The main insight is that automation and human scheduling cannot be optimized separately: chatbot decisions shape the arrival process into the human queues, while scheduling decisions determine how limited human capacity is allocated\. To address this problem, we proposed theUCB\-DPPpolicy, which combines optimistic parameter estimation with a Drift\-Plus\-Penalty objective\. We proved thatUCB\-DPPachieves regret𝒪~​\(K​T\)\\widetilde\{\\mathcal\{O\}\}\(K\\sqrt\{T\}\)and ensures mean\-rate stability of the human\-service queues\. Simulations on synthetic instances show that the policy outperforms natural baselines\.

The model relies on a few simplifying assumptions that make the analysis tractable and could be extended in future work\. The linear chatbot success probability leads to an*on/off*chatbot decision, withct∈\{0,1\}c\_\{t\}\\in\\\{0,1\\\}, so that the chatbot is either fully activated or not used\. More general response functions could capture richer chatbot behavior and allow for intermediate levels of automation\. Similarly, the geometric and preemptive human\-service model could be generalized to non\-memoryless service times and non\-preemptive scheduling\. Finally, another natural direction is to consider systems with multiple human agents, possibly with heterogeneous skills, different service rates, or strategic behavior\. This would lead to richer allocation and incentive\-design questions, especially in settings where human agents may respond strategically to the way tasks are routed or prioritized\.

## References

- \[1\]P\. Auer, N\. Cesa\-Bianchi, and P\. Fischer\(2002\)Finite\-time analysis of the multiarmed bandit problem\.Machine Learning47\(2–3\),pp\. 235–256\.External Links:[Document](https://dx.doi.org/10.1023/A%3A1013689704352)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px3.p1.1),[§3](https://arxiv.org/html/2607.06017#S3.SS0.SSS0.Px3.p9.3)\.
- \[2\]S\. Bubeck and N\. Cesa\-Bianchi\(2012\)Regret analysis of stochastic and nonstochastic multi\-armed bandit problems\.Foundations and Trends in Machine Learning5\(1\),pp\. 1–122\.External Links:[Document](https://dx.doi.org/10.1561/2200000024)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px3.p1.1)\.
- \[3\]N\. Cai, S\. Gao, and J\. Yan\(2024\)How the communication style of chatbots influences consumers’ satisfaction, trust, and engagement in the context of service failure\.Humanities and Social Sciences Communications11,pp\. 687\.External Links:[Document](https://dx.doi.org/10.1057/s41599-024-03212-0),[Link](https://doi.org/10.1057/s41599-024-03212-0)Cited by:[§1\.1](https://arxiv.org/html/2607.06017#S1.SS1.p1.1)\.
- \[4\]S\. Cayci, Y\. Zheng, and A\. Eryilmaz\(2022\)A lyapunov\-based methodology for constrained optimization with bandit feedback\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.36,pp\. 3716–3723\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v36i4.20285)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px4.p1.1)\.
- \[5\]S\. Chadaga and E\. Modiano\(2025\)Drift plus optimistic penalty – a learning framework for stochastic network optimization\.InIEEE INFOCOM 2025 \- IEEE Conference on Computer Communications,Vol\.,pp\. 1–10\.External Links:[Document](https://dx.doi.org/10.1109/INFOCOM55648.2025.11044621)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px4.p1.1)\.
- \[6\]S\. Chen, X\. Li, K\. Liu, and X\. Wang\(2023\)Chatbot or human? the impact of online customer service on consumers’ purchase intentions\.Psychology & Marketing40\(11\),pp\. 2186–2200\.External Links:[Document](https://dx.doi.org/10.1002/mar.21862),[Link](https://doi.org/10.1002/mar.21862)Cited by:[§1\.1](https://arxiv.org/html/2607.06017#S1.SS1.p1.1)\.
- \[7\]F\. Dell’Acqua, E\. McFowland, E\. R\. Mollick, H\. Lifshitz\-Assaf, K\. Kellogg, S\. Rajendran, L\. Krayer, F\. Candelon, and K\. R\. Lakhani\(2026\)Navigating the jagged technological frontier: field experimental evidence of the effects of artificial intelligence on knowledge worker productivity and quality\.Organization Science\.External Links:[Document](https://dx.doi.org/10.1287/orsc.2025.21838)Cited by:[§1](https://arxiv.org/html/2607.06017#S1.p4.1)\.
- \[8\]A\. Eryilmaz and R\. Srikant\(2005\)Fair resource allocation in wireless networks using queue\-length\-based scheduling and congestion control\.InProceedings of IEEE INFOCOM,pp\. 1794–1803\.Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px2.p1.1)\.
- \[9\]D\. Fotheringham and M\. A\. Wiles\(2023\)The effect of implementing chatbot customer service on stock returns: an event study analysis\.Journal of the Academy of Marketing Science51\(4\),pp\. 802–822\.External Links:[Document](https://dx.doi.org/10.1007/s11747-022-00841-2),[Link](https://doi.org/10.1007/s11747-022-00841-2)Cited by:[§1\.1](https://arxiv.org/html/2607.06017#S1.SS1.p1.1)\.
- \[10\]D\. Freund, T\. Lykouris, and W\. Weng\(2023\)The transient cost of learning in queueing systems\.External Links:2308\.07817,[Document](https://dx.doi.org/10.48550/arXiv.2308.07817)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px4.p1.1)\.
- \[11\]X\. Fu and E\. Modiano\(2022\)Joint learning and control in stochastic queueing networks with unknown utilities\.Proceedings of the ACM on Measurement and Analysis of Computing Systems6\(3\)\.Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px4.p1.1)\.
- \[12\]L\. Georgiadis, M\. J\. Neely, and L\. Tassiulas\(2006\)Resource allocation and cross\-layer control in wireless networks\.Foundations and Trends in Networking1\(1\),pp\. 1–144\.External Links:[Document](https://dx.doi.org/10.1561/1300000001)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px2.p1.1)\.
- \[13\]A\. Greilich, K\. Bremser, and K\. Wüst\(2025\)Consumer response to anthropomorphism of text\-based ai chatbots: a systematic literature review and future research directions\.International Journal of Consumer Studies49\(5\),pp\. e70108\.External Links:[Document](https://dx.doi.org/10.1111/ijcs.70108),[Link](https://doi.org/10.1111/ijcs.70108)Cited by:[§1\.1](https://arxiv.org/html/2607.06017#S1.SS1.p1.1)\.
- \[14\]C\. Hsu and J\. C\. Lin\(2023\)Understanding the user satisfaction and loyalty of customer service chatbots\.Journal of Retailing and Consumer Services71,pp\. 103211\.External Links:[Document](https://dx.doi.org/10.1016/j.jretconser.2022.103211),[Link](https://doi.org/10.1016/j.jretconser.2022.103211)Cited by:[§1\.1](https://arxiv.org/html/2607.06017#S1.SS1.p1.1)\.
- \[15\]D\. Huang, D\. G\. Markovitch, and R\. A\. Stough\(2024\)Can chatbot customer service match human service agents on customer satisfaction? an investigation in the role of trust\.Journal of Retailing and Consumer Services76,pp\. 103600\.External Links:[Document](https://dx.doi.org/10.1016/j.jretconser.2023.103600),[Link](https://doi.org/10.1016/j.jretconser.2023.103600)Cited by:[§1\.1](https://arxiv.org/html/2607.06017#S1.SS1.p1.1)\.
- \[16\]J\. Huang, L\. Golubchik, and L\. Huang\(2023\)Queue scheduling with adversarial bandit learning\.External Links:2303\.01745,[Document](https://dx.doi.org/10.48550/arXiv.2303.01745)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px4.p1.1)\.
- \[17\]S\. Kraus, Y\. Oshrat, Y\. Aumann, T\. Hollander, O\. Maksimov, A\. Ostroumov, and N\. Shechtman\(2023\-06\)Customer service combining human operators and virtual agents: a call for multidisciplinary ai research\.Proceedings of the AAAI Conference on Artificial Intelligence37,pp\. 15393–15401\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v37i13.26795)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px1.p1.1)\.
- \[18\]S\. Krishnasamy, R\. Sen, R\. Johari, and S\. Shakkottai\(2021\)Learning unknown service rates in queues: a multiarmed bandit approach\.Operations Research69\(1\),pp\. 315–330\.External Links:[Document](https://dx.doi.org/10.1287/opre.2020.1995)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px4.p1.1)\.
- \[19\]T\. L\. Lai and H\. Robbins\(1985\)Asymptotically efficient adaptive allocation rules\.Advances in Applied Mathematics6\(1\),pp\. 4–22\.External Links:[Document](https://dx.doi.org/10.1016/0196-8858%2885%2990002-8)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px3.p1.1)\.
- \[20\]T\. Lattimore and C\. Szepesvári\(2020\)Bandit algorithms\.Cambridge University Press\.External Links:[Document](https://dx.doi.org/10.1017/9781108571401)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px3.p1.1)\.
- \[21\]B\. Legros and F\. de Vericourt\(2025\-01\)Human\-ai interaction in congested service systems: when it improves performance, and when it doesn’t\.SSRN Electronic Journal,pp\.\.External Links:[Document](https://dx.doi.org/10.2139/ssrn.5401875)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px1.p1.1)\.
- \[22\]J\. Liu, Z\. Gao, Y\. Kang, Z\. Jiang, G\. He, C\. Sun, X\. Liu, and W\. Lu\(2021\)Time to transfer: predicting and evaluating machine\-human chatting handoff\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.35,pp\. 5841–5849\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v35i7.16731)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px1.p2.1)\.
- \[23\]J\. Liu, K\. Song, Y\. Kang, G\. He, Z\. Jiang, C\. Sun, W\. Lu, and X\. Liu\(2021\)A role\-selected sharing network for joint machine\-human chatting handoff and service satisfaction analysis\.InProceedings of the 2021 Conference on Empirical Methods in Natural Language Processing,Online and Punta Cana, Dominican Republic,pp\. 9731–9741\.External Links:[Document](https://dx.doi.org/10.18653/v1/2021.emnlp-main.767),[Link](https://aclanthology.org/2021.emnlp-main.767/)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px1.p2.1)\.
- \[24\]M\. J\. Neely, E\. Modiano, and C\. Li\(2008\)Fairness and optimal stochastic control for heterogeneous networks\.IEEE/ACM Transactions on Networking16\(2\),pp\. 396–409\.External Links:[Document](https://dx.doi.org/10.1109/TNET.2007.900405)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px2.p2.1)\.
- \[25\]M\. J\. Neely\(2010\)Stochastic network optimization with application to communication and queueing systems\.Morgan and Claypool Publishers\.External Links:ISBN 160845455XCited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px2.p2.1),[§2](https://arxiv.org/html/2607.06017#S2.SS0.SSS0.Px3.p5.1)\.
- \[26\]Y\. Oshrat, Y\. Aumann, T\. Hollander, O\. Maksimov, A\. Ostroumov, N\. Shechtman, and S\. Kraus\(2022\)Efficient customer service combining human operators and virtual agents\.External Links:2209\.05226,[Link](https://arxiv.org/abs/2209.05226)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px1.p1.1)\.
- \[27\]B\. Sheehan, H\. S\. Jin, and U\. Gottlieb\(2020\)Customer service chatbots: anthropomorphism and adoption\.Journal of Business Research115,pp\. 14–24\.External Links:[Document](https://dx.doi.org/10.1016/j.jbusres.2020.04.030),[Link](https://doi.org/10.1016/j.jbusres.2020.04.030)Cited by:[§1\.1](https://arxiv.org/html/2607.06017#S1.SS1.p1.1)\.
- \[28\]M\. Song, X\. Xing, Y\. Duan, J\. Cohen, and J\. Mou\(2022\)Will artificial intelligence replace human customer service? the impact of communication quality and privacy risks on adoption intention\.Journal of Retailing and Consumer Services66,pp\. 102900\.External Links:[Document](https://dx.doi.org/10.1016/j.jretconser.2021.102900),[Link](https://doi.org/10.1016/j.jretconser.2021.102900)Cited by:[§1\.1](https://arxiv.org/html/2607.06017#S1.SS1.p1.1)\.
- \[29\]A\. L\. Stolyar\(2004\)MaxWeight scheduling in a generalized switch: state space collapse and workload minimization in heavy traffic\.The Annals of Applied Probability14\(1\),pp\. 1–53\.External Links:[Document](https://dx.doi.org/10.1214/aoap/1075828046)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px2.p1.1)\.
- \[30\]L\. Tassiulas and A\. Ephremides\(1992\)Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks\.IEEE Transactions on Automatic Control37\(12\),pp\. 1936–1948\.External Links:[Document](https://dx.doi.org/10.1109/9.182479)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px2.p1.1)\.
- \[31\]J\. C\. Vasquez\-Correa, J\. C\. Guerrero\-Sierra, J\. L\. Pemberty\-Tamayo, J\. E\. Jaramillo, and A\. F\. Tejada\-Castro\(2021\)One system to rule them all: a universal intent recognition system for customer service chatbots\.External Links:2112\.08261,[Link](https://arxiv.org/abs/2112.08261)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px1.p2.1)\.
- \[32\]Y\. Wang, C\. Zhu, T\. Feng, L\. X\. Lu, and B\. Jia\(2026\)Agentic ai and human\-in\-the\-loop interventions: field experimental evidence from alibaba’s customer service operations\.External Links:2605\.14830,[Link](https://arxiv.org/abs/2605.14830)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px1.p2.1)\.
- \[33\]Y\. Xu, C\. Shieh, P\. van Esch, and I\. Ling\(2020\)AI customer service: task complexity, problem\-solving ability, and usage intention\.Australasian Marketing Journal28\(4\),pp\. 189–199\.External Links:[Document](https://dx.doi.org/10.1016/j.ausmj.2020.03.005)Cited by:[§1](https://arxiv.org/html/2607.06017#S1.p4.1)\.
- \[34\]G\. Yang and R\. Roet\-Green\(2026\)On the design of an ai\-human service system with strategic customers: should ai be mandated?\.SSRN Electronic Journal\.External Links:[Document](https://dx.doi.org/10.2139/ssrn.6475258),[Link](https://ssrn.com/abstract=6475258)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px1.p1.1)\.
- \[35\]Z\. Yang, R\. Srikant, and L\. Ying\(2023\)Learning while scheduling in multi\-server systems with unknown statistics: maxweight with discounted ucb\.InProceedings of The 26th International Conference on Artificial Intelligence and Statistics,Proceedings of Machine Learning Research, Vol\.206,pp\. 4275–4312\.Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px4.p1.1)\.
- \[36\]H\. Yu, M\. J\. Neely, and X\. Wei\(2017\)Online convex optimization with stochastic constraints\.InAdvances in Neural Information Processing Systems 30,pp\. 1428–1438\.Cited by:[§C\.3](https://arxiv.org/html/2607.06017#A3.SS3.p5.1)\.
- \[37\]S\. Zhong, J\. Qin, Z\. Huang, and D\. Li\(2022\)CEM: machine\-human chatting handoff via causal\-enhance module\.InProceedings of the 2022 Conference on Empirical Methods in Natural Language Processing,Abu Dhabi, United Arab Emirates,pp\. 3242–3253\.External Links:[Document](https://dx.doi.org/10.18653/v1/2022.emnlp-main.213),[Link](https://aclanthology.org/2022.emnlp-main.213/)Cited by:[§1\.3](https://arxiv.org/html/2607.06017#S1.SS3.SSS0.Px1.p2.1)\.

## Appendix ALower Bound via Static Optimization Problem

### A\.1Proof of Theorem[1](https://arxiv.org/html/2607.06017#Thmtheorem1)

For allk∈\[K\]k\\in\[K\], let us sum overttthe queue dynamics Equation \([8](https://arxiv.org/html/2607.06017#S2.E8)\) and useQ1,kπ=0Q\_\{1,k\}^\{\\pi\}=0:

QT\+1,kπ=∑t=1T\(At,kπ−Dt,kπ\)\.Q\_\{T\+1,k\}^\{\\pi\}=\\sum\_\{t=1\}^\{T\}\(A\_\{t,k\}^\{\\pi\}\-D\_\{t,k\}^\{\\pi\}\)\.For simplicity of notation, let∑t\\sum\_\{t\}denote∑t=1T\\sum\_\{t=1\}^\{T\}\. Taking expectation and dividing byTT, we obtain

1T​𝔼​\[∑tAt,kπ\]=1T​𝔼​\[∑tDt,kπ\]\+1T​𝔼​\[QT\+1,kπ\]\.\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[\\sum\_\{t\}A\_\{t,k\}^\{\\pi\}\\right\]=\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[\\sum\_\{t\}D\_\{t,k\}^\{\\pi\}\\right\]\+\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[Q\_\{T\+1,k\}^\{\\pi\}\\right\]\.\(31\)
Now let us rewrite the objects associated with a policyπ\\piin a static form\. Define the average cost per type as

c¯kπ=1T​λk​𝔼​\[∑tctπ​𝟙​\{Xt=k\}\],\\bar\{c\}\_\{k\}^\{\\pi\}=\\frac\{1\}\{T\\lambda\_\{k\}\}\\mathbb\{E\}\\left\[\\sum\_\{t\}c\_\{t\}^\{\\pi\}\\mathds\{1\}\\\{X\_\{t\}=k\\\}\\right\],then it follows that

1T​𝔼​\[∑tctπ\]=∑kλk​c¯kπ\.\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[\\sum\_\{t\}c\_\{t\}^\{\\pi\}\\right\]=\\sum\_\{k\}\\lambda\_\{k\}\\bar\{c\}\_\{k\}^\{\\pi\}\.
Let

Ut,kπ:=𝟙​\{atπ=k,Qt,kπ\>0\}U\_\{t,k\}^\{\\pi\}:=\\mathds\{1\}\\\{a\_\{t\}^\{\\pi\}=k,\\;Q\_\{t,k\}^\{\\pi\}\>0\\\}be the indicator that, at slottt, the human agent serves a non\-empty type\-kkqueue\. Define

ρ¯kπ=1T​𝔼​\[∑tUt,kπ\]\.\\bar\{\\rho\}\_\{k\}^\{\\pi\}=\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[\\sum\_\{t\}U\_\{t,k\}^\{\\pi\}\\right\]\.Since at each slot the agent works on at most one type, it follows that

∑k=1Kρ¯kπ≤1\.\\sum\_\{k=1\}^\{K\}\\bar\{\\rho\}\_\{k\}^\{\\pi\}\\leq 1\.
Finally define the average final backlog per unit of time as

q¯kπ=1T​𝔼​\[QT\+1,kπ\]\.\\bar\{q\}\_\{k\}^\{\\pi\}=\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[Q\_\{T\+1,k\}^\{\\pi\}\\right\]\.\(32\)Recall that for the arrival process, givenXt=kX\_\{t\}=k,

𝔼​\[At,kπ∣Xt=k,ctπ\]=1−pk​ctπ\.\\mathbb\{E\}\[A\_\{t,k\}^\{\\pi\}\\mid X\_\{t\}=k,c\_\{t\}^\{\\pi\}\]=1\-p\_\{k\}c\_\{t\}^\{\\pi\}\.Therefore, by the tower property,

𝔼​\[At,kπ\]=𝔼​\[𝔼​\[At,kπ∣Xt,ctπ\]\]\.\\mathbb\{E\}\[A\_\{t,k\}^\{\\pi\}\]=\\mathbb\{E\}\\\!\\left\[\\mathbb\{E\}\[A\_\{t,k\}^\{\\pi\}\\mid X\_\{t\},c\_\{t\}^\{\\pi\}\]\\right\]\.SinceAt,kπ=0A\_\{t,k\}^\{\\pi\}=0wheneverXt≠kX\_\{t\}\\neq k, we get

𝔼​\[At,kπ\]=𝔼​\[𝟏​\{Xt=k\}​𝔼​\[At,kπ∣Xt=k,ctπ\]\]=𝔼​\[𝟏​\{Xt=k\}​\(1−pk​ctπ\)\]\.\\mathbb\{E\}\[A\_\{t,k\}^\{\\pi\}\]=\\mathbb\{E\}\\\!\\left\[\\mathbf\{1\}\\\{X\_\{t\}=k\\\}\\,\\mathbb\{E\}\[A\_\{t,k\}^\{\\pi\}\\mid X\_\{t\}=k,c\_\{t\}^\{\\pi\}\]\\right\]=\\mathbb\{E\}\\\!\\left\[\\mathbf\{1\}\\\{X\_\{t\}=k\\\}\(1\-p\_\{k\}c\_\{t\}^\{\\pi\}\)\\right\]\.Expanding the right\-hand side,

𝔼​\[At,kπ\]=𝔼​\[𝟏​\{Xt=k\}\]−pk​𝔼​\[𝟏​\{Xt=k\}​ctπ\]\.\\mathbb\{E\}\[A\_\{t,k\}^\{\\pi\}\]=\\mathbb\{E\}\[\\mathbf\{1\}\\\{X\_\{t\}=k\\\}\]\-p\_\{k\}\\,\\mathbb\{E\}\\\!\\left\[\\mathbf\{1\}\\\{X\_\{t\}=k\\\}c\_\{t\}^\{\\pi\}\\right\]\.Usingℙ​\(Xt=k\)=λk\\mathbb\{P\}\(X\_\{t\}=k\)=\\lambda\_\{k\}, this becomes

𝔼​\[At,kπ\]=λk−pk​𝔼​\[𝟏​\{Xt=k\}​ctπ\]\.\\mathbb\{E\}\[A\_\{t,k\}^\{\\pi\}\]=\\lambda\_\{k\}\-p\_\{k\}\\,\\mathbb\{E\}\\\!\\left\[\\mathbf\{1\}\\\{X\_\{t\}=k\\\}c\_\{t\}^\{\\pi\}\\right\]\.Summing overt=1,…,Tt=1,\\dots,T, dividing byTT, and using the definition ofc¯kπ\\bar\{c\}\_\{k\}^\{\\pi\}, we obtain

1T​𝔼​\[∑tAt,kπ\]=λk−pk​1T​𝔼​\[∑t𝟏​\{Xt=k\}​ctπ\]=λk−pk​λk​c¯kπ\.\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[\\sum\_\{t\}A\_\{t,k\}^\{\\pi\}\\right\]=\\lambda\_\{k\}\-p\_\{k\}\\,\\frac\{1\}\{T\}\\mathbb\{E\}\\\!\\left\[\\sum\_\{t\}\\mathbf\{1\}\\\{X\_\{t\}=k\\\}c\_\{t\}^\{\\pi\}\\right\]=\\lambda\_\{k\}\-p\_\{k\}\\lambda\_\{k\}\\bar\{c\}\_\{k\}^\{\\pi\}\.Hence

1T​𝔼​\[∑tAt,kπ\]=λk​\(1−pk​c¯kπ\)\.\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[\\sum\_\{t\}A\_\{t,k\}^\{\\pi\}\\right\]=\\lambda\_\{k\}\(1\-p\_\{k\}\\bar\{c\}\_\{k\}^\{\\pi\}\)\.\(33\)For the service process, conditional on actually serving a non\-empty queue of typekk, recall

𝔼​\[Dt,kπ∣Ut,kπ=1\]=μk\.\\mathbb\{E\}\[D\_\{t,k\}^\{\\pi\}\\mid U\_\{t,k\}^\{\\pi\}=1\]=\\mu\_\{k\}\.SinceDt,kπ=0D\_\{t,k\}^\{\\pi\}=0wheneverUt,kπ=0U\_\{t,k\}^\{\\pi\}=0, we can write

𝔼​\[Dt,kπ\]=𝔼​\[Dt,kπ∣Ut,kπ=1\]​ℙ​\(Ut,kπ=1\)=μk​𝔼​\[Ut,kπ\]\.\\mathbb\{E\}\[D\_\{t,k\}^\{\\pi\}\]=\\mathbb\{E\}\[D\_\{t,k\}^\{\\pi\}\\mid U\_\{t,k\}^\{\\pi\}=1\]\\mathbb\{P\}\(U\_\{t,k\}^\{\\pi\}=1\)=\\mu\_\{k\}\\,\\mathbb\{E\}\[U\_\{t,k\}^\{\\pi\}\]\.Therefore,

1T​𝔼​\[∑tDt,kπ\]=μk​1T​𝔼​\[∑tUt,kπ\]=μk​ρ¯kπ\.\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[\\sum\_\{t\}D\_\{t,k\}^\{\\pi\}\\right\]=\\mu\_\{k\}\\,\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[\\sum\_\{t\}U\_\{t,k\}^\{\\pi\}\\right\]=\\mu\_\{k\}\\bar\{\\rho\}\_\{k\}^\{\\pi\}\.\(34\)
Putting Equations[32](https://arxiv.org/html/2607.06017#A1.E32),[33](https://arxiv.org/html/2607.06017#A1.E33)and[34](https://arxiv.org/html/2607.06017#A1.E34)into Equation \([31](https://arxiv.org/html/2607.06017#A1.E31)\), we get

λk​\(1−pk​c¯kπ\)=μk​ρ¯kπ\+q¯kπ\.\\lambda\_\{k\}\(1\-p\_\{k\}\\bar\{c\}\_\{k\}^\{\\pi\}\)=\\mu\_\{k\}\\bar\{\\rho\}\_\{k\}^\{\\pi\}\+\\bar\{q\}\_\{k\}^\{\\pi\}\.\(35\)So it follows that policyπ\\pi, through\(𝒄¯π,𝝆¯π\)\(\\bar\{\\bm\{c\}\}^\{\\pi\},\\bar\{\\bm\{\\rho\}\}^\{\\pi\}\), violates the static constraints of the optimization problem in \([13](https://arxiv.org/html/2607.06017#S2.E13)\) by a term controlled by the final backlog𝒒¯π\\bar\{\\bm\{q\}\}^\{\\pi\}\.

Let us use a duality argument\. Consider the static problemOPT​\(𝜽\)\\text\{OPT\}\(\\bm\{\\theta\}\)in \([13](https://arxiv.org/html/2607.06017#S2.E13)\)\. Introduce the dual multipliersyk≥0y\_\{k\}\\geq 0for the queue\-balance constraints

λk​\(1−pk​ck\)−μk​ρk≤0,\\lambda\_\{k\}\(1\-p\_\{k\}c\_\{k\}\)\-\\mu\_\{k\}\\rho\_\{k\}\\leq 0,and the multiplierν≥0\\nu\\geq 0for the capacity constraint∑k=1Kρk≤1\\sum\_\{k=1\}^\{K\}\\rho\_\{k\}\\leq 1\. The Lagrangian of the optimization problem is then

ℒ​\(𝒄,𝝆,𝜽;𝒚,ν\)=∑kλk​ck\+∑kyk​\(λk​\(1−pk​ck\)−μk​ρk\)\+ν​\(∑kρk−1\)\.\\mathcal\{L\}\(\\bm\{c\},\\bm\{\\rho\},\\bm\{\\theta\};\\bm\{y\},\\nu\)=\\sum\_\{k\}\\lambda\_\{k\}c\_\{k\}\+\\sum\_\{k\}y\_\{k\}\\big\(\\lambda\_\{k\}\(1\-p\_\{k\}c\_\{k\}\)\-\\mu\_\{k\}\\rho\_\{k\}\\big\)\+\\nu\\big\(\\sum\_\{k\}\\rho\_\{k\}\-1\\big\)\.Let\(𝒚∗,ν∗\)\(\\bm\{y\}^\{\*\},\\nu^\{\*\}\)be an optimal dual solution\. Since the static linear program in[13](https://arxiv.org/html/2607.06017#S2.E13)is feasible and bounded, by strong duality

OPT​\(𝜽\)=inf𝒄,𝝆ℒ​\(𝒄,𝝆,𝜽;𝒚∗,ν∗\)\.\\text\{OPT\}\(\\bm\{\\theta\}\)=\\inf\_\{\\bm\{c\},\\bm\{\\rho\}\}\\mathcal\{L\}\(\\bm\{c\},\\bm\{\\rho\},\\bm\{\\theta\};\\bm\{y\}^\{\*\},\\nu^\{\*\}\)\.
So for every choice of\(𝒄,𝝆\)\(\\bm\{c\},\\bm\{\\rho\}\)it holds that

ℒ​\(𝒄,𝝆,𝜽;𝒚∗,ν∗\)≥OPT​\(𝜽\)\.\\mathcal\{L\}\(\\bm\{c\},\\bm\{\\rho\},\\bm\{\\theta\};\\bm\{y\}^\{\*\},\\nu^\{\*\}\)\\geq\\text\{OPT\}\(\\bm\{\\theta\}\)\.From here, using the definition ofℒ\\mathcal\{L\}, we get

∑kλk​ck≥OPT​\(𝜽\)−∑kyk∗​\(λk​\(1−pk​ck\)−μk​ρk\)−ν∗​\(∑kρk−1\)\.\\sum\_\{k\}\\lambda\_\{k\}c\_\{k\}\\geq\\text\{OPT\}\(\\bm\{\\theta\}\)\-\\sum\_\{k\}y\_\{k\}^\{\*\}\\big\(\\lambda\_\{k\}\(1\-p\_\{k\}c\_\{k\}\)\-\\mu\_\{k\}\\rho\_\{k\}\\big\)\-\\nu^\{\*\}\\big\(\\sum\_\{k\}\\rho\_\{k\}\-1\\big\)\.\(36\)
Now let us use \([36](https://arxiv.org/html/2607.06017#A1.E36)\) with𝒄=𝒄¯π\\bm\{c\}=\\bar\{\\bm\{c\}\}^\{\\pi\}and𝝆=𝝆¯π\\bm\{\\rho\}=\\bar\{\\bm\{\\rho\}\}^\{\\pi\}\. Since∑kρ¯kπ≤1\\sum\_\{k\}\\bar\{\\rho\}\_\{k\}^\{\\pi\}\\leq 1andν∗≥0\\nu^\{\*\}\\geq 0, we have

−ν∗​\(∑kρ¯kπ−1\)≥0\.\-\\nu^\{\*\}\\big\(\\sum\_\{k\}\\bar\{\\rho\}\_\{k\}^\{\\pi\}\-1\\big\)\\geq 0\.In addition, using Equation \([35](https://arxiv.org/html/2607.06017#A1.E35)\), we get

∑kλk​c¯kπ≥OPT​\(𝜽\)−∑kyk∗​q¯kπ\.\\sum\_\{k\}\\lambda\_\{k\}\\bar\{c\}\_\{k\}^\{\\pi\}\\geq\\text\{OPT\}\(\\bm\{\\theta\}\)\-\\sum\_\{k\}y\_\{k\}^\{\*\}\\bar\{q\}\_\{k\}^\{\\pi\}\.\(37\)
We now conclude the lower bound by multiplying \([37](https://arxiv.org/html/2607.06017#A1.E37)\) byTTand using the definition of the averages

𝔼​\[∑tctπ\]≥T​OPT​\(𝜽\)−∑kyk∗​𝔼​\[QT\+1,kπ\]\.\\mathbb\{E\}\\big\[\\sum\_\{t\}c\_\{t\}^\{\\pi\}\\big\]\\geq T\\text\{OPT\}\(\\bm\{\\theta\}\)\-\\sum\_\{k\}y\_\{k\}^\{\*\}\\,\\mathbb\{E\}\[Q\_\{T\+1,k\}^\{\\pi\}\]\.Using the definition of total final cost, we get

𝔼​\[Cπ​\(T\)\]=𝔼​\[∑tctπ\]\+∑krk​𝔼​\[QT\+1,kπ\]≥T​OPT​\(𝜽\)\+∑k\(rk−yk∗\)​𝔼​\[QT\+1,kπ\]\.\\mathbb\{E\}\[C^\{\\pi\}\(T\)\]=\\mathbb\{E\}\\big\[\\sum\_\{t\}c\_\{t\}^\{\\pi\}\\big\]\+\\sum\_\{k\}r\_\{k\}\\,\\mathbb\{E\}\[Q\_\{T\+1,k\}^\{\\pi\}\]\\geq T\\text\{OPT\}\(\\bm\{\\theta\}\)\+\\sum\_\{k\}\(r\_\{k\}\-y\_\{k\}^\{\*\}\)\\mathbb\{E\}\[Q\_\{T\+1,k\}^\{\\pi\}\]\.Finally, since we assumed that for allk∈\[K\]k\\in\[K\]rk≥yk∗r\_\{k\}\\geq y\_\{k\}^\{\*\}, the second term of the sum in the rhs is non\-negative\. Hence by taking the infimum over the set of policies we obtain

infπ∈Π∗𝔼​\[Cπ​\(T\)\]≥T⋅OPT​\(𝜽\),\\inf\_\{\\pi\\in\\Pi^\{\*\}\}\\mathbb\{E\}\[C^\{\\pi\}\(T\)\]\\geq T\\cdot\\text\{OPT\}\(\\bm\{\\theta\}\),which proves the theorem\.□\\square

### A\.2Proof of Proposition[1](https://arxiv.org/html/2607.06017#Thmproposition1)

SincecXt∗=ck∗c\_\{X\_\{t\}\}^\{\*\}=c\_\{k\}^\{\*\}wheneverXt=kX\_\{t\}=k, and the arrivals are i\.i\.d\. with distribution𝝀\\bm\{\\lambda\}, it holds that

1T​∑t=1T𝔼​\[cXt∗\]=∑k=1Kλk​ck∗=OPT​\(𝜽\)\.\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[c\_\{X\_\{t\}\}^\{\*\}\]=\\sum\_\{k=1\}^\{K\}\\lambda\_\{k\}c\_\{k\}^\{\*\}=\\text\{OPT\}\(\\bm\{\\theta\}\)\.Therefore, using Theorem[1](https://arxiv.org/html/2607.06017#Thmtheorem1)in the definition of regret \([12](https://arxiv.org/html/2607.06017#S2.E12)\), we obtain

RTπ≤∑t=1T𝔼​\[ctπ\]−T​OPT​\(𝜽\)\+∑k=1Krk​𝔼​\[QT\+1,kπ\]=∑t=1T𝔼​\[ctπ−cXt∗\]\+∑k=1Krk​𝔼​\[QT\+1,kπ\]\.R\_\{T\}^\{\\pi\}\\leq\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[c\_\{t\}^\{\\pi\}\]\-T\\text\{OPT\}\(\\bm\{\\theta\}\)\+\\sum\_\{k=1\}^\{K\}r\_\{k\}\\,\\mathbb\{E\}\[Q\_\{T\+1,k\}^\{\\pi\}\]=\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[c\_\{t\}^\{\\pi\}\-c\_\{X\_\{t\}\}^\{\*\}\]\+\\sum\_\{k=1\}^\{K\}r\_\{k\}\\,\\mathbb\{E\}\[Q\_\{T\+1,k\}^\{\\pi\}\]\.□\\square

## Appendix BUCB\-DPPPolicy

### B\.1Proof of Lemma[1](https://arxiv.org/html/2607.06017#Thmlemma1)

For eachk∈\[K\]k\\in\[K\], the queue dynamics is

Qt\+1,k=Qt,k\+At,k−Dt,k\.Q\_\{t\+1,k\}=Q\_\{t,k\}\+A\_\{t,k\}\-D\_\{t,k\}\.Therefore,

Qt\+1,k2=Qt,k2\+\(At,k−Dt,k\)2\+2​Qt,k​\(At,k−Dt,k\)\.Q\_\{t\+1,k\}^\{2\}=Q\_\{t,k\}^\{2\}\+\(A\_\{t,k\}\-D\_\{t,k\}\)^\{2\}\+2Q\_\{t,k\}\(A\_\{t,k\}\-D\_\{t,k\}\)\.Using the definition ofΦ\\Phi, we obtain

Φ​\(𝑸t\+1\)−Φ​\(𝑸t\)=12​∑k=1Krk​\(At,k−Dt,k\)2\+∑k=1Krk​Qt,k​\(At,k−Dt,k\)\.\\Phi\(\\bm\{Q\}\_\{t\+1\}\)\-\\Phi\(\\bm\{Q\}\_\{t\}\)=\\frac\{1\}\{2\}\\sum\_\{k=1\}^\{K\}r\_\{k\}\(A\_\{t,k\}\-D\_\{t,k\}\)^\{2\}\+\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\(A\_\{t,k\}\-D\_\{t,k\}\)\.At each slot there is at most one arrival to the human queues and at most one departure\. Hence the vector\(At,k−Dt,k\)k∈\[K\]\(A\_\{t,k\}\-D\_\{t,k\}\)\_\{k\\in\[K\]\}has at most two nonzero entries, each with absolute value at most one\. Thus,

∑k=1K\(At,k−Dt,k\)2≤2\.\\sum\_\{k=1\}^\{K\}\(A\_\{t,k\}\-D\_\{t,k\}\)^\{2\}\\leq 2\.Sincerk≤rmaxr\_\{k\}\\leq r\_\{\\max\}for allk∈\[K\]k\\in\[K\], it follows that

12​∑k=1Krk​\(At,k−Dt,k\)2≤rmax\.\\frac\{1\}\{2\}\\sum\_\{k=1\}^\{K\}r\_\{k\}\(A\_\{t,k\}\-D\_\{t,k\}\)^\{2\}\\leq r\_\{\\max\}\.Consequently,

Φ​\(𝑸t\+1\)−Φ​\(𝑸t\)≤rmax\+∑k=1Krk​Qt,k​\(At,k−Dt,k\)\.\\Phi\(\\bm\{Q\}\_\{t\+1\}\)\-\\Phi\(\\bm\{Q\}\_\{t\}\)\\leq r\_\{\\max\}\+\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\(A\_\{t,k\}\-D\_\{t,k\}\)\.Taking conditional expectation with respect toℱt\\mathcal\{F\}\_\{t\}gives the desired bound\.□\\square

TheUCB\-DPPpolicy is summarized in Algorithm[1](https://arxiv.org/html/2607.06017#alg1)\. At each slot, the policy first updates boosted estimates of the unknown chatbot and service parameters, then minimizes the optimistic drift\-plus\-penalty surrogate\. Due to the linearity of the chatbot success probability in the cost, the chatbot decision has a threshold form\.

Algorithm 1UCB\-DPPPolicy1:Input:horizon

TT, number of classes

KK, weights

\(rk\)k=1K\(r\_\{k\}\)\_\{k=1\}^\{K\}, parameter

V\>0V\>0, confidence level

δ∈\(0,1\)\\delta\\in\(0,1\)\.

2:Initialize:

Q1,k=0Q\_\{1,k\}=0and

Nk​\(0\)=Sk​\(0\)=Mk​\(0\)=Gk​\(0\)=0N\_\{k\}\(0\)=S\_\{k\}\(0\)=M\_\{k\}\(0\)=G\_\{k\}\(0\)=0for all

k∈\[K\]k\\in\[K\]\.

3:for

t=1,…,Tt=1,\\ldots,Tdo

4:Observe the current queues

𝑸t\\bm\{Q\}\_\{t\}and the arriving type

XtX\_\{t\}\.

5:For each

k∈\[K\]k\\in\[K\], compute

μ^k​\(t−1\)\\hat\{\\mu\}\_\{k\}\(t\-1\)as in \([16](https://arxiv.org/html/2607.06017#S3.E16)\) and

μ¯k​\(t−1\)\\bar\{\\mu\}\_\{k\}\(t\-1\)as in \([17](https://arxiv.org/html/2607.06017#S3.E17)\)\.

6:For each

k∈\[K\]k\\in\[K\], compute

p^k​\(t−1\)\\hat\{p\}\_\{k\}\(t\-1\)as in \([19](https://arxiv.org/html/2607.06017#S3.E19)\) and

p¯k​\(t−1\)\\bar\{p\}\_\{k\}\(t\-1\)as in \([20](https://arxiv.org/html/2607.06017#S3.E20)\)\.

7:Choose the*chatbot cost*

ct=\{1,if​rXt​Qt,Xt​p¯Xt​\(t−1\)≥V,0,otherwise\.c\_\{t\}=\\begin\{cases\}1,&\\text\{if \}r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\\geq V,\\\\ 0,&\\text\{otherwise\.\}\\end\{cases\}
8:Choose the*scheduling action*

at∈arg⁡maxk∈\[K\]⁡rk​Qt,k​μ¯k​\(t−1\)\.a\_\{t\}\\in\\arg\\max\_\{k\\in\[K\]\}r\_\{k\}Q\_\{t,k\}\\bar\{\\mu\}\_\{k\}\(t\-1\)\.
9:If all queues are empty, choose

ata\_\{t\}arbitrarily\.

10:Apply the chatbot decision and observe:

Yt=𝟙​\{chatbot succeeds at slot​t\}Y\_\{t\}=\\mathds\{1\}\\\{\\text\{chatbot succeeds at slot \}t\\\}\.

11:Define the human\-queue arrivals:

At,k=𝟙​\{Xt=k\}​\(1−Yt\)A\_\{t,k\}=\\mathds\{1\}\\\{X\_\{t\}=k\\\}\(1\-Y\_\{t\}\)for all

k∈\[K\]k\\in\[K\]\.

12:*Serve*queue

ata\_\{t\}\. If

Qt,at\>0Q\_\{t,a\_\{t\}\}\>0, observe the service outcome

Dt,atD\_\{t,a\_\{t\}\}; otherwise set

Dt,at=0D\_\{t,a\_\{t\}\}=0\.

13:*Set*

Dt,k=0D\_\{t,k\}=0for all

k≠atk\\neq a\_\{t\}\.

14:*Update*the queues according to:

Qt\+1,k=Qt,k\+At,k−Dt,k,k∈\[K\]\.Q\_\{t\+1,k\}=Q\_\{t,k\}\+A\_\{t,k\}\-D\_\{t,k\},\\qquad k\\in\[K\]\.
15:*Update*the chatbot counters:

MXt​\(t\)=MXt​\(t−1\)\+ct,GXt​\(t\)=GXt​\(t−1\)\+Yt\.M\_\{X\_\{t\}\}\(t\)=M\_\{X\_\{t\}\}\(t\-1\)\+c\_\{t\},\\qquad G\_\{X\_\{t\}\}\(t\)=G\_\{X\_\{t\}\}\(t\-1\)\+Y\_\{t\}\.
16:*Update*the service counters:

Nat​\(t\)=Nat​\(t−1\)\+𝟙​\{Qt,at\>0\},Sat​\(t\)=Sat​\(t−1\)\+Dt,at\.N\_\{a\_\{t\}\}\(t\)=N\_\{a\_\{t\}\}\(t\-1\)\+\\mathds\{1\}\\\{Q\_\{t,a\_\{t\}\}\>0\\\},\\qquad S\_\{a\_\{t\}\}\(t\)=S\_\{a\_\{t\}\}\(t\-1\)\+D\_\{t,a\_\{t\}\}\.
17:All counters not explicitly updated remain unchanged\.

18:endfor

## Appendix CRegret Bound

### C\.1Proof of Regret Decomposition Lemma[2](https://arxiv.org/html/2607.06017#Thmlemma2)

Recall that, according to Proposition[1](https://arxiv.org/html/2607.06017#Thmproposition1), the regret of any policy, and in particular that ofUCB\-DPP, satisfies

RTUCB\-DPP≤∑t=1T𝔼​\[ctUCB\-DPP−cXt∗\]\+∑k=1Krk​𝔼​\[QT\+1,kUCB\-DPP\]\.R\_\{T\}^\{\\texttt\{UCB\-DPP\}\}\\leq\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[c\_\{t\}^\{\\texttt\{UCB\-DPP\}\}\-c\_\{X\_\{t\}\}^\{\*\}\]\+\\sum\_\{k=1\}^\{K\}r\_\{k\}\\,\\mathbb\{E\}\[Q\_\{T\+1,k\}^\{\\texttt\{UCB\-DPP\}\}\]\.For ease of notation, from now on we omit the superscriptUCB\-DPPfrom all relevant quantities whenever no ambiguity arises\. In particular, we simply writectc\_\{t\},ata\_\{t\}, andQt,kQ\_\{t,k\}\. Recall that\(𝒄∗,𝝆∗\)\(\\bm\{c\}^\{\*\},\\bm\{\\rho\}^\{\*\}\)is the optimal solution of the static optimization problem \([13](https://arxiv.org/html/2607.06017#S2.E13)\)\.

##### Decomposition into good and bad events\.

For everyt∈\[T\]t\\in\[T\],

𝔼​\[ct−cXt∗\]=𝔼​\[\(ct−cXt∗\)​𝟙​\{𝒢t\}\]\+𝔼​\[\(ct−cXt∗\)​𝟙​\{𝒢¯t\}\]\.\\mathbb\{E\}\[c\_\{t\}\-c\_\{X\_\{t\}\}^\{\*\}\]=\\mathbb\{E\}\[\(c\_\{t\}\-c\_\{X\_\{t\}\}^\{\*\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\]\+\\mathbb\{E\}\[\(c\_\{t\}\-c\_\{X\_\{t\}\}^\{\*\}\)\\mathds\{1\}\\\{\\overline\{\\mathscr\{G\}\}\_\{t\}\\\}\]\.Since bothctc\_\{t\}andcXt∗c\_\{X\_\{t\}\}^\{\*\}are in\[0,1\]\[0,1\], it follows that

ct−cXt∗≤1\.c\_\{t\}\-c\_\{X\_\{t\}\}^\{\*\}\\leq 1\.Hence

𝔼​\[ct−cXt∗\]≤𝔼​\[\(ct−cXt∗\)​𝟙​\{𝒢t\}\]\+ℙ​\(𝒢¯t\)\.\\mathbb\{E\}\[c\_\{t\}\-c\_\{X\_\{t\}\}^\{\*\}\]\\leq\\mathbb\{E\}\[\(c\_\{t\}\-c\_\{X\_\{t\}\}^\{\*\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\]\+\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{t\}\)\.\(38\)
We can now observe that𝒢¯t⊆𝒢¯T\\overline\{\\mathscr\{G\}\}\_\{t\}\\subseteq\\overline\{\\mathscr\{G\}\}\_\{T\}, hence

ℙ​\(𝒢¯t\)≤ℙ​\(𝒢¯T\)\.\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{t\}\)\\leq\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}\)\.Summing overtt, we obtain:

∑t=1T𝔼​\[ct−cXt∗\]≤∑t=1T𝔼​\[\(ct−cXt∗\)​𝟙​\{𝒢t\}\]\+T​ℙ​\(𝒢¯T\)\.\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[c\_\{t\}\-c\_\{X\_\{t\}\}^\{\*\}\]\\leq\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[\(c\_\{t\}\-c\_\{X\_\{t\}\}^\{\*\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\]\+T\\,\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}\)\.\(39\)The second term is exactlyR2​\(T\)R\_\{2\}\(T\)\.

##### Drift Plus Penalty under good events\.

Letℋt\\mathcal\{H\}\_\{t\}denote the information available at the beginning of slottt, before the arrival typeXtX\_\{t\}is observed\. By the i\.i\.d\. assumption on the arrivals, for everyk∈\[K\]k\\in\[K\],

ℙ​\(Xt=k∣ℋt\)=λk\.\\mathbb\{P\}\(X\_\{t\}=k\\mid\\mathcal\{H\}\_\{t\}\)=\\lambda\_\{k\}\.
By the bound on the conditional drift in Lemma[1](https://arxiv.org/html/2607.06017#Thmlemma1), together with the conditional expectations on arrivals and departures, we have

Δt\+V​ct≤rmax\+rXt​Qt,Xt​\(1−pXt​ct\)−rat​Qt,at​μat\+V​ct\.\\Delta\_\{t\}\+Vc\_\{t\}\\leq r\_\{\\max\}\+r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}\(1\-p\_\{X\_\{t\}\}c\_\{t\}\)\-r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\mu\_\{a\_\{t\}\}\+Vc\_\{t\}\.\(40\)Let us add and subtract the quantitiesrXt​Qt,Xt​\(1−p¯Xt​\(t−1\)​ct\)r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}\(1\-\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)c\_\{t\}\)andrat​Qt,at​μ¯at​\(t−1\)r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\. We obtain

Δt\+V​ct≤\\displaystyle\\Delta\_\{t\}\+Vc\_\{t\}\\leqrmax\+\(V​ct\+rXt​Qt,Xt​\(1−p¯Xt​\(t−1\)​ct\)−rat​Qt,at​μ¯at​\(t−1\)\)\\displaystyle\\;r\_\{\\max\}\+\\left\(Vc\_\{t\}\+r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}\(1\-\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)c\_\{t\}\)\-r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\\right\)\+rXt​Qt,Xt​ct​\(p¯Xt​\(t−1\)−pXt\)\+rat​Qt,at​\(μ¯at​\(t−1\)−μat\)\.\\displaystyle\+r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}c\_\{t\}\\left\(\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\-p\_\{X\_\{t\}\}\\right\)\+r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\left\(\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\-\\mu\_\{a\_\{t\}\}\\right\)\.
By policy definition,UCB\-DPPchooses at eachttthe pair\(ct,at\)\(c\_\{t\},a\_\{t\}\)minimizing

V​c\+rXt​Qt,Xt​\(1−p¯Xt​\(t−1\)​c\)−ra​Qt,a​μ¯a​\(t−1\),Vc\+r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}\(1\-\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)c\)\-r\_\{a\}Q\_\{t,a\}\\bar\{\\mu\}\_\{a\}\(t\-1\),overc∈\[0,1\]c\\in\[0,1\]anda∈\{1,…,K\}a\\in\\\{1,\\ldots,K\\\}\. Therefore, for every alternative pair\(c~t,a~t\)\(\\tilde\{c\}\_\{t\},\\tilde\{a\}\_\{t\}\),

Δt\+V​ct≤\\displaystyle\\Delta\_\{t\}\+Vc\_\{t\}\\leqrmax\+\(V​c~t\+rXt​Qt,Xt​\(1−p¯Xt​\(t−1\)​c~t\)−ra~t​Qt,a~t​μ¯a~t​\(t−1\)\)\\displaystyle\\;r\_\{\\max\}\+\\left\(V\\tilde\{c\}\_\{t\}\+r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}\(1\-\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\\tilde\{c\}\_\{t\}\)\-r\_\{\\tilde\{a\}\_\{t\}\}Q\_\{t,\\tilde\{a\}\_\{t\}\}\\bar\{\\mu\}\_\{\\tilde\{a\}\_\{t\}\}\(t\-1\)\\right\)\(41\)\+rXt​Qt,Xt​ct​\(p¯Xt​\(t−1\)−pXt\)\+rat​Qt,at​\(μ¯at​\(t−1\)−μat\)\.\\displaystyle\+r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}c\_\{t\}\\left\(\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\-p\_\{X\_\{t\}\}\\right\)\+r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\left\(\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\-\\mu\_\{a\_\{t\}\}\\right\)\.

##### Comparison with the static benchmark\.

We now compare the policy with the static solution\(𝒄∗,𝝆∗\)\(\\bm\{c\}^\{\*\},\\bm\{\\rho\}^\{\*\}\)\. Choose\(c~t,a~t\)\(\\tilde\{c\}\_\{t\},\\tilde\{a\}\_\{t\}\)in Equation \([41](https://arxiv.org/html/2607.06017#A3.E41)\) as follows:

- •ifXt=kX\_\{t\}=k, thenc~t=ck∗\\tilde\{c\}\_\{t\}=c\_\{k\}^\{\*\};
- •choosea~t=j\\tilde\{a\}\_\{t\}=jwith probabilityρj∗\\rho\_\{j\}^\{\*\}\.

Note that this randomized scheduling rule, induced by the solution of the static optimization problem, is not queue\-aware: if the selected queue is empty, then no service takes place during that slot, so the policy effectively wastes one service opportunity\.

Substitutingc~t=cXt∗\\tilde\{c\}\_\{t\}=c\_\{X\_\{t\}\}^\{\*\}into \([41](https://arxiv.org/html/2607.06017#A3.E41)\) and taking conditional expectation with respect to the randomized comparison actiona~t\\tilde\{a\}\_\{t\}, given the history up to the beginning of slotttand the realized typeXtX\_\{t\}, we first obtain

Δt\+V​\(ct−cXt∗\)≤\\displaystyle\\Delta\_\{t\}\+V\(c\_\{t\}\-c\_\{X\_\{t\}\}^\{\*\}\)\\leqrmax\+rXt​Qt,Xt​\(1−p¯Xt​\(t−1\)​cXt∗\)−∑j=1Kρj∗​rj​Qt,j​μ¯j​\(t−1\)\\displaystyle\\;r\_\{\\max\}\+r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}\\left\(1\-\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)c\_\{X\_\{t\}\}^\{\*\}\\right\)\-\\sum\_\{j=1\}^\{K\}\\rho\_\{j\}^\{\*\}\\,r\_\{j\}Q\_\{t,j\}\\bar\{\\mu\}\_\{j\}\(t\-1\)\+rXt​Qt,Xt​ct​\(p¯Xt​\(t−1\)−pXt\)\+rat​Qt,at​\(μ¯at​\(t−1\)−μat\)\.\\displaystyle\+r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}c\_\{t\}\\left\(\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\-p\_\{X\_\{t\}\}\\right\)\+r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\left\(\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\-\\mu\_\{a\_\{t\}\}\\right\)\.Here we used that

𝔼​\[ra~t​Qt,a~t​μ¯a~t​\(t−1\)∣ℱt\]=∑j=1Kρj∗​rj​Qt,j​μ¯j​\(t−1\)\.\\mathbb\{E\}\\\!\\left\[r\_\{\\tilde\{a\}\_\{t\}\}Q\_\{t,\\tilde\{a\}\_\{t\}\}\\bar\{\\mu\}\_\{\\tilde\{a\}\_\{t\}\}\(t\-1\)\\mid\\mathcal\{F\}\_\{t\}\\right\]=\\sum\_\{j=1\}^\{K\}\\rho\_\{j\}^\{\*\}\\,r\_\{j\}Q\_\{t,j\}\\bar\{\\mu\}\_\{j\}\(t\-1\)\.
We then take conditional expectation with respect toXtX\_\{t\}, conditioning on the information available at the beginning of slottt\. Sinceℙ​\(Xt=k∣ℋt\)=λk\\mathbb\{P\}\(X\_\{t\}=k\\mid\\mathcal\{H\}\_\{t\}\)=\\lambda\_\{k\}, we obtain

𝔼​\[Δt\+V​\(ct−cXt∗\)∣ℋt\]≤\\displaystyle\\mathbb\{E\}\\\!\\left\[\\Delta\_\{t\}\+V\(c\_\{t\}\-c\_\{X\_\{t\}\}^\{\*\}\)\\mid\\mathcal\{H\}\_\{t\}\\right\]\\leqrmax\+∑k=1Krk​Qt,k​\(λk​\(1−p¯k​\(t−1\)​ck∗\)−ρk∗​μ¯k​\(t−1\)\)\\displaystyle\\;r\_\{\\max\}\+\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\\left\(\\lambda\_\{k\}\(1\-\\bar\{p\}\_\{k\}\(t\-1\)c\_\{k\}^\{\*\}\)\-\\rho\_\{k\}^\{\*\}\\bar\{\\mu\}\_\{k\}\(t\-1\)\\right\)\+𝔼​\[rXt​Qt,Xt​ct​\(p¯Xt​\(t−1\)−pXt\)∣ℋt\]\\displaystyle\+\\mathbb\{E\}\\\!\\left\[r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}c\_\{t\}\\left\(\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\-p\_\{X\_\{t\}\}\\right\)\\mid\\mathcal\{H\}\_\{t\}\\right\]\+𝔼​\[rat​Qt,at​\(μ¯at​\(t−1\)−μat\)∣ℋt\]\.\\displaystyle\+\\mathbb\{E\}\\\!\\left\[r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\left\(\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\-\\mu\_\{a\_\{t\}\}\\right\)\\mid\\mathcal\{H\}\_\{t\}\\right\]\.
Now suppose that the good event𝒢t\\mathscr\{G\}\_\{t\}holds\. Then, for everyk∈\[K\]k\\in\[K\],

p¯k​\(t−1\)≥pkandμ¯k​\(t−1\)≥μk\.\\bar\{p\}\_\{k\}\(t\-1\)\\geq p\_\{k\}\\qquad\\text\{and\}\\qquad\\bar\{\\mu\}\_\{k\}\(t\-1\)\\geq\\mu\_\{k\}\.Therefore,

λk​\(1−p¯k​\(t−1\)​ck∗\)−ρk∗​μ¯k​\(t−1\)≤λk​\(1−pk​ck∗\)−ρk∗​μk\.\\lambda\_\{k\}\(1\-\\bar\{p\}\_\{k\}\(t\-1\)c\_\{k\}^\{\*\}\)\-\\rho\_\{k\}^\{\*\}\\bar\{\\mu\}\_\{k\}\(t\-1\)\\leq\\lambda\_\{k\}\(1\-p\_\{k\}c\_\{k\}^\{\*\}\)\-\\rho\_\{k\}^\{\*\}\\mu\_\{k\}\.Since\(𝒄∗,𝝆∗\)\(\\bm\{c\}^\{\*\},\\bm\{\\rho\}^\{\*\}\)is feasible for the static problem,

λk​\(1−pk​ck∗\)−ρk∗​μk≤0\.\\lambda\_\{k\}\(1\-p\_\{k\}c\_\{k\}^\{\*\}\)\-\\rho\_\{k\}^\{\*\}\\mu\_\{k\}\\leq 0\.Hence, under𝒢t\\mathscr\{G\}\_\{t\},

𝔼​\[Δt\+V​\(ct−cXt∗\)∣ℋt\]≤\\displaystyle\\mathbb\{E\}\\\!\\left\[\\Delta\_\{t\}\+V\(c\_\{t\}\-c\_\{X\_\{t\}\}^\{\*\}\)\\mid\\mathcal\{H\}\_\{t\}\\right\]\\leqrmax\+𝔼​\[rXt​Qt,Xt​ct​\(p¯Xt​\(t−1\)−pXt\)∣ℋt\]\\displaystyle\\;r\_\{\\max\}\+\\mathbb\{E\}\\\!\\left\[r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}c\_\{t\}\\left\(\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\-p\_\{X\_\{t\}\}\\right\)\\mid\\mathcal\{H\}\_\{t\}\\right\]\(42\)\+𝔼​\[rat​Qt,at​\(μ¯at​\(t−1\)−μat\)∣ℋt\]\.\\displaystyle\+\\mathbb\{E\}\\\!\\left\[r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\left\(\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\-\\mu\_\{a\_\{t\}\}\\right\)\\mid\\mathcal\{H\}\_\{t\}\\right\]\.
Multiplying by𝟙​\{𝒢t\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}, taking expectation, and summing overtt, we obtain

∑t=1T𝔼​\[\(ct−cXt∗\)​𝟙​\{𝒢t\}\]≤\\displaystyle\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[\(c\_\{t\}\-c\_\{X\_\{t\}\}^\{\*\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\]\\leqrmax​TV\+1V​𝔼​\[∑t=1TrXt​Qt,Xt​ct​\(p¯Xt​\(t−1\)−pXt\)​𝟙​\{𝒢t\}\]\\displaystyle\\;\\frac\{r\_\{\\max\}T\}\{V\}\+\\frac\{1\}\{V\}\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}c\_\{t\}\\left\(\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\-p\_\{X\_\{t\}\}\\right\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\right\]\(43\)\+1V​𝔼​\[∑t=1Trat​Qt,at​\(μ¯at​\(t−1\)−μat\)​𝟙​\{𝒢t\}\]\\displaystyle\+\\frac\{1\}\{V\}\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\left\(\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\-\\mu\_\{a\_\{t\}\}\\right\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\right\]−1V​∑t=1T𝔼​\[𝟙​\{𝒢t\}​Δt\]\.\\displaystyle\-\\frac\{1\}\{V\}\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\Delta\_\{t\}\]\.

##### Control of the drift term\.

Using the definition ofΔt\\Delta\_\{t\}and linearity of expectation,

∑t=1T𝔼​\[𝟙​\{𝒢t\}​Δt\]=𝔼​\[∑t=1T𝟙​\{𝒢t\}​\(Φ​\(𝑸t\+1\)−Φ​\(𝑸t\)\)\]\.\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\Delta\_\{t\}\]=\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\left\(\\Phi\(\\bm\{Q\}\_\{t\+1\}\)\-\\Phi\(\\bm\{Q\}\_\{t\}\)\\right\)\\right\]\.Since the events\{𝒢t\}t∈\[T\]\\\{\\mathscr\{G\}\_\{t\}\\\}\_\{t\\in\[T\]\}are decreasing and nested, we have

∑t=1T𝟙​\{𝒢t\}​\(Φ​\(𝑸t\+1\)−Φ​\(𝑸t\)\)≥−Φ​\(𝑸1\)=0,\\sum\_\{t=1\}^\{T\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\left\(\\Phi\(\\bm\{Q\}\_\{t\+1\}\)\-\\Phi\(\\bm\{Q\}\_\{t\}\)\\right\)\\geq\-\\Phi\(\\bm\{Q\}\_\{1\}\)=0,because𝑸1=𝟎\\bm\{Q\}\_\{1\}=\\bm\{0\}\. Therefore,

−∑t=1T𝔼​\[𝟙​\{𝒢t\}​Δt\]≤0\.\-\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\Delta\_\{t\}\]\\leq 0\.
Plugging this into Equation \([43](https://arxiv.org/html/2607.06017#A3.E43)\), we finally get

∑t=1T𝔼​\[\(ct−cXt∗\)​𝟙​\{𝒢t\}\]≤\\displaystyle\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[\(c\_\{t\}\-c\_\{X\_\{t\}\}^\{\*\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\]\\leqrmax​TV\+1V​𝔼​\[∑t=1TrXt​Qt,Xt​ct​\(p¯Xt​\(t−1\)−pXt\)​𝟙​\{𝒢t\}\]\\displaystyle\\;\\frac\{r\_\{\\max\}T\}\{V\}\+\\frac\{1\}\{V\}\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}c\_\{t\}\\left\(\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\-p\_\{X\_\{t\}\}\\right\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\right\]\(44\)\+1V​𝔼​\[∑t=1Trat​Qt,at​\(μ¯at​\(t−1\)−μat\)​𝟙​\{𝒢t\}\]\.\\displaystyle\+\\frac\{1\}\{V\}\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\left\(\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\-\\mu\_\{a\_\{t\}\}\\right\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\right\]\.
The three terms on the right\-hand side are exactlyR3​\(T\)R\_\{3\}\(T\),R1p​\(T\)R\_\{1\}^\{p\}\(T\), andR1μ​\(T\)R\_\{1\}^\{\\mu\}\(T\)\.

##### Conclusion\.

By Proposition[1](https://arxiv.org/html/2607.06017#Thmproposition1),

RTUCB\-DPP≤∑t=1T𝔼​\[ct−cXt∗\]\+∑k=1Krk​𝔼​\[QT\+1,k\]\.R\_\{T\}^\{\\texttt\{UCB\-DPP\}\}\\leq\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[c\_\{t\}\-c\_\{X\_\{t\}\}^\{\*\}\]\+\\sum\_\{k=1\}^\{K\}r\_\{k\}\\,\\mathbb\{E\}\[Q\_\{T\+1,k\}\]\.Combining this with Equations \([39](https://arxiv.org/html/2607.06017#A3.E39)\) and[44](https://arxiv.org/html/2607.06017#A3.E44), we obtain

RTUCB\-DPP≤R1p​\(T\)\+R1μ​\(T\)\+R2​\(T\)\+R3​\(T\)\+R4​\(T\),R\_\{T\}^\{\\texttt\{UCB\-DPP\}\}\\leq R\_\{1\}^\{p\}\(T\)\+R\_\{1\}^\{\\mu\}\(T\)\+R\_\{2\}\(T\)\+R\_\{3\}\(T\)\+R\_\{4\}\(T\),where the last term is exactly

R4​\(T\)=∑k=1Krk​𝔼​\[QT\+1,k\]\.R\_\{4\}\(T\)=\\sum\_\{k=1\}^\{K\}r\_\{k\}\\,\\mathbb\{E\}\[Q\_\{T\+1,k\}\]\.This proves the lemma\.□\\square

### C\.2Proof of Proposition[2](https://arxiv.org/html/2607.06017#Thmproposition2)

We split the good event as defined in Equation \([28](https://arxiv.org/html/2607.06017#S4.E28)\) into the service\-side and chatbot\-side parts\. Define

𝒢Tμ:=⋂s=1T⋂k=1K\{\|μ^k​\(s−1\)−μk\|≤βkμ​\(s−1\)\},\\mathscr\{G\}\_\{T\}^\{\\mu\}:=\\bigcap\_\{s=1\}^\{T\}\\bigcap\_\{k=1\}^\{K\}\\left\\\{\|\\hat\{\\mu\}\_\{k\}\(s\-1\)\-\\mu\_\{k\}\|\\leq\\beta\_\{k\}^\{\\mu\}\(s\-1\)\\right\\\},and

𝒢Tp:=⋂s=1T⋂k=1K\{\|p^k​\(s−1\)−pk\|≤βkp​\(s−1\)\}\.\\mathscr\{G\}\_\{T\}^\{p\}:=\\bigcap\_\{s=1\}^\{T\}\\bigcap\_\{k=1\}^\{K\}\\left\\\{\|\\hat\{p\}\_\{k\}\(s\-1\)\-p\_\{k\}\|\\leq\\beta\_\{k\}^\{p\}\(s\-1\)\\right\\\}\.Then

𝒢T=𝒢Tμ∩𝒢Tp,\\mathscr\{G\}\_\{T\}=\\mathscr\{G\}\_\{T\}^\{\\mu\}\\cap\\mathscr\{G\}\_\{T\}^\{p\},so that

ℙ​\(𝒢¯T\)≤ℙ​\(𝒢¯Tμ\)\+ℙ​\(𝒢¯Tp\)\.\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}\)\\leq\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}^\{\\mu\}\)\+\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}^\{p\}\)\.
##### Control of the service\-side event\.

For allk∈\[K\]k\\in\[K\]andn≥1n\\geq 1, define the time of thenn\-th effective service attempt on typekkby

τn,k:=inf\{t≥1:Nk​\(t\)=n\}\.\\tau\_\{n,k\}:=\\inf\\\{t\\geq 1:N\_\{k\}\(t\)=n\\\}\.Whenτn,k<∞\\tau\_\{n,k\}<\\infty, define

dn,k:=Dτn,k,k,d\_\{n,k\}:=D\_\{\\tau\_\{n,k\},k\},namely the indicator of completion observed at thenn\-th effective service attempt on typekk\.

By the model assumptions, every time the server makes an effective service attempt on a queue of typekk, the completion occurs with probabilityμk\\mu\_\{k\}, independently of the past\. Therefore, for everykk, the sequence\(dn,k\)n≥1\(d\_\{n,k\}\)\_\{n\\geq 1\}is i\.i\.d\. Bernoulli with parameterμk\\mu\_\{k\}\.

Moreover, for everytt,

Sk​\(t\)=∑n=1Nk​\(t\)dn,k\.S\_\{k\}\(t\)=\\sum\_\{n=1\}^\{N\_\{k\}\(t\)\}d\_\{n,k\}\.Hence, ifNk​\(t\)=n≥1N\_\{k\}\(t\)=n\\geq 1, then

μ^k​\(t\)=1n​∑m=1ndm,k\.\\hat\{\\mu\}\_\{k\}\(t\)=\\frac\{1\}\{n\}\\sum\_\{m=1\}^\{n\}d\_\{m,k\}\.
Now fixs∈\{1,…,T\}s\\in\\\{1,\\dots,T\\\}andk∈\[K\]k\\in\[K\]\. IfNk​\(s−1\)=0N\_\{k\}\(s\-1\)=0, then by definition

μ^k​\(s−1\)=0,βkμ​\(s−1\)=1,\\hat\{\\mu\}\_\{k\}\(s\-1\)=0,\\qquad\\beta\_\{k\}^\{\\mu\}\(s\-1\)=1,and therefore

\|μ^k​\(s−1\)−μk\|≤1=βkμ​\(s−1\)\.\|\\hat\{\\mu\}\_\{k\}\(s\-1\)\-\\mu\_\{k\}\|\\leq 1=\\beta\_\{k\}^\{\\mu\}\(s\-1\)\.
Assume now thatNk​\(s−1\)≥1N\_\{k\}\(s\-1\)\\geq 1\. SinceNk​\(s−1\)≤s−1N\_\{k\}\(s\-1\)\\leq s\-1, we can write

ℙ​\(\|μ^k​\(s−1\)−μk\|\>βkμ​\(s−1\)\)=∑n=1s−1ℙ​\(\|μ^k​\(s−1\)−μk\|\>βkμ​\(s−1\),Nk​\(s−1\)=n\)\.\\mathbb\{P\}\\\!\\left\(\|\\hat\{\\mu\}\_\{k\}\(s\-1\)\-\\mu\_\{k\}\|\>\\beta\_\{k\}^\{\\mu\}\(s\-1\)\\right\)=\\sum\_\{n=1\}^\{s\-1\}\\mathbb\{P\}\\\!\\left\(\|\\hat\{\\mu\}\_\{k\}\(s\-1\)\-\\mu\_\{k\}\|\>\\beta\_\{k\}^\{\\mu\}\(s\-1\),\\ N\_\{k\}\(s\-1\)=n\\right\)\.On the event\{Nk​\(s−1\)=n\}\\\{N\_\{k\}\(s\-1\)=n\\\}, we have

μ^k​\(s−1\)=1n​∑m=1ndm,k,βkμ​\(s−1\)=log⁡\(4​K​\(s−1\)/δ\)2​n\.\\hat\{\\mu\}\_\{k\}\(s\-1\)=\\frac\{1\}\{n\}\\sum\_\{m=1\}^\{n\}d\_\{m,k\},\\qquad\\beta\_\{k\}^\{\\mu\}\(s\-1\)=\\sqrt\{\\frac\{\\log\\\!\\left\(4K\(s\-1\)/\\delta\\right\)\}\{2n\}\}\.Therefore,

ℙ​\(\|μ^k​\(s−1\)−μk\|\>βkμ​\(s−1\)\)≤∑n=1s−1ℙ​\(\|1n​∑m=1ndm,k−μk\|\>log⁡\(4​K​\(s−1\)/δ\)2​n\)\.\\mathbb\{P\}\\\!\\left\(\|\\hat\{\\mu\}\_\{k\}\(s\-1\)\-\\mu\_\{k\}\|\>\\beta\_\{k\}^\{\\mu\}\(s\-1\)\\right\)\\leq\\sum\_\{n=1\}^\{s\-1\}\\mathbb\{P\}\\\!\\left\(\\left\|\\frac\{1\}\{n\}\\sum\_\{m=1\}^\{n\}d\_\{m,k\}\-\\mu\_\{k\}\\right\|\>\\sqrt\{\\frac\{\\log\\\!\\left\(4K\(s\-1\)/\\delta\\right\)\}\{2n\}\}\\right\)\.By Hoeffding’s inequality, for everyn≥1n\\geq 1,

ℙ​\(\|1n​∑m=1ndm,k−μk\|\>log⁡\(4​K​\(s−1\)/δ\)2​n\)≤δ2​K​\(s−1\)\.\\mathbb\{P\}\\\!\\left\(\\left\|\\frac\{1\}\{n\}\\sum\_\{m=1\}^\{n\}d\_\{m,k\}\-\\mu\_\{k\}\\right\|\>\\sqrt\{\\frac\{\\log\\\!\\left\(4K\(s\-1\)/\\delta\\right\)\}\{2n\}\}\\right\)\\leq\\frac\{\\delta\}\{2K\(s\-1\)\}\.Hence,

ℙ​\(\|μ^k​\(s−1\)−μk\|\>βkμ​\(s−1\)\)≤∑n=1s−1δ2​K​\(s−1\)=δ2​K\.\\mathbb\{P\}\\\!\\left\(\|\\hat\{\\mu\}\_\{k\}\(s\-1\)\-\\mu\_\{k\}\|\>\\beta\_\{k\}^\{\\mu\}\(s\-1\)\\right\)\\leq\\sum\_\{n=1\}^\{s\-1\}\\frac\{\\delta\}\{2K\(s\-1\)\}=\\frac\{\\delta\}\{2K\}\.
Taking a union bound overs∈\{2,…,T\}s\\in\\\{2,\\dots,T\\\}andk∈\[K\]k\\in\[K\], we get

ℙ​\(𝒢¯Tμ\)≤∑s=2T∑k=1Kδ2​K=\(T−1\)​δ2\.\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}^\{\\mu\}\)\\leq\\sum\_\{s=2\}^\{T\}\\sum\_\{k=1\}^\{K\}\\frac\{\\delta\}\{2K\}=\\frac\{\(T\-1\)\\delta\}\{2\}\.

##### Control of the chatbot\-side event\.

Recall that the chatbot decision is bang\-bang, so the estimation ofpkp\_\{k\}is based on those slots in whichXt=kX\_\{t\}=kandct=1c\_\{t\}=1\.

For allk∈\[K\]k\\in\[K\]andn≥1n\\geq 1, define the time of thenn\-th informative chatbot exposure on typekkby

σn,k:=inf\{t≥1:Mk​\(t\)=n\}\.\\sigma\_\{n,k\}:=\\inf\\\{t\\geq 1:\\ M\_\{k\}\(t\)=n\\\}\.Whenσn,k<∞\\sigma\_\{n,k\}<\\infty, define

zn,k:=Yσn,k,z\_\{n,k\}:=Y\_\{\\sigma\_\{n,k\}\},whereYt=𝟙​\{chatbot succeeds at slot​t\}Y\_\{t\}=\\mathds\{1\}\\\{\\text\{chatbot succeeds at slot \}t\\\}\.

By construction, whenevert=σn,kt=\\sigma\_\{n,k\}we haveXt=kX\_\{t\}=kandct=1c\_\{t\}=1, hence

𝔼​\[Yt∣Xt=k,ct=1\]=pk\.\\mathbb\{E\}\[Y\_\{t\}\\mid X\_\{t\}=k,c\_\{t\}=1\]=p\_\{k\}\.Therefore, for everykk, the sequence\(zn,k\)n≥1\(z\_\{n,k\}\)\_\{n\\geq 1\}is i\.i\.d\. Bernoulli with parameterpkp\_\{k\}\.

Moreover, for everytt,

Gk​\(t\)=∑n=1Mk​\(t\)zn,k\.G\_\{k\}\(t\)=\\sum\_\{n=1\}^\{M\_\{k\}\(t\)\}z\_\{n,k\}\.Hence, ifMk​\(t\)=n≥1M\_\{k\}\(t\)=n\\geq 1, then

p^k​\(t\)=1n​∑m=1nzm,k\.\\hat\{p\}\_\{k\}\(t\)=\\frac\{1\}\{n\}\\sum\_\{m=1\}^\{n\}z\_\{m,k\}\.
Now fixs∈\{1,…,T\}s\\in\\\{1,\\dots,T\\\}andk∈\[K\]k\\in\[K\]\. IfMk​\(s−1\)=0M\_\{k\}\(s\-1\)=0, then by definition

p^k​\(s−1\)=0,βkp​\(s−1\)=1,\\hat\{p\}\_\{k\}\(s\-1\)=0,\\qquad\\beta\_\{k\}^\{p\}\(s\-1\)=1,and therefore

\|p^k​\(s−1\)−pk\|≤1=βkp​\(s−1\)\.\|\\hat\{p\}\_\{k\}\(s\-1\)\-p\_\{k\}\|\\leq 1=\\beta\_\{k\}^\{p\}\(s\-1\)\.
Assume now thatMk​\(s−1\)≥1M\_\{k\}\(s\-1\)\\geq 1\. As in the service\-side case, we decompose according to the possible values ofMk​\(s−1\)M\_\{k\}\(s\-1\)and use

p^k​\(s−1\)=1n​∑m=1nzm,kon​\{Mk​\(s−1\)=n\},\\hat\{p\}\_\{k\}\(s\-1\)=\\frac\{1\}\{n\}\\sum\_\{m=1\}^\{n\}z\_\{m,k\}\\qquad\\text\{on \}\\\{M\_\{k\}\(s\-1\)=n\\\},Therefore,

ℙ​\(\|p^k​\(s−1\)−pk\|\>βkp​\(s−1\)\)\\displaystyle\\mathbb\{P\}\\\!\\left\(\|\\hat\{p\}\_\{k\}\(s\-1\)\-p\_\{k\}\|\>\\beta\_\{k\}^\{p\}\(s\-1\)\\right\)≤∑n=1s−1ℙ​\(\|1n​∑m=1nzm,k−pk\|\>log⁡\(4​K​\(s−1\)/δ\)2​n\)\\displaystyle\\leq\\sum\_\{n=1\}^\{s\-1\}\\mathbb\{P\}\\\!\\left\(\\left\|\\frac\{1\}\{n\}\\sum\_\{m=1\}^\{n\}z\_\{m,k\}\-p\_\{k\}\\right\|\>\\sqrt\{\\frac\{\\log\\\!\\left\(4K\(s\-1\)/\\delta\\right\)\}\{2n\}\}\\right\)≤∑n=1s−1δ2​K​\(s−1\)=δ2​K,\\displaystyle\\leq\\sum\_\{n=1\}^\{s\-1\}\\frac\{\\delta\}\{2K\(s\-1\)\}=\\frac\{\\delta\}\{2K\},where the second inequality follows from Hoeffding’s inequality\.

Taking a union bound overs∈\{2,…,T\}s\\in\\\{2,\\dots,T\\\}andk∈\[K\]k\\in\[K\], we obtain

ℙ​\(𝒢¯Tp\)≤∑s=2T∑k=1Kδ2​K=\(T−1\)​δ2\.\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}^\{p\}\)\\leq\\sum\_\{s=2\}^\{T\}\\sum\_\{k=1\}^\{K\}\\frac\{\\delta\}\{2K\}=\\frac\{\(T\-1\)\\delta\}\{2\}\.

##### Conclusion\.

Combining the bounds on the two parts,

ℙ​\(𝒢¯T\)≤ℙ​\(𝒢¯Tμ\)\+ℙ​\(𝒢¯Tp\)≤δ​\(T−1\)≤δ​T\.\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}\)\\leq\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}^\{\\mu\}\)\+\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}^\{p\}\)\\leq\\delta\(T\-1\)\\leq\\delta T\.This completes the proof\.□\\square

### C\.3BoundingR4​\(T\)R\_\{4\}\(T\)

Before proceeding, we introduce several auxiliary quantities that will be used throughout the proofs\. Set

Aε:=rmax\+V​∑k=1Kλk​ckε,A\_\{\\varepsilon\}:=r\_\{\\max\}\+V\\sum\_\{k=1\}^\{K\}\\lambda\_\{k\}c\_\{k\}^\{\\varepsilon\},\(45\)and

Lε:=⌈32​log⁡\(4​K​T/δ\)ε2⌉,ηε:=ε​rmin8,δr:=2​rmax,Cr:=δr\+ηε\.L\_\{\\varepsilon\}:=\\left\\lceil\\frac\{32\\log\(4KT/\\delta\)\}\{\\varepsilon^\{2\}\}\\right\\rceil,\\qquad\\eta\_\{\\varepsilon\}:=\\frac\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\{8\},\\qquad\\delta\_\{r\}:=\\sqrt\{2r\_\{\\max\}\},\\qquad C\_\{r\}:=\\delta\_\{r\}\+\\eta\_\{\\varepsilon\}\.\(46\)
Finally, define

θε:=8​Aεε​rmin\.\\theta\_\{\\varepsilon\}:=\\frac\{8A\_\{\\varepsilon\}\}\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\.\(47\)
We also define, for eacht∈\[T\]t\\in\[T\], the indicators of exceptional slots:

Jtμ:=𝟙​\{Qt,at\>0,βatμ​\(t−1\)\>ε8\},J\_\{t\}^\{\\mu\}:=\\mathds\{1\}\\left\\\{Q\_\{t,a\_\{t\}\}\>0,\\ \\beta^\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\>\\frac\{\\varepsilon\}\{8\}\\right\\\},\(48\)and

Jtp:=𝟙​\{ct=1,βXtp​\(t−1\)\>ε8\}\.J\_\{t\}^\{p\}:=\\mathds\{1\}\\left\\\{c\_\{t\}=1,\\ \\beta^\{p\}\_\{X\_\{t\}\}\(t\-1\)\>\\frac\{\\varepsilon\}\{8\}\\right\\\}\.\(49\)
These indicators identify the slots in which the relevant confidence radius is larger than a threshold proportional toε\\varepsilon\. We finally define

Jt:=max⁡\{Jtμ,Jtp\}\.J\_\{t\}:=\\max\\\{J\_\{t\}^\{\\mu\},J\_\{t\}^\{p\}\\\}\.\(50\)
We then state a well\-known drift lemma introduced in\[[36](https://arxiv.org/html/2607.06017#bib.bib35)\]\. For our purposes, we present it directly in the special caset0=1t\_\{0\}=1\.

###### Lemma 4\.

Let\{Ut\}t≥1\\\{U\_\{t\}\\\}\_\{t\\geq 1\}be a process adapted to a filtration\{ℱt\}t≥1\\\{\\mathcal\{F\}\_\{t\}\\\}\_\{t\\geq 1\}, withU1=0U\_\{1\}=0\. Assume that there exist constantsθ\>0\\theta\>0,δ\>0\\delta\>0, andη\>0\\eta\>0such that, for allt≥1t\\geq 1,

Ut\+1−Ut≤δa\.s\.,U\_\{t\+1\}\-U\_\{t\}\\leq\\delta\\qquad\\text\{a\.s\.\},and

𝔼​\[Ut\+1−Ut∣ℱt\]≤δwhenever​Ut<θ,\\mathbb\{E\}\[U\_\{t\+1\}\-U\_\{t\}\\mid\\mathcal\{F\}\_\{t\}\]\\leq\\delta\\qquad\\text\{whenever \}U\_\{t\}<\\theta,while

𝔼​\[Ut\+1−Ut∣ℱt\]≤−ηwhenever​Ut≥θ\.\\mathbb\{E\}\[U\_\{t\+1\}\-U\_\{t\}\\mid\\mathcal\{F\}\_\{t\}\]\\leq\-\\eta\\qquad\\text\{whenever \}U\_\{t\}\\geq\\theta\.Then, for everyt≥1t\\geq 1,

𝔼​\[Ut\]≤θ\+δ\+4​δ2η​log⁡\(8​δ2η2\)\.\\mathbb\{E\}\[U\_\{t\}\]\\leq\\theta\+\\delta\+\\frac\{4\\delta^\{2\}\}\{\\eta\}\\log\\\!\\left\(\\frac\{8\\delta^\{2\}\}\{\\eta^\{2\}\}\\right\)\.

#### C\.3\.1Proof of Lemma[3](https://arxiv.org/html/2607.06017#Thmlemma3)

Recall thatℋt\\mathcal\{H\}\_\{t\}denote the information available at the beginning of slottt, before the arrival typeXtX\_\{t\}is observed\. In particular,𝑸t\\bm\{Q\}\_\{t\},𝒑^​\(t−1\)\\hat\{\\bm\{p\}\}\(t\-1\),𝝁^​\(t−1\)\\hat\{\\bm\{\\mu\}\}\(t\-1\), and𝒢t\\mathscr\{G\}\_\{t\}areℋt\\mathcal\{H\}\_\{t\}\-measurable\. Recall also thatℱt\\mathcal\{F\}\_\{t\}is the information available after observing the arrival type and selecting the control actions at slottt\.

We first control the number of exceptional slots as defined in Equations[48](https://arxiv.org/html/2607.06017#A3.E48),[49](https://arxiv.org/html/2607.06017#A3.E49)and[50](https://arxiv.org/html/2607.06017#A3.E50)\.

##### Service\-side exceptional slots\.

IfJtμ=1J\_\{t\}^\{\\mu\}=1andat=ka\_\{t\}=k, then eitherNk​\(t−1\)=0N\_\{k\}\(t\-1\)=0, in which case trivially

Nk​\(t−1\)=0<32​log⁡\(4​K​T/δ\)ε2,N\_\{k\}\(t\-1\)=0<\\frac\{32\\log\(4KT/\\delta\)\}\{\\varepsilon^\{2\}\},orNk​\(t−1\)≥1N\_\{k\}\(t\-1\)\\geq 1, in which case necessarilyt≥2t\\geq 2and

βkμ​\(t−1\)=log⁡\(4​K​\(t−1\)/δ\)2​Nk​\(t−1\)\>ε8,\\beta\_\{k\}^\{\\mu\}\(t\-1\)=\\sqrt\{\\frac\{\\log\(4K\(t\-1\)/\\delta\)\}\{2N\_\{k\}\(t\-1\)\}\}\>\\frac\{\\varepsilon\}\{8\},which implies

Nk​\(t−1\)<32​log⁡\(4​K​\(t−1\)/δ\)ε2≤32​log⁡\(4​K​T/δ\)ε2\.N\_\{k\}\(t\-1\)<\\frac\{32\\log\(4K\(t\-1\)/\\delta\)\}\{\\varepsilon^\{2\}\}\\leq\\frac\{32\\log\(4KT/\\delta\)\}\{\\varepsilon^\{2\}\}\.SinceQt,k\>0Q\_\{t,k\}\>0, slotttis an effective service attempt on typekk, hence the counterNkN\_\{k\}increases by one\. More precisely, for each fixedk∈\[K\]k\\in\[K\], every slotttsuch thatJtμ=1J\_\{t\}^\{\\mu\}=1andat=ka\_\{t\}=kcontributes one unit to the counterNkN\_\{k\}\. Since this can only occur whileNk​\(t−1\)<LεN\_\{k\}\(t\-1\)<L\_\{\\varepsilon\}\(as defined in Equation[46](https://arxiv.org/html/2607.06017#A3.E46)\), we must have

∑t=1T𝟙​\{Jtμ=1,at=k\}≤Lε\.\\sum\_\{t=1\}^\{T\}\\mathds\{1\}\\\{J\_\{t\}^\{\\mu\}=1,\\ a\_\{t\}=k\\\}\\leq L\_\{\\varepsilon\}\.Summing overk∈\[K\]k\\in\[K\], we obtain

∑t=1TJtμ=∑k=1K∑t=1T𝟙​\{Jtμ=1,at=k\}≤K​Lε\.\\sum\_\{t=1\}^\{T\}J\_\{t\}^\{\\mu\}=\\sum\_\{k=1\}^\{K\}\\sum\_\{t=1\}^\{T\}\\mathds\{1\}\\\{J\_\{t\}^\{\\mu\}=1,\\ a\_\{t\}=k\\\}\\leq KL\_\{\\varepsilon\}\.\(51\)

##### Chatbot\-side exceptional slots\.

We can reason in the same way as in the previous case\. IfJtp=1J\_\{t\}^\{p\}=1andXt=kX\_\{t\}=k, then by definitionct=1c\_\{t\}=1, so slotttis an informative chatbot exposure for typekk, and therefore the counterMkM\_\{k\}increases by one at timett\.

Moreover, eitherMk​\(t−1\)=0M\_\{k\}\(t\-1\)=0, in which case trivially

Mk​\(t−1\)=0<32​log⁡\(4​K​T/δ\)ε2,M\_\{k\}\(t\-1\)=0<\\frac\{32\\log\(4KT/\\delta\)\}\{\\varepsilon^\{2\}\},orMk​\(t−1\)≥1M\_\{k\}\(t\-1\)\\geq 1, in which case necessarilyt≥2t\\geq 2and

βkp​\(t−1\)=log⁡\(4​K​\(t−1\)/δ\)2​Mk​\(t−1\)\>ε8,\\beta\_\{k\}^\{p\}\(t\-1\)=\\sqrt\{\\frac\{\\log\(4K\(t\-1\)/\\delta\)\}\{2M\_\{k\}\(t\-1\)\}\}\>\\frac\{\\varepsilon\}\{8\},which implies

Mk​\(t−1\)<32​log⁡\(4​K​\(t−1\)/δ\)ε2≤32​log⁡\(4​K​T/δ\)ε2\.M\_\{k\}\(t\-1\)<\\frac\{32\\log\(4K\(t\-1\)/\\delta\)\}\{\\varepsilon^\{2\}\}\\leq\\frac\{32\\log\(4KT/\\delta\)\}\{\\varepsilon^\{2\}\}\.Hence, for each fixedkk, the event\{Jtp=1,Xt=k\}\\\{J\_\{t\}^\{p\}=1,\\ X\_\{t\}=k\\\}can occur at mostLεL\_\{\\varepsilon\}times\. Summing overkk, we obtain the bound

∑t=1TJtp≤K​Lε\.\\sum\_\{t=1\}^\{T\}J\_\{t\}^\{p\}\\leq KL\_\{\\varepsilon\}\.\(52\)
SinceJt≤Jtμ\+JtpJ\_\{t\}\\leq J\_\{t\}^\{\\mu\}\+J\_\{t\}^\{p\}, it follows that

∑t=1TJt≤2​K​Lε\.\\sum\_\{t=1\}^\{T\}J\_\{t\}\\leq 2KL\_\{\\varepsilon\}\.\(53\)

##### Drift bound on good non\-exceptional slots\.

By Lemma[1](https://arxiv.org/html/2607.06017#Thmlemma1),

Δt≤rmax\+rXt​Qt,Xt​\(1−pXt​ct\)−rat​Qt,at​μat\.\\Delta\_\{t\}\\leq r\_\{\\max\}\+r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}\(1\-p\_\{X\_\{t\}\}c\_\{t\}\)\-r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\mu\_\{a\_\{t\}\}\.Hence, by adding and subtracting relevant quantities,

Δt\+V​ct≤\\displaystyle\\Delta\_\{t\}\+Vc\_\{t\}\\leqrmax\+\(V​ct\+rXt​Qt,Xt​\(1−p¯Xt​\(t−1\)​ct\)−rat​Qt,at​μ¯at​\(t−1\)\)\\displaystyle\\;r\_\{\\max\}\+\\left\(Vc\_\{t\}\+r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}\(1\-\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)c\_\{t\}\)\-r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\\right\)\+rXt​Qt,Xt​ct​\(p¯Xt​\(t−1\)−pXt\)\+rat​Qt,at​\(μ¯at​\(t−1\)−μat\)\.\\displaystyle\+r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}c\_\{t\}\\left\(\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\-p\_\{X\_\{t\}\}\\right\)\+r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\left\(\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\-\\mu\_\{a\_\{t\}\}\\right\)\.
By policy definition, for every realizedXtX\_\{t\}, theUCB\-DPPpolicy minimizes in\(c,a\)\(c,a\)the surrogate objective

V​c\+rXt​Qt,Xt​\(1−p¯Xt​\(t−1\)​c\)−ra​Qt,a​μ¯a​\(t−1\)\.Vc\+r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}\(1\-\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)c\)\-r\_\{a\}Q\_\{t,a\}\\bar\{\\mu\}\_\{a\}\(t\-1\)\.
We now compare the policy with the randomized stationary policy induced by\(𝒄ε,𝝆ε\)\(\\bm\{c\}^\{\\varepsilon\},\\bm\{\\rho\}^\{\\varepsilon\}\), whose existence is guaranteed by assumption\. More precisely, we consider the policy defined as follows:

- •choosec~t=cXtε\\tilde\{c\}\_\{t\}=c\_\{X\_\{t\}\}^\{\\varepsilon\};
- •choosea~t=k\\tilde\{a\}\_\{t\}=kwith probabilityρkε\\rho\_\{k\}^\{\\varepsilon\}\.

Hence, by taking conditional expectation first with respect to the randomized comparison action and then with respect toXtX\_\{t\}, conditioning onℋt\\mathcal\{H\}\_\{t\}, we get

𝔼​\[Δt\+V​ct∣ℋt\]≤\\displaystyle\\mathbb\{E\}\[\\Delta\_\{t\}\+Vc\_\{t\}\\mid\\mathcal\{H\}\_\{t\}\]\\leqAε\+∑k=1Krk​Qt,k​\(λk​\(1−p¯k​\(t−1\)​ckε\)−ρkε​μ¯k​\(t−1\)\)\\displaystyle\\;A\_\{\\varepsilon\}\+\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\\left\(\\lambda\_\{k\}\(1\-\\bar\{p\}\_\{k\}\(t\-1\)c\_\{k\}^\{\\varepsilon\}\)\-\\rho\_\{k\}^\{\\varepsilon\}\\bar\{\\mu\}\_\{k\}\(t\-1\)\\right\)\+𝔼\[rXtQt,Xtct\(p¯Xt\(t−1\)−pXt\)\|ℋt\]\\displaystyle\+\\mathbb\{E\}\\\!\\left\[r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}c\_\{t\}\\left\(\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\-p\_\{X\_\{t\}\}\\right\)\\,\\middle\|\\,\\mathcal\{H\}\_\{t\}\\right\]\+𝔼\[ratQt,at\(μ¯at\(t−1\)−μat\)\|ℋt\]\.\\displaystyle\+\\mathbb\{E\}\\\!\\left\[r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\left\(\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\-\\mu\_\{a\_\{t\}\}\\right\)\\,\\middle\|\\,\\mathcal\{H\}\_\{t\}\\right\]\.whereAεA\_\{\\varepsilon\}is defined in Equation[45](https://arxiv.org/html/2607.06017#A3.E45)\.

Now let us work on the event𝒢t∩\{Jt=0\}\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}\. Since this event isℱt\\mathcal\{F\}\_\{t\}\-measurable, we first control the last two terms pathwise onℱt\\mathcal\{F\}\_\{t\}, and then return toℋt\\mathcal\{H\}\_\{t\}by the tower property\.

Since𝒢t\\mathscr\{G\}\_\{t\}holds andJtμ=0J\_\{t\}^\{\\mu\}=0, we have

0≤μ¯at​\(t−1\)−μat≤2​βatμ​\(t−1\)≤ε4,0\\leq\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\-\\mu\_\{a\_\{t\}\}\\leq 2\\beta^\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\\leq\\frac\{\\varepsilon\}\{4\},and therefore, pathwise on𝒢t∩\{Jt=0\}\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\},

rat​Qt,at​\(μ¯at​\(t−1\)−μat\)≤ε4​∑k=1Krk​Qt,k\.r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\left\(\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\-\\mu\_\{a\_\{t\}\}\\right\)\\leq\\frac\{\\varepsilon\}\{4\}\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\.
Moreover, on𝒢t∩\{Jt=0\}\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}, the chatbot optimism term is controlled pathwise as follows:

- •ifct=0c\_\{t\}=0, then rXt​Qt,Xt​ct​\(p¯Xt​\(t−1\)−pXt\)=0;r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}c\_\{t\}\\left\(\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\-p\_\{X\_\{t\}\}\\right\)=0;
- •ifct=1c\_\{t\}=1, thenJtp=0J\_\{t\}^\{p\}=0, hence βXtp​\(t−1\)≤ε8,\\beta^\{p\}\_\{X\_\{t\}\}\(t\-1\)\\leq\\frac\{\\varepsilon\}\{8\},and since𝒢t\\mathscr\{G\}\_\{t\}holds, 0≤p¯Xt​\(t−1\)−pXt≤2​βXtp​\(t−1\)≤ε4\.0\\leq\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\-p\_\{X\_\{t\}\}\\leq 2\\beta^\{p\}\_\{X\_\{t\}\}\(t\-1\)\\leq\\frac\{\\varepsilon\}\{4\}\.Therefore, rXt​Qt,Xt​ct​\(p¯Xt​\(t−1\)−pXt\)≤ε4​rXt​Qt,Xt≤ε4​∑k=1Krk​Qt,k\.r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}c\_\{t\}\\left\(\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\-p\_\{X\_\{t\}\}\\right\)\\leq\\frac\{\\varepsilon\}\{4\}\\,r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}\\leq\\frac\{\\varepsilon\}\{4\}\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\.

Thus, by the tower property,

𝔼\[ratQt,at\(μ¯at\(t−1\)−μat\)𝟙\{𝒢t\}𝟙\{Jt=0\}\|ℋt\]\\displaystyle\\mathbb\{E\}\\\!\\left\[r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\left\(\\bar\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\-\\mu\_\{a\_\{t\}\}\\right\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\,\\middle\|\\,\\mathcal\{H\}\_\{t\}\\right\]≤ε4​∑k=1Krk​Qt,k​ℙ​\(𝒢t∩\{Jt=0\}∣ℋt\),\\displaystyle\\qquad\\leq\\frac\{\\varepsilon\}\{4\}\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\\,\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\),and similarly

𝔼\[rXtQt,Xtct\(p¯Xt\(t−1\)−pXt\)𝟙\{𝒢t\}𝟙\{Jt=0\}\|ℋt\]\\displaystyle\\mathbb\{E\}\\\!\\left\[r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}c\_\{t\}\\left\(\\bar\{p\}\_\{X\_\{t\}\}\(t\-1\)\-p\_\{X\_\{t\}\}\\right\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\,\\middle\|\\,\\mathcal\{H\}\_\{t\}\\right\]≤ε4​∑k=1Krk​Qt,k​ℙ​\(𝒢t∩\{Jt=0\}∣ℋt\)\.\\displaystyle\\qquad\\leq\\frac\{\\varepsilon\}\{4\}\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\\,\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\)\.
Finally, since𝒢t\\mathscr\{G\}\_\{t\}impliesp¯k​\(t−1\)≥pk\\bar\{p\}\_\{k\}\(t\-1\)\\geq p\_\{k\}andμ¯k​\(t−1\)≥μk\\bar\{\\mu\}\_\{k\}\(t\-1\)\\geq\\mu\_\{k\}, strict feasibility gives

λk​\(1−p¯k​\(t−1\)​ckε\)−ρkε​μ¯k​\(t−1\)≤λk​\(1−pk​ckε\)−ρkε​μk≤−ε\.\\lambda\_\{k\}\(1\-\\bar\{p\}\_\{k\}\(t\-1\)c\_\{k\}^\{\\varepsilon\}\)\-\\rho\_\{k\}^\{\\varepsilon\}\\bar\{\\mu\}\_\{k\}\(t\-1\)\\leq\\lambda\_\{k\}\(1\-p\_\{k\}c\_\{k\}^\{\\varepsilon\}\)\-\\rho\_\{k\}^\{\\varepsilon\}\\mu\_\{k\}\\leq\-\\varepsilon\.Therefore,

𝔼​\[\(Δt\+V​ct\)​𝟙​\{𝒢t\}​𝟙​\{Jt=0\}∣ℋt\]\\displaystyle\\mathbb\{E\}\\\!\\left\[\(\\Delta\_\{t\}\+Vc\_\{t\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\\right\]≤\(Aε−ε​∑k=1Krk​Qt,k\+ε4​∑k=1Krk​Qt,k\+ε4​∑k=1Krk​Qt,k\)​ℙ​\(𝒢t∩\{Jt=0\}∣ℋt\),\\displaystyle\\qquad\\leq\\left\(A\_\{\\varepsilon\}\-\\varepsilon\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\+\\frac\{\\varepsilon\}\{4\}\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\+\\frac\{\\varepsilon\}\{4\}\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\\right\)\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\),that is,

𝔼​\[\(Δt\+V​ct\)​𝟙​\{𝒢t\}​𝟙​\{Jt=0\}∣ℋt\]≤\(Aε−ε2​∑k=1Krk​Qt,k\)​ℙ​\(𝒢t∩\{Jt=0\}∣ℋt\)\.\\mathbb\{E\}\\\!\\left\[\(\\Delta\_\{t\}\+Vc\_\{t\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\\right\]\\leq\\left\(A\_\{\\varepsilon\}\-\\frac\{\\varepsilon\}\{2\}\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\\right\)\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\)\.\(54\)
SinceV​ct≥0Vc\_\{t\}\\geq 0, it follows that

𝔼​\[Δt​𝟙​\{𝒢t\}​𝟙​\{Jt=0\}∣ℋt\]≤\(Aε−ε2​∑k=1Krk​Qt,k\)​ℙ​\(𝒢t∩\{Jt=0\}∣ℋt\)\.\\mathbb\{E\}\\\!\\left\[\\Delta\_\{t\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\\right\]\\leq\\left\(A\_\{\\varepsilon\}\-\\frac\{\\varepsilon\}\{2\}\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}\\right\)\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\)\.\(55\)
Now observe that

∑k=1Krk​Qt,k=∑k=1Krk​\(rk​Qt,k\)≥rmin​∑k=1Krk​Qt,k≥rmin​\(∑k=1Krk​Qt,k2\)1/2=rmin​Zt\.\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}=\\sum\_\{k=1\}^\{K\}\\sqrt\{r\_\{k\}\}\\,\(\\sqrt\{r\_\{k\}\}Q\_\{t,k\}\)\\geq\\sqrt\{r\_\{\\min\}\}\\sum\_\{k=1\}^\{K\}\\sqrt\{r\_\{k\}\}Q\_\{t,k\}\\geq\\sqrt\{r\_\{\\min\}\}\\left\(\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{t,k\}^\{2\}\\right\)^\{1/2\}=\\sqrt\{r\_\{\\min\}\}\\,Z\_\{t\}\.The third relation is true since each element of the sum∑krk​Qt,k\\sum\_\{k\}\\sqrt\{r\_\{k\}\}Q\_\{t,k\}is non\-negative\.

Hence, from \([55](https://arxiv.org/html/2607.06017#A3.E55)\),

𝔼​\[Δt​𝟙​\{𝒢t\}​𝟙​\{Jt=0\}∣ℋt\]≤\(Aε−ε​rmin2​Zt\)​ℙ​\(𝒢t∩\{Jt=0\}∣ℋt\)\.\\mathbb\{E\}\\\!\\left\[\\Delta\_\{t\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\\right\]\\leq\\left\(A\_\{\\varepsilon\}\-\\frac\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\{2\}Z\_\{t\}\\right\)\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\)\.\(56\)
Since

Δt=12​𝔼​\[Zt\+12−Zt2∣ℱt\],\\Delta\_\{t\}=\\frac\{1\}\{2\}\\,\\mathbb\{E\}\[Z\_\{t\+1\}^\{2\}\-Z\_\{t\}^\{2\}\\mid\\mathcal\{F\}\_\{t\}\],the tower property yields

𝔼​\[\(Zt\+12−Zt2\)​𝟙​\{𝒢t\}​𝟙​\{Jt=0\}∣ℋt\]=2​𝔼​\[Δt​𝟙​\{𝒢t\}​𝟙​\{Jt=0\}∣ℋt\]\.\\mathbb\{E\}\\\!\\left\[\(Z\_\{t\+1\}^\{2\}\-Z\_\{t\}^\{2\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\\right\]=2\\,\\mathbb\{E\}\\\!\\left\[\\Delta\_\{t\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\\right\]\.Therefore, by \([56](https://arxiv.org/html/2607.06017#A3.E56)\),

𝔼​\[\(Zt\+12−Zt2\)​𝟙​\{𝒢t\}​𝟙​\{Jt=0\}∣ℋt\]≤\(2​Aε−ε​rmin​Zt\)​ℙ​\(𝒢t∩\{Jt=0\}∣ℋt\)\.\\mathbb\{E\}\\\!\\left\[\(Z\_\{t\+1\}^\{2\}\-Z\_\{t\}^\{2\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\\right\]\\leq\\left\(2A\_\{\\varepsilon\}\-\\varepsilon\\sqrt\{r\_\{\\min\}\}\\,Z\_\{t\}\\right\)\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\)\.\(57\)
WheneverUt≥θεU\_\{t\}\\geq\\theta\_\{\\varepsilon\}, we haveUt≤Zt​𝟙​\{𝒢t\}≤ZtU\_\{t\}\\leq Z\_\{t\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\leq Z\_\{t\}, hence necessarily𝒢t\\mathscr\{G\}\_\{t\}holds andZt≥θεZ\_\{t\}\\geq\\theta\_\{\\varepsilon\}\. By the definition ofθε\\theta\_\{\\varepsilon\}\(Equation[47](https://arxiv.org/html/2607.06017#A3.E47)\),

ε​rmin​Zt≥8​Aε,\\varepsilon\\sqrt\{r\_\{\\min\}\}\\,Z\_\{t\}\\geq 8A\_\{\\varepsilon\},and therefore

2​Aε−ε​rmin​Zt≤−ε​rmin4​Zt=−2​ηε​Zt\.2A\_\{\\varepsilon\}\-\\varepsilon\\sqrt\{r\_\{\\min\}\}\\,Z\_\{t\}\\leq\-\\frac\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\{4\}Z\_\{t\}=\-2\\eta\_\{\\varepsilon\}Z\_\{t\}\.Hence, on\{Ut≥θε\}\\\{U\_\{t\}\\geq\\theta\_\{\\varepsilon\}\\\},

𝔼​\[\(Zt\+12−Zt2\)​𝟙​\{𝒢t\}​𝟙​\{Jt=0\}∣ℋt\]≤−2​ηε​Zt​ℙ​\(𝒢t∩\{Jt=0\}∣ℋt\)\.\\mathbb\{E\}\\\!\\left\[\(Z\_\{t\+1\}^\{2\}\-Z\_\{t\}^\{2\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\\right\]\\leq\-2\\eta\_\{\\varepsilon\}Z\_\{t\}\\,\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\)\.\(58\)
Since

Zt2−2​ηε​Zt≤\(Zt−ηε\)2,Z\_\{t\}^\{2\}\-2\\eta\_\{\\varepsilon\}Z\_\{t\}\\leq\(Z\_\{t\}\-\\eta\_\{\\varepsilon\}\)^\{2\},it follows from \([58](https://arxiv.org/html/2607.06017#A3.E58)\) that, on\{Ut≥θε\}\\\{U\_\{t\}\\geq\\theta\_\{\\varepsilon\}\\\},

𝔼​\[Zt\+12​𝟙​\{𝒢t\}​𝟙​\{Jt=0\}∣ℋt\]≤\(Zt−ηε\)2​ℙ​\(𝒢t∩\{Jt=0\}∣ℋt\)\.\\mathbb\{E\}\\\!\\left\[Z\_\{t\+1\}^\{2\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\\right\]\\leq\(Z\_\{t\}\-\\eta\_\{\\varepsilon\}\)^\{2\}\\,\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\)\.By Cauchy–Schwarz,

𝔼​\[Zt\+1​𝟙​\{𝒢t\}​𝟙​\{Jt=0\}∣ℋt\]2\\displaystyle\\mathbb\{E\}\\\!\\left\[Z\_\{t\+1\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\\right\]^\{2\}≤ℙ​\(𝒢t∩\{Jt=0\}∣ℋt\)​𝔼​\[Zt\+12​𝟙​\{𝒢t\}​𝟙​\{Jt=0\}∣ℋt\]\\displaystyle\\leq\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\)\\,\\mathbb\{E\}\\\!\\left\[Z\_\{t\+1\}^\{2\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\\right\]≤\(Zt−ηε\)2​ℙ​\(𝒢t∩\{Jt=0\}∣ℋt\)2\.\\displaystyle\\leq\(Z\_\{t\}\-\\eta\_\{\\varepsilon\}\)^\{2\}\\,\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\)^\{2\}\.SinceZt\+1≥0Z\_\{t\+1\}\\geq 0, we conclude that on\{Ut≥θε\}\\\{U\_\{t\}\\geq\\theta\_\{\\varepsilon\}\\\},

𝔼​\[\(Zt\+1−Zt\)​𝟙​\{𝒢t\}​𝟙​\{Jt=0\}∣ℋt\]≤−ηε​ℙ​\(𝒢t∩\{Jt=0\}∣ℋt\)\.\\mathbb\{E\}\\\!\\left\[\(Z\_\{t\+1\}\-Z\_\{t\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\\right\]\\leq\-\\eta\_\{\\varepsilon\}\\,\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\)\.\(59\)

##### Compensated process\.

Since in each slot there is at most one arrival and at most one departure, using inverse triangular inequality we get

Zt\+1−Zt≤\(∑k=1Krk​\(Qt\+1,k−Qt,k\)2\)1/2≤2​rmax\.Z\_\{t\+1\}\-Z\_\{t\}\\leq\\left\(\\sum\_\{k=1\}^\{K\}r\_\{k\}\(Q\_\{t\+1,k\}\-Q\_\{t,k\}\)^\{2\}\\right\)^\{1/2\}\\leq\\sqrt\{2r\_\{\\max\}\}\.Now recall thatδr=2​rmax\\delta\_\{r\}=\\sqrt\{2r\_\{\\max\}\}as defined in Equation[46](https://arxiv.org/html/2607.06017#A3.E46)\.

Define the process

Ut:=Zt​1​\{𝒢t\}−Cr​∑s=1t−1Js​1​\{𝒢s\},t=1,…,T\+1,U\_\{t\}:=Z\_\{t\}\\,\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\-C\_\{r\}\\sum\_\{s=1\}^\{t\-1\}J\_\{s\}\\,\\mathds\{1\}\\\{\\mathscr\{G\}\_\{s\}\\\},\\qquad t=1,\\dots,T\+1,whereCrC\_\{r\}is defined in Equation[46](https://arxiv.org/html/2607.06017#A3.E46)\. Since𝑸1=0\\bm\{Q\}\_\{1\}=0, we haveZ1=0Z\_\{1\}=0, and thus

We claim that Lemma[4](https://arxiv.org/html/2607.06017#Thmlemma4)applies to\{Ut\}t≥1\\\{U\_\{t\}\\\}\_\{t\\geq 1\}with respect to the filtration\{ℋt\}t≥1\\\{\\mathcal\{H\}\_\{t\}\\\}\_\{t\\geq 1\}\.

First,

Ut\+1−Ut=Zt\+1​𝟙​\{𝒢t\+1\}−Zt​𝟙​\{𝒢t\}−Cr​Jt​𝟙​\{𝒢t\}\.U\_\{t\+1\}\-U\_\{t\}=Z\_\{t\+1\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\+1\}\\\}\-Z\_\{t\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\-C\_\{r\}J\_\{t\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\.Since𝒢t\+1⊆𝒢t\\mathscr\{G\}\_\{t\+1\}\\subseteq\\mathscr\{G\}\_\{t\}, we have𝟙​\{𝒢t\+1\}≤𝟙​\{𝒢t\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\+1\}\\\}\\leq\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}, so

Ut\+1−Ut≤\(Zt\+1−Zt\)​𝟙​\{𝒢t\}−Cr​Jt​𝟙​\{𝒢t\}≤Zt\+1−Zt≤δr\.U\_\{t\+1\}\-U\_\{t\}\\leq\(Z\_\{t\+1\}\-Z\_\{t\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\-C\_\{r\}J\_\{t\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\leq Z\_\{t\+1\}\-Z\_\{t\}\\leq\\delta\_\{r\}\.The first condition of Lemma[4](https://arxiv.org/html/2607.06017#Thmlemma4)is therefore satisfied\.

IfUt<θεU\_\{t\}<\\theta\_\{\\varepsilon\}, then trivially

𝔼​\[Ut\+1−Ut∣ℋt\]≤δr\.\\mathbb\{E\}\[U\_\{t\+1\}\-U\_\{t\}\\mid\\mathcal\{H\}\_\{t\}\]\\leq\\delta\_\{r\}\.Thus the second condition of Lemma[4](https://arxiv.org/html/2607.06017#Thmlemma4)also holds\.

Now suppose thatUt≥θεU\_\{t\}\\geq\\theta\_\{\\varepsilon\}\. SinceUt≤Zt​𝟙​\{𝒢t\}≤ZtU\_\{t\}\\leq Z\_\{t\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\leq Z\_\{t\}, we must have𝒢t\\mathscr\{G\}\_\{t\}andZt≥θεZ\_\{t\}\\geq\\theta\_\{\\varepsilon\}\. Then

𝔼​\[Ut\+1−Ut∣ℋt\]≤\\displaystyle\\mathbb\{E\}\[U\_\{t\+1\}\-U\_\{t\}\\mid\\mathcal\{H\}\_\{t\}\]\\leq𝔼​\[\(Zt\+1−Zt\)​𝟙​\{𝒢t\}​𝟙​\{Jt=0\}∣ℋt\]\\displaystyle\\;\\mathbb\{E\}\[\(Z\_\{t\+1\}\-Z\_\{t\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\]\+𝔼​\[\(Zt\+1−Zt−Cr\)​𝟙​\{𝒢t\}​𝟙​\{Jt=1\}∣ℋt\]\.\\displaystyle\+\\mathbb\{E\}\[\(Z\_\{t\+1\}\-Z\_\{t\}\-C\_\{r\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=1\\\}\\mid\\mathcal\{H\}\_\{t\}\]\.
By \([59](https://arxiv.org/html/2607.06017#A3.E59)\),

𝔼​\[\(Zt\+1−Zt\)​𝟙​\{𝒢t\}​𝟙​\{Jt=0\}∣ℋt\]≤−ηε​ℙ​\(𝒢t∩\{Jt=0\}∣ℋt\)\.\\mathbb\{E\}\[\(Z\_\{t\+1\}\-Z\_\{t\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\]\\leq\-\\eta\_\{\\varepsilon\}\\,\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=0\\\}\\mid\\mathcal\{H\}\_\{t\}\)\.
On the other hand, on𝒢t∩\{Jt=1\}\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=1\\\}we simply useZt\+1−Zt≤δrZ\_\{t\+1\}\-Z\_\{t\}\\leq\\delta\_\{r\}, hence

𝔼​\[\(Zt\+1−Zt−Cr\)​𝟙​\{𝒢t\}​𝟙​\{Jt=1\}∣ℋt\]\\displaystyle\\mathbb\{E\}\[\(Z\_\{t\+1\}\-Z\_\{t\}\-C\_\{r\}\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\mathds\{1\}\\\{J\_\{t\}=1\\\}\\mid\\mathcal\{H\}\_\{t\}\]≤\(δr−Cr\)​ℙ​\(𝒢t∩\{Jt=1\}∣ℋt\)\\displaystyle\\leq\(\\delta\_\{r\}\-C\_\{r\}\)\\,\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=1\\\}\\mid\\mathcal\{H\}\_\{t\}\)=−ηε​ℙ​\(𝒢t∩\{Jt=1\}∣ℋt\)\.\\displaystyle=\-\\eta\_\{\\varepsilon\}\\,\\mathbb\{P\}\(\\mathscr\{G\}\_\{t\}\\cap\\\{J\_\{t\}=1\\\}\\mid\\mathcal\{H\}\_\{t\}\)\.Combining the two estimates yields

𝔼​\[Ut\+1−Ut∣ℋt\]≤−ηε\.\\mathbb\{E\}\[U\_\{t\+1\}\-U\_\{t\}\\mid\\mathcal\{H\}\_\{t\}\]\\leq\-\\eta\_\{\\varepsilon\}\.Therefore the third condition of Lemma[4](https://arxiv.org/html/2607.06017#Thmlemma4)is satisfied as well\.

We may now apply Lemma[4](https://arxiv.org/html/2607.06017#Thmlemma4)with

θ=θε,δ=δr,η=ηε\.\\theta=\\theta\_\{\\varepsilon\},\\qquad\\delta=\\delta\_\{r\},\\qquad\\eta=\\eta\_\{\\varepsilon\}\.It follows that

𝔼​\[UT\+1\]≤Mε\\mathbb\{E\}\[U\_\{T\+1\}\]\\leq M\_\{\\varepsilon\}\(60\)with

Mε=\(8​∑k=1Kλk​ckεε​rmin\)⋅V\+8​rmaxε​rmin\+2​rmax\+16​rmaxε​rmin​log⁡\(1024​rmaxε2​rmin\)\.M\_\{\\varepsilon\}=\\left\(\\frac\{8\\sum\_\{k=1\}^\{K\}\\lambda\_\{k\}c\_\{k\}^\{\\varepsilon\}\}\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\\right\)\\cdot V\+\\frac\{8r\_\{\\max\}\}\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\+\\sqrt\{2r\_\{\\max\}\}\+\\frac\{16r\_\{\\max\}\}\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\\log\\left\(\\frac\{1024r\_\{\\max\}\}\{\\varepsilon^\{2\}r\_\{\\min\}\}\\right\)\.\(61\)Since we are just interested in the dependency onTT, we can observe thatMε=𝒪​\(V\)M\_\{\\varepsilon\}=\\mathcal\{O\}\(V\)\(the choice of the right value ofVVis horizon\-dependent\)\.

Finally, by definition ofUT\+1U\_\{T\+1\},

UT\+1=ZT\+1​𝟙​\{𝒢T\}−Cr​∑t=1TJt​𝟙​\{𝒢t\}\.U\_\{T\+1\}=Z\_\{T\+1\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{T\}\\\}\-C\_\{r\}\\sum\_\{t=1\}^\{T\}J\_\{t\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\.Hence

ZT\+1​𝟙​\{𝒢T\}≤UT\+1\+Cr​∑t=1TJt\.Z\_\{T\+1\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{T\}\\\}\\leq U\_\{T\+1\}\+C\_\{r\}\\sum\_\{t=1\}^\{T\}J\_\{t\}\.Using \([53](https://arxiv.org/html/2607.06017#A3.E53)\), we conclude that

ZT\+1​𝟙​\{𝒢T\}≤UT\+1\+2​Cr​K​Lε\.Z\_\{T\+1\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{T\}\\\}\\leq U\_\{T\+1\}\+2C\_\{r\}KL\_\{\\varepsilon\}\.Taking expectations and using Equation[60](https://arxiv.org/html/2607.06017#A3.E60), we finally get

𝔼​\[ZT\+1​𝟙​\{𝒢T\}\]≤Mε\+2​Cr​K​Lε\.\\mathbb\{E\}\[Z\_\{T\+1\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{T\}\\\}\]\\leq M\_\{\\varepsilon\}\+2C\_\{r\}KL\_\{\\varepsilon\}\.We can observe that2​Cr​K​Lε=𝒪​\(K​log⁡\(T/δ\)\)2C\_\{r\}KL\_\{\\varepsilon\}=\\mathcal\{O\}\(K\\log\(T/\\delta\)\)\.

This proves the lemma\.□\\square

#### C\.3\.2Proof of Proposition[3](https://arxiv.org/html/2607.06017#Thmproposition3)

We decompose

R4​\(T\)=∑k=1Krk​𝔼​\[QT\+1,k​𝟙​\{𝒢T\}\]\+∑k=1Krk​𝔼​\[QT\+1,k​𝟙​\{𝒢¯T\}\]\.R\_\{4\}\(T\)=\\sum\_\{k=1\}^\{K\}r\_\{k\}\\,\\mathbb\{E\}\[Q\_\{T\+1,k\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{T\}\\\}\]\+\\sum\_\{k=1\}^\{K\}r\_\{k\}\\,\\mathbb\{E\}\[Q\_\{T\+1,k\}\\mathds\{1\}\\\{\\overline\{\\mathscr\{G\}\}\_\{T\}\\\}\]\.
Since at most one task arrives in each slot and the queues start empty, the total backlog satisfies

∑k=1KQT\+1,k≤T\.\\sum\_\{k=1\}^\{K\}Q\_\{T\+1,k\}\\leq T\.Hence

∑k=1Krk​QT\+1,k≤rmax​∑k=1KQT\+1,k≤rmax​T,\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{T\+1,k\}\\leq r\_\{\\max\}\\sum\_\{k=1\}^\{K\}Q\_\{T\+1,k\}\\leq r\_\{\\max\}T,and therefore

∑k=1Krk​𝔼​\[QT\+1,k​𝟙​\{𝒢¯T\}\]≤rmax​T​ℙ​\(𝒢¯T\)\.\\sum\_\{k=1\}^\{K\}r\_\{k\}\\,\\mathbb\{E\}\[Q\_\{T\+1,k\}\\mathds\{1\}\\\{\\overline\{\\mathscr\{G\}\}\_\{T\}\\\}\]\\leq r\_\{\\max\}T\\,\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}\)\.
On the good event, by Cauchy–Schwarz,

∑k=1Krk​QT\+1,k=∑k=1Krk​\(rk​QT\+1,k\)≤\(∑k=1Krk\)1/2​\(∑k=1Krk​QT\+1,k2\)1/2=\(∑k=1Krk\)1/2​ZT\+1\.\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{T\+1,k\}=\\sum\_\{k=1\}^\{K\}\\sqrt\{r\_\{k\}\}\\,\(\\sqrt\{r\_\{k\}\}Q\_\{T\+1,k\}\)\\leq\\left\(\\sum\_\{k=1\}^\{K\}r\_\{k\}\\right\)^\{1/2\}\\left\(\\sum\_\{k=1\}^\{K\}r\_\{k\}Q\_\{T\+1,k\}^\{2\}\\right\)^\{1/2\}=\\left\(\\sum\_\{k=1\}^\{K\}r\_\{k\}\\right\)^\{1/2\}Z\_\{T\+1\}\.Thus

∑k=1Krk​𝔼​\[QT\+1,k​𝟙​\{𝒢T\}\]≤\(∑k=1Krk\)1/2​𝔼​\[ZT\+1​𝟙​\{𝒢T\}\]\.\\sum\_\{k=1\}^\{K\}r\_\{k\}\\,\\mathbb\{E\}\[Q\_\{T\+1,k\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{T\}\\\}\]\\leq\\left\(\\sum\_\{k=1\}^\{K\}r\_\{k\}\\right\)^\{1/2\}\\mathbb\{E\}\[Z\_\{T\+1\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{T\}\\\}\]\.Applying Lemma[3](https://arxiv.org/html/2607.06017#Thmlemma3), we obtain

∑k=1Krk​𝔼​\[QT\+1,k​𝟙​\{𝒢T\}\]≤\(∑k=1Krk\)1/2​\(Mε\+2​Cr​K​Lε\)\.\\sum\_\{k=1\}^\{K\}r\_\{k\}\\,\\mathbb\{E\}\[Q\_\{T\+1,k\}\\mathds\{1\}\\\{\\mathscr\{G\}\_\{T\}\\\}\]\\leq\\left\(\\sum\_\{k=1\}^\{K\}r\_\{k\}\\right\)^\{1/2\}\\left\(M\_\{\\varepsilon\}\+2C\_\{r\}KL\_\{\\varepsilon\}\\right\)\.
Combining the good\-event and bad\-event contributions yields

R4​\(T\)≤\(∑k=1Krk\)1/2​\(Mε\+2​Cr​K​Lε\)\+rmax​T​ℙ​\(𝒢¯T\)\.R\_\{4\}\(T\)\\leq\\left\(\\sum\_\{k=1\}^\{K\}r\_\{k\}\\right\)^\{1/2\}\\left\(M\_\{\\varepsilon\}\+2C\_\{r\}KL\_\{\\varepsilon\}\\right\)\+r\_\{\\max\}T\\,\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}\)\.
Finally, sinceMε=𝒪​\(V\)M\_\{\\varepsilon\}=\\mathcal\{O\}\(V\)and2​Cr​K​Lε=𝒪​\(K​log⁡\(T/δ\)\)2C\_\{r\}KL\_\{\\varepsilon\}=\\mathcal\{O\}\(K\\log\(T/\\delta\)\), we conclude that

R4​\(T\)=𝒪​\(V\+K​log⁡\(T/δ\)\)\+rmax​T​ℙ​\(𝒢¯T\)\.R\_\{4\}\(T\)=\\mathcal\{O\}\\left\(V\+K\\log\(T/\\delta\)\\right\)\+r\_\{\\max\}T\\,\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}\)\.□\\square

### C\.4BoundingR1μ​\(T\)R\_\{1\}^\{\\mu\}\(T\)andR1p​\(T\)R\_\{1\}^\{p\}\(T\)

Before proceeding to the bound onR1μ​\(T\)R\_\{1\}^\{\\mu\}\(T\)andR1p​\(T\)R\_\{1\}^\{p\}\(T\), we need an additional technical lemma\. The result extends the backlog estimate of Lemma[3](https://arxiv.org/html/2607.06017#Thmlemma3)to suitable random times, which naturally arise in the analysis of the estimation errors\.

For everyk∈\[K\]k\\in\[K\]and everyn∈\[T\]n\\in\[T\], let us first define the random time of thenn\-th effective service on queuekkas

τk,n:=inf\{t≥1:Nk​\(t\)=n\}\.\\tau\_\{k,n\}:=\\inf\\\{t\\geq 1:\\ N\_\{k\}\(t\)=n\\\}\.\(62\)Similarly, for everyk∈\[K\]k\\in\[K\]and everyn∈\[T\]n\\in\[T\], define the random time of thenn\-th informative chatbot exposure on typekkas

σk,n:=inf\{t≥1:Mk​\(t\)=n\}\.\\sigma\_\{k,n\}:=\\inf\\\{t\\geq 1:\\ M\_\{k\}\(t\)=n\\\}\.\(63\)
###### Lemma 5\.

For everyk∈\[K\]k\\in\[K\]and everyn∈\[T\]n\\in\[T\], the random timesτk,n∧T\\tau\_\{k,n\}\\wedge Tandσk,n∧T\\sigma\_\{k,n\}\\wedge Tare stopping times\. Moreover, for every random timeκk,n∈\{τk,n,σk,n\}\\kappa\_\{k,n\}\\in\\\{\\tau\_\{k,n\},\\sigma\_\{k,n\}\\\}, it holds that

𝔼​\[rk​Qκk,n,k​1​\{κk,n≤T\}​1​\{𝒢κk,n\}\]=𝒪​\(V\+K​log⁡\(T/δ\)\)\\mathbb\{E\}\\\!\\left\[r\_\{k\}Q\_\{\\kappa\_\{k,n\},k\}\\,\\mathds\{1\}\\\{\\kappa\_\{k,n\}\\leq T\\\}\\,\\mathds\{1\}\\\{\\mathscr\{G\}\_\{\\kappa\_\{k,n\}\}\\\}\\right\]=\\mathcal\{O\}\(V\+K\\log\(T/\\delta\)\)

###### Proof\.

Fixk∈\[K\]k\\in\[K\]andn∈\[T\]n\\in\[T\], and letκk,n∈\{τk,n,σk,n\}\\kappa\_\{k,n\}\\in\\\{\\tau\_\{k,n\},\\sigma\_\{k,n\}\\\}as defined in Equations \([62](https://arxiv.org/html/2607.06017#A3.E62)\) and \([63](https://arxiv.org/html/2607.06017#A3.E63)\)\.

First,κk,n∧T\\kappa\_\{k,n\}\\wedge Tis a stopping time\. Indeed,

\{τk,n≤t\}=\{Nk​\(t\)≥n\}∈ℱt,\{σk,n≤t\}=\{Mk​\(t\)≥n\}∈ℱt\.\\\{\\tau\_\{k,n\}\\leq t\\\}=\\\{N\_\{k\}\(t\)\\geq n\\\}\\in\\mathcal\{F\}\_\{t\},\\qquad\\\{\\sigma\_\{k,n\}\\leq t\\\}=\\\{M\_\{k\}\(t\)\\geq n\\\}\\in\\mathcal\{F\}\_\{t\}\.Define the first bad time as

τbad:=inf\{t≥1:𝒢¯t\}∧\(T\+1\)\.\\tau\_\{\\mathrm\{bad\}\}:=\\inf\\\{t\\geq 1:\\overline\{\\mathscr\{G\}\}\_\{t\}\\\}\\wedge\(T\+1\)\.We define an auxiliary process\{Vt\}t=1T\+1\\\{V\_\{t\}\\\}\_\{t=1\}^\{T\+1\}by

Vt=\{Zt−Cr​∑s=1t−1Js,if​t<τbad,Vτbad−1−ηε​\(t−τbad\+1\),if​t≥τbad\.V\_\{t\}=\\begin\{cases\}Z\_\{t\}\-C\_\{r\}\\displaystyle\\sum\_\{s=1\}^\{t\-1\}J\_\{s\},&\\text\{if \}t<\\tau\_\{\\mathrm\{bad\}\},\\\\\[5\.69054pt\] V\_\{\\tau\_\{\\mathrm\{bad\}\}\-1\}\-\\eta\_\{\\varepsilon\}\\,\(t\-\\tau\_\{\\mathrm\{bad\}\}\+1\),&\\text\{if \}t\\geq\\tau\_\{\\mathrm\{bad\}\}\.\\end\{cases\}whereηε\\eta\_\{\\varepsilon\}andCrC\_\{r\}are defined in Equation[46](https://arxiv.org/html/2607.06017#A3.E46)\. Thus, up to the first bad time, the processVtV\_\{t\}coincides with the compensated processUtU\_\{t\}used in the proof of Lemma[3](https://arxiv.org/html/2607.06017#Thmlemma3), while afterτbad\\tau\_\{\\mathrm\{bad\}\}it is continued deterministically with slope−ηε\-\\eta\_\{\\varepsilon\}\.

##### Bounded increments ofVtV\_\{t\}\.

Recall that, according to Equation[46](https://arxiv.org/html/2607.06017#A3.E46),

δr=2​rmax,Cr=δr\+ηε\.\\delta\_\{r\}=\\sqrt\{2r\_\{\\max\}\},\\qquad C\_\{r\}=\\delta\_\{r\}\+\\eta\_\{\\varepsilon\}\.Plus recall that, since in each slot there is at most one arrival and at most one departure, we have

\|Zt\+1−Zt\|≤\(∑j=1Krj​\(Qt\+1,j−Qt,j\)2\)1/2≤δr\.\|Z\_\{t\+1\}\-Z\_\{t\}\|\\leq\\left\(\\sum\_\{j=1\}^\{K\}r\_\{j\}\(Q\_\{t\+1,j\}\-Q\_\{t,j\}\)^\{2\}\\right\)^\{1/2\}\\leq\\delta\_\{r\}\.Define

Bε:=δr\+Cr\.B\_\{\\varepsilon\}:=\\delta\_\{r\}\+C\_\{r\}\.\(64\)
Ift<τbad−1t<\\tau\_\{\\mathrm\{bad\}\}\-1, then

Vt\+1−Vt=Zt\+1−Zt−Cr​Jt,V\_\{t\+1\}\-V\_\{t\}=Z\_\{t\+1\}\-Z\_\{t\}\-C\_\{r\}J\_\{t\},hence

\|Vt\+1−Vt\|≤\|Zt\+1−Zt\|\+Cr​Jt≤δr\+Cr=Bε\.\|V\_\{t\+1\}\-V\_\{t\}\|\\leq\|Z\_\{t\+1\}\-Z\_\{t\}\|\+C\_\{r\}J\_\{t\}\\leq\\delta\_\{r\}\+C\_\{r\}=B\_\{\\varepsilon\}\.Ift=τbad−1t=\\tau\_\{\\mathrm\{bad\}\}\-1, then by definition

Vt\+1−Vt=−ηε,V\_\{t\+1\}\-V\_\{t\}=\-\\eta\_\{\\varepsilon\},and ift≥τbadt\\geq\\tau\_\{\\mathrm\{bad\}\}, again

Vt\+1−Vt=−ηε\.V\_\{t\+1\}\-V\_\{t\}=\-\\eta\_\{\\varepsilon\}\.Therefore, for everyt∈\[T\]t\\in\[T\],

\|Vt\+1−Vt\|≤Bεa\.s\.\|V\_\{t\+1\}\-V\_\{t\}\|\\leq B\_\{\\varepsilon\}\\qquad\\text\{a\.s\.\}\(65\)
Next we verify the negative drift condition above the thresholdθε\\theta\_\{\\varepsilon\}, defined in Equation[47](https://arxiv.org/html/2607.06017#A3.E47)\. Ift<τbad−1t<\\tau\_\{\\mathrm\{bad\}\}\-1, thenVtV\_\{t\}coincides with the compensated processUtU\_\{t\}considered in the proof of Lemma[3](https://arxiv.org/html/2607.06017#Thmlemma3)\. Hence, wheneverVt≥θεV\_\{t\}\\geq\\theta\_\{\\varepsilon\}, that proof gives

𝔼​\[Vt\+1−Vt∣ℱt\]≤−ηε\.\\mathbb\{E\}\[V\_\{t\+1\}\-V\_\{t\}\\mid\\mathcal\{F\}\_\{t\}\]\\leq\-\\eta\_\{\\varepsilon\}\.If insteadt≥τbad−1t\\geq\\tau\_\{\\mathrm\{bad\}\}\-1, then by construction

Vt\+1−Vt=−ηε\.V\_\{t\+1\}\-V\_\{t\}=\-\\eta\_\{\\varepsilon\}\.Thus, for everyt∈\[T\]t\\in\[T\],

𝔼​\[Vt\+1−Vt∣ℱt\]≤−ηεwhenever​Vt≥θε\.\\mathbb\{E\}\[V\_\{t\+1\}\-V\_\{t\}\\mid\\mathcal\{F\}\_\{t\}\]\\leq\-\\eta\_\{\\varepsilon\}\\qquad\\text\{whenever \}V\_\{t\}\\geq\\theta\_\{\\varepsilon\}\.\(66\)

##### Exponential recursion\.

Set

aε:=ηεBε2,ρε:=exp⁡\(−ηε22​Bε2\)∈\(0,1\)\.a\_\{\\varepsilon\}:=\\frac\{\\eta\_\{\\varepsilon\}\}\{B\_\{\\varepsilon\}^\{2\}\},\\qquad\\rho\_\{\\varepsilon\}:=\\exp\\\!\\left\(\-\\frac\{\\eta\_\{\\varepsilon\}^\{2\}\}\{2B\_\{\\varepsilon\}^\{2\}\}\\right\)\\in\(0,1\)\.Let

Δ​Vt:=Vt\+1−Vt\.\\Delta V\_\{t\}:=V\_\{t\+1\}\-V\_\{t\}\.By \([65](https://arxiv.org/html/2607.06017#A3.E65)\), we have\|Δ​Vt\|≤Bε\|\\Delta V\_\{t\}\|\\leq B\_\{\\varepsilon\}almost surely\. Therefore, by the conditional Hoeffding lemma, with−Bε≤Δ​Vt≤Bε\-B\_\{\\varepsilon\}\\leq\\Delta V\_\{t\}\\leq B\_\{\\varepsilon\},

𝔼​\[eaε​\(Δ​Vt−𝔼​\[Δ​Vt∣ℱt\]\)∣ℱt\]≤exp⁡\(aε2​Bε22\)\.\\mathbb\{E\}\\\!\\left\[e^\{a\_\{\\varepsilon\}\(\\Delta V\_\{t\}\-\\mathbb\{E\}\[\\Delta V\_\{t\}\\mid\\mathcal\{F\}\_\{t\}\]\)\}\\mid\\mathcal\{F\}\_\{t\}\\right\]\\leq\\exp\\\!\\left\(\\frac\{a\_\{\\varepsilon\}^\{2\}B\_\{\\varepsilon\}^\{2\}\}\{2\}\\right\)\.Hence, on the event\{Vt≥θε\}\\\{V\_\{t\}\\geq\\theta\_\{\\varepsilon\}\\\}, using \([66](https://arxiv.org/html/2607.06017#A3.E66)\),

𝔼​\[eaε​Δ​Vt∣ℱt\]\\displaystyle\\mathbb\{E\}\[e^\{a\_\{\\varepsilon\}\\Delta V\_\{t\}\}\\mid\\mathcal\{F\}\_\{t\}\]≤exp⁡\(aε​𝔼​\[Δ​Vt∣ℱt\]\+aε2​Bε22\)\\displaystyle\\leq\\exp\\\!\\left\(a\_\{\\varepsilon\}\\mathbb\{E\}\[\\Delta V\_\{t\}\\mid\\mathcal\{F\}\_\{t\}\]\+\\frac\{a\_\{\\varepsilon\}^\{2\}B\_\{\\varepsilon\}^\{2\}\}\{2\}\\right\)≤exp⁡\(−aε​ηε\+aε2​Bε22\)\\displaystyle\\leq\\exp\\\!\\left\(\-a\_\{\\varepsilon\}\\eta\_\{\\varepsilon\}\+\\frac\{a\_\{\\varepsilon\}^\{2\}B\_\{\\varepsilon\}^\{2\}\}\{2\}\\right\)=exp⁡\(−ηε22​Bε2\)=ρε\.\\displaystyle=\\exp\\\!\\left\(\-\\frac\{\\eta\_\{\\varepsilon\}^\{2\}\}\{2B\_\{\\varepsilon\}^\{2\}\}\\right\)=\\rho\_\{\\varepsilon\}\.Therefore,

𝔼​\[eaε​Vt\+1∣ℱt\]≤ρε​eaε​Vton​\{Vt≥θε\}\.\\mathbb\{E\}\[e^\{a\_\{\\varepsilon\}V\_\{t\+1\}\}\\mid\\mathcal\{F\}\_\{t\}\]\\leq\\rho\_\{\\varepsilon\}e^\{a\_\{\\varepsilon\}V\_\{t\}\}\\qquad\\text\{on \}\\\{V\_\{t\}\\geq\\theta\_\{\\varepsilon\}\\\}\.\(67\)
On the other hand, ifVt<θεV\_\{t\}<\\theta\_\{\\varepsilon\}, then using \([65](https://arxiv.org/html/2607.06017#A3.E65)\),

Vt\+1≤Vt\+Bε<θε\+Bε,V\_\{t\+1\}\\leq V\_\{t\}\+B\_\{\\varepsilon\}<\\theta\_\{\\varepsilon\}\+B\_\{\\varepsilon\},and hence

eaε​Vt\+1≤eaε​\(θε\+Bε\)on​\{Vt<θε\}\.e^\{a\_\{\\varepsilon\}V\_\{t\+1\}\}\\leq e^\{a\_\{\\varepsilon\}\(\\theta\_\{\\varepsilon\}\+B\_\{\\varepsilon\}\)\}\\qquad\\text\{on \}\\\{V\_\{t\}<\\theta\_\{\\varepsilon\}\\\}\.\(68\)
Combining \([67](https://arxiv.org/html/2607.06017#A3.E67)\) and \([68](https://arxiv.org/html/2607.06017#A3.E68)\), we obtain

𝔼​\[eaε​Vt\+1∣ℱt\]≤ρε​eaε​Vt\+eaε​\(θε\+Bε\)\.\\mathbb\{E\}\[e^\{a\_\{\\varepsilon\}V\_\{t\+1\}\}\\mid\\mathcal\{F\}\_\{t\}\]\\leq\\rho\_\{\\varepsilon\}e^\{a\_\{\\varepsilon\}V\_\{t\}\}\+e^\{a\_\{\\varepsilon\}\(\\theta\_\{\\varepsilon\}\+B\_\{\\varepsilon\}\)\}\.Let

Mt:=𝔼​\[eaε​Vt\]\.M\_\{t\}:=\\mathbb\{E\}\[e^\{a\_\{\\varepsilon\}V\_\{t\}\}\]\.Taking expectations, we get the recursion

Mt\+1≤ρε​Mt\+eaε​\(θε\+Bε\)\.M\_\{t\+1\}\\leq\\rho\_\{\\varepsilon\}M\_\{t\}\+e^\{a\_\{\\varepsilon\}\(\\theta\_\{\\varepsilon\}\+B\_\{\\varepsilon\}\)\}\.SinceV1=Z1=0V\_\{1\}=Z\_\{1\}=0, we haveM1=1M\_\{1\}=1\. Iterating the recursion yields and using the fact thatρε≤1\\rho\_\{\\varepsilon\}\\leq 1

Mt≤ρεt−1\+1−ρεt−11−ρε​eaε​\(θε\+Bε\)≤1\+eaε​\(θε\+Bε\)1−ρε\.M\_\{t\}\\leq\\rho\_\{\\varepsilon\}^\{\\,t\-1\}\+\\frac\{1\-\\rho\_\{\\varepsilon\}^\{\\,t\-1\}\}\{1\-\\rho\_\{\\varepsilon\}\}e^\{a\_\{\\varepsilon\}\(\\theta\_\{\\varepsilon\}\+B\_\{\\varepsilon\}\)\}\\leq 1\+\\frac\{e^\{a\_\{\\varepsilon\}\(\\theta\_\{\\varepsilon\}\+B\_\{\\varepsilon\}\)\}\}\{1\-\\rho\_\{\\varepsilon\}\}\.Define

bε:=e−aε​θε​\(1\+eaε​\(θε\+Bε\)1−ρε\)\.b\_\{\\varepsilon\}:=e^\{\-a\_\{\\varepsilon\}\\theta\_\{\\varepsilon\}\}\\left\(1\+\\frac\{e^\{a\_\{\\varepsilon\}\(\\theta\_\{\\varepsilon\}\+B\_\{\\varepsilon\}\)\}\}\{1\-\\rho\_\{\\varepsilon\}\}\\right\)\.Then, by Markov’s inequality, for everyt∈\[T\+1\]t\\in\[T\+1\]and everyx≥0x\\geq 0,

ℙ​\(Vt≥θε\+x\)\\displaystyle\\mathbb\{P\}\(V\_\{t\}\\geq\\theta\_\{\\varepsilon\}\+x\)=ℙ​\(eaε​Vt≥eaε​\(θε\+x\)\)\\displaystyle=\\mathbb\{P\}\\\!\\left\(e^\{a\_\{\\varepsilon\}V\_\{t\}\}\\geq e^\{a\_\{\\varepsilon\}\(\\theta\_\{\\varepsilon\}\+x\)\}\\right\)\(69\)≤e−aε​\(θε\+x\)​𝔼​\[eaε​Vt\]\\displaystyle\\leq e^\{\-a\_\{\\varepsilon\}\(\\theta\_\{\\varepsilon\}\+x\)\}\\,\\mathbb\{E\}\[e^\{a\_\{\\varepsilon\}V\_\{t\}\}\]≤bε​e−aε​x\.\\displaystyle\\leq b\_\{\\varepsilon\}e^\{\-a\_\{\\varepsilon\}x\}\.

##### Bound on the maximum\.

Applying a union bound overt=1,…,Tt=1,\\dots,T, from \([69](https://arxiv.org/html/2607.06017#A3.E69)\) we obtain

ℙ​\(max1≤s≤T⁡Vs≥θε\+x\)≤T​bε​e−aε​x\.\\mathbb\{P\}\\\!\\left\(\\max\_\{1\\leq s\\leq T\}V\_\{s\}\\geq\\theta\_\{\\varepsilon\}\+x\\right\)\\leq Tb\_\{\\varepsilon\}e^\{\-a\_\{\\varepsilon\}x\}\.\(70\)This is true since the probability of the maximum is equal to probability that at least oneVsV\_\{s\}is greater than the threshold, i\.e\. the union\.

Integrating the bound, we obtain

𝔼​\[max1≤s≤T⁡Vs\]\\displaystyle\\mathbb\{E\}\\\!\\left\[\\max\_\{1\\leq s\\leq T\}V\_\{s\}\\right\]=∫0∞ℙ​\(max1≤s≤T⁡Vs≥y\)​𝑑y\\displaystyle=\\int\_\{0\}^\{\\infty\}\\mathbb\{P\}\\\!\\left\(\\max\_\{1\\leq s\\leq T\}V\_\{s\}\\geq y\\right\)\\,dy≤θε\+∫0∞min⁡\{1,T​bε​e−aε​x\}​𝑑x\.\\displaystyle\\leq\\theta\_\{\\varepsilon\}\+\\int\_\{0\}^\{\\infty\}\\min\\\{1,Tb\_\{\\varepsilon\}e^\{\-a\_\{\\varepsilon\}x\}\\\}\\,dx\.\(71\)Indeed, fory≤θεy\\leq\\theta\_\{\\varepsilon\}we use the trivial bound by11, while fory=θε\+xy=\\theta\_\{\\varepsilon\}\+x,x≥0x\\geq 0, we use Equation[70](https://arxiv.org/html/2607.06017#A3.E70)\. LetC:=T​bεC:=Tb\_\{\\varepsilon\}\. Since

min⁡\{1,C​e−aε​x\}≤𝟙​\{x≤log⁡Caε\}\+C​e−aε​x​𝟙​\{x\>log⁡Caε\},\\min\\\{1,Ce^\{\-a\_\{\\varepsilon\}x\}\\\}\\leq\\mathds\{1\}\\left\\\{x\\leq\\frac\{\\log C\}\{a\_\{\\varepsilon\}\}\\right\\\}\+Ce^\{\-a\_\{\\varepsilon\}x\}\\mathds\{1\}\\left\\\{x\>\\frac\{\\log C\}\{a\_\{\\varepsilon\}\}\\right\\\},we get

∫0∞min⁡\{1,C​e−aε​x\}​𝑑x\\displaystyle\\int\_\{0\}^\{\\infty\}\\min\\\{1,Ce^\{\-a\_\{\\varepsilon\}x\}\\\}\\,dx≤log⁡Caε\+∫log⁡Caε∞C​e−aε​x​𝑑x\\displaystyle\\leq\\frac\{\\log C\}\{a\_\{\\varepsilon\}\}\+\\int\_\{\\frac\{\\log C\}\{a\_\{\\varepsilon\}\}\}^\{\\infty\}Ce^\{\-a\_\{\\varepsilon\}x\}\\,dx=log⁡Caε\+1aε\.\\displaystyle=\\frac\{\\log C\}\{a\_\{\\varepsilon\}\}\+\\frac\{1\}\{a\_\{\\varepsilon\}\}\.\(72\)Therefore,

𝔼​\[max1≤s≤T⁡Vs\]≤θε\+1\+log⁡\(T​bε\)aε\.\\mathbb\{E\}\\\!\\left\[\\max\_\{1\\leq s\\leq T\}V\_\{s\}\\right\]\\leq\\theta\_\{\\varepsilon\}\+\\frac\{1\+\\log\(Tb\_\{\\varepsilon\}\)\}\{a\_\{\\varepsilon\}\}\.\(73\)

##### Control at the random timeκk,n\\kappa\_\{k,n\}\.

Define the event

Ak,n:=\{κk,n≤T\}∩\{𝒢κk,n\}\.A\_\{k,n\}:=\\\{\\kappa\_\{k,n\}\\leq T\\\}\\cap\\\{\\mathscr\{G\}\_\{\\kappa\_\{k,n\}\}\\\}\.OnAk,nA\_\{k,n\}we necessarily haveκk,n<τbad\\kappa\_\{k,n\}<\\tau\_\{\\mathrm\{bad\}\}, and therefore

Vκk,n=Zκk,n−Cr​∑s=1κk,n−1Js\.V\_\{\\kappa\_\{k,n\}\}=Z\_\{\\kappa\_\{k,n\}\}\-C\_\{r\}\\sum\_\{s=1\}^\{\\kappa\_\{k,n\}\-1\}J\_\{s\}\.Hence, onAk,nA\_\{k,n\},

Zκk,n=Vκk,n\+Cr​∑s=1κk,n−1Js≤Vκk,n\+Cr​∑s=1TJs\.Z\_\{\\kappa\_\{k,n\}\}=V\_\{\\kappa\_\{k,n\}\}\+C\_\{r\}\\sum\_\{s=1\}^\{\\kappa\_\{k,n\}\-1\}J\_\{s\}\\leq V\_\{\\kappa\_\{k,n\}\}\+C\_\{r\}\\sum\_\{s=1\}^\{T\}J\_\{s\}\.Using the pathwise bound in Equation \([53](https://arxiv.org/html/2607.06017#A3.E53)\),

∑s=1TJs≤2​K​Lε,\\sum\_\{s=1\}^\{T\}J\_\{s\}\\leq 2KL\_\{\\varepsilon\},we deduce that

Zκk,n​𝟙​\{Ak,n\}≤\(max1≤s≤T⁡Vs\+2​Cr​K​Lε\)​𝟙​\{Ak,n\}≤max1≤s≤T⁡Vs\+2​Cr​K​Lε\.Z\_\{\\kappa\_\{k,n\}\}\\mathds\{1\}\\\{A\_\{k,n\}\\\}\\leq\\left\(\\max\_\{1\\leq s\\leq T\}V\_\{s\}\+2C\_\{r\}KL\_\{\\varepsilon\}\\right\)\\mathds\{1\}\\\{A\_\{k,n\}\\\}\\leq\\max\_\{1\\leq s\\leq T\}V\_\{s\}\+2C\_\{r\}KL\_\{\\varepsilon\}\.
Finally, by the definition ofZtZ\_\{t\},

rk​Qt,k=rk​\(rk​Qt,k\)≤rk​Zt\.r\_\{k\}Q\_\{t,k\}=\\sqrt\{r\_\{k\}\}\\,\(\\sqrt\{r\_\{k\}\}Q\_\{t,k\}\)\\leq\\sqrt\{r\_\{k\}\}\\,Z\_\{t\}\.Therefore,

rk​Qκk,n,k​𝟙​\{Ak,n\}\\displaystyle r\_\{k\}Q\_\{\\kappa\_\{k,n\},k\}\\mathds\{1\}\\\{A\_\{k,n\}\\\}≤rk​Zκk,n​𝟙​\{Ak,n\}\\displaystyle\\leq\\sqrt\{r\_\{k\}\}\\,Z\_\{\\kappa\_\{k,n\}\}\\mathds\{1\}\\\{A\_\{k,n\}\\\}≤rk​\(max1≤s≤T⁡Vs\+2​Cr​K​Lε\)\.\\displaystyle\\leq\\sqrt\{r\_\{k\}\}\\left\(\\max\_\{1\\leq s\\leq T\}V\_\{s\}\+2C\_\{r\}KL\_\{\\varepsilon\}\\right\)\.Taking expectations and using \([73](https://arxiv.org/html/2607.06017#A3.E73)\), we conclude that

𝔼​\[rk​Qκk,n,k​1​\{κk,n≤T\}​1​\{𝒢κk,n\}\]\\displaystyle\\mathbb\{E\}\\\!\\left\[r\_\{k\}Q\_\{\\kappa\_\{k,n\},k\}\\,\\mathds\{1\}\\\{\\kappa\_\{k,n\}\\leq T\\\}\\,\\mathds\{1\}\\\{\\mathscr\{G\}\_\{\\kappa\_\{k,n\}\}\\\}\\right\]≤rk​𝔼​\[max1≤s≤T⁡Vs\]\+2​rk​Cr​K​Lε\\displaystyle\\leq\\sqrt\{r\_\{k\}\}\\,\\mathbb\{E\}\\\!\\left\[\\max\_\{1\\leq s\\leq T\}V\_\{s\}\\right\]\+2\\sqrt\{r\_\{k\}\}\\,C\_\{r\}KL\_\{\\varepsilon\}≤rk​\(θε\+1\+log⁡\(T​bε\)aε\+2​Cr​K​Lε\)\.\\displaystyle\\leq\\sqrt\{r\_\{k\}\}\\left\(\\theta\_\{\\varepsilon\}\+\\frac\{1\+\\log\(Tb\_\{\\varepsilon\}\)\}\{a\_\{\\varepsilon\}\}\+2C\_\{r\}KL\_\{\\varepsilon\}\\right\)\.Sinceθε=𝒪​\(V\)\\theta\_\{\\varepsilon\}=\\mathcal\{O\}\(V\),aε−1=𝒪​\(1\)a\_\{\\varepsilon\}^\{\-1\}=\\mathcal\{O\}\(1\),log⁡\(T​bε\)=𝒪​\(log⁡T\)\\log\(Tb\_\{\\varepsilon\}\)=\\mathcal\{O\}\(\\log T\), and2​Cr​K​Lε=𝒪​\(K​log⁡\(T/δ\)\)2C\_\{r\}KL\_\{\\varepsilon\}=\\mathcal\{O\}\(K\\log\(T/\\delta\)\), this yields

𝔼​\[rk​Qκk,n,k​1​\{κk,n≤T\}​1​\{𝒢κk,n\}\]≤rk​𝒪​\(V\+K​log⁡\(T/δ\)\)\.\\mathbb\{E\}\\\!\\left\[r\_\{k\}Q\_\{\\kappa\_\{k,n\},k\}\\,\\mathds\{1\}\\\{\\kappa\_\{k,n\}\\leq T\\\}\\,\\mathds\{1\}\\\{\\mathscr\{G\}\_\{\\kappa\_\{k,n\}\}\\\}\\right\]\\leq\\sqrt\{r\_\{k\}\}\\,\\mathcal\{O\}\(V\+K\\log\(T/\\delta\)\)\.This proves the lemma\. ∎

#### C\.4\.1Proof of Proposition[4](https://arxiv.org/html/2607.06017#Thmproposition4)

##### Bound ofR1μ​\(T\)R\_\{1\}^\{\\mu\}\(T\)

On the event𝒢t\\mathscr\{G\}\_\{t\}, for everyk∈\[K\]k\\in\[K\],

0≤μ¯k​\(t−1\)−μk≤2​βkμ​\(t−1\)\.0\\leq\\bar\{\\mu\}\_\{k\}\(t\-1\)\-\\mu\_\{k\}\\leq 2\\beta\_\{k\}^\{\\mu\}\(t\-1\)\.Therefore,

R1μ​\(T\)≤2V​𝔼​\[∑t=1Trat​Qt,at​βatμ​\(t−1\)​𝟙​\{𝒢t\}\]\.R\_\{1\}^\{\\mu\}\(T\)\\leq\\frac\{2\}\{V\}\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}r\_\{a\_\{t\}\}Q\_\{t,a\_\{t\}\}\\beta^\{\\mu\}\_\{a\_\{t\}\}\(t\-1\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\right\]\.\(74\)
We now reorganize the sum by type and service number\. Whenever queuekkis effectively served at timett, we havet=τk,nt=\\tau\_\{k,n\}for somen∈\[Nk​\(T\)\]n\\in\[N\_\{k\}\(T\)\]\(as defined in Equation \([62](https://arxiv.org/html/2607.06017#A3.E62)\)\)\. Hence,

R1μ​\(T\)≤2V​∑k=1K𝔼​\[∑n=1Nk​\(T\)rk​Qτk,n,k​βkμ​\(τk,n−1\)​1​\{𝒢τk,n\}\]\.R\_\{1\}^\{\\mu\}\(T\)\\leq\\frac\{2\}\{V\}\\sum\_\{k=1\}^\{K\}\\mathbb\{E\}\\\!\\left\[\\sum\_\{n=1\}^\{N\_\{k\}\(T\)\}r\_\{k\}Q\_\{\\tau\_\{k,n\},k\}\\,\\beta\_\{k\}^\{\\mu\}\(\\tau\_\{k,n\}\-1\)\\,\\mathds\{1\}\\\{\\mathscr\{G\}\_\{\\tau\_\{k,n\}\}\\\}\\right\]\.Extending the sum ton=1,…,Tn=1,\\dots,T, we get

R1μ​\(T\)≤2V​∑k=1K∑n=1T𝔼​\[rk​Qτk,n,k​βkμ​\(τk,n−1\)​1​\{τk,n≤T\}​1​\{𝒢τk,n\}\]\.R\_\{1\}^\{\\mu\}\(T\)\\leq\\frac\{2\}\{V\}\\sum\_\{k=1\}^\{K\}\\sum\_\{n=1\}^\{T\}\\mathbb\{E\}\\\!\\left\[r\_\{k\}Q\_\{\\tau\_\{k,n\},k\}\\,\\beta\_\{k\}^\{\\mu\}\(\\tau\_\{k,n\}\-1\)\\,\\mathds\{1\}\\\{\\tau\_\{k,n\}\\leq T\\\}\\,\\mathds\{1\}\\\{\\mathscr\{G\}\_\{\\tau\_\{k,n\}\}\\\}\\right\]\.\(75\)
Now we boundβkμ​\(τk,n−1\)\\beta\_\{k\}^\{\\mu\}\(\\tau\_\{k,n\}\-1\)on the event\{τk,n≤T\}\\\{\\tau\_\{k,n\}\\leq T\\\}\.

Ifn=1n=1, thenNk​\(τk,1−1\)=Nk​\(0\)=0N\_\{k\}\(\\tau\_\{k,1\}\-1\)=N\_\{k\}\(0\)=0, hence

βkμ​\(τk,1−1\)=βkμ​\(0\)=1\.\\beta\_\{k\}^\{\\mu\}\(\\tau\_\{k,1\}\-1\)=\\beta\_\{k\}^\{\\mu\}\(0\)=1\.Sincelog⁡\(4​K​T/δ\)≥log⁡4\\log\(4KT/\\delta\)\\geq\\log 4, we have

1≤2​log⁡\(4​K​T/δ\)2=2​log⁡\(4​K​T/δ\)2⋅1\.1\\leq 2\\sqrt\{\\frac\{\\log\(4KT/\\delta\)\}\{2\}\}=2\\sqrt\{\\frac\{\\log\(4KT/\\delta\)\}\{2\\cdot 1\}\}\.
Ifn≥2n\\geq 2, then on\{τk,n≤T\}\\\{\\tau\_\{k,n\}\\leq T\\\}we haveNk​\(τk,n−1\)=n−1≥1N\_\{k\}\(\\tau\_\{k,n\}\-1\)=n\-1\\geq 1, so

βkμ​\(τk,n−1\)=log⁡\(4​K​\(τk,n−1\)/δ\)2​\(n−1\)≤log⁡\(4​K​T/δ\)2​\(\(n−1\)∨1\)\.\\beta\_\{k\}^\{\\mu\}\(\\tau\_\{k,n\}\-1\)=\\sqrt\{\\frac\{\\log\\\!\\left\(4K\(\\tau\_\{k,n\}\-1\)/\\delta\\right\)\}\{2\(n\-1\)\}\}\\leq\\sqrt\{\\frac\{\\log\(4KT/\\delta\)\}\{2\(\(n\-1\)\\vee 1\)\}\}\.Using the elementary inequality

1\(n−1\)∨1≤2n,∀n≥1,\\frac\{1\}\{\\sqrt\{\(n\-1\)\\vee 1\}\}\\leq\\frac\{2\}\{\\sqrt\{n\}\},\\qquad\\forall n\\geq 1,we deduce that

βkμ​\(τk,n−1\)≤2​log⁡\(4​K​T/δ\)2​n\.\\beta\_\{k\}^\{\\mu\}\(\\tau\_\{k,n\}\-1\)\\leq 2\\sqrt\{\\frac\{\\log\(4KT/\\delta\)\}\{2n\}\}\.
Therefore, for everyn∈\[T\]n\\in\[T\],

βkμ​\(τk,n−1\)≤2​log⁡\(4​K​T/δ\)2​n\.\\beta\_\{k\}^\{\\mu\}\(\\tau\_\{k,n\}\-1\)\\leq 2\\sqrt\{\\frac\{\\log\(4KT/\\delta\)\}\{2n\}\}\.\(76\)
Substituting \([76](https://arxiv.org/html/2607.06017#A3.E76)\) into \([75](https://arxiv.org/html/2607.06017#A3.E75)\), we obtain

R1μ​\(T\)≤4V​log⁡\(4​K​T/δ\)2​∑k=1K∑n=1T1n​𝔼​\[rk​Qτk,n,k​1​\{τk,n≤T\}​1​\{𝒢τk,n\}\]\.R\_\{1\}^\{\\mu\}\(T\)\\leq\\frac\{4\}\{V\}\\sqrt\{\\frac\{\\log\(4KT/\\delta\)\}\{2\}\}\\sum\_\{k=1\}^\{K\}\\sum\_\{n=1\}^\{T\}\\frac\{1\}\{\\sqrt\{n\}\}\\,\\mathbb\{E\}\\\!\\left\[r\_\{k\}Q\_\{\\tau\_\{k,n\},k\}\\,\\mathds\{1\}\\\{\\tau\_\{k,n\}\\leq T\\\}\\,\\mathds\{1\}\\\{\\mathscr\{G\}\_\{\\tau\_\{k,n\}\}\\\}\\right\]\.
We may now apply Lemma[5](https://arxiv.org/html/2607.06017#Thmlemma5), which yields

𝔼​\[rk​Qτk,n,k​1​\{τk,n≤T\}​1​\{𝒢τk,n\}\]≤rk​M¯ε\.\\mathbb\{E\}\\\!\\left\[r\_\{k\}Q\_\{\\tau\_\{k,n\},k\}\\,\\mathds\{1\}\\\{\\tau\_\{k,n\}\\leq T\\\}\\,\\mathds\{1\}\\\{\\mathscr\{G\}\_\{\\tau\_\{k,n\}\}\\\}\\right\]\\leq\\sqrt\{r\_\{k\}\}\\,\\overline\{M\}\_\{\\varepsilon\}\.with

M¯ε:=θε\+1\+log⁡\(T​bε\)aε\+2​Cr​K​Lε\\overline\{M\}\_\{\\varepsilon\}:=\\theta\_\{\\varepsilon\}\+\\frac\{1\+\\log\(Tb\_\{\\varepsilon\}\)\}\{a\_\{\\varepsilon\}\}\+2C\_\{r\}KL\_\{\\varepsilon\}\(77\)Hence

R1μ​\(T\)\\displaystyle R\_\{1\}^\{\\mu\}\(T\)≤4​M¯εV​log⁡\(4​K​T/δ\)2​∑k=1Krk​∑n=1T1n\\displaystyle\\leq\\frac\{4\\,\\overline\{M\}\_\{\\varepsilon\}\}\{V\}\\sqrt\{\\frac\{\\log\(4KT/\\delta\)\}\{2\}\}\\sum\_\{k=1\}^\{K\}\\sqrt\{r\_\{k\}\}\\sum\_\{n=1\}^\{T\}\\frac\{1\}\{\\sqrt\{n\}\}≤8​M¯εV​\(∑k=1Krk\)​T​log⁡\(4​K​Tδ\),\\displaystyle\\leq\\frac\{8\\,\\overline\{M\}\_\{\\varepsilon\}\}\{V\}\\left\(\\sum\_\{k=1\}^\{K\}\\sqrt\{r\_\{k\}\}\\right\)\\sqrt\{T\\log\\\!\\left\(\\frac\{4KT\}\{\\delta\}\\right\)\},where we used

∑n=1T1n≤2​T\.\\sum\_\{n=1\}^\{T\}\\frac\{1\}\{\\sqrt\{n\}\}\\leq 2\\sqrt\{T\}\.
Finally, using

∑k=1Krk≤K​rmax,\\sum\_\{k=1\}^\{K\}\\sqrt\{r\_\{k\}\}\\leq K\\sqrt\{r\_\{\\max\}\},we obtain the simpler bound

R1μ​\(T\)≤8​K​rmax​M¯εV​T​log⁡\(4​K​Tδ\)\.R\_\{1\}^\{\\mu\}\(T\)\\leq\\frac\{8K\\sqrt\{r\_\{\\max\}\}\\,\\overline\{M\}\_\{\\varepsilon\}\}\{V\}\\sqrt\{T\\log\\\!\\left\(\\frac\{4KT\}\{\\delta\}\\right\)\}\.This completes the first part of the proof\.

##### Bound ofR1p​\(T\)R\_\{1\}^\{p\}\(T\)

The same reasoning holds in the bound ofR1p​\(T\)R\_\{1\}^\{p\}\(T\)as well\. On the event𝒢t\\mathscr\{G\}\_\{t\}, for everyk∈\[K\]k\\in\[K\],

0≤p¯k​\(t−1\)−pk≤2​βkp​\(t−1,δ\)\.0\\leq\\bar\{p\}\_\{k\}\(t\-1\)\-p\_\{k\}\\leq 2\\beta\_\{k\}^\{p\}\(t\-1,\\delta\)\.Therefore,

R1p​\(T\)≤2V​𝔼​\[∑t=1TrXt​Qt,Xt​ct​βXtp​\(t−1\)​𝟙​\{𝒢t\}\]\.R\_\{1\}^\{p\}\(T\)\\leq\\frac\{2\}\{V\}\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}r\_\{X\_\{t\}\}Q\_\{t,X\_\{t\}\}c\_\{t\}\\beta^\{p\}\_\{X\_\{t\}\}\(t\-1\)\\mathds\{1\}\\\{\\mathscr\{G\}\_\{t\}\\\}\\right\]\.\(78\)
Since the chatbot decision is bang\-bang, we havect∈\{0,1\}c\_\{t\}\\in\\\{0,1\\\}\. Thus only the informative slots withct=1c\_\{t\}=1contribute to the sum\. WheneverXt=kX\_\{t\}=kandct=1c\_\{t\}=1, we havet=σk,nt=\\sigma\_\{k,n\}\(as defined in Equation \([63](https://arxiv.org/html/2607.06017#A3.E63)\)\) for somen∈\[Mk​\(T\)\]n\\in\[M\_\{k\}\(T\)\]\. Hence,

R1p​\(T\)≤2V​∑k=1K𝔼​\[∑n=1Mk​\(T\)rk​Qσk,n,k​βkp​\(σk,n−1\)​1​\{𝒢σk,n\}\]\.R\_\{1\}^\{p\}\(T\)\\leq\\frac\{2\}\{V\}\\sum\_\{k=1\}^\{K\}\\mathbb\{E\}\\\!\\left\[\\sum\_\{n=1\}^\{M\_\{k\}\(T\)\}r\_\{k\}Q\_\{\\sigma\_\{k,n\},k\}\\,\\beta\_\{k\}^\{p\}\(\\sigma\_\{k,n\}\-1\)\\,\\mathds\{1\}\\\{\\mathscr\{G\}\_\{\\sigma\_\{k,n\}\}\\\}\\right\]\.Extending the sum ton=1,…,Tn=1,\\dots,T, we get

R1p​\(T\)≤2V​∑k=1K∑n=1T𝔼​\[rk​Qσk,n,k​βkp​\(σk,n−1\)​1​\{σk,n≤T\}​1​\{𝒢σk,n\}\]\.R\_\{1\}^\{p\}\(T\)\\leq\\frac\{2\}\{V\}\\sum\_\{k=1\}^\{K\}\\sum\_\{n=1\}^\{T\}\\mathbb\{E\}\\\!\\left\[r\_\{k\}Q\_\{\\sigma\_\{k,n\},k\}\\,\\beta\_\{k\}^\{p\}\(\\sigma\_\{k,n\}\-1\)\\,\\mathds\{1\}\\\{\\sigma\_\{k,n\}\\leq T\\\}\\,\\mathds\{1\}\\\{\\mathscr\{G\}\_\{\\sigma\_\{k,n\}\}\\\}\\right\]\.\(79\)
For boundingβkp​\(σk,n−1\)\\beta\_\{k\}^\{p\}\(\\sigma\_\{k,n\}\-1\)on the event\{σk,n≤T\}\\\{\\sigma\_\{k,n\}\\leq T\\\}, we can apply the same exact reasoning used for the bound ofβkμ​\(τk,n−1\)\\beta\_\{k\}^\{\\mu\}\(\\tau\_\{k,n\}\-1\)and we get

βkp​\(σk,n−1\)≤2​log⁡\(4​K​T/δ\)2​n\.\\beta\_\{k\}^\{p\}\(\\sigma\_\{k,n\}\-1\)\\leq 2\\sqrt\{\\frac\{\\log\(4KT/\\delta\)\}\{2n\}\}\.
Therefore, for everyn∈\[T\]n\\in\[T\],

βkp​\(σk,n−1\)≤2​log⁡\(4​K​T/δ\)2​n\.\\beta\_\{k\}^\{p\}\(\\sigma\_\{k,n\}\-1\)\\leq 2\\sqrt\{\\frac\{\\log\(4KT/\\delta\)\}\{2n\}\}\.\(80\)
Substituting \([80](https://arxiv.org/html/2607.06017#A3.E80)\) into \([79](https://arxiv.org/html/2607.06017#A3.E79)\), we obtain

R1p​\(T\)≤4V​log⁡\(4​K​T/δ\)2​∑k=1K∑n=1T1n​𝔼​\[rk​Qσk,n,k​1​\{σk,n≤T\}​1​\{𝒢σk,n\}\]\.R\_\{1\}^\{p\}\(T\)\\leq\\frac\{4\}\{V\}\\sqrt\{\\frac\{\\log\(4KT/\\delta\)\}\{2\}\}\\sum\_\{k=1\}^\{K\}\\sum\_\{n=1\}^\{T\}\\frac\{1\}\{\\sqrt\{n\}\}\\,\\mathbb\{E\}\\\!\\left\[r\_\{k\}Q\_\{\\sigma\_\{k,n\},k\}\\,\\mathds\{1\}\\\{\\sigma\_\{k,n\}\\leq T\\\}\\,\\mathds\{1\}\\\{\\mathscr\{G\}\_\{\\sigma\_\{k,n\}\}\\\}\\right\]\.
Applying Lemma[5](https://arxiv.org/html/2607.06017#Thmlemma5)we get

𝔼​\[rk​Qσk,n,k​1​\{σk,n≤T\}​1​\{𝒢σk,n\}\]≤rk​M¯ε\.\\mathbb\{E\}\\\!\\left\[r\_\{k\}Q\_\{\\sigma\_\{k,n\},k\}\\,\\mathds\{1\}\\\{\\sigma\_\{k,n\}\\leq T\\\}\\,\\mathds\{1\}\\\{\\mathscr\{G\}\_\{\\sigma\_\{k,n\}\}\\\}\\right\]\\leq\\sqrt\{r\_\{k\}\}\\,\\overline\{M\}\_\{\\varepsilon\}\.withM¯ε\\overline\{M\}\_\{\\varepsilon\}defined in Equation \([77](https://arxiv.org/html/2607.06017#A3.E77)\)\. Hence

R1p​\(T\)\\displaystyle R\_\{1\}^\{p\}\(T\)≤4​M¯εV​log⁡\(4​K​T/δ\)2​∑k=1Krk​∑n=1T1n\\displaystyle\\leq\\frac\{4\\,\\overline\{M\}\_\{\\varepsilon\}\}\{V\}\\sqrt\{\\frac\{\\log\(4KT/\\delta\)\}\{2\}\}\\sum\_\{k=1\}^\{K\}\\sqrt\{r\_\{k\}\}\\sum\_\{n=1\}^\{T\}\\frac\{1\}\{\\sqrt\{n\}\}≤8​M¯εV​\(∑k=1Krk\)​T​log⁡\(4​K​Tδ\),\\displaystyle\\leq\\frac\{8\\,\\overline\{M\}\_\{\\varepsilon\}\}\{V\}\\left\(\\sum\_\{k=1\}^\{K\}\\sqrt\{r\_\{k\}\}\\right\)\\sqrt\{T\\log\\\!\\left\(\\frac\{4KT\}\{\\delta\}\\right\)\},where we used again

∑n=1T1n≤2​T\.\\sum\_\{n=1\}^\{T\}\\frac\{1\}\{\\sqrt\{n\}\}\\leq 2\\sqrt\{T\}\.
Using again

∑k=1Krk≤K​rmax,\\sum\_\{k=1\}^\{K\}\\sqrt\{r\_\{k\}\}\\leq K\\sqrt\{r\_\{\\max\}\},we obtain the bound

R1p​\(T\)≤8​K​rmax​M¯εV​T​log⁡\(4​K​Tδ\)\.R\_\{1\}^\{p\}\(T\)\\leq\\frac\{8K\\sqrt\{r\_\{\\max\}\}\\,\\overline\{M\}\_\{\\varepsilon\}\}\{V\}\\sqrt\{T\\log\\\!\\left\(\\frac\{4KT\}\{\\delta\}\\right\)\}\.This completes the second part of the proof\.

##### Conclusion\.

Combining the two bounds, we obtain

R1μ​\(T\),R1p​\(T\)≤C​K​M¯εV​T​log⁡\(4​K​T/δ\)R\_\{1\}^\{\\mu\}\(T\),\\;R\_\{1\}^\{p\}\(T\)\\leq CK\\frac\{\\overline\{M\}\_\{\\varepsilon\}\}\{V\}\\sqrt\{T\\log\(4KT/\\delta\)\}for some constantC\>0C\>0\. SinceM¯ε=𝒪​\(V\),\\overline\{M\}\_\{\\varepsilon\}=\\mathcal\{O\}\(V\),it follows that

R1μ​\(T\),R1p​\(T\)=𝒪​\(K​T​log⁡\(T/δ\)\)\.R\_\{1\}^\{\\mu\}\(T\),\\;R\_\{1\}^\{p\}\(T\)=\\mathcal\{O\}\\\!\\left\(K\\sqrt\{T\\log\(T/\\delta\)\}\\right\)\.This concludes the proof\.□\\square

### C\.5Proof of Theorem[2](https://arxiv.org/html/2607.06017#Thmtheorem2)

Recall from Lemma[2](https://arxiv.org/html/2607.06017#Thmlemma2)that

RTUCB\-DPP≤R1μ​\(T\)\+R1p​\(T\)\+R2​\(T\)\+R3​\(T\)\+R4​\(T\)\.R\_\{T\}^\{\\texttt\{UCB\-DPP\}\}\\leq R\_\{1\}^\{\\mu\}\(T\)\+R\_\{1\}^\{p\}\(T\)\+R\_\{2\}\(T\)\+R\_\{3\}\(T\)\+R\_\{4\}\(T\)\.
We first make explicit the constants appearing in the bound on the estimation terms\. Recall that

ηε=ε​rmin8,δr=2​rmax,Cr=δr\+ηε,\\eta\_\{\\varepsilon\}=\\frac\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\{8\},\\qquad\\delta\_\{r\}=\\sqrt\{2r\_\{\\max\}\},\\qquad C\_\{r\}=\\delta\_\{r\}\+\\eta\_\{\\varepsilon\},and

Bε=δr\+Cr=2​2​rmax\+ε​rmin8\.B\_\{\\varepsilon\}=\\delta\_\{r\}\+C\_\{r\}=2\\sqrt\{2r\_\{\\max\}\}\+\\frac\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\{8\}\.Moreover,

aε=ηεBε2=ε​rmin8​\(2​2​rmax\+ε​rmin8\)2,a\_\{\\varepsilon\}=\\frac\{\\eta\_\{\\varepsilon\}\}\{B\_\{\\varepsilon\}^\{2\}\}=\\frac\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\{8\\left\(2\\sqrt\{2r\_\{\\max\}\}\+\\frac\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\{8\}\\right\)^\{2\}\},and

ρε=exp⁡\(−ηε22​Bε2\)\.\\rho\_\{\\varepsilon\}=\\exp\\\!\\left\(\-\\frac\{\\eta\_\{\\varepsilon\}^\{2\}\}\{2B\_\{\\varepsilon\}^\{2\}\}\\right\)\.The constantbεb\_\{\\varepsilon\}is defined as

bε=e−aε​θε​\(1\+eaε​\(θε\+Bε\)1−ρε\)\.b\_\{\\varepsilon\}=e^\{\-a\_\{\\varepsilon\}\\theta\_\{\\varepsilon\}\}\\left\(1\+\\frac\{e^\{a\_\{\\varepsilon\}\(\\theta\_\{\\varepsilon\}\+B\_\{\\varepsilon\}\)\}\}\{1\-\\rho\_\{\\varepsilon\}\}\\right\)\.Equivalently,

bε=e−aε​θε\+eaε​Bε1−ρε\.b\_\{\\varepsilon\}=e^\{\-a\_\{\\varepsilon\}\\theta\_\{\\varepsilon\}\}\+\\frac\{e^\{a\_\{\\varepsilon\}B\_\{\\varepsilon\}\}\}\{1\-\\rho\_\{\\varepsilon\}\}\.Sinceθε≥0\\theta\_\{\\varepsilon\}\\geq 0, we have

bε≤1\+eaε​Bε1−ρε\.b\_\{\\varepsilon\}\\leq 1\+\\frac\{e^\{a\_\{\\varepsilon\}B\_\{\\varepsilon\}\}\}\{1\-\\rho\_\{\\varepsilon\}\}\.Thus, defining

Γε:=log⁡\(1\+eaε​Bε1−ρε\),\\Gamma\_\{\\varepsilon\}:=\\log\\left\(1\+\\frac\{e^\{a\_\{\\varepsilon\}B\_\{\\varepsilon\}\}\}\{1\-\\rho\_\{\\varepsilon\}\}\\right\),we have

log⁡bε≤Γε\.\\log b\_\{\\varepsilon\}\\leq\\Gamma\_\{\\varepsilon\}\.Notice thatΓε\\Gamma\_\{\\varepsilon\}depends only onε,rmin,rmax\\varepsilon,r\_\{\\min\},r\_\{\\max\}, and is independent ofT,VT,VandKK\.

Now recall that

θε=8ε​rmin​\(rmax\+V​∑k=1Kλk​ckε\),\\theta\_\{\\varepsilon\}=\\frac\{8\}\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\\left\(r\_\{\\max\}\+V\\sum\_\{k=1\}^\{K\}\\lambda\_\{k\}c\_\{k\}^\{\\varepsilon\}\\right\),and

Lε=⌈32​log⁡\(4​K​T/δ\)ε2⌉\.L\_\{\\varepsilon\}=\\left\\lceil\\frac\{32\\log\(4KT/\\delta\)\}\{\\varepsilon^\{2\}\}\\right\\rceil\.Therefore,

M¯ε=θε\+1\+log⁡\(T​bε\)aε\+2​Cr​K​Lε\\overline\{M\}\_\{\\varepsilon\}=\\theta\_\{\\varepsilon\}\+\\frac\{1\+\\log\(Tb\_\{\\varepsilon\}\)\}\{a\_\{\\varepsilon\}\}\+2C\_\{r\}KL\_\{\\varepsilon\}satisfies the explicit upper bound

M¯ε≤θε\+1\+log⁡T\+Γεaε\+2​Cr​K​⌈32​log⁡\(4​K​T/δ\)ε2⌉\.\\overline\{M\}\_\{\\varepsilon\}\\leq\\theta\_\{\\varepsilon\}\+\\frac\{1\+\\log T\+\\Gamma\_\{\\varepsilon\}\}\{a\_\{\\varepsilon\}\}\+2C\_\{r\}K\\left\\lceil\\frac\{32\\log\(4KT/\\delta\)\}\{\\varepsilon^\{2\}\}\\right\\rceil\.Let us denote the right\-hand side by

M~ε:=θε\+1\+log⁡T\+Γεaε\+2​Cr​K​⌈32​log⁡\(4​K​T/δ\)ε2⌉\.\\widetilde\{M\}\_\{\\varepsilon\}:=\\theta\_\{\\varepsilon\}\+\\frac\{1\+\\log T\+\\Gamma\_\{\\varepsilon\}\}\{a\_\{\\varepsilon\}\}\+2C\_\{r\}K\\left\\lceil\\frac\{32\\log\(4KT/\\delta\)\}\{\\varepsilon^\{2\}\}\\right\\rceil\.
By Proposition[4](https://arxiv.org/html/2607.06017#Thmproposition4), we have

R1μ​\(T\)\+R1p​\(T\)≤16​K​rmaxV​M~ε​T​log⁡\(4​K​T/δ\)\.R\_\{1\}^\{\\mu\}\(T\)\+R\_\{1\}^\{p\}\(T\)\\leq\\frac\{16K\\sqrt\{r\_\{\\max\}\}\}\{V\}\\widetilde\{M\}\_\{\\varepsilon\}\\sqrt\{T\\log\(4KT/\\delta\)\}\.
Moreover,

R2​\(T\)=T​ℙ​\(𝒢¯T\)≤δ​T2,R\_\{2\}\(T\)=T\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}\)\\leq\\delta T^\{2\},and

R3​\(T\)=rmax​TV\.R\_\{3\}\(T\)=\\frac\{r\_\{\\max\}T\}\{V\}\.Finally, Proposition[3](https://arxiv.org/html/2607.06017#Thmproposition3)yields

R4​\(T\)≤∑k=1Krk​\(Mε\+2​Cr​K​Lε\)\+rmax​T​ℙ​\(𝒢¯T\),R\_\{4\}\(T\)\\leq\\sqrt\{\\sum\_\{k=1\}^\{K\}r\_\{k\}\}\\left\(M\_\{\\varepsilon\}\+2C\_\{r\}KL\_\{\\varepsilon\}\\right\)\+r\_\{\\max\}T\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}\),where

Mε=8​Vε​rmin​∑k=1Kλk​ckε\+8​rmaxε​rmin\+2​rmax\+16​rmaxε​rmin​log⁡\(1024​rmaxε2​rmin\)\.M\_\{\\varepsilon\}=\\frac\{8V\}\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\\sum\_\{k=1\}^\{K\}\\lambda\_\{k\}c\_\{k\}^\{\\varepsilon\}\+\\frac\{8r\_\{\\max\}\}\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\+\\sqrt\{2r\_\{\\max\}\}\+\\frac\{16r\_\{\\max\}\}\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\\log\\\!\\left\(\\frac\{1024r\_\{\\max\}\}\{\\varepsilon^\{2\}r\_\{\\min\}\}\\right\)\.
We now choose

V=T,δ=T−2\.V=\\sqrt\{T\},\\qquad\\delta=T^\{\-2\}\.Then

log⁡\(4​K​T/δ\)=log⁡\(4​K​T3\),\\log\(4KT/\\delta\)=\\log\(4KT^\{3\}\),and Proposition[2](https://arxiv.org/html/2607.06017#Thmproposition2)gives

ℙ​\(𝒢¯T\)≤δ​T=T−1\.\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}\)\\leq\\delta T=T^\{\-1\}\.Thus

R2​\(T\)≤1,rmax​T​ℙ​\(𝒢¯T\)≤rmax\.R\_\{2\}\(T\)\\leq 1,\\qquad r\_\{\\max\}T\\mathbb\{P\}\(\\overline\{\\mathscr\{G\}\}\_\{T\}\)\\leq r\_\{\\max\}\.
With this choice of parameters,

θε=8ε​rmin​\(rmax\+T​∑k=1Kλk​ckε\),\\theta\_\{\\varepsilon\}=\\frac\{8\}\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\\left\(r\_\{\\max\}\+\\sqrt\{T\}\\sum\_\{k=1\}^\{K\}\\lambda\_\{k\}c\_\{k\}^\{\\varepsilon\}\\right\),and

M~ε:=8ε​rmin​\(rmax\+T​∑k=1Kλk​ckε\)\+1\+log⁡T\+Γεaε\+2​Cr​K​⌈32​log⁡\(4​K​T3\)ε2⌉\.\\widetilde\{M\}\_\{\\varepsilon\}:=\\frac\{8\}\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\\left\(r\_\{\\max\}\+\\sqrt\{T\}\\sum\_\{k=1\}^\{K\}\\lambda\_\{k\}c\_\{k\}^\{\\varepsilon\}\\right\)\+\\frac\{1\+\\log T\+\\Gamma\_\{\\varepsilon\}\}\{a\_\{\\varepsilon\}\}\+2C\_\{r\}K\\left\\lceil\\frac\{32\\log\(4KT^\{3\}\)\}\{\\varepsilon^\{2\}\}\\right\\rceil\.
Combining all the terms, we obtain the explicit bound

RTUCB\-DPP≤\\displaystyle R\_\{T\}^\{\\texttt\{UCB\-DPP\}\}\\leq\\;16​K​rmax​M~ε​log⁡\(4​K​T3\)\+rmax​T\+1\+rmax\\displaystyle 16K\\sqrt\{r\_\{\\max\}\}\\,\\widetilde\{M\}\_\{\\varepsilon\}\\sqrt\{\\log\(4KT^\{3\}\)\}\+r\_\{\\max\}\\sqrt\{T\}\+1\+r\_\{\\max\}\+∑k=1Krk\[8​Tε​rmin∑k=1Kλkckε\+8​rmaxε​rmin\+2​rmax\\displaystyle\+\\sqrt\{\\sum\_\{k=1\}^\{K\}r\_\{k\}\}\\Bigg\[\\frac\{8\\sqrt\{T\}\}\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\\sum\_\{k=1\}^\{K\}\\lambda\_\{k\}c\_\{k\}^\{\\varepsilon\}\+\\frac\{8r\_\{\\max\}\}\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\+\\sqrt\{2r\_\{\\max\}\}\+16​rmaxε​rminlog\(1024​rmaxε2​rmin\)\+2\(2​rmax\+ε​rmin8\)K⌈32​log⁡\(4​K​T3\)ε2⌉\]\.\\displaystyle\+\\frac\{16r\_\{\\max\}\}\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\\log\\\!\\left\(\\frac\{1024r\_\{\\max\}\}\{\\varepsilon^\{2\}r\_\{\\min\}\}\\right\)\+2\\left\(\\sqrt\{2r\_\{\\max\}\}\+\\frac\{\\varepsilon\\sqrt\{r\_\{\\min\}\}\}\{8\}\\right\)K\\left\\lceil\\frac\{32\\log\(4KT^\{3\}\)\}\{\\varepsilon^\{2\}\}\\right\\rceil\\Bigg\]\.
This expression keeps all constants explicit\. Since

∑k=1Kλk​ckε≤∑k=1Kλk=1,\\sum\_\{k=1\}^\{K\}\\lambda\_\{k\}c\_\{k\}^\{\\varepsilon\}\\leq\\sum\_\{k=1\}^\{K\}\\lambda\_\{k\}=1,we have

M~ε=𝒪​\(T\+K​log⁡\(K​T\)\),\\widetilde\{M\}\_\{\\varepsilon\}=\\mathcal\{O\}\\\!\\left\(\\sqrt\{T\}\+K\\log\(KT\)\\right\),where the hidden constants depend only onε,rmin,rmax\\varepsilon,r\_\{\\min\},r\_\{\\max\}\. Consequently,

RTUCB\-DPP=𝒪​\(K​T​log⁡T\),R\_\{T\}^\{\\texttt\{UCB\-DPP\}\}=\\mathcal\{O\}\\\!\\left\(K\\sqrt\{T\\log T\}\\right\),up to constants depending onε,rmin,rmax\\varepsilon,r\_\{\\min\},r\_\{\\max\}\.□\\square

## Appendix DSimulations

In this section, we report numerical simulations of theUCB\-DPPpolicy on synthetic instances\.

![Refer to caption](https://arxiv.org/html/2607.06017v1/R_strongC_weakH.png)\(a\)𝒑strong\\bm\{p\}^\{\\mathrm\{strong\}\}and𝝁weak\\bm\{\\mu\}^\{\\mathrm\{weak\}\}
![Refer to caption](https://arxiv.org/html/2607.06017v1/R_weakC_strongH.png)\(b\)𝒑weak\\bm\{p\}^\{\\mathrm\{weak\}\}and𝝁strong\\bm\{\\mu\}^\{\\mathrm\{strong\}\}

Figure 3:Average cumulative regret of theUCB\-DPPpolicy in two different parameter regimes\. The shaded regions correspond to one standard error\.![Refer to caption](https://arxiv.org/html/2607.06017v1/R_medium.png)Figure 4:Average cumulative regret of theUCB\-DPPpolicy with𝒑medium\\bm\{p\}^\{\\mathrm\{medium\}\}and𝝁medium\\bm\{\\mu\}^\{\\mathrm\{medium\}\}\. The shaded region corresponds to one standard error\.We consider a system withK=5K=5task classes and a uniform arrival distribution, namelyλk=1/K\\lambda\_\{k\}=1/Kfor allk=1,…,Kk=1,\\ldots,K\. The experiments are carried out under three different regimes for the chatbot success probabilities𝒑\\bm\{p\}and the human service rates𝝁\\bm\{\\mu\}\. The first regime corresponds to a strong chatbot and weak human service \(Figure[3\(a\)](https://arxiv.org/html/2607.06017#A4.F3.sf1)\), the second to a weak chatbot and strong human service \(Figure[5](https://arxiv.org/html/2607.06017#A4.F5)\), and the third to an intermediate case in which both components have medium performance \(Figure[4](https://arxiv.org/html/2607.06017#A4.F4)\)\.

The chatbot success probability vectors are chosen as

𝒑strong=\(0\.90,0\.85,0\.95,0\.88,0\.92\),𝒑weak=\(0\.25,0\.30,0\.20,0\.35,0\.28\),\\bm\{p\}^\{\\mathrm\{strong\}\}=\(0\.90,0\.85,0\.95,0\.88,0\.92\),\\qquad\\bm\{p\}^\{\\mathrm\{weak\}\}=\(0\.25,0\.30,0\.20,0\.35,0\.28\),and

𝒑medium=\(0\.55,0\.60,0\.50,0\.65,0\.58\)\.\\bm\{p\}^\{\\mathrm\{medium\}\}=\(0\.55,0\.60,0\.50,0\.65,0\.58\)\.The corresponding human service\-rate vectors are

𝝁strong=\(0\.80,0\.90,0\.85,0\.88,0\.82\),𝝁weak=\(0\.25,0\.30,0\.35,0\.28,0\.32\),\\bm\{\\mu\}^\{\\mathrm\{strong\}\}=\(0\.80,0\.90,0\.85,0\.88,0\.82\),\\qquad\\bm\{\\mu\}^\{\\mathrm\{weak\}\}=\(0\.25,0\.30,0\.35,0\.28,0\.32\),and

𝝁medium=\(0\.45,0\.50,0\.48,0\.52,0\.46\)\.\\bm\{\\mu\}^\{\\mathrm\{medium\}\}=\(0\.45,0\.50,0\.48,0\.52,0\.46\)\.
For each regime, the parameters are chosen so that the static optimization problem is feasible\.

We then solve the static benchmark problem and compute an optimal dual solution𝒚∗\\bm\{y\}^\{\*\}\. The terminal backlog weights𝒓\\bm\{r\}are selected slightly above the corresponding optimal dual multipliers, namely

rk=1\.05⋅yk∗,k=1,…,K\.r\_\{k\}=1\.05\\cdot y\_\{k\}^\{\*\},\\qquad k=1,\\ldots,K\.This choice is consistent with the condition required by the static lower\-bound result\.

The policy parameter is set toV=TV=\\sqrt\{T\}andδ=T−2\\delta=T^\{\-2\}\. In the simulations we use the horizonT=10000T=10000\. Each experiment is repeated over100100independent runs\. The curves report the empirical average cumulative regret, computed with respect to the static benchmark valueT⋅OPT⁡\(θ\)T\\cdot\\operatorname\{OPT\}\(\\theta\)\. The shaded regions represent one standard error, that is, the empirical standard deviation divided by the square root of the number of runs\.

![Refer to caption](https://arxiv.org/html/2607.06017v1/Backlogs.png)Figure 5:Average total backlog of theUCB\-DPPpolicy in the three parameter regimes\.Figure[5](https://arxiv.org/html/2607.06017#A4.F5)reports the evolution of the average total backlog, defined as∑k=1KQT\+1,k\\sum\_\{k=1\}^\{K\}Q\_\{T\+1,k\}, under the same experimental specifications described above\. The three curves correspond to the strong\-chatbot/weak\-service, weak\-chatbot/strong\-service, and medium\-chatbot/medium\-service regimes\. As in the regret plots, each curve is averaged over100100independent runs, and the shaded regions represent one standard error\.

Overall, the plots show that the cumulative regret remains controlled across all three regimes, with relatively narrow confidence bands over the replications\. The strong\-chatbot/weak\-service regime exhibits a larger backlog, as the human server alone has limited capacity and the policy must rely more heavily on the chatbot to stabilize the system\. In contrast, when the human service rates are high, the queues are more easily drained, leading to a smaller overall congestion level\. The medium regime displays an intermediate behavior\.

The backlog plot confirms that the total queue length remains stable over time in all three scenarios\. This is consistent with the stabilizing effect of the Drift\-Plus\-Penalty scheduling rule\.

The code used for the experiments is available at the anonymous link:[UCB\-DPPSimulations](https://anonymous.4open.science/r/UCB-DPP-Simulations-ACA5/README.md)\.