Toward Optimal Solution for the Context-Attentive Bandit Problem

1 Introduction

The contextual bandit (CB) problem has been extensively studied in the past, and a variety of solutions have been proposed. In LINUCB [Li et al., 2010; Abbasi-Yadkori et al., 2011; Bouneffouf et al., 2019; Bouneffouf and Rish, 2019], Neural Bandit [Allesiardo et al., 2014] and in linear Thompson Sampling [Agrawal and Goyal, 2013; Balakrishnan et al., 2019a; Balakrishnan et al., 2019b], a linear dependency is assumed between the expected reward given the context and an action taken after observing this context; the representation space is modeled using a set of linear predictors.

Recently, a promising variant of contextual bandits, called a Context Attentive Bandit (CAB) was proposed in [Bouneffouf et al., 2017], where no context is given by default, but the agent can request to observe (to focus its "attention" on) a limited number of context variables at each iteration. We propose here an extension of this problem setting: a small subset of V context variables is revealed at each iteration (i.e. partially observable context), followed by the agent's choice of additional U features, where V , U, and the set of V immediately observed features are fixed at all iterations. The agent must learn to select both the best additional features and, subsequently, the best arm to play, given the resulting V + U observed features. (The original Context Attentive Bandit corresponds to V = 0.)

The proposed setting is motivated by several real-life applications where observing the full context is impossible and the agent is allowed to observe just a small subset of information at the onset.

For instance, in a clinical setting, a doctor may first take a look at patient's medical record (partially observed context) to decide which medical test (additional context variables) to perform, before choosing a treatment plan (selecting an arm to play). It is often too costly or even impossible to conduct all possible tests (i.e., observe the full context); therefore, given the limit on the number of tests, the doctor must decide which subset of tests will result into maximally effective treatment choice (maximize the reward).

Similar problems can arise in multi-skill orchestration for AI agents. For example, in dialog orchestration, a user's query is first directed to a number of domain-specific agents, each providing a different response, and then the best response is selected. However, it might be too costly to request the answers from all domain-specific experts, especially in multi-purpose dialog systems with a very large number of domains experts. Given a limit on the number of experts to use for each query, the orchestration agent must choose the best subset of experts to use. In this application, the query is the immediately observed part of the overall context, while the responses of domain-specific experts are the initially unobserved features from which a limited subset must be selected and observed, before choosing an arm, i.e. deciding on the best out of the available responses. For multi-purpose dialog systems, such as, for example, personal home assistants, retrieving features or responses from every domain-specific agent is computationally expensive or intractable, with the potential to cause a poor user experience, again underscoring the need for effective feature selection.

Overall, the main contributions of this paper include:

1. a generalization of Context Attentive Bandit, and a first lower bound for this problem.
2. an algorithm called Context Attentive Thompson Sampling for stationary and non-stationary environments, and its regret bound in the case of stationary environment.
3. an extensive empirical evaluation demonstrating advantages of our proposed algorithm over the previous contextattentive bandit approach [Bouneffouf et al., 2017], on a range of datasets in both stationary and non-stationary settings.

This paper is organized as follows. In section 2 we review related works. The section 3 introduces some background concepts. Then we introduce the Context-Attentive Bandit, the proposed algorithms for both stationary and nonstationary environments, and we provide a lower bound of the proposed problem and a regret bound of the proposed algorithm in the case of stationary environment. Experimental evaluation on several datasets, for varying parameter settings, is presented afterward. Finally, the last section concludes the paper and points out possible directions for future works.

2 RelatedWork

In the contextual bandit problem [Langford and Zhang, 2008; Agarwal et al., 2009; Auer et al., 2003], the objective of is to learn the relationship between the context and reward, in order to find the best arm-selection policy for maximizing cumulative reward over time. Motivated by dimensionality reduction tasks, [Abbasi-Yadkori et al., 2012] studied a sparse variant of stochastic linear bandits, where only a relatively small and unknown subset of features is relevant to a multivariate function optimization. It presents an application to the problem of optimizing a function that depends on many features, where only a small, initially unknown subset of features is relevant. Similarly, [Carpentier and Munos, 2012] also considered high-dimensional stochastic linear bandits with sparsity. There the authors combined ideas from compressed sensing and bandit theory to derive a novel algorithm. In [Oswal et al., 2020], authors explores a new form of the linear bandit problem in which the algorithm receives the usual stochastic rewards as well as stochastic feedback about which features are relevant to the rewards and propose an algorithm that can achieve O(√T) regret, without prior knowledge of which features are relevant.

