Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems

Details Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems

2011-02-14

arxiv.org/abs/1102.2670v1

Computer Science

Artificial Intelligence

Submitted to the 24th Annual Conference on Learning Theory (COLT 2011)

Scientific paper

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 a 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.

Affiliated with

Also associated with

No associations

Rating

Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-215055