Regret: Definition and Examples

Regret is the gap between the reward a learning agent actually collects and the reward it would have collected by always taking the best action from the start. It is the standard yardstick for exploration strategies: the faster regret stops growing, the more efficiently the agent has learned.

Definition

In a multi-armed bandit with arm means $μ_{a}$ and best mean $μ^{*} = max_{a} μ_{a}$ , the expected regret after $T$ rounds is

R_{T} = T μ^{*} - E [t = 1 \sum T μ_{A_{t}}] = a \sum Δ_{a} E [N_{a} (T)],

where $Δ_{a} = μ^{*} - μ_{a}$ is arm $a$ 's gap and $N_{a} (T)$ the number of times it was pulled. The second form says regret is just "how often you pulled each bad arm, times how bad it is".

How fast regret grows

Linear regret, $R_{T} \propto T$ , means the agent never stops making mistakes at a constant rate. Pure greedy and fixed- $ϵ$ epsilon-greedy are linear.
Logarithmic regret, $R_{T} = O (lo g T)$ , is achieved by UCB and Thompson sampling. Lai and Robbins proved that no reasonable algorithm can do better: each suboptimal arm must be pulled on the order of $lo g T$ times, with a constant set by how hard it is to tell that arm from the best.
Worst-case regret over all problems with $K$ arms is of order $K T$ , because gaps can be arbitrarily small.

Worked example

Two Bernoulli arms pay off with probability 0.6 and 0.5, so $Δ = 0.1$ . Epsilon-greedy with $ϵ = 0.1$ picks uniformly at random on 10% of rounds, so even with perfect estimates it pulls the bad arm on 5% of rounds: regret $0.05 \times 0.1 \times T$ . The Lai and Robbins rate for this pair is about $ln T / KL (0.5 ∥ 0.6)$ bad pulls, with $KL \approx 0.0204$ . At $T = 10, 000$ the two are similar (regret about 50 versus 45). At $T = 1, 000, 000$ epsilon-greedy has lost 5,000 while an asymptotically optimal method has lost about 68. Logarithmic regret is a statement about the long run.

Beyond bandits

In episodic MDPs, regret compares the agent's total return over $K$ episodes with $K$ times the optimal value. Online learning uses the same word for a different comparison: loss relative to the best fixed decision in hindsight, often against adversarially chosen data.

Why it matters

Regret measures the cost of learning while acting, which is the real cost when every decision affects a user, patient or system. Cumulative reward alone hides this: two agents can end with the same final policy while one paid far more for its exploration along the way. Regret bounds are also a clean way to compare exploration strategies on equal terms.

Sources

T. L. Lai, Herbert Robbins. Asymptotically efficient adaptive allocation rules, 1985. doi.org
Tor Lattimore, Csaba Szepesvári. Bandit Algorithms, 2020. tor-lattimore.com