In [Bouneffouf et al., 2017] the authors proposed the novel framework of contextual bandit with restricted context, where observing the whole feature vector at each iteration is too costly or impossible for some reasons; however, the agent can request to observe the values of an arbitrary subset of features within a given budget, i.e. the limit on the number of features observed. This paper explores a more general problem, and unlike [Bouneffouf et al., 2017], we provide a theoretical analysis of the proposed problem and the proposed algorithm.

The Context Attentive Bandit problem is related to the budgeted learning problem, where a learner can access only a limited number of attributes from the training set or from the test set (see for instance [Cesa-Bianchi et al., 2011]). In [Foster et al., 2016], the authors studied the online budgeted learning problem. They showed a significant negative result: for any δ > 0 no algorithm can achieve regret bounded by O(T 1-δ ) in polynomial time. For overcoming this negative result, an additional assumption is necessary. Here, following [Durand and Gagn´e, 2014], we assume that the expected reward of selecting a subset of features is the sum of the expected rewards of selecting individually the features. We obtain an efficient algorithm, which has a linear algorithmic complexity in terms of time horizon.

3 Context Attentive Bandit Problem

We now introduce the problem setting, outlined in Algorithm 1. Let C be a set of N features. At each time point t the environment generates a feature vector c(t) = (c1(t), ..., cN(t), 1) ∈ RN+1 , which the agent cannot observe fully, but a partial observation of the context is allowed: the values of a subset of V < N observed features C V ⊂ C, are revealed: cV = (cV1 (t), ..., cVN (t), 1) ∈ RN+1 , ∀i ∈ C, cVi (t) = ci(t)1{i ∈ C V }. Based on this partially observed context, the agent is allowed to request an additional subset of U unobserved features C U ⊂ C \ C V , V + U ≤ N. The goal of the agent is to maximize its total reward over time via (1) the optimal choice of the additional set of features C U , given the initial observed features cV (t), and (2) the optimal choice of an arm k ∈ [K] = {1, ...,K} based on cV+U (t) = (cV+U 1 (t), ..., cV+U N (t), 1) ∈ RN+1 , ∀i ∈ C, cV+U i (t) = ci(t)1{i ∈ C V ∨ i ∈ C U }. We assume Pr(r|c, k), an unknown probability distribution of the reward given the context and the action taken in that context. In the following the expectations are taken over the probability distribution Pr(r|c, k).

Algorithm 1 Context Attentive Bandit Problem (CAB)

• 1: for t := 1 to T do
• 2: Context c(t) is chosen by the environment
• 3: The values cV (t) of a subset C V ⊂ C are revealed
• 4: The agent selects a subset C U ⊆ C \ C V
• 5: The values cU (t) are revealed;
• 6: The agent chooses an arm k(t) := π(cV+U (t))
• 7: The reward rk(t) is sampled from distribution Pr(r|c, k) and it is revealed
• 8: The agent updates the policy π ∈ ΠCV+U

9:

• 10: end for

The contextual bandit problem. Following [Langford and Zhang, 2008], this problem is defined as follows. At each time point t ∈ {1, ..., T}, an agent is presented with a context (i.e. feature vector) c(t) ∈ RN+1 before choosing an armk ∈ [K]. Let r(t) = (r1(t), ..., rK(t)) ∈ RK denote a reward vector, where rk(t) is the reward at time t associated with the arm k. Let π : RN+1 → [K] denote a policy, mapping a context c(t) ∈ RN+1 into an arm k ∈ [K]. We assume that the expected reward is a linear function of the context.

