Dependencies

A sequential, stochastic algorithm with actions in a measurable space \(\mathcal{A}\) and observations in a measurable space \(\mathcal{R}\) is described by the following data:

• for all \(t \in \mathbb {N}\), a policy \(\pi _t : (\mathcal{A} \times \mathcal{R})^{t+1} \rightsquigarrow \mathcal{A}\), a Markov kernel which gives the distribution of the action of the algorithm at time \(t+1\) given the history of previous pulls and observations,

• \(P_0 \in \mathcal{P}(\mathcal{A})\), a probability measure that gives the distribution of the first action.

For \(t \in \mathbb {N}\), we denote by \(A_t\) the arm pulled at time \(t\) and by \(X_t\) the reward received at time \(t\). Formally, these are measurable functions on \(\Omega = (\mathcal{A} \times \mathbb {R})^{\mathbb {N}} \times \mathbb {R}^{\mathbb {N} \times \mathcal{A}}\), defined by \(A_t(\omega ) = \omega _{1,t,1}\) and \(X_t(\omega ) = \omega _{1,t,2}\). We denote by \(H_t \in (\mathcal{A} \times \mathbb {R})^{t+1}\) the history of pulls and rewards up to and including time \(t\), that is \(H_t = ((A_0, X_0), \ldots , (A_t, X_t))\). Formally, \(H_t(\omega ) = (\omega _{1,0}, \ldots , \omega _{1,t})\).

For an arm \(a \in \mathcal{A}\), we denote by \(\mu _a\) the mean of the rewards for that arm, that is \(\mu _a = \nu (a)[X]\). We denote by \(\mu ^*\) the mean of the best arm, that is \(\mu ^* = \max _{a \in \mathcal{A}} \mu _a\).

A stochastic bandit is simply a reward distribution for each arm: a Markov kernel \(\nu : \mathcal{A} \rightsquigarrow \mathbb {R}\), conditional distribution of the rewards given the arm pulled.

By an application of the Ionescu-Tulcea theorem, an algorithm \((\pi , P_0)\) and bandit \(\nu \) together defines a probability distribution \(\mathbb {P}_B\) on the space \(\Omega _B := (\mathcal{A} \times \mathbb {R})^{\mathbb {N}}\), the space of infinite sequences of arms and rewards. We augment that probability space with a stream of rewards from each arm, independent of the bandit interaction, to get the probability space \((\Omega , \mathbb {P})\), where \(\Omega = \Omega _B \times \mathbb {R}^{\mathbb {N} \times \mathcal{A}}\) and \(\mathbb {P} = \mathbb {P}_B \otimes (\bigotimes _{n \in \mathbb {N}, a \in \mathcal{A}} \nu (a))\).

TODO: explain how the probability distribution \(\mathbb {P}_B\) is constructed.

The filtration \(\mathcal{F}_B\) on \(\Omega _B\) generated by the history of pulls and rewards is the increasing family of \(\sigma \)-algebras \(\mathcal{F}_{B,t} = \sigma (H_0, \ldots , H_t)\), for \(t \in \mathbb {N}\).

An environment with which an algorithm interacts is described by the following data:

• for all \(t \in \mathbb {N}\), a feedback \(\nu _t : (\mathcal{A} \times \mathcal{R})^{t+1} \times \mathcal{A} \rightsquigarrow \mathcal{R}\), a Markov kernel which gives the distribution of the observation at time \(t+1\) given the history of previous pulls and observations, and the action of the algorithm at time \(t+1\),

