Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize

Neural Information Processing Systems 

However, in most cases, there is a consistent gap between these two types of analyses.