Assumption 1 (linear contextual bandit): Whatever the subset of selected features C U ⊂ C \ C V the expected reward is a linear function of the context: E[rk|cV+U (t)] = cV+U (t)⊤µk, where µk ∈ RN+1 is an unknown parameter, ∀k ∈ [K] ||µk|| ≤ 1, and ||cV +U (t)|| ≤ 1.

Contextual Combinatorial Bandit. The contextual combinatorial bandit problem [Qin et al., 2014] can be viewed as a game where the agent sequentially observes a context cV (t), selects a subset C U (t) ⊂ C \ {C V } and observes the reward corresponding to the selected subset. The goal is to maximize the reward over time. Let rU|cV (t), π ∈ R be the reward associated with the set of selected features C U knowing the context vector cU+V (t) and the policy π. We have rU|cV (t), π = rk(t)|cV+U (t), where k(t) = π(cV+U (t)). Each feature i ∈ C U is associated with the corresponding random variable ri|cV (t), π ∈ R which indicates the reward obtained when choosing the i-th feature at time t.

Assumption 2 (linear contextual combinatorial bandit): the mean reward of selecting the set of features C U ⊂ C \ {C V } is: E[rU|cV (t), π] = ∑i∈CU E[ri|cV (t), π], and the expectation of the reward of selecting the feature i is a linear function of the context vector cV (t): E[ri|cV (t), π] = cV (t)⊤θi, where θi ∈ RN+1 is an unknown weight vector associated with the feature i, ∀i ∈ C \ C V ||θi|| ≤ 1, and ||cV (t)|| ≤ 1. Let ΠCV+U be the set of linear policies such that only the features coming from C V+U are used, where C V is a fixed subset of C, and C U is any subset of C \ C V . The objective of Contextual Attentive Bandit (Algorithm 1) is to find an optimal policy π∗ ∈ ΠCV+U , over T iterations or time points, so that the total reward is maximized.

Definition 1 (Optimal Policy for CAB). The optimal policy π∗ for handling the CAB problem is selecting the arm at time t:

where

.

Definition 2 (Cumulative regret). The cumulative regret over T iterations of the policy π ∈ ΠCV+U , is defined as R(T) = ∑Tt=1 E[rπ∗ (c(t))] - ∑Tt=1 E[rπ(c(t))].

Property 1 (Regret decomposition). The cumulative regret over T iterations of the policy π ∈ ΠCV+U can be rewritten as following:

Remark 1. CAB problem generalizes contextual bandit with restricted context problem ([Bouneffouf et al., 2017]). Indeed, when the subset of observed context C V is empty, the reward of selecting the feature i is given by θi,N+1, which is the coordinate N + 1 of the vector θi.

Before introducing an algorithm for solving the above CAB problem, we will derive a lower bound on the expected regret of any algorithm used to solve this problem.

Theorem 1. For any policy π ∈ ΠCV+U solving Context Attentive Bandit problem (Algorithm 1) under Assumption 1.1 and 1.2, there exists probability distribution Pr(r|c, k), such that the lower bound of the regret accumulated by π over T

Proof. The left term of the regret (see Property 1) is lower bounded by the lower bound of linear bandits in dimension U +V (Theorem 2 in [Chu et al., 2011]), while the right term is lower bounded by the lower bound of U linear bandits in dimension V .

4 Context Attentive Thompson Sampling (CATS)

We now propose an algorithm for solving the CAB problem, called Context-Attentive Thompson Sampling (CATS), and summarize it in Algorithm 2. The basic idea of CATS is to use linear Thompson Sampling [Agrawal and Goyal, 2013] for solving the U linear bandit problems for selecting the set of additional relevant features C U ∗ knowing cV (t) ∈ C V , and for selecting the best arm knowing cV +U ∗ (t) ∈ C V +U ∗ . Linear Thompson Sampling assumes a Gaussian prior for the likelihood function, which corresponds in CAB for arm k to ˜µk ∼ N(cV+U (t)⊤ ˆµk, α2 ), and for feature i to, ˜θi ∼ N(cV (t)⊤ˆθi, α2 ). Then the posterior at time t + 1 are respectively P(˜µk|rk(t)) ∼ N(ˆµk, α2A-1k) for arm k, and P(˜µk|rk(t)) ∼ N(ˆθi, α2B-1k) for feature i.

