Research map / Bandits and online learning / RL theory and MDPs
Reinforcement Learning and Regret Bounds for Admission Control
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes UCRL-AC, a UCRL2-inspired episodic regret-minimizing algorithm for multi-class admission control in M/M/c/S queues, with regret O(S log T + sqrt(mT log T)) and no diameter dependence in the infinite-server case.
Problem
Regret minimization for admission control in multi-class M/M/c/S queues with unknown arrival rates, where generic RL regret bounds depend on the MDP diameter, which is exponential in the buffer size.
Approach
Exploits the birth-and-death structure and threshold/bias properties of optimal admission policies: optimistic CTMDP via truncated empirical mean of arrival rate and L1-confidence on class probabilities, solved with policy iteration using closed-form bias computation, giving regret independent of the diameter.
Key results
- Regret upper bound O(S log T + sqrt(mT log T)) for finite servers; dependence on S vanishes in the infinite-server case.
- Theoretical upper bound is reported as an order of magnitude lower than UCRL2 and UCRL3 in the studied setting.
- Empirical regret of UCRL-AC is lower than UCRL2, PSRL, KL-UCRL and UCRL3 especially as queue size S grows, though PSRL is better early for S=20, mu=0.3.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use UCRL-AC instead of UCRL2, PSRL, KL-UCRL, or UCRL3 | Admission control with two job classes and five servers · Overloaded, balanced, and under-loaded regimes; S in {20, 50} | empirical regret | Helped |
| Use UCRL-AC instead of UCRL2 or UCRL3 | Admission control · Theoretical upper-bound comparison | regret upper bound | Helped |
| Use PI instead of VI (ablation) | UCRL-AC · Admission control experiments | empirical regret | No clear effect |
| Use UCRL-AC instead of PSRL | Admission control with S=20 and μ=0.3 · Early learning | empirical regret | Hurt |
| Use Policy Iteration instead of Value Iteration (ablation) | UCRL-AC · Admission control, finite servers | expected regret upper bound | Mixed |
Surprising findings
- PI and VI produced exactly the same regrets in the experiments.
- PSRL has smaller regret than UCRL-AC at the beginning in the S=20, mu=0.3 setting, attributed to overestimation of the arrival rate.
Limitations
- Assumes known service rate, number of servers, and class rewards/holding costs; only arrival rates are learned.
- Estimator is reset each episode, discarding past arrival data; the regret bound for non-stationary or state-dependent extensions would gain a sqrt(S) factor.
Experimental setup
Benchmarks: M/M/c/S admission control simulation (buffers 20 and 50, 5 servers, 2 classes)
Metrics: expected cumulative regret theoretical regret upper bound
Baselines: UCRL2 PSRL KL-UCRL UCRL3 Zhang and Ji algorithm
Builds on: UCRL2 Feinberg and Yang trunk reservation results Miller policy iteration Bubeck truncated empirical mean
Closest papers by meaning
- Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space (NeurIPS 2022 · similarity 0.90)
- Regret Bounds for Learning State Representations in Reinforcement Learning (NeurIPS 2019 · similarity 0.89)
- Position: Constants are Critical in Regret Bounds for Reinforcement Learning (ICML 2025 · similarity 0.87)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.87)
- Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.86)
- Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.