A Proofs

A.1 Proof of Claim 4.1 We first define the notion of restricted minimum eigenvalue. We then bound one-step instantaneous regret. When the number of actions is large or infinite, we will bound it through the following information-theoretic argument. The remaining step is to choose proper policy null π . Then we will bound the following in two steps.