Multi-armed bandit

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.