Multinomial Logit Bandit with Linear Utility Functions

1 Introduction

In traditional stochastic multi-armed bandit (MAB) [Bubeck and Cesa-Bianchi, 2012], the player selects one fromN items and receives a reward corresponding to that item in each round. The objective is to maximize cumulative reward over a finite horizon of length T, or alternatively, minimize the regret relative to an oracle. Typically, algorithms are designed based on appropriate exploration-exploitation tradeoff which allows the player to identify the best item through exploration whilst not spending too much on sub-optimal ones, and the family of upper confidence bound (UCB) algorithms [Auer, 2002; Chu et al., 2011] and Thompson sampling (TS) [Thompson, 1933; Agrawal and Goyal, 2012] are representative examples. This paper studies a combinatorial variant of MAB, where in each round, the player offers a subset of cardinality K to a user, and receives the reward associated with one of the items in the selected subset 1 . The player faces the problem of determining which subset of items to present to users who arrive sequentially, whilst not knowing user preference. Similar to MAB, we need to solve the exploration-exploitation tradeoff in this problem. However, a naive translation of this problem to MAB is prohibitive, since the number of possible K-cardinality subsets is exponentially large and cannot be efficiently explored within a reasonable sized time horizon. To tackle this issue, different strategies have been proposed in the literature, e.g., [Kveton et al., 2015; Lagr´ee et al., 2016; Agrawal et al., 2017a].

In recent literature, the multinomial logit (MNL) choice model [Luce, 2005; Plackett, 1975] which is widely used in economics is utilized to model user choice behavior by specifying the probability that a user selects an item given the offered set, and above exploration-exploitation problem is referred as the MNL-Bandit problem [Rusmevichientong et al., 2010; Agrawal et al., 2017a; 2017b; Cheung and SimchiLevi, 2017]. Unlike other combinatorial bandit problems, MNL-Bandit problem considers the substitution property among items and leads to non-monotonic reward function. By exploiting specific characteristics of the MNL model, UCBstyle [Agrawal et al., 2017a] and TS-style [Agrawal et al., 2017b] algorithms have been developed to dynamically learn the parameters of the MNL model which are a priori unknown, achieving a regret of ˜O(√NT ) under a mild assumption. Also, a lower regret bound is established in [Agrawal et al., 2017a], by showing that any algorithm based on the MNL choice model must incur a regret of Ω(√NT/K). It is easy to find that the regret depends on the number of candidate items N, making them less preferred in many large scale applications such as online advertising.

In this paper, we use the linear utility MNL choice model (formulated in Section 3) to model user choice behavior given a set of items, rather than traditional MNL model. Specifically, it is assumed that each item in candidate set is described by a d-dimension feature vector, and item utilities of the MNL model can be formulated as linear functions of item features. Based on this, the problem of estimating item utilities (i.e., parameters of the MNL model) is changed to estimating underlying model parameters of linear functions. Since the number of parameters is irrelevant with the number of items, it is possible to achieve more efficient solution when the number of items is large. By taking the UCB approach, we propose an algorithm, titled LUMB (which is short for Linear Utility MNL-Bandit), to dynamically learn the parameters and narrow the regret. The main contributions of this work include:

1 This problem is known as dynamic assortment selection in the literature [Caro and Gallien, 2007; Rusmevichientong et al., 2010], where the selected subset of items forms an assortment.

• To the best of our knowledge, this is the first to use linear utility MNL choice model in sequential subset selection problem. Also, an UCB-style algorithm LUMB is proposed to learn the model parameters dynamically.
• An upper regret bound O(dK√T (logT)2 ) is established for the proposed LUMB algorithm. This regret bound is free of candidate item set size, which means that LUMB can be applied to large item set.
• Empirical studies demonstrate the superiority of the proposed LUMB algorithm over existing algorithms.

The rest of this paper is organized as follows. Section 2 briefly introduces related work. Section 3 and 4 present problem formulation and the LUMB algorithm. Section 5 establishes regret analysis. Section 6 summarizes the experiments, and Section 7 concludes this work with future directions.

2 RelatedWork

Classical bandit algorithms aim to find the best arm with exploration-exploitation strategy. Auer [2002] first proposes a UCB approach in linear payoff setting. Dani et al. [2008] and Abbasi-Yadkori et al. [2011] propose improved algorithms which bound the linear parameters directly. Agrawal and Goyal [2013] propose a Thompson sampling approach. However, because the reward of a subset is not a linear function of item features in the subset, these works cannot be directly applied to our problem.

