Context Attentive Bandits: Contextual Bandit with Restricted Context

1 Introduction

In sequential decision problems encountered in various applications, from clinical trials [Villar et al., 2015] and recommender systems [Mary et al., 2015] to visual attention models [Mnih et al., 2014], a decision-making algorithm must choose among several actions at each time point. The actions are typically associated with a side information, or a context (e.g., a user's profile), and the reward feedback is limited to the chosen option. For example, in image processing with attention models [Mnih et al., 2014], the context is an input image, the action is classifying the image into one of the given categories, and the reward is 1 if classification is correct and 0 otherwise. A different example involves clinical trials [Villar et al., 2015], where the context is the patient's medical record (e.g. health condition, family history, etc.), the actions correspond to the treatment options being compared, and the reward represents the outcome of the proposed treatment (e.g., success or failure). In this setting, we are looking for a good trade-off between the exploration (e.g., of the new drug) and the exploitation (of the known drug).

This inherent exploration vs. exploitation trade-off exists in many sequential decision problems, and is traditionally formulated as the multi-armed bandit (MAB) problem, stated as follows: given K "arms", or possible actions, each associated with a fixed but unknown reward probability distribution [Lai and Robbins, 1985; Auer et al., 2002], an agent selects an arm to play at each iteration, and receives a reward, drawn according to the selected arm's distribution, independently from the previous actions. A particularly useful version of MAB is the contextual multi-arm bandit (CMAB), or simply contextual bandit problem, where at each iteration, before choosing an arm, the agent observes an N-dimensional context, or feature vector. The agent uses this context, along with the rewards of the arms played in the past, to choose which arm to play in the current iteration. Over time, the agent's aim is to collect enough information about the relationship between the context vectors and rewards, so that it can predict the next best arm to play by looking at the corresponding contexts [Langford and Zhang, 2008; Agrawal and Goyal, 2013].

We introduce here a novel and practically important special case of the contextual bandit problem, called the contextual bandit with restricted context (CBRC), where observing the full feature vector at each iteration is too expensive or impossible for some reasons, and the player can only request to observe a limited number of those features; the upper bound (budget) on the feature subset is fixed for all iteration, but within the budget, the player can choose any feature subset of the given size. The problem is to select the best feature subset so that the overall reward is maximized, which involves exploring both the feature space as well as the arms space.

For instance, in [Tekin et al., 2015], the analysis of clinical trials shows that a doctor can ask a patient only a limited number of question before deciding on drug prescription. In the visual attention models involved in visual pattern recognition [Mnih et al., 2014], a retinalike representation is used, where at each moment only a small region of an image is observed at high resolution, and image classification is performed based on such partial information about the image. Furthermore, in recommender system setting [Hu and Ogihara, 2011], recommending an advertisement depends on user's profile, but usually only a limited aspects of such profile are available. The above examples can be modeled within the proposed framework, assuming that only a limited number of features from the full context can be selected and observed before choosing an arm (action) at each iteration.

Overall, the main contributions of this paper include (1) a new formulation of a bandit problem with restricted context, motivated by practical applications with a limited budget on information access, (2) two new algorithms, both for stationary and non-stationary settings of the restricted-context contextual bandit problem, and (3) empirical evaluation demonstrating advantages of the proposed methods over a range of datasets and parameter settings.

This paper is organized as follows. Section 2 reviews related works. Section 3 introduces some background concepts. Section 4 introduces the contextual bandit model with restricted context, and the proposed algorithms for both stationary and non-stationary environments. Experimental evaluation on several datasets, for varying parameter settings, is presented in Section 5. Finally, the last section concludes the paper and points out possible directions for future works.

2 RelatedWork

The multi-armed bandit problem has been extensively studied. Different solutions have been proposed using a stochastic formulation [Lai and Robbins, 1985; Auer et al., 2002; Bouneffouf and F´eraud, 2016] and a Bayesian formulation [Agrawal and Goyal, 2012]; however, these approaches did not take into account the context.

In LINUCB [Li et al., 2010], Neural Bandit [Allesiardo et al., 2014] and in Contextual Thompson Sampling (CTS) [Agrawal and Goyal, 2013], a linear dependency is assumed between the expected reward of an action and its context; the representation space is modeled using a set of linear predictors. However, the context is assumed to be fully observable, unlike in this paper.

Motivated by dimensionality reduction task, [AbbasiYadkori et al., 2012] studied a sparse variant of stochastic linear bandits, where only a relatively small (unknown) subset of features is relevant to a multivariate function optimization. Similarly, [Carpentier and Munos, 2012] also considered the high-dimensional stochastic linear bandits with sparsity, combining the ideas from compressed sensing and bandit theory. In [Bastani and Bayati, 2015], the problem is formulated as a MAB with high-dimensional covariates, and a new efficient bandit algorithm based on the LASSO estimator is presented. Still, the above work, unlike ours, assumes full observability of the context variables.

In classical online learning (non-bandit) setting, where the actual label of a mislabeled sample is revealed to the classifier (unlike 0 reward for any wrong classification decision in the bandit setting), the authors of [Wang et al., 2014] investigate the problem of Online Feature Selection, where the aim is to make accurate predictions using only a small number of active features.

Finally, [Durand and Gagn´e, 2014] tackles the online feature selection problem by addressing the combinatorial optimization problem in the stochastic bandit setting with bandit feedback, utilizing the Thompson Sampling algorithm. Note that none of the previous approaches addresses the problem of context restriction (variable selection) in the contextual bandit setting, which is the main focus of this work.

3 Background

This section introduces some background concepts our approach builds upon, such as contextual bandit, combinatorial bandit, and Thompson Sampling.

The contextual bandit problem. Following [Langford and Zhang, 2008], this problem is defined as follows. At each time point (iteration) t ∈ {1, ..., T}, a player is presented with a context (feature vector) c(t) ∈ RN before choosing an arm i ∈ A = {1, ...,K}. We will denote by C = {C1, ...,CN} the set of features (variables) defining the context. Let r = (r1(t), ..., rK(t)) denote a reward vector, where ri(t) ∈ [0, 1] is a reward at time t associated with the arm i ∈ A. Herein, we will primarily focus on the Bernoulli bandit with binary reward, i.e. ri(t) ∈ {0, 1}. Let π : C → A denote a policy. Also, Dc,r denotes a joint distribution (c, r). We will assume that the expected reward is a linear function of the context, i.e. E[rk(t)|c(t)] = µTk c(t), where µk is an unknown weight vector (to be learned from the data) associated with the arm k.

Thompson Sampling (TS). The TS [Thompson, 1933], also known as Basyesian posterior sampling, is a classical approach to multi-arm bandit problem, where the reward ri(t) for choosing an arm i at time t is assumed to follow a distribution Pr(rt|˜µ) with the parameter ˜µ. Given a prior Pr(˜µ) on these parameters, their posterior distribution is given by the Bayes rule, Pr(˜µ|rt) ∝ Pr(rt|˜µ)Pr(˜µ). A particular case of the Thomson Sampling approach assumes a Bernoulli bandit problem, with rewards being 0 or 1, and the parameters following the Beta prior. TS initially assumes arm i to have prior Beta(1, 1) on µi (the probability of success). At time t, having observed Si(t) successes (reward = 1) and Fi(t) failures (reward = 0), the algorithm updates the distribution on µi as Beta(Si(t), Fi(t)). The algorithm then generates independent samples θi(t) from these posterior distributions of the µi, and selects the arm with the largest sample value. For more details, see, for example, [Agrawal and Goyal, 2012].

Combinatorial Bandit. Our feature subset selection aproach will build upon the combinatorial bandit problem [Durand and Gagn´e, 2014], specified as follows: Each arm i ∈ {1, ...,K} is associated with the corresponding variable xi(t) ∈ R, which indicates the reward obtained when choosing the i-th arm at time t, for t > 1. Let us consider a constrained set of arm subsets S ⊆ P(K), where P(K) is the power set of K, associated with a set of variables {rM(t)}, for all M ∈ S and t > 1. Variable rM(t) ∈ R indicates the reward associated with selecting a subset of arms M at time t, where rM(t) = h(xi(t), i ∈ M, for some function h(·). The combinatorial bandit setting can be viewed as a game where a player sequentially selects subsets in S and observes rewards corresponding to the played subsets. Here we will define the reward function h(·) used to compute rM(t) as a sum of the outcomes of the arms in M, i.e. rM(t) = ∑i∈M xi(t), although more sophisticated nonlinear rewards are also possible. The objective of the combinatorial bandit problem is to maximize the reward over time.

4 Problem Setting

In this section, we define a new type of a bandit problem, the contextual bandit with restricted context (CBRC); the combinatorial task of feature subset (i.e., restricted context) selection as treated as a combinatorial bandit problem [Durand and Gagn´e, 2014], and our approach will be based on the Thompson Sampling [Agrawal and Goyal, 2012].

4.1 Contextual Bandit with Restricted Context in Stationary Environment (CBRC)

Let c(t) ∈ RN denote a value assignments to the vector of random variables, or features, (C1, ...,CN) at time t, and let C = {1, ...,N} be the set of their indexes. Furthermore, let cd (t) denote a sparse vector of assignments to only d ≤ N out of N features, with indexes from a subset C d ⊆ C, |C d | = d, and with zeros assigned to all features with indexes outside of C d .

Formally, we denote the set of all such vectors as RNCd = {cd (t) ∈ RN | cdi = 0 ∀i /∈ C d }. In the future, we will always use C d to denote a feature subset of size d, and by cd the corresponding sparse vector. We will consider a set Πd = ∪Cd⊆C{π : RN → A, π(c) = ˆ π(s(c))} of compound-function policies, where the function s : RN → RNCd maps each c(t) to cd (t), for a given subset C d , and the function ˆπ : RNCd → A maps cd (t) to an action in A.

As mentioned before, in our setting, the rewards are binary ri(t) ∈ {0, 1}. The objective of a contextual bandit algorithm would be learn a hypothesis π over T iterations maximizing the total reward.

Algorithm 1 The CBRC Problem Setting

• 1: Repeat
• 2: (c(t), r(t)) is drawn according to distribution Dc,r
• 3: The player chooses a subset C d ⊆ C
• 4: The values of cd (t) of features in C d are revealed
• 5: The player chooses an arm k(t) = ˆπ(cd (t))
• 6: The reward rk(t) is revealed
• 7: The player updates its policy π
• 8: t = t +1
• 9: Until t=T

Thompson Sampling with Restricted Context

Algorithm 2 Thompson Sampling with Restricted Context (TSRC)

• 1: Require: The size d of the feature subset, the initial values Si(0) and Fi(0) of the Beta distribution parameters.
• 2: Initialize: ∀k ∈ {1, ...,K},Bk = Id, ˆ µk = 0d, gk = 0d, and ∀i ∈ {1, ...,N}, ni(0) = 0, rf i (0) = 0.
• 3: Foreach t = 1, 2, ..., T do
• 4: Foreach context feature i = 1, ...,N do
• 5: Si(t) = Si(0) + rf i (t -1)
• 6: Fi(t) = Fi(0) +ni(t -1) - rf i (t -1)
• 7: Sample θi from Beta(Si(t), Fi(t)) distribution
• 8: End do
• 9: Select C d (t) = argmaxCd⊆C ∑i∈Cd θi
• 10: Obtain sparse vector cd (t) of feature assignments in C d , where ci = 0 ∀i /∈ C d
• 11: Foreach arm k = 1, ...,K do
• 12: Sample ˜ µk fromN( ˆ µk, v2B-1 k ) distribution. 13: End do 14: Select arm k(t) = argmax k⊂{1,...,K} cd (t)⊤ ˜ µk 15: Observe rk(t) 16: if rk(t) = 1 then 17: Bk = Bk + cd (t)cd (t)T 18: gk = gk + cd (t)rk(t) 19: ˆ µk = B-1 k gk 20: ∀i ∈ C d (t), ni(t) = ni(t - 1) + 1 and rf i (t) = rf i (t -1) +1. 21: End if 22: End do

We now propose a method for solving the stationary CBRC problem, called Thompson Sampling with Restricted Context (TSRC), and summarize it in Algorithm 2 (see section 3 for background on Thompson Sampling); here the combinatorial task of selecting the best subset of features is approached as a combinatorial bandit problem, following the approach of [Durand and Gagn´e, 2014], and the subsequent decision-making (action selection) task as a contextual bandit problem solved by Thompson Sampling [Agrawal and Goyal, 2013], respectively.

Let ni(t) be the number of times the i-th feature has been selected so far, let rf i (t) be the cumulative reward associated with the feature i, and let rk(t) be the reward associated with the arm k at time t.

The algorithm takes as an input the desired number of features d, as well as the initial values of the Beta distribution parameters in TS. At each iteration t, we update the values of those parameters, Si and Fi (steps 5 and 6), to represent the current total number of successes and failures, respectively, and then sample the "probability of success" parameter θi from the corresponding Beta distribution, separately for each feature i (step 7). We select the best subset of features, C d ⊆ C, which maximizes the sum of those parameters (step 9); note that implementing this step does not actually require combinatorial search 1 .

Once a subset of features is selected using the combinatorial bandit approach, we switch to the contextual bandit setting in steps 10-13, to choose an arm based on the context consisting now of a subset of features.

We will assume that the expected reward is a linear function of a restricted context, E[ri(t)|cd (t)] = µTi cd (t); note that this assumption is different from the linear reward assumption of [Agrawal and Goyal, 2013] where single parameter µ was considered for all arms, there was no restricted context, and for each arm, a separate context vector ci(t) was assumed.

Besides this difference, we will follow the approach of [Agrawal and Goyal, 2013] for the contextual Thompson Sampling. We assume that reward ri(t) for choosing arm i at time t follows a parametric likelihood function Pr(r(t)| ˜ µi), and that the posterior distribution at time t+1, Pr(˜µ|r(t)) ∝ Pr(r(t)|˜µ)Pr(˜µ) is given by a multivariate Gaussian distribution N( ˆ µi(t + 1), v2Bi(t + 1)-1 ), where Bi(t) = Id + ∑t-1 τ=1 c(τ)c(τ)⊤ with d the size of the context vectors c, v = R√ 24 ϵ dln( 1 γ ) with R > 0, ϵ ∈]0, 1], γ ∈]0, 1] constants, and ˆµ = B(t)-1 (∑t-1 τ=1 c(τ )c(τ )).

