concentration bounds

When you estimate a value by averaging a finite number of noisy samples, how far can your estimate stray from the truth? Concentration bounds answer that with high-probability tail guarantees: they say the average sits within a shrinking window of the mean except on a tiny-probability bad event. They are the statistical glue that turns "we collected n samples" into "our value estimate is accurate to within ε."

Hoeffding's and Bernstein's inequalities are the workhorses; the error typically shrinks like one over the square root of the sample count, with Bernstein tightening this when the variance is small. In RL these bounds are applied per state-action pair to control reward and transition estimates, then propagated through the Bellman equation. A union bound over all S×A pairs adds a logarithmic price, which is why sample-complexity results carry log(SA/δ) factors.

Naively bounding each value independently and summing can be loose; modern analyses use variance-aware (Bernstein-style) and total-variance arguments to avoid paying the horizon factor multiple times, which is how the tightest horizon dependence is recovered.