What are regret bounds?
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.