The Generalized Likelihood Ratio Test meets klUCB: an Improved Algorithm for Piece-Wise Non-Stationary Bandits

Multi-Armed Bandit (MAB) problems form a well-studied class of sequential decision making problems, in which an agent repeatedly chooses an action $I_t\in \{1,\dots ,K\}$ or “arm” –in reference to the arm of a one-armed bandit– among a set of $K$ arms. In the most standard version of the stochastic bandit model, each arm $i$ is associated with an i.i.d. sequence of rewards $\left(r_{i,t}\right)$ that follow some distribution of mean ${\mu }_i$. Upon selecting arm $I_t$, the agent receives the reward $r_{I_t,t}$ associated to the chosen arm, and her goal is to adopt a sequential sampling strategy that maximize the expected sum of these rewards. This is equivalent to minimizing the regret, defined as the difference between the total reward of the oracle strategy always selecting the arm with largest mean, ${\mu }^{\ast }$, and that of our strategy: $R_T=\text{E}\left[{\sum }_{t=1}^T\right({\mu }^{\ast }-{\mu }_{I_t}\left)\right]$.

Regret minimization in stochastic bandits has been extensively studied since the works of [H. Robbins (1952)] and [T. L. Lai and H. Robbins (1985)], and several algorithms with a $\left(\log \right(T\left)\right)$ problem-dependent regret upper bound have been proposed (see, e.g., [T. Lattimore and C. Szepesvári (2019)] for a survey). Among those, the klUCB algorithm (Cappé et al., 2013) has been shown to be asymptotically optimal for Bernoulli distributions (in that it exactly matches the lower bound given by Lai and Robbins (1985)) and can also be employed when the rewards are assumed to be bounded in $[0,1]$. Problem-independent upper bounds of the form $R_T=\Omega \left(\sqrt{KT}\right)$ (with no hidden constant depending on the arms distributions) have also been established for stochastic algorithms, like MOSS, or klUCB-Switch by Garivier et al. (2018), while klUCB is known to enjoy a sub-optimal $\left(\sqrt{KT\ln \left(T\right)}\right)$ problem-independent regret.

Stochastic bandits were historically introduced as a simple model for clinical trials, where arms correspond to some treatments with unknown efficacy (Thompson, 1933). More recently, MAB models have been proved useful for different applications, like cognitive radio, where arms can model the vacancy of radio channels, or parameters of a dynamically configurable radio hardware (Maghsudi and Hossain, 2016; Bonnefoi et al., 2017; Kerkouche et al., 2018). Another application is the design of recommender systems, where arms model the popularity of different items (e.g., news recommendation, Li et al. (2010)).

For both cognitive radio and recommender systems, the assumption that the arms distribution do not evolve over time may be a big limitation. Indeed, in cognitive radio new devices can enter or leave the network, which impacts the availability of the radio channel they use to communicate; whereas in online recommendation, the popularity of items is also subject to trends. Hence, there has been some interest on how to take those non-stationary aspects into account within a multi-armed bandit model.

A first possibility to cope with non-stationary is to model the decision making problem as an adversarial bandit problem (Auer et al., 2002b). Under this model, rewards are completely arbitrary and are not assumed to follow any probability distribution. For adversarial environments, the pseudo-regret, which compares the accumulated reward of a given strategy with that of the best fixed-arm policy, is often studied. The pseudo regret of the EXP3 algorithm has been shown to be $\left(\sqrt{KT}\right)$, which matches the lower bound given by Auer et al. (2002b). However, this model is a bit too general for the considered applications, where reward distributions do not necessarily vary at every round. For these reasons, an intermediate model, called the piece-wise stationary MAB, has been introduced by Kocsis and Szepesvári (2006) and Yu and Mannor (2009). In this model, described in full details in Section 2, the (random) reward of arm $i$ at round $t$ has some mean ${\mu }_i\left(t\right)$, that is constant on intervals between two breakpoints, and the regret is measured with respect to the current best arm $i_t^{\ast }=\arg {max}_i{\mu }_i\left(t\right)$.

In this paper, we propose a new algorithm for the piece-wise stationary bandit problem with bounded rewards, called GLR-klUCB. Like previous approaches – CUSUM (Liu et al., 2018) and M-UCB (Cao et al., 2019) – our algorithm relies on combining a standard multi-armed bandit algorithm with a change-point detector. For the bandit component, we propose the use of the klUCB algorithm, that is known to outperform UCB1 (Auer et al., 2002a) used in previous works. For the change-point detector, we propose the Bernoulli Generalized Likelihood Ratio Test (GLRT), for which we provide new non-asymptotic properties that are of independent interest. This choice is particularly appealing because unlike previous approaches, the Bernoulli GLRT is parameter-free: it does not need the tuning of a window size ($w$ in M-UCB), or the knowledge of a lower bound on the magnitude of the smallest change ($\epsilon$ in CUSUM).

