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.

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.