Another class of bandit works related to our work is combinatorial bandit where the player selects a subset of arms and receive a collective reward in each round. Researchers study the problem mainly on two settings, stochastic setting [Gai et al., 2012; Russo and Van Roy, 2014; Kveton et al., 2015] and adversarial setting [Cesa-Bianchi and Lugosi, 2012; Audibert et al., 2013]. Gai et al. [2012] first learn the problem in linear reward setting and Kveton et al. [2015] prove a tight regret bound. It is generalized to non-linear rewards in [Chen et al., 2016; 2013]. Wen et al. [2015] and Wang et al. [2017] propose contextual algorithms which can handle large item sets. However, these works imply that the reward is monotonic which is not satisfied in MNL-Bandit (Section 3). In practice, as clarified in [Cheung and Simchi-Levi, 2017], the low-reward item may divert the attention of user and lead to lower subset reward.

Rusmevichientong et al. [2010] solve the MNL-Bandit problem and achieve instance-dependent upper regret bound O(logT), and Saur´e and Zeevi [2013] extend to a wider class of choice models. Agrawal et al. [2017a] propose a UCB approach and achieve instance-independent upper regret bound O (√NT ). Agrawal et al. [2017a] propose a Thompson sampling approach with better empirical performance. Recently, some works begin to study variants of classic MNL-Bandit problem. Some works learn the personalized MNL-Bandit problem [Kallus and Udell, 2016; Bernstein et al., 2017; Golrezaei et al., 2014]. Cheung and Simchi-Levi [2017] learn the problem with resource constraints. However, as clarified in Section 1, these works model item utility separately which is not feasible for large item sets.

3 ProblemFormulation

Suppose there is a candidate item set, S = {1, · · · ,N}, to offer to users. Each item i corresponds to a reward ri ≥ 0 and a feature vector xi ∈ Rd . Let X = [x1, · · · , xN] be the feature matrix. InMNL-Bandit, at each time step t, the player selects a subset St ∈ C (S) = {S|S ⊆ S, |S| ≤ K} and observes the user choice ct ∈ St ∪{0}, where ct = 0 represents that the user chooses nothing from St. The objective is to design a bandit policy to approximately maximize the expected cumulative reward of chosen items, i.e., E(∑t rct ).

According to above setting, in each time step t, a bandit policy is only allowed to exploit the item features {x1, · · · , xN}, historical selected subsets, {Sτ |τ < t} and the user choice feedbacks, {cτ |τ < t}.

The user choice follows the MNL model [Luce, 2005; Plackett, 1975]. MNL assumes substitution property among items in a selected subset. Specifically, for item i, the larger the utilities of the other items, the smaller the chosen probability of item i is. The choice probability follows a multinomial distribution,

where vi ≥ 0 is item utility which is a priori unknown to the player. The choice probability of item i in selected subset, St, is linear with its utility, vi. Besides, it is possible that nothing is chosen which is realized by adding a virtual item 0 with utility 1. With the MNL model, we have the expected reward under given utility vector, v = [v1, · · · , vN],

Note that the expected reward is non-monotonic, that is, both the addition of low-reward item to selected subset and increment on utility of low-reward itemmay lead to lower reward. The expected cumulative reward is

Since direct analysis of (3) is not tractable when v is unknown, we analyze the regret instead,

where T is the length of time horizon and S∗ is the optimal subset,

Naturally, the objective is to approximately minimize the expected cumulative regret, Reg (T, v), with appropriate bandit policy. Especially, after enough time steps, an appropriate solution should almost achieve the subsets with highest reward, which implies that the cumulative regret, Reg (T, v), should be sub-linear with T. As each item corresponds to an utility which needs to be estimated separately, this makes the lower cumulative regret bound relevant with item number and will be not feasible for large item sets.

Therefore, linear item utility is introduced where item utility is a linear function of item feature,

where θ∗ is a linear parameter vector unknown to the player. Thus, estimating item utilities will be changed to estimating utility function parameters which can exploit the correlation between items on features, then it is potential to achieve regret bound free of item number, N.

4 Algorithm

We propose an algorithm, called Linear Utility MNL-Bandit (LUMB), which proposes a UCB approach to sequentially estimate linear utility function and approach highest reward. LUMB first estimates the linear parameters of utility function, then constructs the UCB of item utility and subset reward, finally offers the subset with highest reward UCB. Algorithm 1 clarifies the detail of LUMB.

4.1 Estimation of Linear Utility Function

As the choice probability of an item is non-linear with the parameters of utility function, it is difficult to estimate the parameters directly with user choice feedback. Instead, we split the time horizon into epochs like [Agrawal et al., 2017a]. Let L be the number of epochs. In each epoch l, the selected subset, Sl ∈ C (S), is offered repeatedly until that the user chooses nothing from the offered subset. Then, we can obtain the chosen times of each item i ∈ Sl,

