No-regret learning
= No-regret learning
In <online learning>, a learner chooses $a_t$ before observing the round's <loss function> $\ell_t$. Its external <cumulative regret> against a fixed action set $A$ is
$$
R_T=\sum_{t=1}^T\ell_t(a_t)-\min_{a\in A}\sum_{t=1}^T\ell_t(a).
$$
<No-regret learning> seeks a guarantee $R_T=o(T)$, often in <expected value>[expectation] for a <randomized algorithm>, under stated feedback and adversary assumptions. The average excess loss then tends to zero. The comparator is the best \i[single] action in hindsight; it does not choose the best action separately on every round.
For example, against two prediction rules, an exponential-weights learner starts with equal weights and multiplies rule $i$'s weight by $\exp(-\eta\ell_t(i))$ after seeing all rule losses. Sampling in proportion to the weights gradually shifts <probability> toward better rules. For losses in $[0,1]$, an appropriate learning rate gives an order-$\sqrt T$ expected bound for this fixed two-rule setting. This compares performance even without independent observations from one fixed <probability distribution>[distribution]; it does not guarantee small absolute loss when every rule predicts badly.