The algorithm takes the total number of features N, the number of features initially observed V , the number of additional features to observe U, the set of observed features C V , the number of actions K, the time horizon T, the distribution parameter α > 0 used in linear Thompson Sampling, and a function of time λ(t), which is used for adapting the algorithm to non-stationary linear bandits.

At each iteration t the values cV (t) of features in the subset C V are observed (line 4 Algorithm 2). Then the vector parameters ˜θi are sampled for each feature i ∈ C V (lines 57) from the posterior distribution (line 6). Then the subset of best estimated features at time t is selected (lines 8-9). Once the feature vector cU(t) is observed line 10, Linear Thompson

Algorithm 2 Context Attentive Thompson Sampling (CATS)

• 1: Require: N, V , U, K, T , C V , α > 0, λ(t)
• 2: Initialize: ∀k ∈ [K],Ak := IN+1, gk := 0N+1, ˆ µk := 0N+1, and ∀i ∈ [N], Bi := IN+1, zi := 0N+1, ˆ θi := 0N+1.
• 3: Foreach t = 1, 2, ..., T do
• 4: observe cV (t)
• 5: Foreach context feature i ∈ C \ C V do
• 6: Sample ˜θi fromN(ˆ θi, α2B-1 i )
• 7: End do
• 8: Sort (cV (t)⊤˜θ1, ...cV (t))⊤˜θN) in decreasing order
• 9: Select C U (t) := {i ∈ C \ C V , cV (t)⊤˜θi ≥ cV (t)⊤˜θV }
• 10: observe values cV+U (t)
• 11: Foreach arm k = 1, ...,K do
• 12: Sample ˜µk fromN(ˆµk, α2A-1 k ) distribution
• 13: End do
• 14: Select arm k(t) := argmaxk⊂[K] cV+U (t)⊤ ˜µk
• 15: Observe rk(t)
• 16: Ak := Ak + cV+U (t)cV+U (t)⊤, gk := gk + cV+U (t)rk(t), ˆµk := A-1 k gk
• 17: Foreach i ∈ C U
• 18: Bi := λ(t)Bi + cV (t)cV (t)⊤, zi := zi + cV (t)rk(t), ˆθi := λ(t)B-1 i zi
• 19: End do
• 20: End do

Sampling is applied in steps 11-15 to choose an arm. When the reward of selected arm is observed (line 15) the parameters are updated lines 16-19.

Remark 2 (Algorithmic complexity). At each time set, Algorithm 2 sorts a set of size V and inverts U + 1 matrices in dimensions N + 1 that leads to an algorithmic complexity in O(V log V + (U + 1)(N + 1)2 )T .

Due to assumption 2, CATS algorithm benefits from a linear algorithmic complexity, overcoming the negative result stated in [Foster et al., 2016]. Before providing an upper bound of the regret of CATS in ˜O(√T) ( ˜O hides logarithmic factors), we need an additional assumption on the noise ηk(t).

Assumption 3 (Sub-Gaussian noise): ∀ C U+V ∈ C and ∀k ∈ [K], the noise nk(t) = rk(t)|cV+U (t) - cU+V (t)⊤µk is conditionally ρ-sub-Gaussian with ρ ≥ 0, that is for all t ≥ 1,

Lemma 1. (Theorem 2 in [Agrawal and Goyal, 2013]) When the measurement noise nk(t) satisfies Assumption 2, ∀t ∈ {1, ..., T} ||ck(t) ≤ 1||, ||µ ≤ 1||, α = ρ√9N log Tδ , and ϵ = 1 logT the regret R(T) of Thompson Sampling in the Linear bandit problem with K parameters is upper bounded with a probability 1 - δ by:

We can now derive the following result.

