$$c_{i,s}=\sqrt{\frac{1+N_{i,s}}{N_{i,s}^{2}}\left(1+2\log\left(\frac{K(1+N_{i,s})^{1/2}}{\delta}\right)\right)}.$$
$$\left(15\right)$$
7
Modify the UCB Algorithm of Auer et al. (2002) to use the confidence **intervals (14) and change the**
action selection rule accordingly. Hence, at time t**, we choose the action**
$$I_{t}=\operatorname{argmax}\,\bar{X}_{i,t}+c_{i,t}.$$
i
X¯i,t + ci,t. **(15)**
We call this algorithm UCB(δ).

Theorem 6. With probability at least 1−δ, the total regret of the UCB(δ**) algorithm with the action**
selection rule (15) **is constant and is bounded by**

$$R(T)\leq\sum_{i:\Delta_{i}>0}\left(3\Delta_{i}+\frac{16}{\Delta_{i}}\log\frac{2K}{\Delta_{i}\delta}\right).$$

where i∗ **is the index of the optimal action.**
Proof. Suppose the confidence intervals do not fail. If we play action i**, the upper estimate of the** action is above µ
∗**. Hence,**

$$c_{i,s}\geq{\frac{\Delta_{i}}{2}}.$$

Substituting ci,s **and squaring gives**

$\scriptsize4\text{}\text{}2\text{}5$ 3. 
$$\frac{N_{i,s}^{2}-1}{N_{i,s}+1}\leq\frac{N_{i,s}^{2}}{N_{i,s}+1}\leq\frac{4}{\Delta_{i}^{2}}\left(1+2\log\frac{K(1+N_{i,s})^{1/2}}{\delta}\right).$$
By using Lemma 8 of Antos et al. (2010), we get that

$$N_{i,s}\leq3+\frac{16}{\Delta_{i}^{2}}\log\frac{2K}{\Delta_{i}\delta}.$$
$x_{\alpha}R(T)=\sum_{i}x_{i}$. 
Thus, using R(T ) = Pi6=i∗ ∆iNi,T , we get that with probability at least 1 − δ**, the total regret is**
bounded by

$$R(T)\leq\sum_{i:\Delta_{i}>0}\left(3\Delta_{i}+\frac{16}{\Delta_{i}}\log\frac{2K}{\Delta_{i}\delta}\right).$$

Remark 7. **Lai and Robbins (1985) prove that for any suboptimal arm** j,

$$\boxed{\mathrm{~D~}}$$
$$\mathbb{E}\left[N_{i,t}\right]\geq{\frac{\log t}{D(p_{j},p_{*})}},$$

where, p∗ and pj are the reward density of the optimal arm and arm j respectively, and D **is the**
KD-divergence. This lower bound does not contradict Theorem 6, as Theorem 6 only states a high probability upper bound for the regret. Note that UCB(δ**) takes delta as its input. Because with** probability δ, the regret in time t can be t**, on expectation, the algorithm might have a regret of** tδ. Now if we select δ = 1/t, then we get O(log t**) upper bound on the expected regret.**

## 5 Application To Least Squares Estimation And Linear Bandit **Problem**

In this section we first apply Theorem 3 to derive confidence intervals for least-squares estimation, where the covariate process is an arbitrary process and then use **these confidence intervals to improve**
the regret bound of Dani et al. (2008) for the linear bandit problem. In particular, our assumption on the data is as follows:
Assumption A1 Let (Fi) be a filtration, (x1, y1), . . ., (xt, yt**) be a sequence of random variables**
over R
d × R such that xiis Fi-measurable, and yiis Fi+1-measurable (i = 1, 2, . . .**). Assume that**
there exists θ∗ ∈ R
dsuch that E[yi|Fi] = x
⊤ i θ∗**, i.e.,** εi = yi − x
⊤ i θ∗ **is a martingale difference**
sequence (E[εi|Fi] = 0, i = 1, 2, . . .) and that εiis sub-Gaussian: There exists R > **0 such that for**
any γ ∈ R,E[exp(γεi)|Fi−1] ≤ **exp(**γ 2R
2/2).