At each time point t, and for each arm, we sample a ddimensional ˜ µi from N( ˆ µi(t), v2Bi(t)-1 ), and choose an arm maximizing cd (t)⊤ ˜ µi (step 14 in the algorithm), obtain the reward (step 15), and update the parameters of the distributions for each ˜ µi (steps 16-21). Finally, the reward rk(t) for choosing an arm k is observed, and relevant parameters are updated.

1 Since the individual rewards θi are non-negative (recall that they follow Beta-distribution), we can simply select the set Cd of d arms with the highest individual rewards θi(t).

4.2 Contextual Bandit with Restricted Context in Non-stationary Environments

In a stationary environment, the context vectors and the rewards are drawn from fixed probability distributions; the objective is to identify a subset of features allowing for the optimal context-to-arm mapping. However, the objective changes when the environment becomes nonstationary.

In the non-stationary CBRC setting, we will assume that the rewards distribution can change only at certain times, and remain stationary between such changes. Given the non-stationarity of the reward, the player should continue looking for feature subsets which allow for the optimal context-arm mapping, rather than converge to a fixed subset.

Similarly to stationary CBRC problem described earlier, at each iteration, a context c(t) ∈ RN describes the environment, the player chooses a subset C d ⊆ C of the feature set C, and observes the values of those features as a sparse vector cd(t), where all features outside of C d are set to zero. Given cd(t), the player chooses an arm k(t). The reward rk(t) of the played arm is revealed. The reward distribution is non-stationary as described above, and the (stationary) reward distributions between the change points are unknown. We will make a very specific simplifying assumptions that the change points occur at every v time points, i.e. that all windows of stationarity have a fixed size.