Theorem 2. When the measurement noise ηk(t) satisfies Assumption 3, ∀t ∈ {1, ..., T} ||ck(t) ≤ 1||, ||µ ≤ 1||, α = ρ√9N log Tδ , λ(t) = 1 and ϵ = 1 logT the regret R(T) of CATS (Algorithm 2) is upper bounded with a probability 1 - δ by:

Proof. For upper bounding the left term of the regret (see Property 1), we apply Lemma 1, and for upper bounding the right term, which is the regret of Thompson Sampling in U linear bandit problems in V dimensions with respectively N - V, N - V - 1, ..., N - V - U - 1 parameters, we apply Lemma 1.

Theorem 2 states that the regret of CATS depends on the following two terms: the left term is the regret due to selecting a sub-optimal arm, while the right term is the regret of selecting a sub-optimal subset of features. We can see that there is still a gap between the lower bound of the Context Attentive Bandit problem and the upper bound of the proposed algorithm. The left term of the lower bound scales in Ω(√(U +V )T), while the left term of the upper bound of CATS scales in ˜O((U+V )√KT logK), where ˜O hides logarithmic factor. The right term of the lower bound scales in Ω(U √V T ), while the right term of the upper bound of CATS scales in ˜O((U + V )√(N - V )T log(N - V )). These gaps are due to the upper bound of regret of CATS, which uses Lemma 1. This suggests that the use of linear bandits based on an upper confidence balls, which scale in ˜O√dT [AbbasiYadkori et al., 2011] (d is the dimension of contexts), could reduce this theoretical gap. As we show in the next section, we choose the Thompson Sampling approach for its better empirical performances.

5 Experiments

We compare the proposed CATS algorithm with:

1. Random-EI: in addition to the V observed features, this algorithm selects a Random subset of features of the specified size U at each Iteration (thus, Random-EI), and then invokes the linear Thompson sampling algorithm.
2. Random-fix: this algorithm invokes linear Thompson sampling on a subset of U + V features, where the subset V is randomly selected once prior to seeing any data samples, and remains fixed.
3. The state-of-art method for context-attentive bandits proposed in [Bouneffouf et al., 2017], Thompson Sampling with Restricted Context (TSRC): TSRC solves the CBRC (contextual bandit with restricted context) problem discussed earlier: at each iteration, the algorithm decides on U +V features to observe (referred to as unobserved context). In our setting, however, V out of N features are immediately observed at each iteration (referred to as known context), then

TSRC decision mechanism is used to select U additional unknown features to observe, followed by linear Thompson sampling on U+V features.

(4) CALINUCB: where we replace the contextual TS in CATS with LINUCB.

(5) CATS-fix: is heuristic where we stop the features exploration after some iterations T ′ = 10%, 20%....90% (we report here the an average over the best results).

Empirical evaluation of Random-fix, Random-EI, CATSfix, CALINUCB, CATS 1 and TSRC was performed on several publicly available datasets, as well as on a proprietary corporate dialog orchestration dataset. Publicly available Covertype and CNAE-9 were featured in the original TSRC paper and Warfarin [Sharabiani et al., 2015] is a historically popular dataset for evaluating bandit methods.

To simulate the known and unknown context space, we randomly fix 10% of the context feature space of each dataset to be known at the onset and explore a subset of U unknown features. To consider the possibility of nonstationarity in the unknown context space over time, we introduce a weight decay parameter λ(t) that reduces the effect of past examples when updating the CATS parameters. We refer to the stationary case as CATS and fix λ(t) = 1. For the nonstationary setting, we simulate nonstationarity in the unknown feature space by duplicating each dataset, randomly fixing the known context in the same manner as above, and shuffling the unknown feature set - label pairs. Then we stochastically replace events in the original dataset with their shuffled counterparts, with the probability of replacement increasing uniformly with each additional event. We refer to the nonstationary case as NCATS and use λ(t) as defined by the GP-UCB algorithm [Srinivas et al., 2009]. We compare NCATS to NCATS-fix and NCALINUCB which are the non stationary version of CATS-fix and CALINUCB. we have also compare NCATS to the Weighted TSRC (WTSRC), the nonstationary version of TSRC also developed by [Bouneffouf et al., 2017]. WTSRC makes updates to its feature selection model based only on recent events, where recent events are defined by a time period, or "window" w. We choose w = 100 for WTSRC. We report the total average reward divided by T over 200 trials across a range of U corresponding to various percentages of N for each algorithm in Table ??.