where El is the set of time steps in epoch l, ct is the chosen item in time step t.

It can be proven that E(ˆ vi,l) = vi (Lemma 1), which means the empirical average of ˆ vi,l is almost equal to real item utility and irrelevant to other items in the subset. Thus, the estimation of utility function can be simply formulated as a linear regression which directly approaches empirical samples of ˆ vi,l. Specifically,

Algorithm 1 Linear Utility MNL-Bandit

where λ is a constant regularization coefficient. Then, we can obtain close-form solution

where Id is a d-by-d identity matrix.

4.2 Construction of Upper Confidence Bound

We construct the UCB of item utility, which is proven in Lemma 2, as

where α is constant. Let vUCB l = [vUCB 1,l , · · · , vUCB N,l ]. Then, the UCB of the highest reward, R(S∗ , v), is constructed as the highest reward with vUCB l (Lemma 5). The corresponding subset is

and we offer the subset Sl+1 in epoch l + 1.

It is hard to get Sl+1 by directly solving the above optimization problem. According to [Davis et al., 2013], the above optimization problem can be translated to a linear program problem,

Then, Sl+1 = {i|wi > 0, i > 0}.

5 Regret Analysis

In this section, we analyze the upper regret bound of Algorithm 1 to theoretically identify the convergence performance. Without loss of generality, we first declare the assumption in the following analysis.

According to the assumption, we have that ∀i ∈ S, vi ≤ 1. Moreover, we let λ = 1. Then, we give the upper bound of regret in Theorem 1 in advance which is proven in Section 5.3. We can achieve result similar to Theorem 1 when the parameters in Assumption 1 are bounded by finite constants.

Theorem 1. Following the process in Algorithm 1, let

then the upper bound of Reg (T, v) is

The proof is separated into three steps. We first prove the correctness of the constructed UCB of utility and the cumulative deviation between UCB of utility and real utility which is sublinear with respect to T. Then we prove that the deviation between UCB of reward and real reward can be bounded by deviation of utility, finally the upper bound of cumulative regret can be proved by combining the above two results.

5.1 Analysis of Utility

We first prove the distribution of ˆ vi,l .

Lemma 1. With the definition in Eq. (6), ∀l ≤ L, i ∈ Sl, ˆ vi,l follows geometric distribution, that is

Because of the space limitation, proof will be attached in a longer version. According to above Lemma, the deviation between ˆ vi,l and real utility is unbounded. This makes the prove of utility UCB difficult. Fortunately, the probability P (ˆ vi,l > β) decays exponentially when β increases. We bound ˆ vi,l in a relative small interval with high probability. Then, we can prove the utility UCB as below.

Lemma 2. With definition of vUCB i,l in Eq. (10) and definition of ˆ vi,l in Eq. (6), if β ≥ 2 log2 T, ∀τ ≤ l, j ∈ Sl, ˆ vj,τ ≤ β, then ∀i ∈ S, l ≤ L,

with probability at least

Proof. Let ∆i,l = |θ⊤ l xi - vi|, we just need to prove

According to Lemma 1, when ˆ vi,l ≤ β,

Note that the result of E(ˆ vi,l - vi) is irrelevant with l. Let ϵi = E (ˆ vi,l - vi).

We prove the bound of two parts respectively. Let ui = ˆ vi,τ - vi - ϵi, sl = ∑τ≤l ∑i∈Sτ xiui, it is easy to prove that

then, with Lemma 9 in [Abbasi-Yadkori et al., 2011], we can prove that with probability

we have that

Moreover, with Cauchy-Schwarz inequality, the other part is bounded as

The lemma can be proven by combining Eq. (17) and Eq. (18).

Moreover, we prove the bound of cumulative utility deviation.

Lemma 3. Following the process in Algorithm 1, the cumulative deviation between utility UCB and real utility can be bounded as∑L

Proof is similar to the proof of Lemma 3 in [Chu et al., 2011]. Because of the space limitation, the proof will be attached in a longer version. Lemma 3 shows that the bound of cumulative deviation is sub-linear with epoch number, and the average deviation in each epoch will vanish after enough epochs.

5.2 Analysis of Reward

We first estimate the deviation between estimated reward and real reward of Sl with the result of Lemma 3.

Lemma 4. In each epoch l of Algorithm 1, if ∀i ∈ Sl,

then the cumulative deviation between estimated reward and real reward of Sl is

