Learning When to Automate: Queue Control in Human-AI Service Systems Giovanni Montanari1,3 , Marco Scarsini4 , and Vianney Perchet1,2,3 1
FairPlay Joint Team, Inria, France 2 Criteo AI Lab, Paris, France 3 CREST, ENSAE, Institut Polytechnique de Paris 4 Department of Economics and Financial Markets, Luiss University
arXiv:2607.06017v1 [cs.LG] 7 Jul 2026
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 consider T sequentially arriving tasks, each belonging to one of K heterogeneous 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 the UCB-DPP policy, 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 that UCB-DPP achieves regret √ e O(K T ) and guarantees mean-rate stability of the human-service queues. Simulations on synthetic instances show that the proposed policy outperforms natural baselines.
1
Introduction
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 horizon T and belong to one of K heterogeneous 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 1
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], while recent work on generative AI highlights that model performance may vary sharply across tasks that appear similar [7]. 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.1
Motivation
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], 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, 28, 14, 15, 6, 3, 13]. 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.2
Contributions
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 the UCB-DPP policy, 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 that UCB-DPP achieves a sublinear regret bound of e order O(K 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 that UCB-DPP outperforms natural baseline policies. 2
1.3
Related 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, 26]. 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]. 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]. 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], jointly models handoff prediction and service satisfaction [23], and incorporates cost-aware considerations into handoff decisions [37]. Other works study intent recognition mechanisms for identifying requests to switch from chatbot to human service [31]. 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]. 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], and have been further analyzed in generalized switch and heavy-traffic regimes [29]. More broadly, queue-length-based scheduling and resource-allocation rules have become standard tools for the control of stochastic networks [12, 8]. The algorithmic approach proposed in this work is particularly inspired by Lyapunov optimization and the Drift-Plus-Penalty methodology [24, 25]. 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], while finite-time regret guarantees for Upper Confidence Bound algorithms were developed in [1]. We refer to [2, 20] for broader treatments of stochastic and adversarial bandit models. Although UCB-DPP relies 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 3
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], scheduling with unknown statistics through MaxWeight and UCBtype rules [35], and the analysis of transient congestion effects induced by learning [10]. Related approaches combine Lyapunov-drift methods with bandit feedback or adversarial learning in constrained scheduling and stochastic network optimization problems [16, 11, 4, 5]. This work is related to the literature on learning in queueing systems, but the model has a different twostage 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.
2
The Model
s ces
Resolved automatically
suc
Task arrival Xt ∈ [K]
Chatbot cost ct success prob. pXt ct
fail u
re
Human queues (Qt,1 , . . . , Qt,K )
Scheduling action at
Human agent service prob. µat
Figure 1: Illustration of the human-chatbot service system. Tasks arrive sequentially over a finite time horizon T , which is assumed to be known in advance. At each time t ∈ [T ], a task of type Xt enters the system, where Xt ∈ [K] := {1, . . . , 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 ) over the set of task types. Thus, for every k ∈ [K], λk = P(Xt = k) > 0, P and K λ k=1 k = 1. The arrival distribution λ 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 time t is of type k, the decision maker selects a cost level c ∈ [0, 1], representing the amount of resources allocated to the chatbot for handling that task. The chatbot then succeeds in resolving the task with probability sk (c), and fails otherwise. Equivalently, the chatbot outcome is a Bernoulli random variable with parameter sk (c). We assume that the chatbot success probability is linear in the allocated cost. Namely, for each type k ∈ [K], there exists an unknown parameter pk ∈ (0, 1] such that c ∈ [0, 1].
sk (c) = pk c, 4
(1)
Thus, pk captures the intrinsic effectiveness of the chatbot on tasks of type k, while the control variable c modulates 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 } such that, whenever the human agent works on a task of type k, the task is completed by the end of the slot with probability µk ∈ (0, 1]. Equivalently, each slot devoted to a type-k task produces an independent Bernoulli service attempt with success probability µk . Hence, conditional on the task type k, the service time L (measured in number of slots) follows a geometric distribution and satisfies E[L | k] =
1 . µk
(2)
To capture heterogeneity across task types, we consider K separate queues, one for each type, and introduce a scheduling decision for the human server. At each slot t, the decision maker chooses an action at ∈ {1, . . . , K}.
(3)
If at = k and the corresponding queue is nonempty, then the human agent serves one type-k task during slot t. 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 Qt := (Qt,1 , . . . , Qt,K ) denote the backlog vector at the beginning of slot t, where Qt,k ∈ N is the number of pending type-k tasks in the human queue. We assume that all queues are initially empty, namely Q1,k = 0 for all k ∈ [K]. At each slot t, one task of type Xt ∈ [K] arrives and is first routed to the chatbot. After the decision maker selects the chatbot cost ct ∈ [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 := 1{Xt = k} 1{the chatbot fails at slot t},
k ∈ [K].
(4)
Thus, at most one human queue receives an arrival in each slot. Moreover, conditional on Xt = k and ct , the expected arrival to queue k is E[At,k | Xt = k, ct ] = 1 − pk ct , (5) while At,j = 0 for all j ̸= k. The scheduling action at ∈ [K] determines which queue is selected for service. If at = k and queue k is nonempty, the human agent attempts to complete one type-k task during slot t. We define the departure indicators as Dt,k := 1{at = k} 1{Qt,k > 0} Zt,k , k ∈ [K], (6) where Zt,k ∼ B(µk ). Hence, conditional on the current backlog and on the scheduling decision, E[Dt,k | Qt , at ] = 1{at = k}1{Qt,k > 0}µk .
(7)
In particular, Dt,k = 0 whenever at ̸= k or Qt,k = 0. The human queues then evolve according to Qt+1,k = Qt,k + At,k − Dt,k ,
k ∈ [K].
Since Dt,k ≤ 1{Qt,k > 0}, the queue lengths remain nonnegative at all times. 5
(8)
Remark 1. Within each slot t, the decision maker first observes (Qt , Xt ) and chooses (ct , at ); then the chatbot outcome and the service outcome are realized, yielding At,k and Dt,k , and finally the queues are updated according to Equation (8). Tasks forwarded to the human system during slot t become available for service only from slot t + 1 onward. Following [24], we say that queue k is mean rate stable if its expected backlog grows sublinearly over time, namely if E[QT,k ] lim = 0. (9) T →∞ T Equivalently, the queue does not accumulate unresolved tasks at a linear rate. Figure 1 provides a schematic illustration of the model.
2.1
Cost Objective and Regret
A control policy specifies both the chatbot-cost decision and the human-service scheduling action over time. Formally, an admissible policy π is a decision rule that, at each slot t, maps the current task type, the current backlog vector, and the past history into an action pair πt : (Xt , Qπt , Ft−1 ) 7→ (cπt , aπt ),
(10)
where cπt ∈ [0, 1] is the cost allocated to the chatbot and aπt ∈ [K] is the queue selected for human service. Here Ft−1 denotes the information available up to the end of slot t − 1. Given a horizon T , we evaluate a policy through the total cost CTπ :=
T X
cπt +
t=1
K X
rk QπT +1,k ,
(11)
k=1
where rk ∈ [rmin , rmax ], with 0 < rmin < rmax , is the penalty weight associated with unfinished tasks of type k. 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 of rk 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 Π denote the class of admissible policies satisfying (10). The regret of a policy π ∈ Π is defined as ′
RTπ := E[CTπ ] − inf E[CTπ ]. ′ π ∈Π
(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 π relative to the best parameter-aware admissible policy over the same horizon.
2.2
Lower Bound via Static Optimization Problem
Characterizing the optimal policy in (12) is generally difficult, since such a policy may depend both on the true system parameters θ = (λ, p, µ) and on the current backlog state Qt . To obtain a tractable benchmark,
6
we introduce the following static optimization problem: K X
OPT(θ) = min
ck ∈[0,1] ρk ≥0
λk ck
k=1
λk (1 − pk ck ) ≤ µk ρk ,
s.t.
K X
(13)
∀k ∈ [K],
ρk ≤ 1.
k=1
Here, ck represents the chatbot cost that would be assigned to all tasks of type k under a static type-dependent rule. The quantity λk (1 − pk ck ) is the effective rate at which type-k tasks are not resolved by the chatbot and therefore enter the human queue. The variable ρk represents the fraction of human service capacity allocated to type k, so that µk ρ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 (c, ρ) 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) is feasible. Equivalently, since the residual load is minimized by taking ck = 1 for all k, feasibility is guaranteed if and only if K X λk (1 − pk ) k=1
µk
≤ 1.
The Lagrangian associated with the optimization problem (13) is L(c, ρ; y, ν) =
K X
λk ck +
K X
yk (λk (1 − pk ck ) − µk ρk ) + ν
k=1
k=1
K X
! ρk − 1 ,
(14)
k=1
where yk ≥ 0 is the dual multiplier associated with the k-th balance constraint, and ν ≥ 0 is the dual multiplier associated with the total capacity constraint. Let (y ∗ , ν ∗ ) 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].
Then, for every horizon T ≥ 1, inf E[CTπ ] ≥ T · OPT(θ).
π∈Π
The multiplier yk∗ can be interpreted as the shadow congestion cost of an additional unit of residual type-k load. The condition rk ≥ yk∗ 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 (c∗ , ρ∗ ) denote an optimal solution to the static optimization problem (13). The following proposition is a direct consequence of Theorem 1. Proposition 1. For any policy π, the regret RTπ satisfies RTπ ≤
T X
E[cπt − c∗Xt ] +
t=1
K X k=1
The proofs of this section are in Appendix A. 7
rk E[QπT +1,k ].
3
UCB-DPP Policy
The goal is to design an online policy that jointly chooses, at each slot t, the chatbot cost ct ∈ [0, 1] and the human-service scheduling action at ∈ [K]. The policy uses the current backlog vector Qt together with the information collected about the unknown chatbot success probabilities p = (p1 , . . . , pK ) and human service rates µ = (µ1 , . . . , µK ). Its objective is to minimize cumulative chatbot costs while keeping the human queues stable in the sense of Equation (9). Throughout this section, we omit the superscript π from all policy-dependent quantities. Estimation of µ. Whenever the human agent serves a nonempty queue of type k, the service attempt succeeds with probability µk . Thus, each effective service attempt on type k produces a Bernoulli observation. For each k ∈ [K], define Nk (t) :=
t X
1{as = k, Qs,k > 0},
Sk (t) :=
s=1
t X
Ds,k .
(15)
s=1
Here, Nk (t) is the number of effective service attempts on type k up to time t, while Sk (t) is the number of successful completions of type-k tasks. We set Nk (0) = Sk (0) = 0. The empirical estimator of µk is if Nk (t) = 0, 0, µ̂k (t) := Sk (t) (16) , if Nk (t) ≥ 1. Nk (t) Given a confidence radius βkµ (t) ≥ 0, defined below, we use the optimistic estimate µ̄k (t) := min 1, µ̂k (t) + βkµ (t) .
(17)
Estimation of p. When a task of type k arrives at slot t and the chatbot cost ct is chosen, the chatbot succeeds with probability pk ct . Let Yt := 1{chatbot succeeds at slot t}. Conditionally on (Xt = k, ct ), E[Yt | Xt = k, ct ] = pk ct . To estimate pk , for each k ∈ [K] we define Mk (t) :=
t X
cs 1{Xs = k},
Gk (t) :=
s=1
t X
Ys 1{Xs = k}.
(18)
s=1
Here, Mk (t) is the cumulative exposure of type k to the chatbot, while Gk (t) is the cumulative number of chatbot successes on type k. As shown below, the UCB-DPP cost decision is threshold-based and therefore satisfies ct ∈ {0, 1}. Hence Mk (t) counts the number of effective chatbot trials on type k. We set Mk (0) = Gk (0) = 0. The empirical estimator of pk is if Mk (t) = 0, 0, p̂k (t) := Gk (t) (19) , if Mk (t) > 0. Mk (t) Given a confidence radius βkp (t) ≥ 0, we define p̄k (t) := min 1, p̂k (t) + βkp (t) . 8
(20)
Drift-Plus-Penalty principle.
We use a weighted quadratic Lyapunov function, K
1X Φ(Qt ) = rk Q2t,k . 2
(21)
∆t = E Φ(Qt+1 ) − Φ(Qt ) | Ft .
(22)
k=1
Let us define the conditional drift as
The following drift bound follows directly from the queue dynamics. Lemma 1 (Drift Upper Bound). For all t ∈ [T ], it holds that ∆t ≤ rmax +
K X
rk Qt,k E[At,k − Dt,k | Ft ].
k=1
The proof is in Appendix B. Following the Drift-Plus-Penalty methodology, the control actions are chosen by minimizing an upper bound on ∆t + V c t , (23) where the parameter V > 0 balances instantaneous chatbot costs against queue growth. Larger values of V put more weight on cost minimization, while smaller values prioritize congestion control. Using Lemma 1, we have ∆t + V ct ≤ rmax +
K X
rk Qt,k E[At,k − Dt,k | Ft ] + V ct .
(24)
k=1
Substituting the conditional expectations of the arrival and departure processes, and dropping the constant term rmax , yields the surrogate objective Ψt (c, a) := V c + rXt Qt,Xt (1 − pXt c) − ra Qt,a µa .
(25)
Since the parameters p and µ are unknown, the UCB-DPP policy replaces them with their optimistic estimates and minimizes e t (c, a) := V c + rXt Qt,Xt (1 − p̄Xt (t − 1)c) − ra Qt,a µ̄a (t − 1). Ψ
(26)
Thus, at each slot t, (ct , at ) ∈ arg
min c∈[0,1], a∈[K]
e t (c, a). Ψ
(27)
e t is separable in c and a and linear in c, the policy admits the explicit form Since Ψ ( 1, rXt p̄Xt (t − 1)Qt,Xt ≥ V, ct = at ∈ arg max rj Qt,j µ̄j (t − 1). j∈[K] 0, otherwise, 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 threshold V , 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 form sk (c) = pk c: since the surrogate objective is linear in c, the chatbot cost always takes values in {0, 1}, corresponding to an on/off decision. Learning enters the policy through two UCB mechanisms [1]: 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 the UCB-DPP policy is provided in Appendix B. 9
4
Regret Bound
We now show that the regret of the UCB-DPP policy grows sublinearly with the horizon T . 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 every t ∈ [T ], define the good event up to time t as Gt =
t \ K \
|µk − µ̂k (s − 1)| ≤ βkµ (s − 1) ∩ |pk − p̂k (s − 1)| ≤ βkp (s − 1) .
(28)
s=1 k=1
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 to t. Lemma 2 (Regret decomposition). The regret of the UCB-DPP policy satisfies RTUCB-DPP ≤ R1p (T ) + R1µ (T ) + R2 (T ) + R3 (T ) + R4 (T ), where hP i T • R1p (T ) := V1 E r Q c (p̄ (t − 1) − p ) 1{G } t , Xt Xt t=1 Xt t,Xt t hP i T • R1µ (T ) := V1 E r Q (µ̄ (t − 1) − µ ) 1{G } at at t , t=1 at t,at • R2 (T ) := T P(G T ), T • R3 (T ) := rmax V , P • R4 (T ) := K k=1 rk E[QT +1,k ].
We now bound the terms appearing in Lemma 2. Control of the bad event. We first control the probability of the complement of the good event. Fix δ ∈ (0, 1), whose value will be specified later. We set βkµ (0) := 1, βkp (0) := 1 and, for every t ≥ 1, define 1, s
βkµ (t) =
if Nk (t) = 0, log(4Kt/δ) , 2Nk (t)
if Nk (t) ≥ 1,
βkp (t)
=
1, s
if Mk (t) = 0, log(4Kt/δ) , 2Mk (t)
if Mk (t) ≥ 1.
(29)
Proposition 2. The event GT satisfies P(G T ) ≤ δT. We next control the backlog contribution R4 (T ). Define !1/2 K X p 2 Zt := 2Φ(Qt ) = rk Qt,k .
Control of the terminal backlog.
k=1
Lemma 3. Assume that there exist ε > 0 and a strictly feasible point (cε , ρε ) such that λk (1 − pk cεk ) + ε ≤ µk ρεk , ∀k ∈ [K]
and
K X k=1
Then E[ZT +1 1{GT }] ≤ O(V + K log(T /δ)). 10
ρεk ≤ 1.
(30)
The assumption in Lemma 3 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 class k, the effective service capacity µk ρεk exceeds the residual arrival rate λk (1 − pk cεk ) by a uniform margin ε. 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 on R4 (T )). Under the assumptions of Lemma 3, R4 (T ) satisfies R4 (T ) = O(V + K log(T /δ)) + rmax T P(G T ). Control of the estimation-error terms. It remains to control the two terms involving estimation errors on the good event, namely R1µ (T ) and R1p (T ). Proposition 4. The estimation-error terms satisfy p R1µ (T ), R1p (T ) = O K T log(T /δ) . 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, by setting V = T and δ = T −2 , the UCB-DPP policy satisfies, for T ≥ 2, p RTUCB-DPP = O K T log T . The proof starts from the regret decomposition in Lemma 2. 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 √ contribution T /V , and the terminal backlog, which is of order V up to logarithmic factors. Setting V = T and δ = T −2 balances these terms and gives the stated regret bound. √ We can also observe that, as a direct consequence of Proposition 3, choosing V = T and δ = T −2 gives a sublinear weighted terminal backlog. Since rk ≥ rmin > 0 for all k ∈ [K], each human-service queue is mean-rate stable: E[QT +1,k ] lim = 0, ∀k ∈ [K]. T →∞ T The complete proofs of this section are provided in Appendix C.
5
Simulations
We test the UCB-DPP policy on a synthetic instance with K = 5 task classes, arrival rates λ = (0.32, 0.08, 0.25, 0.20, 0.15), chatbot success probabilities p = (0.82, 0.35, 0.68, 0.25, 0.9), human service rates µ = (0.3, 0.85, 0.45, 0.75, 0.28), and terminal backlog weights r = (2.3, 0.8, 1.5, 0.9, 2.5), chosen to satisfy the assumption of Lemma 3. All simulations are run over a horizon T = 30000 for the UCB-DPP plot in Figure 2a and over a horizon T = 10000 for the policy comparison plot in Figure 2b. Each curve is averaged over 100 independent runs, and the shaded regions represent one standard error. As shown in Figure 2a, the cumulative regret of UCB-DPP grows sublinearly over time. 11
For the comparison plot, we consider three benchmark policies. The first is a plug-in version of DPP, which has the same decision structure as UCB-DPP but replaces the optimistic estimates p̄k (t) and µ̄k (t) with the empirical estimates p̂k (t) and µ̂k (t). The other two policies always set the chatbot cost to either c = 1 or c = 0, respectively, and use a greedy scheduling rule based only on the empirical service rates: at ∈ arg max rk µ̂k (t − 1). k∈[K]
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 2b 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.
(a) Average cumulative regret of UCB-DPP.
6
(b) Average cumulative regret of UCB-DPP and three baselines.
Conclusion, 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 the UCB-DPP policy, which combines optimistic parameter √ e estimation with a Drift-Plus-Penalty objective. We proved that UCB-DPP achieves regret O(K 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, with ct ∈ {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.
12
References [1] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2–3):235–256, 2002. [2] Sébastien Bubeck and Nicolò Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1–122, 2012. [3] Na Cai, Shuhong Gao, and Jinzhe Yan. How the communication style of chatbots influences consumers’ satisfaction, trust, and engagement in the context of service failure. Humanities and Social Sciences Communications, 11:687, 2024. [4] Semih Cayci, Yilin Zheng, and Atilla Eryilmaz. A lyapunov-based methodology for constrained optimization with bandit feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 3716–3723, 2022. [5] Sathwik Chadaga and Eytan Modiano. Drift plus optimistic penalty – a learning framework for stochastic network optimization. In IEEE INFOCOM 2025 - IEEE Conference on Computer Communications, pages 1–10, 2025. [6] Shili Chen, Xiaolin Li, Kecheng Liu, and Xuesong Wang. Chatbot or human? the impact of online customer service on consumers’ purchase intentions. Psychology & Marketing, 40(11):2186–2200, 2023. [7] Fabrizio Dell’Acqua, Edward McFowland, Ethan R. Mollick, Hila Lifshitz-Assaf, Katherine Kellogg, Saran Rajendran, Lisa Krayer, François Candelon, and Karim R. Lakhani. Navigating the jagged technological frontier: Field experimental evidence of the effects of artificial intelligence on knowledge worker productivity and quality. Organization Science, 2026. [8] Atilla Eryilmaz and R. Srikant. Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control. In Proceedings of IEEE INFOCOM, pages 1794–1803, 2005. [9] Darima Fotheringham and Michael A. Wiles. The effect of implementing chatbot customer service on stock returns: an event study analysis. Journal of the Academy of Marketing Science, 51(4):802–822, 2023. [10] Daniel Freund, Thodoris Lykouris, and Wentao Weng. The transient cost of learning in queueing systems, 2023. [11] Xinzhe Fu and Eytan Modiano. Joint learning and control in stochastic queueing networks with unknown utilities. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(3), 2022. [12] Leonidas Georgiadis, Michael J. Neely, and Leandros Tassiulas. Resource allocation and cross-layer control in wireless networks. Foundations and Trends in Networking, 1(1):1–144, 2006. [13] Angela Greilich, Kerstin Bremser, and Kirsten Wüst. Consumer response to anthropomorphism of text-based ai chatbots: A systematic literature review and future research directions. International Journal of Consumer Studies, 49(5):e70108, 2025. [14] Chin-Lung Hsu and Judy Chuan-Chuan Lin. Understanding the user satisfaction and loyalty of customer service chatbots. Journal of Retailing and Consumer Services, 71:103211, 2023.
13
[15] Dongling Huang, Dmitri G. Markovitch, and Rusty A. Stough. Can chatbot customer service match human service agents on customer satisfaction? an investigation in the role of trust. Journal of Retailing and Consumer Services, 76:103600, 2024. [16] Jiatai Huang, Leana Golubchik, and Longbo Huang. Queue scheduling with adversarial bandit learning, 2023. [17] Sarit Kraus, Yaniv Oshrat, Yonatan Aumann, Tal Hollander, Oleg Maksimov, Anita Ostroumov, and Natali Shechtman. Customer service combining human operators and virtual agents: A call for multidisciplinary ai research. Proceedings of the AAAI Conference on Artificial Intelligence, 37:15393– 15401, 06 2023. [18] Subhashini Krishnasamy, Rajat Sen, Ramesh Johari, and Sanjay Shakkottai. Learning unknown service rates in queues: A multiarmed bandit approach. Operations Research, 69(1):315–330, 2021. [19] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4–22, 1985. [20] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. [21] Benjamin Legros and Francis de Vericourt. Human-ai interaction in congested service systems: When it improves performance, and when it doesn’t. SSRN Electronic Journal, 01 2025. [22] Jiawei Liu, Zhe Gao, Yangyang Kang, Zhuoren Jiang, Guoxiu He, Changlong Sun, Xiaozhong Liu, and Wei Lu. Time to transfer: Predicting and evaluating machine-human chatting handoff. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5841–5849, 2021. [23] Jiawei Liu, Kaisong Song, Yangyang Kang, Guoxiu He, Zhuoren Jiang, Changlong Sun, Wei Lu, and Xiaozhong Liu. A role-selected sharing network for joint machine-human chatting handoff and service satisfaction analysis. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 9731–9741, Online and Punta Cana, Dominican Republic, 2021. Association for Computational Linguistics. [24] Michael J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems. Morgan and Claypool Publishers, 2010. [25] Michael J. Neely, Eytan Modiano, and Chih-Ping Li. Fairness and optimal stochastic control for heterogeneous networks. IEEE/ACM Transactions on Networking, 16(2):396–409, 2008. [26] Yaniv Oshrat, Yonatan Aumann, Tal Hollander, Oleg Maksimov, Anita Ostroumov, Natali Shechtman, and Sarit Kraus. Efficient customer service combining human operators and virtual agents, 2022. [27] Ben Sheehan, Hyun Seung Jin, and Udo Gottlieb. Customer service chatbots: Anthropomorphism and adoption. Journal of Business Research, 115:14–24, 2020. [28] Mengmeng Song, Xinyu Xing, Yucong Duan, Jason Cohen, and Jian Mou. Will artificial intelligence replace human customer service? the impact of communication quality and privacy risks on adoption intention. Journal of Retailing and Consumer Services, 66:102900, 2022. [29] Alexander L. Stolyar. Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. The Annals of Applied Probability, 14(1):1–53, 2004.
14
[30] Leandros Tassiulas and Anthony Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37(12):1936–1948, 1992. [31] Juan Camilo Vasquez-Correa, Juan Carlos Guerrero-Sierra, Jose Luis Pemberty-Tamayo, Juan Esteban Jaramillo, and Andres Felipe Tejada-Castro. One system to rule them all: a universal intent recognition system for customer service chatbots, 2021. [32] Yiwei Wang, Chuan Zhu, Tianjun Feng, Lauren Xiaoyuan Lu, and Bingxin Jia. Agentic ai and humanin-the-loop interventions: Field experimental evidence from alibaba’s customer service operations, 2026. [33] Yingzi Xu, Chih-Hui Shieh, Patrick van Esch, and I-Ling Ling. Ai customer service: Task complexity, problem-solving ability, and usage intention. Australasian Marketing Journal, 28(4):189–199, 2020. [34] Guanling Yang and Ricky Roet-Green. On the design of an ai-human service system with strategic customers: Should ai be mandated? SSRN Electronic Journal, 2026. [35] Zixian Yang, R. Srikant, and Lei Ying. Learning while scheduling in multi-server systems with unknown statistics: Maxweight with discounted ucb. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 4275–4312. PMLR, 2023. [36] Hao Yu, Michael J. Neely, and Xiaohan Wei. Online convex optimization with stochastic constraints. In Advances in Neural Information Processing Systems 30, pages 1428–1438, 2017. [37] Shanshan Zhong, Jinghui Qin, Zhongzhan Huang, and Daifeng Li. Cem: Machine-human chatting handoff via causal-enhance module. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 3242–3253, Abu Dhabi, United Arab Emirates, 2022. Association for Computational Linguistics.
A
Lower Bound via Static Optimization Problem
A.1
Proof of Theorem 1
For all k ∈ [K], let us sum over t the queue dynamics Equation (8) and use Qπ1,k = 0: QπT +1,k =
T X π (Aπt,k − Dt,k ). t=1
For simplicity of notation, let
P
t denote
PT
t=1 . Taking expectation and dividing by T , we obtain
" # " # X X 1 1 1 π E Aπt,k = E Dt,k + E QπT +1,k . T T T t t as
(31)
Now let us rewrite the objects associated with a policy π in a static form. Define the average cost per type " # X 1 π π c̄k = E ct 1{Xt = k} , T λk t
15
then it follows that
" # X X 1 π E ct = λk c̄πk . T t k
Let π Ut,k := 1{aπt = k, Qπt,k > 0}
be the indicator that, at slot t, the human agent serves a non-empty type-k queue. Define " # X 1 π Ut,k . ρ̄πk = E T t Since at each slot the agent works on at most one type, it follows that K X
ρ̄πk ≤ 1.
k=1
Finally define the average final backlog per unit of time as q̄kπ =
1 π E QT +1,k . T
(32)
Recall that for the arrival process, given Xt = k, E[Aπt,k | Xt = k, cπt ] = 1 − pk cπt . Therefore, by the tower property, E[Aπt,k ] = E E[Aπt,k | Xt , cπt ] . Since Aπt,k = 0 whenever Xt ̸= k, we get E[Aπt,k ] = E 1{Xt = k} E[Aπt,k | Xt = k, cπt ] = E[1{Xt = k}(1 − pk cπt )] . Expanding the right-hand side, E[Aπt,k ] = E[1{Xt = k}] − pk E[1{Xt = k}cπt ] . Using P(Xt = k) = λk , this becomes E[Aπt,k ] = λk − pk E[1{Xt = k}cπt ] . Summing over t = 1, . . . , T , dividing by T , and using the definition of c̄πk , we obtain " # " # X 1 1 X π π E At,k = λk − pk E 1{Xt = k}ct = λk − pk λk c̄πk . T T t t Hence
" # X 1 π E At,k = λk (1 − pk c̄πk ). T t
For the service process, conditional on actually serving a non-empty queue of type k, recall π π E[Dt,k | Ut,k = 1] = µk .
16
(33)
π = 0 whenever U π = 0, we can write Since Dt,k t,k π π π π π E[Dt,k ] = E[Dt,k | Ut,k = 1]P(Ut,k = 1) = µk E[Ut,k ].
Therefore, # # " " X X 1 1 π π = µk E = µk ρ̄πk . E Dt,k Ut,k T T t t
(34)
Putting Equations 32, 33 and 34 into Equation (31), we get λk (1 − pk c̄πk ) = µk ρ̄πk + q̄kπ .
(35)
So it follows that policy π, through (c̄π , ρ̄π ), violates the static constraints of the optimization problem in (13) by a term controlled by the final backlog q̄ π . Let us use a duality argument. Consider the static problem OPT(θ) in (13). Introduce the dual multipliers yk ≥ 0 for the queue-balance constraints λk (1 − pk ck ) − µk ρk ≤ 0, P and the multiplier ν ≥ 0 for the capacity constraint K k=1 ρk ≤ 1. The Lagrangian of the optimization problem is then X X X L(c, ρ, θ; y, ν) = λk ck + yk λk (1 − pk ck ) − µk ρk + ν ρk − 1 . k
k
k
Let (y ∗ , ν ∗ ) be an optimal dual solution. Since the static linear program in 13 is feasible and bounded, by strong duality OPT(θ) = inf L(c, ρ, θ; y ∗ , ν ∗ ). c,ρ
So for every choice of (c, ρ) it holds that L(c, ρ, θ; y ∗ , ν ∗ ) ≥ OPT(θ). From here, using the definition of L, we get X X X λk ck ≥ OPT(θ) − yk∗ λk (1 − pk ck ) − µk ρk − ν ∗ ρk − 1 . k
k
Now let us use (36) with c = c̄π and ρ = ρ̄π . Since −ν ∗
(36)
k
X
π ∗ k ρ̄k ≤ 1 and ν ≥ 0, we have
P
ρ̄πk − 1 ≥ 0.
k
In addition, using Equation (35), we get X
λk c̄πk ≥ OPT(θ) −
k
X
yk∗ q̄kπ .
k
We now conclude the lower bound by multiplying (37) by T and using the definition of the averages X X π ct ≥ T OPT(θ) − yk∗ E[QπT +1,k ]. E t
k
17
(37)
Using the definition of total final cost, we get X X π X ct + rk E[QπT +1,k ] ≥ T OPT(θ) + (rk − yk∗ )E[QπT +1,k ]. E[C π (T )] = E t
k
k
Finally, since we assumed that for all k ∈ [K] rk ≥ yk∗ , 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 E[C π (T )] ≥ T · OPT(θ),
π∈Π∗
□
which proves the theorem.
A.2
Proof of Proposition 1
Since c∗Xt = c∗k whenever Xt = k, and the arrivals are i.i.d. with distribution λ, it holds that T
K
t=1
k=1
X 1X E[c∗Xt ] = λk c∗k = OPT(θ). T Therefore, using Theorem 1 in the definition of regret (12), we obtain RTπ ≤
T X
K X
E[cπt ] − T OPT(θ) +
t=1
rk E[QπT +1,k ] =
T X
E[cπt − c∗Xt ] +
t=1
k=1
K X
rk E[QπT +1,k ].
k=1
□
B
UCB-DPP Policy
B.1
Proof of Lemma 1
For each k ∈ [K], the queue dynamics is Qt+1,k = Qt,k + At,k − Dt,k . Therefore, Q2t+1,k = Q2t,k + (At,k − Dt,k )2 + 2Qt,k (At,k − Dt,k ). Using the definition of Φ, we obtain Φ(Qt+1 ) − Φ(Qt ) =
K
K
k=1
k=1
X 1X rk (At,k − Dt,k )2 + rk Qt,k (At,k − Dt,k ). 2
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] has at most two nonzero entries, each with absolute value at most one. Thus, K X (At,k − Dt,k )2 ≤ 2. k=1
Since rk ≤ rmax for all k ∈ [K], it follows that K
1X rk (At,k − Dt,k )2 ≤ rmax . 2 k=1
18
Consequently, Φ(Qt+1 ) − Φ(Qt ) ≤ rmax +
K X
rk Qt,k (At,k − Dt,k ).
k=1
Taking conditional expectation with respect to Ft gives the desired bound. □ The UCB-DPP policy is summarized in Algorithm 1. 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 1 UCB-DPP Policy 1: Input: horizon T , number of classes K, weights (rk )K k=1 , parameter V > 0, confidence level δ ∈ (0, 1). 2: Initialize: Q1,k = 0 and Nk (0) = Sk (0) = Mk (0) = Gk (0) = 0 for all k ∈ [K]. 3: for t = 1, . . . , T do
7:
Observe the current queues Qt and the arriving type Xt . For each k ∈ [K], compute µ̂k (t − 1) as in (16) and µ̄k (t − 1) as in (17). For each k ∈ [K], compute p̂k (t − 1) as in (19) and p̄k (t − 1) as in (20). Choose the chatbot cost ( 1, if rXt Qt,Xt p̄Xt (t − 1) ≥ V, ct = 0, otherwise.
8:
Choose the scheduling action
4: 5: 6:
at ∈ arg max rk Qt,k µ̄k (t − 1). k∈[K]
9: 10: 11: 12: 13: 14:
If all queues are empty, choose at arbitrarily. Apply the chatbot decision and observe: Yt = 1{chatbot succeeds at slot t}. Define the human-queue arrivals: At,k = 1{Xt = k}(1 − Yt ) for all k ∈ [K]. Serve queue at . If Qt,at > 0, observe the service outcome Dt,at ; otherwise set Dt,at = 0. Set Dt,k = 0 for all k ̸= at . Update the queues according to: Qt+1,k = Qt,k + At,k − Dt,k ,
15:
Update the chatbot counters: MXt (t) = MXt (t − 1) + ct ,
16:
k ∈ [K].
GXt (t) = GXt (t − 1) + Yt .
Update the service counters: Nat (t) = Nat (t − 1) + 1{Qt,at > 0},
All counters not explicitly updated remain unchanged. 18: end for 17:
19
Sat (t) = Sat (t − 1) + Dt,at .
C
Regret Bound
C.1
Proof of Regret Decomposition Lemma 2
Recall that, according to Proposition 1, the regret of any policy, and in particular that of UCB-DPP, satisfies RTUCB-DPP ≤
T X
E[cUCB-DPP − c∗Xt ] + t
t=1
K X
rk E[QUCB-DPP T +1,k ].
k=1
For ease of notation, from now on we omit the superscript UCB-DPP from all relevant quantities whenever no ambiguity arises. In particular, we simply write ct , at , and Qt,k . Recall that (c∗ , ρ∗ ) is the optimal solution of the static optimization problem (13). For every t ∈ [T ],
Decomposition into good and bad events.
E[ct − c∗Xt ] = E[(ct − c∗Xt )1{Gt }] + E[(ct − c∗Xt )1{G t }]. Since both ct and c∗Xt are in [0, 1], it follows that ct − c∗Xt ≤ 1. Hence E[ct − c∗Xt ] ≤ E[(ct − c∗Xt )1{Gt }] + P(G t ).
(38)
We can now observe that G t ⊆ G T , hence P(G t ) ≤ P(G T ). Summing over t, we obtain: T X
E[ct − c∗Xt ] ≤
t=1
T X
E[(ct − c∗Xt )1{Gt }] + T P(G T ).
(39)
t=1
The second term is exactly R2 (T ). Drift Plus Penalty under good events. Let Ht denote the information available at the beginning of slot t, before the arrival type Xt is observed. By the i.i.d. assumption on the arrivals, for every k ∈ [K], P(Xt = k | Ht ) = λk . By the bound on the conditional drift in Lemma 1, 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 .
(40)
Let us add and subtract the quantities rXt Qt,Xt (1 − p̄Xt (t − 1)ct ) and rat Qt,at µ̄at (t − 1). We obtain ∆t + V ct ≤ rmax + (V ct + rXt Qt,Xt (1 − p̄Xt (t − 1)ct ) − rat Qt,at µ̄at (t − 1)) + rXt Qt,Xt ct (p̄Xt (t − 1) − pXt ) + rat Qt,at (µ̄at (t − 1) − µat ) . By policy definition, UCB-DPP chooses at each t the pair (ct , at ) minimizing V c + rXt Qt,Xt (1 − p̄Xt (t − 1)c) − ra Qt,a µ̄a (t − 1), over c ∈ [0, 1] and a ∈ {1, . . . , K}. Therefore, for every alternative pair (c̃t , ãt ), ∆t + V ct ≤ rmax + (V c̃t + rXt Qt,Xt (1 − p̄Xt (t − 1)c̃t ) − rãt Qt,ãt µ̄ãt (t − 1)) + rXt Qt,Xt ct (p̄Xt (t − 1) − pXt ) + rat Qt,at (µ̄at (t − 1) − µat ) . 20
(41)
Comparison with the static benchmark. We now compare the policy with the static solution (c∗ , ρ∗ ). Choose (c̃t , ãt ) in Equation (41) as follows: • if Xt = k, then c̃t = c∗k ; • choose ãt = j with probability ρ∗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. Substituting c̃t = c∗Xt into (41) and taking conditional expectation with respect to the randomized comparison action ãt , given the history up to the beginning of slot t and the realized type Xt , we first obtain ∆t + V (ct − c∗Xt ) ≤ rmax + rXt Qt,Xt
1 − p̄Xt (t − 1)c∗Xt
−
K X
ρ∗j rj Qt,j µ̄j (t − 1)
j=1
+ rXt Qt,Xt ct (p̄Xt (t − 1) − pXt ) + rat Qt,at (µ̄at (t − 1) − µat ) . Here we used that E[rãt Qt,ãt µ̄ãt (t − 1) | Ft ] =
K X
ρ∗j rj Qt,j µ̄j (t − 1).
j=1
We then take conditional expectation with respect to Xt , conditioning on the information available at the beginning of slot t. Since P(Xt = k | Ht ) = λk , we obtain K X E ∆t + V (ct − c∗Xt ) | Ht ≤ rmax + rk Qt,k (λk (1 − p̄k (t − 1)c∗k ) − ρ∗k µ̄k (t − 1)) k=1
+ E[rXt Qt,Xt ct (p̄Xt (t − 1) − pXt ) | Ht ] + E[rat Qt,at (µ̄at (t − 1) − µat ) | Ht ] . Now suppose that the good event Gt holds. Then, for every k ∈ [K], p̄k (t − 1) ≥ pk
and
µ̄k (t − 1) ≥ µk .
Therefore, λk (1 − p̄k (t − 1)c∗k ) − ρ∗k µ̄k (t − 1) ≤ λk (1 − pk c∗k ) − ρ∗k µk . Since (c∗ , ρ∗ ) is feasible for the static problem, λk (1 − pk c∗k ) − ρ∗k µk ≤ 0. Hence, under Gt , E ∆t + V (ct − c∗Xt ) | Ht ≤ rmax + E[rXt Qt,Xt ct (p̄Xt (t − 1) − pXt ) | Ht ] + E[rat Qt,at (µ̄at (t − 1) − µat ) | Ht ] . Multiplying by 1{Gt }, taking expectation, and summing over t, we obtain " T # T X X rmax T 1 ∗ + E rXt Qt,Xt ct (p̄Xt (t − 1) − pXt ) 1{Gt } E[(ct − cXt )1{Gt }] ≤ V V t=1 t=1 " T # X 1 + E rat Qt,at (µ̄at (t − 1) − µat ) 1{Gt } V t=1
T
−
1 X E[1{Gt }∆t ]. V t=1
21
(42)
(43)
Using the definition of ∆t and linearity of expectation, " T # T X X E[1{Gt }∆t ] = E 1{Gt } (Φ(Qt+1 ) − Φ(Qt )) .
Control of the drift term.
t=1
t=1
Since the events {Gt }t∈[T ] are decreasing and nested, we have T X
1{Gt } (Φ(Qt+1 ) − Φ(Qt )) ≥ −Φ(Q1 ) = 0,
t=1
because Q1 = 0. Therefore, −
T X
E[1{Gt }∆t ] ≤ 0.
t=1
Plugging this into Equation (43), we finally get " T # X 1 r T max E[(ct − c∗Xt )1{Gt }] ≤ + E rXt Qt,Xt ct (p̄Xt (t − 1) − pXt ) 1{Gt } V V t=1 t=1 " T # X 1 rat Qt,at (µ̄at (t − 1) − µat ) 1{Gt } . + E V
T X
(44)
t=1
The three terms on the right-hand side are exactly R3 (T ), R1p (T ), and R1µ (T ). Conclusion.
By Proposition 1, RTUCB-DPP ≤
T X
E[ct − c∗Xt ] +
t=1
K X
rk E[QT +1,k ].
k=1
Combining this with Equations (39) and 44, we obtain RTUCB-DPP ≤ R1p (T ) + R1µ (T ) + R2 (T ) + R3 (T ) + R4 (T ), where the last term is exactly R4 (T ) =
K X
rk E[QT +1,k ].
k=1
□
This proves the lemma.
C.2
Proof of Proposition 2
We split the good event as defined in Equation (28) into the service-side and chatbot-side parts. Define GTµ :=
T \ K \
|µ̂k (s − 1) − µk | ≤ βkµ (s − 1) ,
s=1 k=1
and GTp :=
T \ K \
|p̂k (s − 1) − pk | ≤ βkp (s − 1) .
s=1 k=1
Then GT = GTµ ∩ GTp , so that
µ
p
P(G T ) ≤ P(G T ) + P(G T ). 22
Control of the service-side event. For all k ∈ [K] and n ≥ 1, define the time of the n-th effective service attempt on type k by τn,k := inf{t ≥ 1 : Nk (t) = n}. When τn,k < ∞, define dn,k := Dτn,k ,k , namely the indicator of completion observed at the n-th effective service attempt on type k. By the model assumptions, every time the server makes an effective service attempt on a queue of type k, the completion occurs with probability µk , independently of the past. Therefore, for every k, the sequence (dn,k )n≥1 is i.i.d. Bernoulli with parameter µk . Moreover, for every t, Nk (t) X Sk (t) = dn,k . n=1
Hence, if Nk (t) = n ≥ 1, then
n
1 X µ̂k (t) = dm,k . n m=1
Now fix s ∈ {1, . . . , T } and k ∈ [K]. If Nk (s − 1) = 0, then by definition βkµ (s − 1) = 1,
µ̂k (s − 1) = 0, and therefore
|µ̂k (s − 1) − µk | ≤ 1 = βkµ (s − 1). Assume now that Nk (s − 1) ≥ 1. Since Nk (s − 1) ≤ s − 1, we can write P |µ̂k (s − 1) − µk | > βkµ (s − 1) =
s−1 X
P |µ̂k (s − 1) − µk | > βkµ (s − 1), Nk (s − 1) = n .
n=1
On the event {Nk (s − 1) = n}, we have n
r
1 X µ̂k (s − 1) = dm,k , n
βkµ (s − 1) =
log(4K(s − 1)/δ) . 2n
n
r
m=1
Therefore, P |µ̂k (s − 1) − µk | > βkµ (s − 1) ≤
s−1 X
1 X dm,k − µk > n
P
n=1
m=1
log(4K(s − 1)/δ) 2n
By Hoeffding’s inequality, for every n ≥ 1, n
P
1 X dm,k − µk > n m=1
r
log(4K(s − 1)/δ) 2n
! ≤
δ . 2K(s − 1)
Hence, s−1 X P |µ̂k (s − 1) − µk | > βkµ (s − 1) ≤ n=1
δ δ = . 2K(s − 1) 2K
Taking a union bound over s ∈ {2, . . . , T } and k ∈ [K], we get µ
P(G T ) ≤
T X K X δ (T − 1)δ = . 2K 2 s=2 k=1
23
! .
Control of the chatbot-side event. Recall that the chatbot decision is bang-bang, so the estimation of pk is based on those slots in which Xt = k and ct = 1. For all k ∈ [K] and n ≥ 1, define the time of the n-th informative chatbot exposure on type k by σn,k := inf{t ≥ 1 : Mk (t) = n}. When σn,k < ∞, define zn,k := Yσn,k , where Yt = 1{chatbot succeeds at slot t}. By construction, whenever t = σn,k we have Xt = k and ct = 1, hence E[Yt | Xt = k, ct = 1] = pk . Therefore, for every k, the sequence (zn,k )n≥1 is i.i.d. Bernoulli with parameter pk . Moreover, for every t, Mk (t) X Gk (t) = zn,k . n=1
Hence, if Mk (t) = n ≥ 1, then
n
1 X zm,k . p̂k (t) = n m=1
Now fix s ∈ {1, . . . , T } and k ∈ [K]. If Mk (s − 1) = 0, then by definition βkp (s − 1) = 1,
p̂k (s − 1) = 0, and therefore
|p̂k (s − 1) − pk | ≤ 1 = βkp (s − 1). Assume now that Mk (s − 1) ≥ 1. As in the service-side case, we decompose according to the possible values of Mk (s − 1) and use n
1 X p̂k (s − 1) = zm,k n
on {Mk (s − 1) = n},
m=1
Therefore, P |p̂k (s − 1) − pk | > βkp (s − 1) ≤ ≤
s−1 X n=1 s−1 X n=1
n
1 X zm,k − pk > n
P
m=1
δ δ = , 2K(s − 1) 2K
where the second inequality follows from Hoeffding’s inequality. Taking a union bound over s ∈ {2, . . . , T } and k ∈ [K], we obtain p
P(G T ) ≤
T X K X δ (T − 1)δ = . 2K 2 s=2 k=1
24
r
log(4K(s − 1)/δ) 2n
!
Conclusion.
Combining the bounds on the two parts, µ
p
P(G T ) ≤ P(G T ) + P(G T ) ≤ δ(T − 1) ≤ δT. □
This completes the proof.
C.3
Bounding R4 (T )
Before proceeding, we introduce several auxiliary quantities that will be used throughout the proofs. Set Aε := rmax + V
K X
λk cεk ,
(45)
k=1
and
32 log(4KT /δ) , Lε := ε2 Finally, define
ηε :=
√ ε rmin , 8
δr :=
√
2rmax ,
8Aε θε := √ . ε rmin
Cr := δr + ηε .
(46)
(47)
We also define, for each t ∈ [T ], the indicators of exceptional slots: n εo Jtµ := 1 Qt,at > 0, βaµt (t − 1) > , (48) 8 and n εo p (t − 1) > Jtp := 1 ct = 1, βX . (49) t 8 These indicators identify the slots in which the relevant confidence radius is larger than a threshold proportional to ε. We finally define Jt := max{Jtµ , Jtp }. (50) We then state a well-known drift lemma introduced in [36]. For our purposes, we present it directly in the special case t0 = 1. Lemma 4. Let {Ut }t≥1 be a process adapted to a filtration {Ft }t≥1 , with U1 = 0. Assume that there exist constants θ > 0, δ > 0, and η > 0 such that, for all t ≥ 1, Ut+1 − Ut ≤ δ
a.s.,
and E[Ut+1 − Ut | Ft ] ≤ δ
whenever Ut < θ,
E[Ut+1 − Ut | Ft ] ≤ −η
whenever Ut ≥ θ.
while Then, for every t ≥ 1, 2 4δ 2 8δ E[Ut ] ≤ θ + δ + log . η η2 C.3.1
Proof of Lemma 3
Recall that Ht denote the information available at the beginning of slot t, before the arrival type Xt is observed. In particular, Qt , p̂(t − 1), µ̂(t − 1), and Gt are Ht -measurable. Recall also that Ft is the information available after observing the arrival type and selecting the control actions at slot t. We first control the number of exceptional slots as defined in Equations 48, 49 and 50. 25
Service-side exceptional slots.
If Jtµ = 1 and at = k, then either Nk (t − 1) = 0, in which case trivially Nk (t − 1) = 0 <
32 log(4KT /δ) , ε2
or Nk (t − 1) ≥ 1, in which case necessarily t ≥ 2 and s log(4K(t − 1)/δ) ε βkµ (t − 1) = > , 2Nk (t − 1) 8 which implies 32 log(4KT /δ) 32 log(4K(t − 1)/δ) ≤ . 2 ε ε2 Since Qt,k > 0, slot t is an effective service attempt on type k, hence the counter Nk increases by one. More precisely, for each fixed k ∈ [K], every slot t such that Jtµ = 1 and at = k contributes one unit to the counter Nk . Since this can only occur while Nk (t − 1) < Lε (as defined in Equation 46), we must have Nk (t − 1) <
T X
1{Jtµ = 1, at = k} ≤ Lε .
t=1
Summing over k ∈ [K], we obtain T X
Jtµ =
t=1
K X T X
1{Jtµ = 1, at = k} ≤ KLε .
(51)
k=1 t=1
Chatbot-side exceptional slots. We can reason in the same way as in the previous case. If Jtp = 1 and Xt = k, then by definition ct = 1, so slot t is an informative chatbot exposure for type k, and therefore the counter Mk increases by one at time t. Moreover, either Mk (t − 1) = 0, in which case trivially Mk (t − 1) = 0 <
32 log(4KT /δ) , ε2
or Mk (t − 1) ≥ 1, in which case necessarily t ≥ 2 and s log(4K(t − 1)/δ) ε p > , βk (t − 1) = 2Mk (t − 1) 8 which implies 32 log(4K(t − 1)/δ) 32 log(4KT /δ) ≤ . 2 ε ε2 Hence, for each fixed k, the event {Jtp = 1, Xt = k} can occur at most Lε times. Summing over k, we obtain the bound T X Jtp ≤ KLε . (52) Mk (t − 1) <
t=1
Since Jt ≤ Jtµ + Jtp , it follows that T X
Jt ≤ 2KLε .
t=1
26
(53)
Drift bound on good non-exceptional slots.
By Lemma 1,
∆t ≤ rmax + rXt Qt,Xt (1 − pXt ct ) − rat Qt,at µat . Hence, by adding and subtracting relevant quantities, ∆t + V ct ≤ rmax + (V ct + rXt Qt,Xt (1 − p̄Xt (t − 1)ct ) − rat Qt,at µ̄at (t − 1)) + rXt Qt,Xt ct (p̄Xt (t − 1) − pXt ) + rat Qt,at (µ̄at (t − 1) − µat ) . By policy definition, for every realized Xt , the UCB-DPP policy minimizes in (c, a) the surrogate objective V c + rXt Qt,Xt (1 − p̄Xt (t − 1)c) − ra Qt,a µ̄a (t − 1). We now compare the policy with the randomized stationary policy induced by (cε , ρε ), whose existence is guaranteed by assumption. More precisely, we consider the policy defined as follows: • choose c̃t = cεXt ; • choose ãt = k with probability ρεk . Hence, by taking conditional expectation first with respect to the randomized comparison action and then with respect to Xt , conditioning on Ht , we get E[∆t + V ct | Ht ] ≤ Aε +
K X
rk Qt,k (λk (1 − p̄k (t − 1)cεk ) − ρεk µ̄k (t − 1))
k=1
+ E[rXt Qt,Xt ct (p̄Xt (t − 1) − pXt ) | Ht ] + E[rat Qt,at (µ̄at (t − 1) − µat ) | Ht ] . where Aε is defined in Equation 45. Now let us work on the event Gt ∩ {Jt = 0}. Since this event is Ft -measurable, we first control the last two terms pathwise on Ft , and then return to Ht by the tower property. Since Gt holds and Jtµ = 0, we have ε 0 ≤ µ̄at (t − 1) − µat ≤ 2βaµt (t − 1) ≤ , 4 and therefore, pathwise on Gt ∩ {Jt = 0}, K
rat Qt,at (µ̄at (t − 1) − µat ) ≤
εX rk Qt,k . 4 k=1
Moreover, on Gt ∩ {Jt = 0}, the chatbot optimism term is controlled pathwise as follows: • if ct = 0, then rXt Qt,Xt ct (p̄Xt (t − 1) − pXt ) = 0; • if ct = 1, then Jtp = 0, hence and since Gt holds,
ε p βX (t − 1) ≤ , t 8
ε p (t − 1) ≤ . 0 ≤ p̄Xt (t − 1) − pXt ≤ 2βX t 4
Therefore, K
rXt Qt,Xt ct (p̄Xt (t − 1) − pXt ) ≤
ε εX rXt Qt,Xt ≤ rk Qt,k . 4 4 k=1
27
Thus, by the tower property, E[rat Qt,at (µ̄at (t − 1) − µat ) 1{Gt }1{Jt = 0} | Ht ] K
≤
εX rk Qt,k P(Gt ∩ {Jt = 0} | Ht ), 4 k=1
and similarly E[rXt Qt,Xt ct (p̄Xt (t − 1) − pXt ) 1{Gt }1{Jt = 0} | Ht ] K
εX ≤ rk Qt,k P(Gt ∩ {Jt = 0} | Ht ). 4 k=1
Finally, since Gt implies p̄k (t − 1) ≥ pk and µ̄k (t − 1) ≥ µk , strict feasibility gives λk (1 − p̄k (t − 1)cεk ) − ρεk µ̄k (t − 1) ≤ λk (1 − pk cεk ) − ρεk µk ≤ −ε. Therefore, E[(∆t + V ct )1{Gt }1{Jt = 0} | Ht ] Aε − ε
≤
K X k=1
K
K
k=1
k=1
εX εX rk Qt,k + rk Qt,k rk Qt,k + 4 4
! P(Gt ∩ {Jt = 0} | Ht ),
that is, K
E[(∆t + V ct )1{Gt }1{Jt = 0} | Ht ] ≤
εX Aε − rk Qt,k 2
! P(Gt ∩ {Jt = 0} | Ht ).
(54)
k=1
Since V ct ≥ 0, it follows that K
E[∆t 1{Gt }1{Jt = 0} | Ht ] ≤
εX rk Qt,k Aε − 2
! P(Gt ∩ {Jt = 0} | Ht ).
(55)
k=1
Now observe that K X k=1
rk Qt,k =
K X √
K
X√ √ √ √ rk ( rk Qt,k ) ≥ rmin rk Qt,k ≥ rmin
k=1
k=1
K X
!1/2 rk Q2t,k
=
∆t =
rmin Zt .
k=1
P √ The third relation is true since each element of the sum k rk Qt,k is non-negative. Hence, from (55), √ ε rmin E[∆t 1{Gt }1{Jt = 0} | Ht ] ≤ Aε − Zt P(Gt ∩ {Jt = 0} | Ht ). 2 Since
√
1 2 E[Zt+1 − Zt2 | Ft ], 2
the tower property yields 2 E (Zt+1 − Zt2 )1{Gt }1{Jt = 0} | Ht = 2 E[∆t 1{Gt }1{Jt = 0} | Ht ] . 28
(56)
Therefore, by (56), 2 √ E (Zt+1 − Zt2 )1{Gt }1{Jt = 0} | Ht ≤ (2Aε − ε rmin Zt ) P(Gt ∩ {Jt = 0} | Ht ).
(57)
Whenever Ut ≥ θε , we have Ut ≤ Zt 1{Gt } ≤ Zt , hence necessarily Gt holds and Zt ≥ θε . By the definition of θε (Equation 47), √ ε rmin Zt ≥ 8Aε , and therefore
√ ε rmin √ Zt = −2ηε Zt . 2Aε − ε rmin Zt ≤ − 4
Hence, on {Ut ≥ θε }, 2 E (Zt+1 − Zt2 )1{Gt }1{Jt = 0} | Ht ≤ −2ηε Zt P(Gt ∩ {Jt = 0} | Ht ).
(58)
Since Zt2 − 2ηε Zt ≤ (Zt − ηε )2 , it follows from (58) that, on {Ut ≥ θε }, 2 E Zt+1 1{Gt }1{Jt = 0} | Ht ≤ (Zt − ηε )2 P(Gt ∩ {Jt = 0} | Ht ). By Cauchy–Schwarz, 2 E[Zt+1 1{Gt }1{Jt = 0} | Ht ]2 ≤ P(Gt ∩ {Jt = 0} | Ht ) E Zt+1 1{Gt }1{Jt = 0} | Ht ≤ (Zt − ηε )2 P(Gt ∩ {Jt = 0} | Ht )2 . Since Zt+1 ≥ 0, we conclude that on {Ut ≥ θε }, E[(Zt+1 − Zt )1{Gt }1{Jt = 0} | Ht ] ≤ −ηε P(Gt ∩ {Jt = 0} | Ht ).
(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 X
!1/2 rk (Qt+1,k − Qt,k )2
≤
√
2rmax .
k=1
Now recall that δr = Define the process
√
2rmax as defined in Equation 46.
Ut := Zt 1{Gt } − Cr
t−1 X
Js 1{Gs },
t = 1, . . . , T + 1,
s=1
where Cr is defined in Equation 46. Since Q1 = 0, we have Z1 = 0, and thus U1 = 0. We claim that Lemma 4 applies to {Ut }t≥1 with respect to the filtration {Ht }t≥1 . First, Ut+1 − Ut = Zt+1 1{Gt+1 } − Zt 1{Gt } − Cr Jt 1{Gt }. 29
Since Gt+1 ⊆ Gt , we have 1{Gt+1 } ≤ 1{Gt }, so Ut+1 − Ut ≤ (Zt+1 − Zt )1{Gt } − Cr Jt 1{Gt } ≤ Zt+1 − Zt ≤ δr . The first condition of Lemma 4 is therefore satisfied. If Ut < θε , then trivially E[Ut+1 − Ut | Ht ] ≤ δr . Thus the second condition of Lemma 4 also holds. Now suppose that Ut ≥ θε . Since Ut ≤ Zt 1{Gt } ≤ Zt , we must have Gt and Zt ≥ θε . Then E[Ut+1 − Ut | Ht ] ≤ E[(Zt+1 − Zt )1{Gt }1{Jt = 0} | Ht ] + E[(Zt+1 − Zt − Cr )1{Gt }1{Jt = 1} | Ht ]. By (59), E[(Zt+1 − Zt )1{Gt }1{Jt = 0} | Ht ] ≤ −ηε P(Gt ∩ {Jt = 0} | Ht ). On the other hand, on Gt ∩ {Jt = 1} we simply use Zt+1 − Zt ≤ δr , hence E[(Zt+1 − Zt − Cr )1{Gt }1{Jt = 1} | Ht ] ≤ (δr − Cr ) P(Gt ∩ {Jt = 1} | Ht ) = −ηε P(Gt ∩ {Jt = 1} | Ht ). Combining the two estimates yields E[Ut+1 − Ut | Ht ] ≤ −ηε . Therefore the third condition of Lemma 4 is satisfied as well. We may now apply Lemma 4 with θ = θε ,
δ = δr ,
η = ηε .
It follows that E[UT +1 ] ≤ Mε with Mε =
8
(60)
! PK ε √ λ c 16rmax 8rmax 1024rmax k k=1 k ·V + √ + 2rmax + √ log . √ ε rmin ε rmin ε rmin ε2 rmin
(61)
Since we are just interested in the dependency on T , we can observe that Mε = O(V ) (the choice of the right value of V is horizon-dependent). Finally, by definition of UT +1 , UT +1 = ZT +1 1{GT } − Cr
T X
Jt 1{Gt }.
t=1
Hence ZT +1 1{GT } ≤ UT +1 + Cr
T X
Jt .
t=1
Using (53), we conclude that ZT +1 1{GT } ≤ UT +1 + 2Cr KLε . Taking expectations and using Equation 60, we finally get E[ZT +1 1{GT }] ≤ Mε + 2Cr KLε . We can observe that 2Cr KLε = O(K log(T /δ)). This proves the lemma.
□ 30
C.3.2
Proof of Proposition 3
We decompose R4 (T ) =
K X
rk E[QT +1,k 1{GT }] +
k=1
K X
rk E[QT +1,k 1{G T }].
k=1
Since at most one task arrives in each slot and the queues start empty, the total backlog satisfies K X
QT +1,k ≤ T.
k=1
Hence
K X
rk QT +1,k ≤ rmax
k=1
and therefore
K X
K X
QT +1,k ≤ rmax T,
k=1
rk E[QT +1,k 1{G T }] ≤ rmax T P(G T ).
k=1
On the good event, by Cauchy–Schwarz, K X k=1
rk QT +1,k =
K X √
√
rk ( rk QT +1,k ) ≤
k=1
K X
!1/2
K X
rk
Thus rk E[QT +1,k 1{GT }] ≤
=
K X
K X
!1/2 rk
ZT +1 .
k=1
k=1
k=1
K X
!1/2 rk Q2T +1,k
!1/2 rk
E[ZT +1 1{GT }].
k=1
k=1
Applying Lemma 3, we obtain K X
rk E[QT +1,k 1{GT }] ≤
K X
!1/2 rk
(Mε + 2Cr KLε ) .
k=1
k=1
Combining the good-event and bad-event contributions yields R4 (T ) ≤
K X
!1/2 rk
(Mε + 2Cr KLε ) + rmax T P(G T ).
k=1
Finally, since Mε = O(V ) and 2Cr KLε = O(K log(T /δ)), we conclude that R4 (T ) = O (V + K log(T /δ)) + rmax T P(G T ). □
31
C.4
Bounding R1µ (T ) and R1p (T )
Before proceeding to the bound on R1µ (T ) and R1p (T ), we need an additional technical lemma. The result extends the backlog estimate of Lemma 3 to suitable random times, which naturally arise in the analysis of the estimation errors. For every k ∈ [K] and every n ∈ [T ], let us first define the random time of the n-th effective service on queue k as τk,n := inf{t ≥ 1 : Nk (t) = n}. (62) Similarly, for every k ∈ [K] and every n ∈ [T ], define the random time of the n-th informative chatbot exposure on type k as σk,n := inf{t ≥ 1 : Mk (t) = n}. (63) Lemma 5. For every k ∈ [K] and every n ∈ [T ], the random times τk,n ∧ T and σk,n ∧ T are stopping times. Moreover, for every random time κk,n ∈ {τk,n , σk,n }, it holds that E rk Qκk,n ,k 1{κk,n ≤ T } 1{Gκk,n } = O(V + K log(T /δ)) Proof. Fix k ∈ [K] and n ∈ [T ], and let κk,n ∈ {τk,n , σk,n } as defined in Equations (62) and (63). First, κk,n ∧ T is a stopping time. Indeed, {τk,n ≤ t} = {Nk (t) ≥ n} ∈ Ft ,
{σk,n ≤ t} = {Mk (t) ≥ n} ∈ Ft .
Define the first bad time as τbad := inf{t ≥ 1 : G t } ∧ (T + 1). +1 by We define an auxiliary process {Vt }Tt=1
Vt =
t−1 X Z − C J , t
r
if t < τbad ,
s
s=1
Vτbad −1 − ηε (t − τbad + 1),
if t ≥ τbad .
where ηε and Cr are defined in Equation 46. Thus, up to the first bad time, the process Vt coincides with the compensated process Ut used in the proof of Lemma 3, while after τbad it is continued deterministically with slope −ηε . Bounded increments of Vt .
Recall that, according to Equation 46, √ δr = 2rmax , Cr = δr + ηε .
Plus recall that, since in each slot there is at most one arrival and at most one departure, we have 1/2 K X |Zt+1 − Zt | ≤ rj (Qt+1,j − Qt,j )2 ≤ δr . j=1
Define Bε := δr + Cr . If t < τbad − 1, then Vt+1 − Vt = Zt+1 − Zt − Cr Jt , 32
(64)
hence |Vt+1 − Vt | ≤ |Zt+1 − Zt | + Cr Jt ≤ δr + Cr = Bε . If t = τbad − 1, then by definition Vt+1 − Vt = −ηε , and if t ≥ τbad , again Vt+1 − Vt = −ηε . Therefore, for every t ∈ [T ], |Vt+1 − Vt | ≤ Bε
a.s.
(65)
Next we verify the negative drift condition above the threshold θε , defined in Equation 47. If t < τbad − 1, then Vt coincides with the compensated process Ut considered in the proof of Lemma 3. Hence, whenever Vt ≥ θε , that proof gives E[Vt+1 − Vt | Ft ] ≤ −ηε . If instead t ≥ τbad − 1, then by construction Vt+1 − Vt = −ηε . Thus, for every t ∈ [T ], E[Vt+1 − Vt | Ft ] ≤ −ηε Exponential recursion.
whenever Vt ≥ θε .
(66)
Set ηε aε := 2 , Bε
ηε2 ρε := exp − 2 ∈ (0, 1). 2Bε
Let ∆Vt := Vt+1 − Vt . By (65), we have |∆Vt | ≤ Bε almost surely. Therefore, by the conditional Hoeffding lemma, with −Bε ≤ ∆Vt ≤ Bε , 2 2 h i a B aε (∆Vt −E[∆Vt |Ft ]) E e | Ft ≤ exp ε ε . 2 Hence, on the event {Vt ≥ θε }, using (66), E[e
aε ∆Vt
a2ε Bε2 | Ft ] ≤ exp aε E[∆Vt | Ft ] + 2 2 2 a B ≤ exp −aε ηε + ε ε 2 2 η = exp − ε 2 = ρε . 2Bε
Therefore, E[eaε Vt+1 | Ft ] ≤ ρε eaε Vt
on {Vt ≥ θε }.
On the other hand, if Vt < θε , then using (65), Vt+1 ≤ Vt + Bε < θε + Bε ,
33
(67)
and hence eaε Vt+1 ≤ eaε (θε +Bε )
on {Vt < θε }.
(68)
Combining (67) and (68), we obtain E[eaε Vt+1 | Ft ] ≤ ρε eaε Vt + eaε (θε +Bε ) . Let Mt := E[eaε Vt ]. Taking expectations, we get the recursion Mt+1 ≤ ρε Mt + eaε (θε +Bε ) . Since V1 = Z1 = 0, we have M1 = 1. Iterating the recursion yields and using the fact that ρε ≤ 1 Mt ≤ ρεt−1 +
eaε (θε +Bε ) 1 − ρεt−1 aε (θε +Bε ) e ≤1+ . 1 − ρε 1 − ρε
Define bε := e−aε θε
eaε (θε +Bε ) 1+ 1 − ρε
! .
Then, by Markov’s inequality, for every t ∈ [T + 1] and every x ≥ 0, P(Vt ≥ θε + x) = P eaε Vt ≥ eaε (θε +x) ≤ e−aε (θε +x) E[eaε Vt ]
(69)
≤ bε e−aε x . Bound on the maximum.
Applying a union bound over t = 1, . . . , T , from (69) we obtain P max Vs ≥ θε + x ≤ T bε e−aε x . 1≤s≤T
(70)
This is true since the probability of the maximum is equal to probability that at least one Vs is greater than the threshold, i.e. the union. Integrating the bound, we obtain Z ∞ E max Vs = P max Vs ≥ y dy 1≤s≤T 1≤s≤T 0 Z ∞ ≤ θε + min{1, T bε e−aε x } dx. (71) 0
Indeed, for y ≤ θε we use the trivial bound by 1, while for y = θε + x, x ≥ 0, we use Equation 70. Let C := T bε . Since log C log C −aε x −aε x min{1, Ce }≤1 x≤ + Ce 1 x> , aε aε we get Z ∞ Z ∞ log C −aε x min{1, Ce } dx ≤ + Ce−aε x dx log C aε 0 aε
log C 1 = + . aε aε
(72)
Therefore, 1 + log(T bε ) E max Vs ≤ θε + . 1≤s≤T aε 34
(73)
Control at the random time κk,n .
Define the event Ak,n := {κk,n ≤ T } ∩ {Gκk,n }.
On Ak,n we necessarily have κk,n < τbad , and therefore κk,n −1
Vκk,n = Zκk,n − Cr
X
Js .
s=1
Hence, on Ak,n , κk,n −1
Zκk,n = Vκk,n + Cr
X
Js ≤ Vκk,n + Cr
T X
Js .
s=1
s=1
Using the pathwise bound in Equation (53), T X
Js ≤ 2KLε ,
s=1
we deduce that Zκk,n 1{Ak,n } ≤
max Vs + 2Cr KLε 1{Ak,n } ≤ max Vs + 2Cr KLε .
1≤s≤T
1≤s≤T
Finally, by the definition of Zt , rk Qt,k =
√
√ √ rk ( rk Qt,k ) ≤ rk Zt .
Therefore, rk Qκk,n ,k 1{Ak,n } ≤
√
rk Zκk,n 1{Ak,n } √ ≤ rk max Vs + 2Cr KLε . 1≤s≤T
Taking expectations and using (73), we conclude that √ √ E rk Qκk,n ,k 1{κk,n ≤ T } 1{Gκk,n } ≤ rk E max Vs + 2 rk Cr KLε 1≤s≤T √ 1 + log(T bε ) ≤ rk θε + + 2Cr KLε . aε Since θε = O(V ), a−1 ε = O(1), log(T bε ) = O(log T ), and 2Cr KLε = O(K log(T /δ)), this yields √ E rk Qκk,n ,k 1{κk,n ≤ T } 1{Gκk,n } ≤ rk O(V + K log(T /δ)). This proves the lemma.
35
C.4.1
Proof of Proposition 4
Bound of R1µ (T )
On the event Gt , for every k ∈ [K], 0 ≤ µ̄k (t − 1) − µk ≤ 2βkµ (t − 1).
Therefore, R1µ (T ) ≤
# " T X 2 µ E rat Qt,at βat (t − 1)1{Gt } . V
(74)
t=1
We now reorganize the sum by type and service number. Whenever queue k is effectively served at time t, we have t = τk,n for some n ∈ [Nk (T )] (as defined in Equation (62)). Hence, Nk (T ) K X X 2 E rk Qτk,n ,k βkµ (τk,n − 1) 1{Gτk,n } . R1µ (T ) ≤ V n=1
k=1
Extending the sum to n = 1, . . . , T , we get R1µ (T ) ≤
K T 2 XX E rk Qτk,n ,k βkµ (τk,n − 1) 1{τk,n ≤ T } 1{Gτk,n } . V
(75)
k=1 n=1
Now we bound βkµ (τk,n − 1) on the event {τk,n ≤ T }. If n = 1, then Nk (τk,1 − 1) = Nk (0) = 0, hence βkµ (τk,1 − 1) = βkµ (0) = 1. Since log(4KT /δ) ≥ log 4, we have r 1≤2
r log(4KT /δ) log(4KT /δ) =2 . 2 2·1
If n ≥ 2, then on {τk,n ≤ T } we have Nk (τk,n − 1) = n − 1 ≥ 1, so s s log(4K(τ − 1)/δ) log(4KT /δ) k,n ≤ . βkµ (τk,n − 1) = 2(n − 1) 2((n − 1) ∨ 1) Using the elementary inequality 1 2 p ≤√ , n (n − 1) ∨ 1 we deduce that
r βkµ (τk,n − 1) ≤ 2
∀n ≥ 1,
log(4KT /δ) . 2n
Therefore, for every n ∈ [T ], r βkµ (τk,n − 1) ≤ 2
log(4KT /δ) . 2n
Substituting (76) into (75), we obtain r K T 4 log(4KT /δ) X X 1 µ √ E rk Qτk,n ,k 1{τk,n ≤ T } 1{Gτk,n } . R1 (T ) ≤ V 2 n k=1 n=1
36
(76)
We may now apply Lemma 5, which yields √ E rk Qτk,n ,k 1{τk,n ≤ T } 1{Gτk,n } ≤ rk M ε . with M ε := θε +
1 + log(T bε ) + 2Cr KLε aε
(77)
Hence 4 Mε R1µ (T ) ≤
K T log(4KT /δ) X √ X 1 √ rk 2 n n=1 k=1 s ! K X √ 4KT rk T log , δ
r
V
≤
8 Mε V
where we used
k=1
T X √ 1 √ ≤ 2 T. n n=1
Finally, using K X √
√ rk ≤ K rmax ,
k=1
we obtain the simpler bound s √ r M 8K 4KT max ε µ T log . R1 (T ) ≤ V δ This completes the first part of the proof. Bound of R1p (T ) The same reasoning holds in the bound of R1p (T ) as well. On the event Gt , for every k ∈ [K], 0 ≤ p̄k (t − 1) − pk ≤ 2βkp (t − 1, δ). Therefore, " T # X 2 p R1p (T ) ≤ E rXt Qt,Xt ct βX (t − 1)1{Gt } . t V
(78)
t=1
Since the chatbot decision is bang-bang, we have ct ∈ {0, 1}. Thus only the informative slots with ct = 1 contribute to the sum. Whenever Xt = k and ct = 1, we have t = σk,n (as defined in Equation (63)) for some n ∈ [Mk (T )]. Hence, Mk (T ) K X X 2 R1p (T ) ≤ E rk Qσk,n ,k βkp (σk,n − 1) 1{Gσk,n } . V k=1
n=1
Extending the sum to n = 1, . . . , T , we get R1p (T ) ≤
K T 2 XX E rk Qσk,n ,k βkp (σk,n − 1) 1{σk,n ≤ T } 1{Gσk,n } . V k=1 n=1
37
(79)
For bounding βkp (σk,n − 1) on the event {σk,n ≤ T }, we can apply the same exact reasoning used for the bound of βkµ (τk,n − 1) and we get r log(4KT /δ) βkp (σk,n − 1) ≤ 2 . 2n Therefore, for every n ∈ [T ], r log(4KT /δ) p βk (σk,n − 1) ≤ 2 . (80) 2n Substituting (80) into (79), we obtain r K T 4 log(4KT /δ) X X 1 p √ E rk Qσk,n ,k 1{σk,n ≤ T } 1{Gσk,n } . R1 (T ) ≤ V 2 n k=1 n=1
Applying Lemma 5 we get √ E rk Qσk,n ,k 1{σk,n ≤ T } 1{Gσk,n } ≤ rk M ε . with M ε defined in Equation (77). Hence 4 Mε R1p (T ) ≤ V ≤
K T log(4KT /δ) X √ X 1 √ rk 2 n n=1 k=1 s ! K X √ 4KT rk T log , δ
r
8 Mε V
k=1
where we used again T X √ 1 √ ≤ 2 T. n n=1
Using again K X √
√ rk ≤ K rmax ,
k=1
we obtain the bound
s √ 8K r M 4KT max ε p . R1 (T ) ≤ T log V δ
This completes the second part of the proof. Conclusion.
Combining the two bounds, we obtain R1µ (T ), R1p (T ) ≤ CK
Mε p T log(4KT /δ) V
for some constant C > 0. Since M ε = O(V ), it follows that p R1µ (T ), R1p (T ) = O K T log(T /δ) . □
This concludes the proof. 38
C.5
Proof of Theorem 2
Recall from Lemma 2 that RTUCB-DPP ≤ R1µ (T ) + R1p (T ) + R2 (T ) + R3 (T ) + R4 (T ). We first make explicit the constants appearing in the bound on the estimation terms. Recall that √ √ ε rmin Cr = δr + ηε , , δr = 2rmax , ηε = 8 and
√ √ ε rmin Bε = δr + Cr = 2 2rmax + . 8
Moreover, ηε aε = 2 = Bε and
√ ε rmin
√ 2 , √ ε r 8 2 2rmax + 8min
η2 ρε = exp − ε 2 . 2Bε
The constant bε is defined as bε = e−aε θε
eaε (θε +Bε ) 1+ 1 − ρε
! .
Equivalently, bε = e−aε θε + Since θε ≥ 0, we have bε ≤ 1 +
eaε Bε . 1 − ρε
eaε Bε . 1 − ρε
Thus, defining eaε Bε Γε := log 1 + , 1 − ρε we have log bε ≤ Γε . Notice that Γε depends only on ε, rmin , rmax , and is independent of T, V and K. Now recall that ! K X 8 rmax + V λk cεk , θε = √ ε rmin k=1
and
Lε =
32 log(4KT /δ) . ε2
Therefore, M ε = θε +
1 + log(T bε ) + 2Cr KLε aε
39
satisfies the explicit upper bound 32 log(4KT /δ) 1 + log T + Γε + 2Cr K . M ε ≤ θε + aε ε2 Let us denote the right-hand side by 1 + log T + Γε 32 log(4KT /δ) f Mε := θε + + 2Cr K . aε ε2 By Proposition 4, we have 16K R1µ (T ) + R1p (T ) ≤
√ V
rmax f p Mε T log(4KT /δ).
Moreover, R2 (T ) = T P(G T ) ≤ δT 2 , and R3 (T ) =
rmax T . V
Finally, Proposition 3 yields v uK uX R (T ) ≤ t r (M + 2C KL ) + r 4
ε
k
r
ε
max T P(G T ),
k=1
where
K √ 8rmax 8V X 16rmax 1024rmax ε Mε = √ λk ck + √ + 2rmax + √ log . ε rmin ε rmin ε rmin ε2 rmin k=1
We now choose
√ V =
δ = T −2 .
T,
Then log(4KT /δ) = log(4KT 3 ), and Proposition 2 gives P(G T ) ≤ δT = T −1 . Thus R2 (T ) ≤ 1,
rmax T P(G T ) ≤ rmax .
With this choice of parameters, 8 θε = √ ε rmin and fε := √8 M ε rmin
K √ X rmax + T λk cεk k=1
K √ X rmax + T λk cεk
! ,
k=1
!
1 + log T + Γε 32 log(4KT 3 ) + + 2Cr K . aε ε2
40
Combining all the terms, we obtain the explicit bound p √ √ fε log(4KT 3 ) + rmax T + 1 + rmax RTUCB-DPP ≤ 16K rmax M v " √ uK K uX √ 8 T X 8rmax t + + 2rmax rk √ λk cεk + √ ε rmin ε rmin k=1 k=1 # √ √ ε rmin 1024rmax 32 log(4KT 3 ) 16rmax log +2 2rmax + K . + √ ε rmin ε2 rmin 8 ε2 This expression keeps all constants explicit. Since K X
λk cεk ≤
k=1
we have fε = O M
K X
λk = 1,
k=1
√
T + K log(KT ) ,
where the hidden constants depend only on ε, rmin , rmax . Consequently, p RTUCB-DPP = O K T log T , up to constants depending on ε, rmin , rmax .
D
□
Simulations
In this section, we report numerical simulations of the UCB-DPP policy on synthetic instances.
(a) pstrong and µweak
(b) pweak and µstrong
Figure 3: Average cumulative regret of the UCB-DPP policy in two different parameter regimes. The shaded regions correspond to one standard error.
41
Figure 4: Average cumulative regret of the UCB-DPP policy with pmedium and µmedium . The shaded region corresponds to one standard error. We consider a system with K = 5 task classes and a uniform arrival distribution, namely λk = 1/K for all k = 1, . . . , K. The experiments are carried out under three different regimes for the chatbot success probabilities p and the human service rates µ. The first regime corresponds to a strong chatbot and weak human service (Figure 3a), the second to a weak chatbot and strong human service (Figure 5), and the third to an intermediate case in which both components have medium performance (Figure 4). The chatbot success probability vectors are chosen as pstrong = (0.90, 0.85, 0.95, 0.88, 0.92),
pweak = (0.25, 0.30, 0.20, 0.35, 0.28),
and pmedium = (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),
and µ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 y ∗ . The terminal backlog weights r are selected slightly above the corresponding optimal dual multipliers, namely rk = 1.05 · yk∗ ,
k = 1, . . . , K.
This choice is consistent with the condition √ required by the static lower-bound result. The policy parameter is set to V = T and δ = T −2 . In the simulations we use the horizon T = 10000. Each experiment is repeated over 100 independent runs. The curves report the empirical average cumulative regret, computed with respect to the static benchmark value T · OPT(θ). The shaded regions represent one standard error, that is, the empirical standard deviation divided by the square root of the number of runs.
42
Figure 5: Average total backlog of the UCB-DPP policy in the three parameter regimes. P Figure 5 reports the evolution of the average total backlog, defined as K k=1 QT +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 over 100 independent 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-DPP Simulations.
43