The results in Table ?? are promising, with our methods outperforming the state of the art in the majority of cases across both settings. The most notable exception is found for CNAE-9 dataset, where CATS sometimes outperforms or nearly matches TSRC performance. This outcome is somewhat expected, since in the original work on TSRC [Bouneffouf et al., 2017], the mean error rate of TSRC was only 0.03% lower than the error corresponding to randomly fixing a subset of unknown features to reveal for each event on CNAE-9. This observation suggests that, for this particular dataset, there may not be a subset of features which would be noticeably more predictive of the reward than the rest of the features. We also observe that the LINUCB version of CATS has comparable performance with CATS with slight advantage to CATS. Another observation is that CATS-fix is performing better than CATS in some situations, the explanation could be that after finding the best features the algorithm do not need to explore anymore and focus on finding the best arms based on these featues. Note that there may not be a subset of features which would be noticeably more predictive of the reward than the rest of the features, which is the underlying assumption of TSRC. On top of this assumption, CATS also assumes that there exist relationships between the known and unknown context features, which is likely to cause a small compounding of error.

1 Note that we have used the same exploration parameter value used in [Chapelle and Li, 2011] for TS and LINUCB type algorithms which are TS ∈ {0.25, 0.5, 1} and LINUCB ∈ {0.51, 1, 2}

We perform a deeper analysis of the Covertype dataset, examining multi-staged selection of the U unknown context feature sets. In CATS, the known context is used to select all U additional context feature sets at once. In a multi-staged approach, the known context grows and is used to select each of the U additional context features incrementally (one feature at a time). Maintaining λ(t) = 1, for the stationary case we denote these two cases of the CATS algorithm as CATS and CATS-Staged respectively and report their performance when 10% of the context is randomly fixed, across various U in Figure 1a.

Note that when the remaining 90% of features are revealed, the CATS and TSRC methods all reduce to simple linear Thompson sampling with the full feature set. Similarly, when 0 additional feature sets are revealed, the methods all reduce to linear Thompson sampling with a sparsely represented known context. Observe that CATS consistently outperforms CATS-Staged across all U tested.

CATS-Staged likely suffers because incremental feature selection adds nonstationarity to the known context - CATS learns relationships between the known and unknown features while CATS-Staged learns relationships between them as the known context grows. Nonetheless, both methods outperform TSRC. In the nonstationary case we use the GP-UCB algorithm for λ(t), refer to the single and multi-staged cases as NCATS and NCATS-Staged, and illustrate their performance in Figure 1b. Here we observe that NCATS and NCATSStaged have comparable performance, and the improvement gain over baseline, in this case WTSRC, is even greater than in the stationary case.

5.1 Customer Assistant Evaluation

Next we evaluate our methods on Customer Assistant, a proprietary multi-skill dialog orchestration dataset. Recall that this kind of application motivates the CAB setting because there is a natural divide between the known and unknown context spaces; the query and its associated features are known at the onset and the potential responses and their associated features are only known for the domain specific agents the query is posed to. In this case, nonstationarity in the unknown context space could reflect independent updates to the underlying domain specific agents, perhaps improving or expanding their responses. As a result, similar queries, defining the known context, could elicit vastly different distributions of response features, the unknown context, over time.

The Customer Assistant orchestrates 9 domain specific agents which we arbitrarily denote as Skill1, . . . , Skill9 in the discussion that follows. In this application, example skills lie in the domains of payroll, compensation, travel, health benefits, and so on. In addition to a textual response to a user query, the skills orchestrated by Customer Assistant also return the following features: an intent, a short string descriptor that categorizes the perceived intent of the query, and a confidence, a real value between 0 and 1 indicating how confident a skill is that its response is relevant to the query. Skills have multiple intents associated with them. The orchestrator uses all the features associated with the query and the candidate responses from all the skills to choose which skill should carry the conversation.

