Abstract

In this talk we will first consider the mixing bandit problem, namely a sequential learning problem over weakly dependent data. For solving optimally this problem, it is important to understand tightly the concentration of weakly dependent processes. With this motivation in mind, I will then present a tight Azuma-Hoeffding-type inequality for partial sums of discrete processes in dimension 1, satisfying a weak dependency assumption of projective type - namely that the conditional expectation given the past of the process at a distance more than u is bounded by a known decreasing function of u. The proof is based on a smart multi-scale approximation of random sums by martingale difference sequences, which was first introduced in [Peligrad, Utev and Wu, 2007]. Based on this, a natural question is on whether this type of results and proof techniques can be extended to weakly dependent random fields in dimension d. I will then present Azuma-Hoeffding and Burkholder-type inequalities for partial sums over a rectangular grid of a random field satisfying a weak dependency assumption of projective type. The analysis is also based on multi-scale approximation of random sums by martingale difference sequences, but a careful decomposition of the d dimensional rectangular grid is essential here in order to obtain tight results.