# Online Least Squares Estimation With Self-Normalized Processes: An Application To Bandit Problems∗

Yasin Abbasi-Yadkori abbasiya@cs.ualberta.ca Dept. of Computing Science University of Alberta D´avid P´al dpal@cs.ualberta.ca Dept. of Computing Science University of Alberta Csaba Szepesv´ari szepesva@cs.ualberta.ca Dept. of Computing Science University of Alberta

## Abstract

The analysis of online least squares estimation is at the heart of many **stochastic sequential** decision-making problems. We employ tools from the self-normalized processes to provide a simple and self-contained proof of a tail bound of a vector-valued **martingale. We use the**
bound to construct new tighter confidence sets for the least squares estimate. We apply the confidence sets to several online decision problems, such as the multi-armed and the linearly parametrized bandit problems. The confidence sets are potentially applicable to other problems such as sleeping bandits, generalized linear **bandits, and other**
linear control problems. We improve the regret bound of the Upper Confidence Bound (UCB) **algorithm of Auer et al.**
(2002) and show that its regret is with high-probability a problem dependent constant. In the case of linear bandits (Dani et al., 2008), we improve the problem **dependent bound in**
the dimension and number of time steps. Furthermore, as opposed **to the previous result,** we prove that our bound holds for small sample sizes, and at the same time the worst case bound is improved by a logarithmic factor and the constant is improved.

## 1 Introduction

The least squares method forms a cornerstone of statistics and machine learning. It is used as the main component of many stochastic sequential decision problems, such as multi-armed bandit, linear bandits, and other linear control problems. However, the analysis of least squares in these online settings is non-trivial because of the correlations between data points. Fortunately, there is a connection between online least squares estimation and the area of self-normalized processes. Study of self-normalized processes has a long history that goes back to Student and is treated in detail in recent book by de la Pe˜na et al. (2009). Using these tools we provide a proof of a bound on the deviation for vector-valued martingales. A less general version of the bound can be found already in de la Pe˜na et al. (2004, 2009). Additionally our proof, based on the method of mixtures, is new, simpler and self-contained. The bound improves the previous bound of Rusmevichientong and Tsitsiklis (2010) and it is applicable to virtually **any online least squares**
problem.

The bound that we derive, gives immediately rise to tight confidence sets for the online least squares estimate that can replace the confidence sets in existing algorithms. In particular, the confidence sets can be used in the UCB algorithm for the multi-armed **bandit problem, the** ConfidenceBall **algorithm of Dani et al. (2008) for the linear bandit problem, and** LinRel **algorithm**
of Auer (2003) for the associative reinforcement learning problem. We show that this leads to improved performance of these algorithms. Our hope is that the new **confidence sets can be used to**
improve the performance of other similar linear decision problems.

The multi-armed bandit problem, introduced by Robbins (1952), is a game between the learner and the environment. At each time step, the learner chooses one of K **actions and receives a reward** which is generated independently at random from a fixed distribution **associated with the chosen**
arm. The objective of the learner is to maximize his total reward. The performance of the learner is evaluated by the regret, which is defined as the difference between his total reward and the total
∗
Submitted to the 24th Annual Conference on Learning Theory (COLT 2011)