Because of the space limitation, proof will be attached in a longer version. This Lemma means that the deviation of subset reward is bounded by deviation of item utilities in the subset.

Lemma 5. (Lemma 4.2 in [Agrawal et al., 2017a])With the reward defined in Eq. (2), suppose there are two subsets, ˜ SUCB and ˜ S, that

If ∀i ∈ ˜ S, vUCB i ≥ vi, then the rewards satisfy the inequality

Lemma 5 shows that the estimated reward of subset Sl is an upper bound of real highest reward. Then we can easily bound the regret in each epoch with Lemma 4 and Lemma 5.

Lemma 6. (Regret bound in a single epoch) In each epoch l of Algorithm 1, if ∀i ∈ Sl ∪ S∗

then the regret of epoch l is

5.3 Upper Bound of Regret

We first prove a more general version of Theorem 1 with parameters, α and β.

Lemma 7. Following the process in Algorithm 1, if β ≥ 2 log2 T, the cumulative regret, defined in Eq. (4), can be bounded,

Proof. We obtain the bound of regret respectively in two situations: the item utility inequality in Lemma 2 is (or not) satisfied. We model the event that the item utility inequality in Lemma 2 is not satisfied as

Then, it is easy to bound the probability of Al,

Let ˜ Al be the complement of Al. Then, the regret can be splited into two parts, that is,

where I (A) is an indicator random variable whose value is 1 when A happens, othewise 0. We first consider the situation that Al happens,

Then, we consider that Al does not happen. According to Lemma 6 and Lemma 3,

Finally, we can finish the proof by adding Eq. (27) and Eq. (28).

With Lemma 7, Theorem 1 can be proven by setting

As our method is in the similar framework of MNLBandit [Agrawal et al., 2017a] whose lower bound is ˜O (√T ), our regret bound matches the lower bound up to logarithmic terms with respect to T .

6 Experiments

In this section, we evaluate LUMB on synthetic data and compare it to three existing alternative algorithms. We demonstrate the superiority of LUMB on cumulative regret. Moreover, we show that the estimated linear parameters of utility function and utilities will asymptotically converge to the real value.

6.1 Setting

The synthetic data is generated randomly. N rewards are sampled from interval (0, 1] uniformly. d-dimension parameter vector of utility function, θ∗ , is sampled from [0, 1]d uniformly, then is normalized to 1. N d-dimension feature vectors are sampled from [0, 1]d uniformly. To follow the experiment setting in [Agrawal et al., 2017b], feature vectors are normalized so that item utilities distribute uniformly on [0, 1]. Experiments are all performed on ten randomly generated data sets and the results show below are all average of results on these data sets.

Three alternative algorithms are compared:

• UCB-MNL [Agrawal et al., 2017a]: This algorithm proposes a UCB approach with MNL choice model.
• Thompson-Beta [Agrawal et al., 2017b]: This algorithm proposes a Thompson sampling approach with MNL choice model.
• Thompson-Corr [Agrawal et al., 2017b]: This algorithm is a variant of Thompson-Beta which samples item utilities with correlated sampling.

6.2 Results

We conduct empirical experiments on synthetic data sets with N = 1000,d = 10. Subset size K is set to 10. Figure 1 shows the cumulative regret on the synthetic data sets, which is normalized by best reward, i.e., Reg (t, v) /R (S∗ , v). Note that the axis of cumulative regret is plot in a logarithm style for the convenience of observing the trend of LUMB regret on time horizon. The cumulative regrets increase slower when time step increases. Besides, we can see that the cumulative regret of LUMB is much smaller than the alternative algorithms through the time horizon.

We evaluate the convergence of utility vector on synthetic data sets with N = 1000,d = 10. Figure 2 shows the deviation between estimated mean utility and real utility, which is normalized by the norm of real utility, i.e., ‖θ⊤ t X-v‖/‖v‖. The deviation of LUMB decreases fast in the early stage and achieve smaller deviation compared to the alternative algorithms.

Moreover, we evaluate the deviation of estimated linear parameter vector in Figure 2. The deviation is normalized by the norm of real parameters, i.e., ‖θt -θ∗ ‖/‖θ∗ ‖. Note that the deviation also decreases fast in the early stage and asymptotically converges to zero finally. This demonstrates that LUMB can correctly estimate the linear parameters.

7 Conclusion

We study the sequential subset selection problem with linear utility MNL choice model, and propose a UCBstyle algorithm, LUMB. Also, an upper regret bound, O (dK√T (logT)2), is established, which is free of candidate item number. Experiments show the performance of LUMB. In the future work, we are interested in extending the idea to other choice models such as nested MNL.