• \(\nu '_0 \in \mathcal{A} \rightsquigarrow \mathcal{R}\), a Markov kernel that gives the distribution of the first observation given the first action.

The Explore-Then-Commit (ETC) algorithm with parameter \(m \in \mathbb {N}\) is defined as follows:

1. for \(t {\lt} Km\), \(A_t = t \mod K\) (pull each arm \(m\) times),

2. compute \(\hat{A}_m^* = \arg \max _{a \in [K]} \hat{\mu }_a\), where \(\hat{\mu }_a = \frac{1}{m} \sum _{t=0}^{Km-1} \mathbb {I}(A_t = a) X_t\) is the empirical mean of the rewards for arm \(a\),

3. for \(t \ge Km\), \(A_t = \hat{A}_m^*\) (pull the empirical best arm).

For an arm \(a \in \mathcal{A}\), its gap is defined as the difference between the mean of the best arm and the mean of that arm: \(\Delta _a = \mu ^* - \mu _a\).

For \(t \in \mathbb {N}\), we denote by \(X_t \in \Omega _t\) the random variable describing the time step \(t\), and by \(H_t \in \prod _{s=0}^t \Omega _s\) the history up to time \(t\). Formally, these are measurable functions on \(\Omega _{\mathcal{T}}\), defined by \(X_t(\omega ) = \omega _t\) and \(H_t(\omega ) = (\omega _1, \ldots , \omega _t)\).

For an arm \(a \in \mathcal{A}\) and a time \(t \in \mathbb {N}\), we denote by \(N_{t,a}\) the number of times that arm \(a\) has been pulled before time \(t\), that is \(N_{t,a} = \sum _{s=0}^{t-1} \mathbb {I}\{ A_s = a\} \).

The regret \(R_T\) of a sequence of arms \(A_0, \ldots , A_{T-1}\) after \(T\) pulls is the difference between the cumulative reward of always playing the best arm and the cumulative reward of the sequence:

For \(a \in \mathcal{A}\) and \(n \in \mathbb {N}\), let \(Z_{n,a} \sim \nu (a)\), independent of the bandit interaction and other \(Z_{m,b}\). In our probability space \(\Omega \), we can take for \(Z_{n,a}\) the function \(\omega \mapsto \omega _{2,n,a}\). We define \(Y_{n, a} = X_{T_{n,a}} \mathbb {I}\{ T_{n, a} {\lt} \infty \} + Z_{n,a} \mathbb {I}\{ T_{n, a} = \infty \} \), the reward received when pulling arm \(a\) for the \(n\)-th time if that time is finite, and equal to \(Z_{n,a}\) otherwise.

For an arm \(a \in \mathcal{A}\) and a time \(n \in \mathbb {N}\), we denote by \(T_{n,a}\) the time at which arm \(a\) was pulled for the \(n\)-th time, that is \(T_{n,a} = \min \{ s \in \mathbb {N} \mid N_{s+1,a} = n\} \). Note that \(T_{n, a}\) can be infinite if the arm is not pulled \(n\) times.

A real valued random variable \(X\) is \(\sigma ^2\)-sub-Gaussian if for any \(\lambda \in \mathbb {R}\),

For \(\mu \in \mathcal{P}(\Omega _0)\), we call trajectory measure the probability measure \(\xi _0 \circ \mu \) on \(\Omega _{\mathcal{T}} := \prod _{i=0}^{\infty } \Omega _i\). We denote it by \(P_{\mathcal{T}}\). The \(\mathcal{T}\) subscript stands for “trajectory”.

Seen as processes defined on \(\Omega _B\), the processes \((H_t)_{t \in \mathbb {N}}\), \((A_t)_{t \in \mathbb {N}}\), and \((X_t)_{t \in \mathbb {N}}\) are adapted to the filtration \(\mathcal{F}_B\).

For any \(t \in \mathbb {N}\), the conditional distribution \(P_{\mathcal{T}}\left[A_{t+1} \mid H_t\right]\) is \(((H_t)_* P_{\mathcal{T}})\)-almost surely equal to \(\pi _t\).

The conditional distribution of the arm \(A_{t+1}\) given the history \(H_t\) in the bandit probability space \((\Omega , \mathbb {P})\) is \(\pi _t(H_t)\).

For any \(t \in \mathbb {N}\), the conditional distribution \(P_{\mathcal{T}}\left[R_{t+1} \mid H_t, A_{t+1}\right]\) is \(((H_t, A_{t+1})_* P_{\mathcal{T}})\)-almost surely equal to \(\nu _t\).

The conditional distribution \(P_{\mathcal{T}}\left[R_0 \mid A_0\right]\) is \((A_{0*} P_{\mathcal{T}})\)-almost surely equal to \(\nu '_0\).

The conditional distribution of the reward \(X_t\) given the arm \(A_t\) in the bandit probability space \((\Omega , \mathbb {P})\) is \(\nu (A_t)\).

For any \(t \in \mathbb {N}\), the conditional distribution \(P_{\mathcal{T}}\left[X_{t+1} \mid H_t\right]\) is \(((H_t)_* P_{\mathcal{T}})\)-almost surely equal to \(\kappa _t\).

For \(n {\gt} 0\) and \(a \in \mathcal{A}\), the law of \(Y_{n,a}\) is \(\nu (a)\).

For \(X\) a \(\sigma ^2\)-sub-Gaussian random variable, for any \(t \ge 0\),

The rewards \((Y_{n,a})_{n \in \mathbb {N}}\) are independent.

For \(a \in \mathcal{A}\), let \(Y^{(a)} = (Y_{n,a})_{n \in \mathbb {N}} \in \mathbb {R}^{\mathbb {N}}\) be the sequence of rewards obtained from pulling arm \(a\). Then the sequences \((Y^{(a)})_{a \in \mathcal{A}}\) are independent.

\(T_{n,a}\) is a stopping time for the filtration generated by the history of pulls and rewards.

The law of \(A_0\) under \(P_{\mathcal{T}}\) is \(\alpha _0\).

The law of the arm \(A_0\) in the bandit probability space \((\Omega , \mathbb {P})\) is \(P_0\).

The law of \(X_0\) under \(P_{\mathcal{T}}\) is \(\mu \).

Let \(a \in \mathcal{A}\). Seen as a process defined on \(\Omega _B\), \((N_{t,a})_{t \in \mathbb {N}}\) is predictable with respect to the filtration \(\mathcal{F}_B\) (that is, \((N_{t,a})_{t \in \mathbb {N}}\) is adapted to \((\mathcal{F}_{B, t-1})_{t \in \mathbb {N}}\)).

Suppose that \(\nu (a)\) is 1-sub-Gaussian for all arms \(a \in [K]\). Then for the Explore-Then-Commit algorithm with parameter \(m\), for any arm \(a \in [K]\) with \(\Delta _a {\gt} 0\), we have \(\mathbb {P}(\hat{A}_m^* = a) \le \exp \left(- \frac{m \Delta _a^2}{4}\right)\).

For the Explore-Then-Commit algorithm with parameter \(m\), for any arm \(a \in [K]\) and any time \(t \ge Km\), we have

For \(\mathcal{A}\) finite, the regret \(R_T\) can be expressed as a sum over the arms and their gaps:

\(Y_{N_{t+1, A_t}, A_t} = X_t\) for all \(t \in \mathbb {N}\) and \(a \in \mathcal{A}\).

\(T_{N_{t+1, A_t}, A_t} = t\) for all \(t \in \mathbb {N}\).

\(T_{N_{t+1, a}, a} \le t {\lt} \infty \) for all \(t \in \mathbb {N}\) and \(a \in \mathcal{A}\).

If \(X\) is \(\sigma _1^2\)-sub-Gaussian and \(Y\) is \(\sigma _2^2\)-sub-Gaussian, and \(X\) and \(Y\) are independent, then \(X + Y\) is \((\sigma _1^2 + \sigma _2^2)\)-sub-Gaussian.

Let \(X_1, \ldots , X_n\) be independent random variables such that \(X_i\) is \(\sigma _i^2\)-sub-Gaussian for \(i \in [n]\). Then for any \(t \ge 0\),

Let \((\Omega _t)_{t \in \mathbb {N}}\) be a family of measurable spaces. Let \((\kappa _t)_{t \in \mathbb {N}}\) be a family of Markov kernels such that for any \(t\), \(\kappa _t\) is a kernel from \(\prod _{i=0}^t \Omega _{i}\) to \(\Omega _{t+1}\). Then there exists a unique Markov kernel \(\xi : \Omega _0 \rightsquigarrow \prod _{i = 1}^{\infty } \Omega _{i}\) such that for any \(n \ge 1\), \(\pi _{[1,n]*} \xi = \kappa _0 \otimes \ldots \otimes \kappa _{n-1}\). Here \(\pi _{[1,n]} : \prod _{i=1}^{\infty } \Omega _i \to \prod _{i=1}^n \Omega _i\) is the projection on the first \(n\) coordinates.

Suppose that \(\nu (a)\) is 1-sub-Gaussian for all arms \(a \in [K]\). Then for the Explore-Then-Commit algorithm with parameter \(m\), the expected regret after \(T\) pulls with \(T \ge Km\) is bounded by