Windows TSRC Algorithm

Similarly to the TSRC algorithm proposed earlier for the stationary CBRC problem, our algorithm for the nonstationary CBRC uses Thompson Sampling (TS) to find the best d features of the context. The two algorithms are practically identical, except for the following important detail: instead of updating the Beta distribution with the number of successes and failures accumulated from the beginning of the game, only the successes and failures within a given stationarity window are counted. The resulting approach is called the Window Thompson Sampling with restricted Context, or WTSRC.

Note that v, the true size of the stationary window assumed above, is not known by the algorithm, and is replaced by some approximate window size parameter w. In this paper, we assumed a fixed w, and experiment with several values of it; however, in the future, can be also adjusted using a bandit approach.

5 Empirical Evaluation

Empirical evaluation of the proposed methods was based on four datasets from the UCI Machine Learning Repository 2 : Covertype, CNAE-9, Internet Advertisements and Poker Hand (for details of each dataset, see Table 1).

2 https://archive.ics.uci.edu/ml/datasets.html

In order to simulate a data stream, we draw samples from the dataset sequentially, starting from the beginning each time we draw the last sample. At each round, the algorithm receives the reward 1 if the instance is classified correctly, and 0 otherwise. We compute the total number of classification errors as a performance metric.

We compare our algorithms with the following competing methods:

