[edit]
Corruption-Robust Contextual Search through Density Updates
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:3504-3505, 2022.
Abstract
We study the problem of contextual search in the adversarial noise model. Let d be the dimension of the problem, T be the time horizon and C be the total amount of noise in the system. For the ϵ-ball loss, we give a tight regret bound of O(C+dlog(1/ϵ)) improving over the O(d3log(1/ϵ))log2(T)+Clog(T)log(1/ϵ)) bound of Krishnamurthy et al (STOC’21). For the symmetric loss, we give an efficient algorithm with regret O(C+dlogT). In terms of techniques, our algorithms are a departure from previous contextual search models in the sense that they keep track of density functions over the candidate vectors instead of a knowledge set consisting of the candidate vectors consistent with the feedback obtained.