Corruption-Robust Contextual Search through Density Updates
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 $\eps$-ball loss, we give a tight
regret bound of $O(C + d \log(1/\eps))$ improving over the $O(d^3 \log(1/\eps))
\log^2(T) + C \log(T) \log(1/\eps))$ bound of Krishnamurthy et al (STOC21). For
the symmetric loss, we give an efficient algorithm with regret $O(C+d \log T)$.
  Our techniques are a significant departure from prior approaches.
Specifically, we keep track of density functions over the candidate vectors
instead of a knowledge set consisting of the candidate vectors consistent with
the feedback obtained.