2024/12/05 by Shanqi Liu, Xin Liu, Liu, Shanqi +1
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Optimization and Search Problems #Smart Parking Systems Research
paper · pdf · doi:10.48550/arxiv.2412.03983
openalex publication_date 2024/12/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies online convex optimization with unknown linear budget constraints, where only the gradient information of the objective and the bandit feedback of constraint functions are observed. We propose a safe and efficient Lyapunov-optimization algorithm (SELO) that can achieve an O(√(T)) regret and zero cumulative constraint violation. The result also implies SELO achieves O(√(T)) regret when the budget is hard and not allowed to be violated. The proposed algorithm is computationally efficient as it resembles a primal-dual algorithm where the primal problem is an unconstrained, strongly convex and smooth problem, and the dual problem has a simple gradient-type update. The algorithm and theory are further justified in a simulated application of energy-efficient task processing in distributed data centers.