The Customer Assistant dataset contains 28,412 events associated with a correct skill response. We encode each query by averaging 50 dimensional GloVe word embeddings [Pennington et al., 2014] for each word in each query and for each skill we create a feature set consisting of its confidence and a one-hot encoding of its intent. The skill feature set size for Skill1, . . . , Skill9 are 181, 9, 4, 7, 6, 27, 110, 297, and 30 respectively.

We concatenate the query features and all of the skill features to form a 721 dimensional context feature vector for each event in this dataset. Recall that there is no need for simulation of the known and unknown contexts; in a live setting the query features are immediately calculable or known, whereas the confidence and intent necessary to build a skill's feature set are unknown until a skill is executed. Because the confidence and intent for a skill are both accessible post execution, we reveal them together. We accommodate this by slightly modifying the objective of CATS to reveal U unknown skill feature sets instead of U unknown individual features for each event. We perform a deeper analysis of the Customer Assistant dataset, examining multi-staged selection of the U unknown context feature sets. Maintaining λ(t) = 1, for the stationary case the results are summarized in Figure 2a. Here both CATS-Staged and CATS methods outperform TSRC by a large margin.

(a) Stationary Setting

(b) Nonstationary Setting

Figure 2: Total Average Reward for Customer Assistant

For the nonstationary case we simulate nonstationarity in the same manner as the publicly available datasets, except using the natural partition of the query features as the known context and the skill feature sets as the unknown context instead of simulated percentages. We use the GP-UCB algorithm for λ(t) and illustrate the performance of NCATS and NCATS-Staged alongside WTSRC in Figure 2b. Here we observe that NCATS slightly outperforms NCATS-Staged, and both outperform the WTSRC baseline.

6 Conclusions and FutureWork

We have introduced here a novel bandit problem with only partially observable context and the option of requesting a limited number of additional observations. We also propose an algorithm, designed to take an advantage of the initial partial observations in order to improve its choice of which additional features to observe, and demonstrate its advantages over the prior art, a standard context-attentive bandit with no partial observations of the context prior to feature selection step. Our problem setting is motivated by several realistic scenarios, including medical applications as well as multidomain dialog systems. Note that our current formulation assumes that all unobserved features have equal observation cost. However, a more practical assumption is that some features may be more costly than others; thus, in our future work, we plan to expand this notion of budget to accommodate more scenarios involving different feature costs. Other directions for future work include using non-bandit algorithms in the context feature selection stage.

7 Broader Impact

This problem has broader impacts in several domains such as voice assistants, healthcare and e-commerce.

• Better medical diagnosis. In a clinical setting, it is often too costly or infeasible to conduct all possible tests; therefore, given the limit on the number of tests, the doctor must decide which subset of tests will result into maximally effective treatment choice in an iterative manner. A doctor may first take a look at patient's medical record to decide which medical test to perform, before choosing a treatment plan.
• Better user preference modeling. Our approach can help to develop better chatbots and automated personal assistants. For example, following a request such as, for example, "play music", an AI-based home assistant must learn to ask several follow-up questions (from a list of possible questions) to better understand the intent of a user and to remove ambiguities: e.g., what type of music do you prefer (jazz, pop, etc)? Would you like it on hi-fi system or on TV? And so on. Another example: a support desk chatbot, in response to user's complaint ("My Internet connection is bad") must learn to ask a sequence of appropriate questions (from a list of possible connection issues): how far is your WIFI hotspot? Do you have a 4G subscription? These scenarios are wellhandled by the framework we proposed in this paper.
• Better recommendations. Voice assistants and recommendation systems in general tend to lock us in our preferences, which can have deleterious effects: e.g., recommendations based only on the past history of user's choices may reinforce certain undesirable tendencies, e.g., suggesting an online content based on a user's with particular bias (e.g., racist, sexist, etc). On the contrary, our approach could potentially help a user to break out of this loop, by suggesting the items (e.g. news) on additional questions (additional features) which can be used to broaden user's horizons.