What are regret bounds? I searched for the term and it appears in a few articles but it is used without explanation. The only explanation I could find is in a PhD thesis: "Regret bounds are the common thread in the analysis of online learning algorithms. A regret bound measures the performance of an online algorithm relative to the performance of a competing prediction mechanism, called a competing hypothesis." 

I am still confused after reading this (I did not read the rest of the thesis as it is way above my understanding in that field). Could someone please explain? Many thanks in advance!
Reinforcement Learning models are often measured relative to each other and sometimes relative to optimal behavior.

Regret is a common measure of performance for Reinforcement Learning systems.

Reinforcement Learning model performance is stochastic. Thus, is better to run the same model many times to estimate the distribution for performance. From that distribution, bounds can be estimated. Those bounds are similar to confidence intervals for scalar parameter estimates.