In this work we jointly investigate, both in theory and in practice, two possible combinations of the bandit algorithm with a change-point detector, namely the use of local restarts (resetting the history of an arm each time a change-point is detected on that arm) and global restarts (resetting the history of all arms once a change-point is detected on one of them). We provide a regret upper bound scaling in $\left(\sqrt{{{\rm Y}}_{T}T\log \left(T\right)}\right)$ for both versions of GLR-klUCB, matching existing results (when ${{\rm Y}}_T$ is known). Our numerical simulations reveal that using local restart leads to better empirical performance, and show that our approach often outperforms existing competitors.

The article is structured as follows. We introduce the model and review related works in Section 2. In Section 3, we study the Generalized Likelihood Ratio test (GLRT) as a Change-Point Detector (CPD) algorithm. We introduce the two variants of GLR-klUCB algorithm in Section 4, where we also present upper bound on the regret of each variant. The unified regret analysis for these two algorithms is sketched in Section 5. Numerical experiments are presented in Section 6, with more details in the Appendix.

A piece-wise stationary bandit model is characterized by a set of $K$ arms. A (random) stream of rewards $(X_{i,t}{)}_{t\in {\text{N}}^{\ast }}$ is associated to each arm $i\in \{1,\dots ,K\}$. We assume that the rewards are bounded, and without loss of generality we assume that $X_{i,t}\in [0,1]$. We denote by ${\mu }_i\left(t\right):=\text{E}\left[X_{i,t}\right]$ the mean reward of arm $i$ at round $t$. At each round $t$, a decision maker has to select an arm $I_t\in \{1,\dots ,K\}$, based on past observation and receives the corresponding reward $r\left(t\right)=X_{I_t,t}$. At time $t$, we denote by $i_t^{\ast }$ an arm with maximal expected reward, i.e., ${\mu }_{i_t^{\ast }}\left(t\right)={max}_i{\mu }_i\left(t\right)$, called an optimal arm (possibly not unique).

In the piece-wise i.i.d. model, we furthermore assume that there is a (relatively small) number of breakpoints, denoted by ${{\rm Y}}_T:={\sum }_{t=1}^{T-1}\text{1}\left(\exists i\in \{1,\dots ,K\}:{\mu }_t\left(i\right)\ne {\mu }_{t+1}\left(i\right)\right)$. We define the $k$-th breakpoint by ${\tau }^{\left(k\right)}=inf\{t>{\tau }^{(k-1)}:\exists i:{\mu }_i(t)\ne {\mu }_i(t+1\left)\right\}$. Hence for $t\in [{\tau }^{\left(k\right)}+1,{\tau }^{(k+1)}]$, the rewards $\left(X_{i,t}\right)$ associated to each arms are i.i.d.. Note than when a breakpoint occurs, we do not assume that all the arms means change, but that there exists an arm whose mean has changed. Depending on the application, many scenario can be meaningful: changes occurring on all arms simultaneously (due to some exogenous event), or only a few arms change at each breakpoint. Introducing the number of change-points on arm $i$, defined as $\text{NCi}:={\sum }_{t=1}^{T-1}\text{1}\left({\mu }_t\left(i\right)\ne {\mu }_{t+1}\left(i\right)\right)$, it clearly holds that $\text{NCi}\le {{\rm Y}}_T$, but there can be an arbitrary difference between these two quantities for some arms. Letting $C_T:={\sum }_{i=1}^K\text{NCi}$ be the total number of change-points on the arms, one can have $C_T\in \{{{\rm Y}}_T,\dots ,K{{\rm Y}}_T\}$.

The piece-wise stationary bandit model can be viewed as an interpolation between stationary and adversarial models, as the stationary model corresponds to ${{\rm Y}}_T=0$, while the adversarial model can be considered as a special (worst) case, with ${{\rm Y}}_T=T$. However, analyzing an algorithm for the piece-wise stationary bandit model requires to assume a small number of changes, typically ${{\rm Y}}_T=o\left(\sqrt{T}\right)$.

Sequential change-point detection has been extensively studied in the statistical community (see, e.g., Basseville and Nikiforov (1993) for a survey). In this article, we are interested in detecting changes on the mean of a probability distribution with bounded support. Assuming that we collect independent samples $X_1,X_2,\dots$ all from some distribution supported in $[0,1]$. We want to discriminate between two possible scenarios: all the samples come from distributions that have a common mean ${\mu }_0$, or there exists a change-point $\tau \in {\text{N}}^{\ast }$ such that $X_1,\dots ,X_{\tau }$ have some mean ${\mu }_0$ and $X_{\tau +1},X_{\tau +2},\dots$ have a different mean ${\mu }_1\ne {\mu }_0$. A sequential change-point detector is a stopping time $\hat{\tau }$ with respect to the filtration ${\text{F}}_t=\sigma (X_1,\dots ,X_t)$ such that $(\hat{\tau }<\infty )$ means that we reject the hypothesis ${\text{H}}_0:\left(\exists {\mu }_0\in [0,1]:\forall i\in \text{N},\text{E}\left[X_i\right]={\mu }_0\right)$.

