Related Work. The work in [1]} shows that PE with modified confidence intervals achieves the optimal regret bound of \(O(d\sqrt{T\log T}+\epsilon \sqrt{d}T)\)  with high probability (matching the \(\Omega (\epsilon \sqrt{d}T)\)  lower bound [1]}) for linear bandits with known \(\epsilon \)  misspecification. If \(\epsilon \)  is unknown, the same algorithm was shown to achieve a regret bound of \(O(d\sqrt{T\log T}+\epsilon \sqrt{d}T\log T)\)  with high probability. The work in [3]}, [1]} proposed variants of LinUCB that achieve a regret bound of \(\tilde{O}(d\sqrt{T}+\epsilon \sqrt{d}T)\)Here \(\tilde{O}\)  hides \(\log \)  factors. with high probability for contextual linear bandits with known \(\epsilon \) . However, changing action sets with unknown \(\epsilon \)  was left as an open problem. The works in [5]}, [6]} made progress in answering this question by providing a regret bound of \(O(d\sqrt{T}\log T+\epsilon \sqrt{d}T)\)  in expectation [6]}. However, improving the \(\log \)  factors in the first term and strengthening the result to a high probability bound was unresolved. Due to the challenge that changing action sets impose on the analysis, the techniques of [6]} cannot be directly extended to provide high probability bounds on the regret. Our result of \(O(d\sqrt{T\log T}+\epsilon \sqrt{d}T\log T)\)  regret removes the \(\sqrt{\log T}\)  factor from the first term and adds a \(\log T\)  factor in the second term; depending on the value of \(\epsilon \)  this can lead to a tighter or looser bound.