• Multi-armBandit (MAB): this is the standard Thomspon Sampling approach to (non-contextual) multiarm bandit setting.
• Fullfeatures: this algorithm uses the contextual Thomspon Sampling (CTS) with the full set of features.
• Random-EI: this algorithm selects a Random subset of features of the specified size d at Each Iteration (thus, Random-EI), and then invokes the contextual bandit algorithm (CTS).
• Random-fix: similarly to Random-EI, this algorithm invokes CTS on a random subset of d features; however, this subset is selected once prior to seeing any data samples, and remains fixed.

We ran the above algorithms and our proposed TSRC and WTSRC methods, in stationary and non-stationary settings, respectively, for different feature subset sizes, such as 5%, 25%, 50% and 75% of the total number of features.

In the Figures presented later in this section, we used the parameter, called sparsity, to denote the percent of features that were not selected, resulting into the sparsity levels of 95%, 75%, 50% and 25%, respectively. In the following sections, we will present our results first for the stationary and then for the non-stationary settings.

5.1 Stationary case

Table 2 summarizes our results for the stationary CBRC setting; it represents the average classification error, i.e. the misclassification error, computed as the total number of misclassified samples over the number of iterations. This average errors for each algorithm were computed using 10 cyclical iterations over each dataset, and over the four different sparsity levels mentioned above.

