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$ isNo-regret learning seeks a guarantee $R_T=o(T)$, often in expectation for a randomized algorithm, under stated feedback and adversary assumptions. The average excess loss then tends to zero. The comparator is the best 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 distribution; it does not guarantee small absolute loss when every rule predicts badly.