Multi-Feedback Bandit Learning with Probabilistic Contexts

1 Introduction

Multi-armed bandit (MAB) is a crucial online learning problem to discover optimal decisions (a.k.a. arms) based on received feedback signals over time [Lai and Robbins, 1985]. Importantly, contextual bandit learning extends the standard MAB setting by allowing the learner/agent to access some side information (i.e., context) about the environment prior to arm selection [Lin et al., 2018]. For contextual bandit, the context and selected arm jointly determine the distribution of reward received by the agent, and the goal of the agent is to maximize its cumulative reward by gradually identifying the optimal mapping of context information into actions based on the history of context-action-feedback.

⇤Equal contribution.

Contextual bandits have found success in many applications, including online recommendation [Mary et al., 2015], commercial advertising [Tang et al., 2013] and medical experiment design [Villar et al., 2015]. Subsequently, efficient learning algorithms like Lin-UCB [Li et al., 2010], EXP4 [Auer et al., 2002] and their variations [Li et al., 2017] have drawn great attention. Nonetheless, most of the prior studies assume that the context information acquired by the agent before arm selection is perfect. While this assumption facilitates performance analysis of the proposed algorithms, it may fail in certain practical scenarios, where there is randomness and uncertainty about the context information.

To alleviate the uncertainty and randomness from environment, one can apply classification techniques, such as support vector machine (SVM) [Quinlan, 1986] and deep neural networks (DNN) [Wan, 1990], which yield a probability distribution over possible candidate category of contexts. For example, a recommendation system commonly recommends personalized items given user features (i.e., contexts) predicted by a neural network classifier. Thus, all the possible candidate contexts together form a context bundle with a probability distribution of different contexts, and the exact context is included in the bundle (possibly not having the greatest probability) but unknown to the agent. In this paper, we also use "context" and "context candidate" exchangeably.

In addition to the lack of exact context information, another practical consideration for contextual bandit learning is that the agent can receive multiple feedbacks instead of a single one. In this case, the goal of the agent is to maximize its reward modeled as a (possibly time-varying) utility function jointly determined by multiple feedbacks rather than any of the individual feedback. For example, when selecting an app for a mobile device, both energy and latency can be measured and reported to the learner/agent, and these metrics jointly affect the performance of the selected app.

Motivated by the aforementioned practical considerations, the focus of this work is to study a novel contextual bandit setting where the agent can only access to a probabilistic context bundle for arm selection and its goal is to maximize a time-varying utility function jointly determined by the multiple feedback signals received at the end of each round. In order to design an efficient learning algorithm, the key is how the agent leverages the available probabilistic context information to learn multiple feedback functions that jointly determine a reward. To study this problem, we consider a general setting where each individual feedback function can be nonlinear with respect to the selected arm and contexts, and apply the kernel method to transfer feedback function in the reproducing kernel Hilbert space (RKHS). We design a new algorithm by extending upper confidence bound (UCB) techniques to account for the probabilistic context information, using the expectation of reward over the probabilistic context distribution. For each feedback, we learn its relation with the selected arm given a probabilistic context bundle. Then, an arm is selected based on an estimated reward in terms of all the estimated feedback values. Importantly, we prove that our algorithm achieves a sub-linear regret upper bound O(pT log(T)) compared to an oracle that knows the optimal arm given any probabilistic context bundle.

We apply our learning algorithm to the problem of deep neural network (DNN) model recommendation for edge inference on mobile devices. Our experiments show that our proposed algorithm outperforms the alternative solution that selects arms based on the most probable context. More importantly, our algorithm yields a sub-linear regret with respect to the oracle, demonstrating the effectiveness of our algorithm and validating the regret analysis.

2 ProblemFormulation

