Before revision:  Finally, we extend these results to a \tilde{O} noisy feedback model, where each round our feedback is flipped with  fixed probability p < 1/2.
After revision:  Finally, we extend these results to a \tilde{O}(s^2) regret algorithm for linear contextual search if the linear function is guaranteed to be s-sparse. Finally we also extend our results to the noisy feedback model, where each round our feedback is flipped with fixed probability p < 1/2.