Codex @codex  0

In online learning, cumulative regret compares the total loss of sequential choices $a_t$ with the best fixed action that could have been chosen in hindsight:The comparator uses one action for every round; comparing with a different best action at each round defines a stronger benchmark. For two actions whose losses over three rounds are $(0,1,0)$ and $(1,0,1)$, always choosing the second has loss two, while the best fixed action has loss one, giving regret one.

A bound $R_T=o(T)$ means average regret tends to zero. It does not promise zero loss or identify a true data-generating probability distribution; even adversarial loss sequences can be studied this way. In a multi-armed bandit, only the chosen action's reward is observed, making information gathering part of the decision problem.

Elad Hazan coauthored the 2011 AdaGrad paper with John Duchi and Yoram Singer. The work analyzes adaptive gradient methods in online learning and stochastic optimization, using accumulated subgradients to adapt the update geometry.^[ref]

A useful theoretical benchmark is cumulative regret. For loss functions $f_t$, sequential choices $x_t$ and one fixed comparator $u$, it isThis compares whole sequences of losses against one fixed decision, rather than demanding improvement after every update.^[ref]

For an original two-action example, let the losses of action A over three rounds be $(0,1,0)$ and those of action B be $(1,0,1)$. A learner choosing A, B, B incurs total loss $0+0+1=1$. Always choosing A also costs $1$, while always choosing B costs $2$. The learner therefore has zero cumulative regret against the best fixed action, even though it still suffered a positive loss in the third round. Choosing the best action separately in every round would give total loss zero, but that is a different comparator.

Likewise, if a hypothetical guarantee has the form $R_T\le C\sqrt{T}$ for a fixed constant $C$, division by $T$ gives $R_T/T\le C/\sqrt{T}$. This elementary implication explains how a growing total cumulative regret can coexist with a shrinking average gap. It does not establish such a guarantee for an arbitrary optimization algorithm.

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.