As expected, the CTS algorihtm with the full set of features (Fullfeatures) achieved the best performance as compared with the rest of the algorithms, underscoring the importance of the amount of context observed in an on-line learning setting.

However, when the context is limited, is in the CBRC problem considered in this work, our TSRC approach shows superior performance (shown in bold in Table 2) when compared to the rest of the algorithms, except for the Fullfeatures, confirming the importance of efficient feature selection in the CBRC setting.

Overall, based on their mean error rate, the top three algorithms were TSRC (mean error 49.01%), Randomfix (mean error 55.46%), and MAB (mean error 57.98%), respectively, suggesting that using a fixed randomly selected feature subset may still be a better strategy than not considering any context at all, as in MAB. However, as it turns out, ignoring the context in MAB may still be a better approach than randomly changing the choice of feature at each iteration in Random-EI; the latter resulted into the worst mean error of 61.18%.

Detailed analysis on Covertype dataset

Figure 1 provides a more detailed evaluation of the algorithms for different levels of sparsity, on a specific dataset. Ignoring the Fullfeatures which, as expected, outperforms all methods since it considers the full context, we observe that:

95 % sparsity: TSRC has the lowest error out of all methods, followed tightly by MAB, suggesting that, at a very high sparsity level, ignoring the context (MAB) is similar to considering only a very small (5%) fraction of it. Also, as mentioned above, sticking to the same fixed subset of randomly selected features appears to be better than changing the random subset at each iteration.

