regret bounds

Regret measures the price of learning while doing. Imagine an agent that must act in a real environment from day one; every time it picks a suboptimal action it loses a little reward compared with an oracle that knew the optimal policy all along. Regret is the running sum of those losses over T steps. Low regret means the agent loses little even though it had to figure the world out on the fly.

A regret bound is a guarantee that this cumulative shortfall grows slowly with T. The gold standard is sublinear regret, typically of order square-root T, which means average regret per step tends to zero — the agent eventually acts nearly optimally. Bounds also expose the dependence on S, A, the horizon, and any problem structure; the tightest match an information-theoretic lower bound up to logarithmic factors.

Regret and sample complexity are cousins but not the same: regret charges you for every mistake along the way, while PAC-style sample complexity only charges you until you output a good policy. The two convert into each other, but the conversion is never free.