Related Work.
Due to its practical significance, a number of works have examined this setup [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}.
To the best of our knowledge, the best known regret bound is \(O(\sqrt{dsT}\log T)\)  with high probability [2]}.
While this is shown to be nearly optimal [11]}, improving the \(\log T\)  factor was left as an open problem. Our work resolves this.
