2024/07/16 by Spencer Hutchinson, Hutchinson, Spencer, Mahnoosh Alizadeh +1
Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Advanced Wireless Network Optimization #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Smart Parking Systems Research
paper · pdf · doi:10.48550/arxiv.2407.11471
openalex publication_date 2024/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Motivated by the stringent safety requirements that are often present in real-world applications, we study a safe online convex optimization setting where the player needs to simultaneously achieve sublinear regret and zero constraint violation while only using zero-order information. In particular, we consider a multi-point feedback setting, where the player chooses d + 1 points in each round (where d is the problem dimension) and then receives the value of the constraint function and cost function at each of these points. To address this problem, we propose an algorithm that leverages forward-difference gradient estimation as well as optimistic and pessimistic action sets to achieve O(d √(T)) regret and zero constraint violation under the assumption that the constraint function is smooth and strongly convex. We then perform a numerical study to investigate the impacts of the unknown constraint and zero-order feedback on empirical performance.