Online learning

Learning through a sequence of decisions and observations, assessing performance by comparison with a benchmark decision or rule. A multi-armed bandit is a model in which only the reward of the selected action is observed.

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.

A decision principle that maximizes possible reward jointly over an action and a parameter in a confidence set. On the event that the set contains the true parameter, the reward predicted for this selected pair is at least the true optimal reward. This inequality bounds pseudoregret by the width of the confidence set in the selected action's direction. For an $L$-Lipschitz continuous reward link and a radius-$\beta$ confidence ellipsoid, Cauchy-Schwarz inequality and the triangle inequality bound that width by $2L\beta \sqrt{x^T{V}^{-1}x}$.

A sequential decision model in which each round selects an action and observes its reward, balancing information gathering against immediate reward. For fixed action means $m(x)$, the pseudoregret compares selected actions with an action maximizing $m$. In models with a link function and parameter $\theta$, rewards may have means $m_{\theta }(x)=\mu (⟨x,\theta ⟩)$.

Let $V_t=V_{t-1}+x_t{x}_t^T$ with positive-definite matrix $V_0$, and suppose $u_t=x_t^T{V}_{t-1}^{-1}{x}_t\le 1$. The matrix determinant lemma gives $\det V_t/\det V_{t-1}=1+u_t$. Since $2\log (1+u)-u$ has nonnegative derivative $(1-u)/(1+u)$ for $0\le u\le 1$, summation proves the displayed bound. In particular, $V_0=\lambda I$, $\lambda \ge 1$, and $\Vert x_t{\Vert }_2\le 1$ ensure $u_t\le 1$. Without that restriction a general form is ${\sum }_t\min \{1,u_t\}\le 2\log (\det V_n/\det V_0)$: for $u\ge 1$, $2\log (1+u)\ge 2\log 2\ge 1$. The bound connects widths of confidence ellipsoids to growth of a determinant.

The cumulative difference between the mean reward of an optimal fixed action and the mean rewards of the selected actions. For adaptive random actions, this sum is itself a random variable; taking its expected value gives expected pseudoregret. Observation noise is absent from the sum, although earlier noise can influence later actions.