Learning unknown service rates in queues: a multiarmed bandit approach
From MaRDI portal
(Redirected from Publication:4994160)
Abstract: Consider a queueing system consisting of multiple servers. Jobs arrive over time and enter a queue for service; the goal is to minimize the size of this queue. At each opportunity for service, at most one server can be chosen, and at most one job can be served. Service is successful with a probability (the service probability) that is a priori unknown for each server. An algorithm that knows the service probabilities (the "genie") can always choose the server of highest service probability. We study algorithms that learn the unknown service probabilities. Our goal is to minimize queue-regret: the (expected) difference between the queue-lengths obtained by the algorithm, and those obtained by the "genie." Since queue-regret cannot be larger than classical regret, results for the standard multi-armed bandit problem give algorithms for which queue-regret increases no more than logarithmically in time. Our paper shows surprisingly more complex behavior. In particular, as long as the bandit algorithm's queues have relatively long regenerative cycles, queue-regret is similar to cumulative regret, and scales (essentially) logarithmically. However, we show that this "early stage" of the queueing bandit eventually gives way to a "late stage", where the optimal queue-regret scaling is . We demonstrate an algorithm that (order-wise) achieves this asymptotic queue-regret in the late stage. Our results are developed in a more general model that allows for multiple job classes as well.
Recommendations
Cites work
- Admission and routing of soft real-time jobs to multiclusters: design and comparison of index policies
- Asymptotically efficient adaptive allocation rules
- Batched bandit problems
- Combinatorial bandits
- Communication networks. An optimization, control and stochastic networks perspective
- Dynamic priority allocation via restless bandit marginal productivity indices
- Dynamic scheduling with convex delay costs: The generalized \(c\mu\) rule
- Exploration-exploitation tradeoff using variance estimates in multi-armed bandits
- Finite-time analysis of the multiarmed bandit problem
- Heavy Traffic Limit Theorems for Queues: A Survey
- scientific article; zbMATH DE number 4087408 (Why is no real title available?)
- scientific article; zbMATH DE number 3638998 (Why is no real title available?)
- Lower bounds and selectivity of weak-consistent policies in stochastic multi-armed bandit problem
- Marginal productivity index policies for scheduling a multiclass delay-/loss-sensitive queue
- Multi-armed bandit allocation indices. With a foreword by Peter Whittle.
- Near-optimal regret bounds for reinforcement learning
- On the optimality of an index rule in multichannel allocation for single-hop mobile networks with multiple service classes
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems
- Regret bounds for restless Markov bandits
- Scheduling of multi-class multi-server queueing systems with abandonments
- The cμ rule revisited
- Thompson sampling: an asymptotically optimal finite-time analysis
Cited in
(2)
This page was built for publication: Learning unknown service rates in queues: a multiarmed bandit approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4994160)