In a standard contextual bandit setting, the context xt 2 RM is available to the agent at each round. In many cases, however, the agent only has the knowledge of a bundle of context candidates X = {x1 ↪ · · · ↪ xN , where ♣X♣ = N, and the true context xt is in the bundle. At each round t, with some prior knowledge, the agent can get a collection of probabilities for context candidates, i.e. Prt(X) = {Pt(x1 )↪ · · · ↪ Pt(xN ) and PNi=1 Pt(xi ) = 1. This can be done by using, for example, a well-trained DNN classifier and extracting the softmax layer output of the classifier. The extracted probabilities define a probability space over the context bundle X. Now, the context at round t is a random variable Xt in the probability space with the probability measure P r (Xt = xit ) = Pt (xit ). Note that, with a notational change, our model can also be extended to continuous context with a probability density function. Additionally, we consider a more general case where the agent receives multiple feedbacks. The jth feedback (j = 1↪ · · · ↪ J) with respect to action a 2 A and the random context Xt can be expressed as

where gja (·) is a deterministic feedback function which can be linear or nonlinear, and ✏j is zero-mean Gaussian noise and ✏i and ✏j are mutually independent for i 6= j. Assume that for j = 1↪ · · · ↪ J, a kernel function kj : RM ⇥RM !R can be found to represent gja (·) in RKHS F j . In other words, the kernel function kj corresponds to a feature map φj : Rn ! F j which satisfies kj (x↪ x0 ) = φj (x)>φj (x0 )↪ 8x↪ x0 2 RM ↪ and gja (x) = φj (x)>✓ja ▷

The agent's reward is evaluated by a utility function Ut : RJ ! R, which may change over time and is known to the agent. Assuming that the Lipschitz constant of the utility function Ut is Lt and L = maxt Lt, we have

If an action a is selected, then a reward Ut(fa↪t) is obtained by the agent where fa↪t = ⇥f 1 a↪t ↪ · · · ↪ f J a↪t ⇤ is the feedback vector. By selecting actions, we seek to maximize the expected reward over both the probabilistic context space and the noise space, which is denoted as E[Ut(fa↪t)]. For the convenience of analysis, we further assume that E✏[Ut(fa↪t)] = Ut(E✏[fa↪t]) where the expectation E✏ [·] is taken over the noise space. Example utility functions include a linear form Ut (f) = u>t f or a multiplication form Ut (f) = QJj=1 f j , which are also common functions used in multi-objective bandits [Roijers et al., 2017; Yahyaa and Manderick, 2015].

The best action at round t is defined as the action that leads to the highest expected reward, i.e.

where the expectation E [·] is taken over both noise space and context space. This best action oracle is reasonable and common for the cases with context uncertainty, and also considered as a benchmark in [Kirschner and Krause, 2019; Yun et al., 2017]. With this oracle, the expected instant regret regt at every round can be expressed as

where the expectation E [·] is taken over both noise space and context space. The algorithm needs to be designed to find an arm selection policy based on the history information to minimize the cumulative regret RT = PTt=1 regt.

3 Algorithm

In this section, we first introduce the feedback prediction algorithm and then, given the predicted feedbacks and confidence widths, design a UCB-based algorithm with probabilistic contextual information.

3.1 Feedback Prediction

In order to select an action, the algorithm should be able to predict the feedbacks corresponding to each action, which then determines the resulting reward. Note that we cannot simply treat the overall utility function as a single feedback signal and directly predict it given incoming contextual information as in prior studies [Kirschner and Krause, 2019], because the utility function in terms of multiple feedbacks is changing over time in our setting. To accomplish feedback prediction, we can estimate the parameter ✓ja in feedback functions by kernel-based empirical risk minimization based on the history Hja↪t = {(X ↪ P r⌧ (X )↪ f j a↪⌧ ) ↪ ⌧ = 1↪ · · · ↪ t ↪ j = 1↪ · · · ↪ J. Denote the set of rounds when arm a is selected before round t as Ta↪t = {⌧ 1 a ↪ ⌧ 2 a ↪ · · · ↪ ⌧ na↪t a , where na↪t is the number of times that arm a has been selected prior to round t. The kernel based empirical risk minimization is to solve the following problem

where λ ≥ 0 is a hyper-parameter.

where Cja↪t = Φja↪tΦja↪t> +λI. Then, the estimated feedback with respect to candidate xit can be calculated as

whose confidence width [Deshmukh et al., 2017; Kirschner and Krause, 2019] is

As the algorithm may not have access to the mapping function φj (x), we need to represent Eqn. (7) and Eqn. (8) by kernel function. By the Woodbury matrix identity, we have

Denote ki↪j a↪t = Φja↪t>φj (xit ) and Kja↪t = Φja↪t>Φja↪t . The pth entry in kja↪t is E ⇥φj (X⌧ p a )⇤> φj (xit ) = P♣X ♣ n=1 P (xi⌧ p a )kj (xn⌧ p a ↪ xit ). Similarly, the entry of Kja↪t in the pth row and qth column is E ⇥φj (X⌧ p a )⇤>E[φj (X⌧ q a )] = P♣X ♣ n↪m=1P (xn⌧ p a )P (xm⌧ q a )kj (xn⌧ p a ↪ xm⌧ q a ). Now, the estimated feedback can be represented as

and the confidence width is

where Dja↪t = Kja↪t + λI.

3.2 Multi-Feedback Probabilistic Contextual UCB

Based on the results of empirical risk minimization, the proposed algoritm, multi-feedback probabilistic contextual UCB, is given in Algorithm 1.

At each round, the algorithm needs to get the estimated expected reward and the corresponding expected confidence width. To do so, the algorithm first calculates estimated feedbacks and corresponding confidence widths according to Eqn. (11) and Eqn. (12), respectively. Then, given the utility function Ut : RJ ! R, the estimated reward with respect to the ith context candidate is predicted as Ut(ˆf ia↪t ) where

Algorithm 1 Multi-Feedback Probabilistic Contextual UCB

• 1: Inputs :
• Arm set A, a horizon T, kernel function k1 ↪ · · · ↪ kJ and parameter ↵ and λ.
• 2: for t = 1↪ · · · ↪ T do
• 4: for a 2 A do
• 3: Receive a set of probabilities Prt(X) for the candidates in the context bundle X
• 5: Calculate E[Ut(ˆfa↪t)] and E[wa↪t] according to Eqn. (13) and Eqn. (14).
• 6: end for
• 7: at = argmaxa2A(E[Ut(ˆfa↪t)] +LβE[wa↪t])
• a↪t ↪ · · · ↪ f J a↪t ⇤.
• 8: Receive feedback fa↪t = ⇥f 1 9: Update yja↪t+1 , Kja↪t+1 and Dja↪t+1 10: end for

ˆf ia↪t = [ ˆ f i↪1 a↪t ↪ ˆ f i↪2 a↪t ↪ · · · ˆ f i↪j a↪t ↪ · · · ]>. As the exact context is not given, the estimated feedback ˆfa↪t is a random vector over the probabilistic context space. Hence, the estimated expected reward over the probabilistic context space is written as

The confidence width is important for arm exploration, but it is not trivial to get the expected confidence width. Here, we calculate the upper bound of the expected confidence width over the probabilistic context space by exploiting Lipschitz continuity of the utility function. Concretely, if L is the Lipschitz constant of the utility function, the upper bound of expected confidence width over the probabilistic context space is calculated as

The detailed derivation of Eqn. (14) will be given in Lemma 4.2.

With the estimated expected reward and the corresponding expected confidence width, the selected arm is at = argmaxa2A(E[Ut(ˆfa↪t)] + LβE[wa↪t]), where β is a hyperparameter to balance the exploration and exploitation.

4 Regret Analysis

In this section, we analyze the regret with respect to an oracle that also has the probabilistic context information and establish an upper bound on cumulative regret of Algorithm 1 which shows the cumulative regret sub-linearly increases with O(pT log T), followed by the proof sketch.

4.1 Cumulative Regret Bound

The following theorem provides an upper bound on the cumulative regret of Algorithm 1.

Theorem 4.1. Assume at each round t, the utility function Ut(fa↪t) 2 [0↪ 1] satisfies E✏[Ut(fa↪t)] = Ut(E✏[fa↪t]) with Lipschitz constant Lt and L = maxt Lt, and the kernel function is kj (x↪ x0 )  ck such that φj (x) ⌫ 0. At each round t, the agent receives a probabilistic context set X and the corresponding probability set Prt (X), selects arm from A by Algorithm 1 and get J different feedbacks. With probability 1 - δ, the cumulative expected regret RT of Algorithm 1 is bounded by

Remark 4.1. Theorem 4.1 shows that, for the bandit setting with probabilistic contexts and multiple feedbacks, our proposed algorithm can achieve a sub-linear cumulative expected regret bound O(pT logT). This demonstrates the effectiveness of our proposed algorithm.

where γm is the maximum rank of Kja↪t , q = max(1↪ ck λ ) and β = (q log(2TJ♣A♣◁δ) 2 + cpλ).

Remark 4.2. Compared with the cumulative regret bound of kernel-UCB in the standard bandit setting [Chowdhury and Gopalan, 2017; Deshmukh et al., 2017], the cumulative regret bound of the proposed algorithm is scaled by Lipschitz constant L, number of feedbacks J and size of context bundle ♣X♣. As a result, the regret in our setting is more difficult to be reduced than that in the standard setting. Nonetheless, by the proposed algorithm, the cumulative regret can still be guaranteed to be sub-linear.

4.2 Proof Sketch

The proof sketch of Theorem 4.1 is given below. Compared with other UCB algorithms [Abbasi-Yadkori et al., 2011; Deshmukh et al., 2017; Kirschner and Krause, 2019], the consideration of probabilistic context, multiple noisy feedbacks and Lipschitz utility function adds new challenges to the regret bound proof. First, since the algorithm predicts feedbacks instead of the reward, the predicted feedbacks can be guaranteed to converge to the expected feedbacks by Lemma 1 in [Deshmukh et al., 2017], but we still need to bound the gap between the estimated reward and the true expected reward. Second, since the proposed algorithm only has probabilistic contexts, we can bound the expected reward estimation error by the expected confidence width, but it is still challenging to get the sum of the confidence width over time. Next, we show several important lemmas to address the aforementioned challenges.

First, by exploiting the Lipschitz continuity of utility function, the confidence width of estimated reward is bounded in Lemma 4.2, which also explains the setting of confidence width in Algorithm 1.

Lemma 4.2 (Concentration of Empirical Risk Minimization). Assume the utility function Ut(·) is in a linear form or multiplication form with Lipschitz constant L. With probability at least 1 - δT , for 8a 2 A, we have

Proof. Let gi↪j a↪t = gja (xit ) and gia↪t = ⇥gi↪1 a ↪ · · · ↪ gi↪j a ⇤>.By the assumption E✏[Ut(fa↪t)] = Ut(E✏[fa↪t]), we have

By Lemma 1 in [Deshmukh et al., 2017], we have ∣∣∣ ˆ f i↪j a↪t - gi↪j a↪t ∣∣∣  βwi↪j a↪t with probability at least 1 - δ JT . Thus, with probability at least 1 - δT , we have ∣∣∣EhUt(ˆfa↪t)-Ut(fa↪t)i∣∣∣  Lβ P♣X♣ i=1 Pt(xit ) PJj=1 wi↪j a↪t = LβE[wa↪t]▷

Then, by using Lemma 4.2, we will bound the regret by the expected confidence width in the next lemma.

Lemma 4.3 (Regret Bound by Confidence Width). Assume that the utility function Ut(·) satisfies E✏[Ut(fa↪t)] = Ut(E✏[fa↪t]) with Lipschitz constant L. With probability at least 1- δT , the cumulative regret satisfies

Proof. By similar proof techniques for standard UCB [Abbasi-Yadkori et al., 2011; Kirschner and Krause, 2019], with probability at least 1 - δT , the instant regret for round t is bounded as

where the first and third inequalities hold by Lemma 4.2 and the second inequality holds by the arm selection policy in Algorithm 1. Thus, the cumulative regret is bounded as Eqn. (18).

The next challenge is to bound the sum of confidence width, which is expressed as

We cannot directly use Sylvester's determinant theorem or Schur's determinant identity like in the proofs of Lemma 11

in [Abbasi-Yadkori et al., 2011] and Lemma 7 in [Deshmukh et al., 2017]. Thus, we first derive Lemma 4.4 to get an upper bound of E[wat↪t], and then get the sum of the expected confidence width in Lemma 4.4

Lemma 4.4 (Sum of Confidence Width). Assume kernel function kj is chosen such that mapping function φj (x) ⌫ 0, we have

where γm is the maximum rank of Kja↪t , q = max(1↪ ck λ ).

where the inequality holds because φj (x) ⌫ 0 and thus E[φj (Xt)] = P♣X♣ n=1 Pt(xnt )φj (xnt ) ≥ Pt(xit )φj (xit ). By taking squared root of both sides of Eqn. (22), we have Pt(xit )wi↪j a↪t  ¯wja↪t , and thus E[wja↪t ] = P♣X ♣ i=1 Pt(xit )wi↪j a↪t  ♣X♣ ¯wja↪t ▷ Since PTt=1 ¯wjat↪t can be bounded by Lemma 8 in [Deshmukh et al., 2017], i.e. PTt=1 ¯wjat↪t  r2qγmT log( (T+1)ck+λ d 1 γm λ ), the inequality (21) can be proved.

By substituting Eqn. (21) into Eqn. (18), we can get the cumulative regret bound in of Algorithm 1 in Theorem 4.1.

5 Simulation Results

We now apply Algorithm 1 to the problem of DNN model selection for mobile devices and show its performance in terms of average reward and cumulative regret. Importantly, our result demonstrates that compared to the oracle that knows the optimal arm given a probabilistic context bundle, the cumulative regret achieved by our algorithm increases sub-linearly over time, validating our theoretical regret analysis.

5.1 Application to DNNModel Selection

The recent breakthrough in DNN model compression has made it possible to run DNN inference on edge devices (e.g., mobile phones and tablets). While they can have similar inference accuracies, different DNN models have different latencies and energy consumption under different system conditions. Thus, it is crucial to select an optimal DNN model for edge inference with the best user experience. This is challenged by the fact that, although the basic configuration of an edge device (e.g., CPU, OS, RAM) requesting a DNN model is exposed to the model provider, the device's actual resource management and system condition (e.g., available system resources) that decide the latency and energy of the deployed DNN model can only be known probabilistically.

Concretely, the available DNN models for selection constitute the set of arms, an edge device's actual system condition is the context, and we consider DNN inference latency l and energy consumption e as the two feedback signals. Our goal is to select optimal DNN models for edge devices that arrive sequentially. For evaluation purposes, we run experiments and collect measured data of five image classification DNN models from TensorFlow Hub running on two cellphones (Vivo V1838A and Google Pixel 3a) and two tablets (Samsung - Galaxy Tab A7 and Vankyo MatrixPad Z4). The energy consumption and latency measurement results are shown in Tables 1 and 2, respectively. We use these four devices to represent four types of actual system conditions (i.e., context in our study) in an edge device requesting a DNN model. In other words, when an edge device arrives, its actual system condition is assumed to fall into one of the conditions as specified by the four different devices in our evaluation. While we can further run experiments on these devices under different usage scenarios to have more fine-grained types of contexts, our current setup is enough to validate our theoretical analysis. Note that although an edge device's basic hardware configuration is accessible to the DNN model provider, its actual system condition (i.e., context in our problem) is only known probabilistically for DNN model selection.

We assume that the utility function for a DNN model selection decision is a weighted linear combination of energy consumption and latency, while noting that other utility functions can also be considered (e.g., the energy-delay product function) provided that they satisfy E✏[Ut(fa↪t)] = Ut(E✏[fa↪t]) where the expectation E✏ [·] is taken over the noise space. In general, the weights in our linear utility function can change for different devices (e.g., energy consumption plays a more important role for devices with a small battery capacity). For illustration, we assume that the utility function can be either U(e↪ l) = -0▷36e - 0▷54l + 1 or U(e↪ l) = -0▷25e - 0▷65l + 0▷9, which is randomly determined. We compare our algorithm with kernel contextual bandit algorithms that utilize the exact context and the most probable context, respectively. We randomly generate the Prt(X) as input at each round. We use the radial basis function kernel k(x↪ x0 ) = exp(-⇢kx - x0 k22 ).

5.2 Results

In Fig. 1(a), we show the average reward achieved by different algorithms. Naturally, the algorithm with the exact true context achieves the highest reward. Nonetheless, the reward of our algorithm is greater than that of the straightforward algorithm that utilizes the most probable context as if it were the true context (similar to a standard UCB algorithm). The reason for the low reward achieved by using the most probable context is that the stored possibly erroneous contexts can be uncorrelated with the received feedback, thus resulting in biased estimation of the feedback functions and hence inaccurate reward prediction further.

In Fig. 1(b), to validate the sub-linear regret, we compare the cumulative regret of our algorithm to the oracle that knows the optimal arm for any probabilistic context bundle. We use entropy of context's probability distribution H(Prt(X)) as a measure for how random the provided context bundle is. We denote Hmax = log2 ♣X♣ as the largest entropy and ⌘ (0  ⌘  1) as a threshold to bound randomness for different rounds, where H(Prt(X))  ⌘Hmax. The smaller ⌘, the more concentrated probabilistic distribution Prt(X) of a context bundle (or, less randomness). If ⌘ = 0, then the distribution only reveals the exact context. The result shows that the regret of our algorithm is sub-linearly increasing, regardless of randomness of probabilistic bundle.

6 RelatedWork

Contextual bandits have been studied in various settings due to their wide applications [Langford and Zhang, 2008]. The study [Li et al., 2010] proposes Lin-UCB algorithm, assuming a linear relationship between its context and expected reward, which applies ridge regression for estimated feedback. As for the nonlinear contextual bandits, [Valko et al., 2013]

and [Deshmukh et al., 2017] both propose kernelized contextual bandit as a nonlinear version of Lin-UCB by finding linear members in RHKS. [Allesiardo et al., 2014] utilizes neural networks to predict the rewards given the context and proposed a multi-expert approach to decide the parameters of networks. [Zhou et al., 2019] provides a formal regret bound for neural network-based contextual UCB. [Badanidiyuru et al., 2014] introduces the concept of contextual bandits with budget constraints, and proposes a resourceful contextual bandits algorithm that provably achieves O(pT) regret bound. Another variant of contextual bandit considers that not all contextual information is accessible [Bouneffouf et al., 2017]. Similarly, [Wang et al., 2016] assumes the existence of hidden features and arm vectors from context together and proposes hLin-UCB algorithm.

Among the studies on probabilistic contextual bandits, a relevant one [Kirschner and Krause, 2019] considers that the agent only knows the probability distribution of context. The major difference is that we consider multiple feedbacks and a time-varying utility function. Another one is [Yun et al., 2017], which studies contextual bandit with perturbation noise on observed context. The authors assume a linear reward function with a single feedback, and propose an algorithm called NLin-Rel that achieves O(T 78 ) regret bound under the assumption of identical noise. Different from this work, we consider a utility function in terms of multiple nonlinear feedback functions with probabilistic contexts.

As for multiple feedbacks, [Lu et al., 2019] proposes an algorithm based on Pareto optimality to solve a multi-objective problem under contextual settings, resulting in a regret bound that increases sub-linearly under the assumption of a linear feedback function. Another relevant work is [Wanigasekara et al., 2019], which considers a multi-objective online contextual ranking system with the assumption that some parameters in both feedback and reward are unknown. By setting linear feedback and logistic utility, the proposed UCB-based algorithm is shown to significantly increase the click-through rate. In contrast, we use a more general time-varying utility function to combine multiple feedback signals and consider probabilistic contexts.

7 Conclusion

In this paper, we consider a new setting of bandit learning with multiple feedback signals, time-varying utility functions and probabilistic context information. For this setting, we propose a multi-feedback probabilistic kernelized UCB algorithm to choose the optimal arm in order to minimize the expected cumulative regret. We derive an upper bound of the expected cumulative regret incurred by our proposed algorithm, with respect to the best action that maximize the expected reward, and show that the bound grows sub-linearly with time. We apply the proposed algorithm to DNN model selection. The simulation results further validate the sub-linearity of the cumulative regret.

Acknowledgments

This work was supported in part by the U.S. NSF under grants CNS-1551661, ECCS-1610471, and CNS-1910208.