75 % sparsity: we observe that Random-EI has a lower error than the Random-fix.

50 % sparsity: TSRC has the lowest error, followed closely by the Random-fix, which implies that, at some levels of sparsity, random subset selection can perform almost as good as our optimization strategy. Again, we observe that Random-fix performs better that the Randon-EI, where the performance of the latter is close to the multi-arm bandit without any context.

25 % sparsity: we observe that TSRC perform practically as good as Fullfeatures, which implies that at this sparsity level, our approach was able to select the optimal feature subset.

5.2 Non-stationary Case

In this setting, for each dataset, we run the experiments for 3,000,000 iterations, where we change the label of class at each 500,000 iteration to simulate the non-stationarity. We evaluate our WTSRC algorithm for the nonstationary CBRC problem against our stationarysetting TSRC method, and against the same five baseline methods we presented before.

Similarly to the stationary case evaluation, the Table 3 reports the mean error over all iterations and over the same for level of sparsity as before. Overall, we observed that the WTSRC performs the best, confirming the effectiveness of using our time-windows approach in a nonstationary on-line learning setting.

Our top three performing algorithms were WTSRC, Fullfeatures and TSRC, in that order, which underscores the importance of the size of the observed context even in the non-stationary on-line learning setting.

Detailed analysis on Covertype dataset

Figure 2 provides a more detailed evaluation of the algorithms for different levels of sparsity, on a specific dataset. The Fullfeatures, as expected, has the same performance on different level of sparsity, since it has the access to all features. We observe that:

95 % sparsity: MAB has the lowest error, as compared with the Random-EI and Random-fix, which implies that, at high sparsity levels, ignoring the context can be better then even considering a small random subset of it.

75 % sparsity: TSRC yields the best result, implying that even in a non-stationary environment, a stationary strategy for best subset selection can be beneficial.

50 % sparsity: both Random-Fix and Randon-EI yield the worst results, implying that random selection is not a good strategy at this sparsity level in non-stationary environment.

25 % sparsity: our nonstationary method, WTSRC, outperforms all other algorithms, demonstrating the advantages of a dynamic feature-selection strategy in a non-stationary environment at relatively low sparsity levels.

6 Conclusions

We have introduced a new formulation of MAB, motivated by several real-world applications including visual attention modeling, medical diagnosis and RS. In this setting, which we refer to as contextual bandit with restricted context (CBRC), a set of features, or a context, is used to describe the current state of world; however, the agent can only choose a limited-size subset of those features to observe, and thus needs to explore the feature space simultaneously with exploring the arm space, in order to find the best feature subset. We proposed two novel algorithms based on Thompson Sampling for solving the CBRC problem in both stationary and nonstationary environments. Empirical evaluation on several datasets demonstrates advantages of the proposed approaches.