Generalized Likelihood Ratio tests date back to the seminal work of Barnard (1959) and were for instance studied for change-point detection by Siegmund and Venkatraman (1995). Exploiting the fact that bounded distribution are $\left(1/4\right)$-sub Gaussian (i.e., their moment generating function is dominated by that of a Gaussian distribution with the same mean and a variance $1/4$), the (Gaussian) GLRT, recently studied in depth by Maillard (2019), can be use for our problem. We propose instead to exploit the fact that bounded distributions are also dominated by Bernoulli distributions. We call a sub-Bernoulli distribution any distribution $\nu$ that satisfies $\ln {\text{E}}_{X\sim \nu }\left[e^{\lambda X}\right]\le {\varphi }_{\mu }\left(\lambda \right)$ with $\mu ={\text{E}}_{X\sim \nu }\left[X\right]$ and ${\varphi }_{\mu }\left(\lambda \right)=\ln (1-\mu +\mu e^{\lambda })$ is the log moment generating function of a Bernoulli distribution with mean $\mu$. Lemma 1 of Cappé et al. (2013) establishes that any bounded distribution supported in $[0,1]$ is a sub-Bernoulli distribution.

Our proposed algorithm, GLR-klUCB, combines a bandit algorithm with a change-point detector running on each arm. It also needs a third ingredient, some forced exploration parameterized by $\alpha \in (0,1)$ to ensure each arm is sampled enough and changes can also be detected on arms currently under-sampled by the bandit algorithm. GLR-klUCB combines the klUCB algorithm (Cappé et al., 2013), known to be optimal for Bernoulli bandits, with the Bernoulli GLR change-point detector introduced in Section 3. This algorithm, formally stated as Algorithm 1, can be used in any bandit model with bounded rewards, and is expected to be very efficient for Bernoulli distributions, which are relevant for practical applications.

The GLR-klUCB algorithm can be viewed as a klUCB algorithm allowing for some restarts on the different arms. A restart happens when the Bernoulli GLR change-point detector detects a change on the arm that has been played (line $9$). To be fully specific, ${\text{GLR}}_{\delta }(Z_1,\dots ,Z_n)=True$ if and only if

with $\beta (n,\delta )$ defined in (5), or $\beta (n,\delta )=\ln \left(3n^{3/2}/\delta \right)$, as recommended in practice, see Section 3.3. We define the (klUCB-like) index used by our algorithm, by denoting ${\tau }_i\left(t\right)$ the last restart that happened for arm $i$ before time $t$, $n_i\left(t\right)={\sum }_{s={\tau }_i\left(t\right)+1}^t\text{1}(A_s=i)$ the number of selections of arm $i$, and ${\hat{\mu }}_i\left(t\right)=\left(1/n_i\right(t\left)\right){\sum }_{s={\tau }_i\left(t\right)+1}^t{X}_{i,s}\text{1}(A_s=i)$ their empirical mean (if $n_i\left(t\right)\ne 0$). With the exploration function $f\left(t\right)=\ln \left(t\right)+3\ln \left(\ln \right(t\left)\right)$ (if $t>1$ else $f\left(t\right)=0$), the index is defined as

In this work, we simultaneously investigate two possible behavior: global restart (reset the history of all arms once a change was detected on one of them, line $11$), and local restart (reset only the history of the arm on which a change was detected, line $13$), which are the two different options in Algorithm 1. Under local restart, in the general case the times ${\tau }_i\left(t\right)$ are not equal for all arms, hence the index policy associated to (7) is not a standard UCB algorithm, as each index uses a different exploration rate. One can highlight that in the CUSUM-UCB algorithm, which is the only existing algorithm based on local restart, the UCB index are defined differently¹: $f(t-{\tau }_i(t\left)\right)$ is replaced by $f\left(n_t\right)$ with $n_t={\sum }_{i=1}^K{n}_i\left(t\right)$.

The forced exploration scheme used in GLR-klUCB (lines $3$-$5$) generalizes the deterministic exploration scheme proposed for M-UCB by (Cao et al., 2019), whereas CUSUM-UCB performs randomized exploration. A consequence of this forced exploration is given in Proposition 4 (proved in Appendix B).

For every pair of instants $s\le t\in {\text{N}}^{\ast }$ between two restarts on arm $i$ (i.e., for a $k\in \{1,\dots ,\text{NCi}\}$, one has ${\tau }_i^{\left(k\right)}={\tau }_i\left(t\right)<s\le t<{\tau }_i^{(k+1)}$) it holds that $n_i\left(t\right)-n_i\left(s\right)\ge \lfloor \frac{\alpha }{K}(t-s)\rfloor$.

In this section, we sketch a unified proof for Theorem 4.1 and 4.2, whose detailed proofs can be found in Appendix D and E respectively. We emphasize that our approach is significantly different from those proposed by Cao et al. (2019) for M-UCB and by Liu et al. (2018) for CUSUM-UCB.