We tackle the problem of recommending products in the online recommendation scenario, which occurs many times in real applications. The most famous and explored instances are news recommendations and advertisements. In this work we propose an extension to the state of the art Bandit models to not only take care of diferent users' interactions, but also to go beyond the linearity assumption of the expected reward. As applicative case we may consider situations in which the number of actions (products) is too big to sample all of them even once, and at the same time we have several changing users to serve content to.
INTRODUCTION AND RELATED WORKS
In the Recommender Systems (RS) field the most valuable
information to rely on are user interactions. That is the reason why
Collaborative Filtering methods are the current state of the art model, or
at least the ones that give the most important contribution when
recommending. In the web we have many real applications such
as: computational advertisement, news recommendation or on-line
streaming, that do not fit the classical recommending scenario.
Their peculiarity is the fact that both the sets of active users and
available products are very fluid , therefore they change with time
[
In this on-line recommendation scenario, in particular when
we also have contexts besides item feature vectors, multi-armed
bandits techniques have shown to be an excellent solution and are
the current state of the art model. Most of the previous eforts on
contextual bandits were spent on looking to the recommendation
problem from a single user standpoint. We may find just a few
preliminary works along the collaborative direction [
With this project we also want to consider scenarios where the
set of products is too big to be explored entirely, therefore we
decide to exploit kernel methods [
In a nutshell, in this paper we demonstrate that Collaborative
Bandits [
The following section details the modeling assumptions and Section 3 presents the proposed algorithm. 2
We assume that the learning process can be divided in T discrete rounds t = 1, . . . , T . At time t , the learner receives a user index ut ∈ U = {1, . . . , n} to provide recommendation to, and a set of available contexts1 (arms) Xt = {xt,1, . . . , xt,ct } ⊆ ℜd . The learner has to select one of the content feature vectors xt ∈ Xt to recommend to ut , and then it observes a payof vt whose expectation is ϕ(xt )⊤θut , where (i) we assume there exists a mapping ϕ : ℜd → H that maps the data to a Hilbert Space, and (ii) θut ∈ H is unknown from the learner. More specifically, we call ℜd the primal space and H the related reproducing kernel Hilbert space.
The learner aims at maximizing the total payof over the T rounds: Ít vt . This goal is usually translated in a minimization/bounding problem of a loss variable called (pseudo-)regret, that measures the gap of the learner policy wrt. the optimal one (being aware of parameters (θu )u ∈U ). The regret at time t is defined as: rt = max ϕ(x)⊤θut − ϕ(xt )⊤θut x∈Xt (1)
Let define the kernel function as: k(x, x’) := ϕ(x)⊤ϕ(x’) ∀x, x’ ∈ ℜd . From that function and given a dataset composed by t records x1, . . . , xt ∈ ℜd , we define the kernel matrix as Kt := k(xi , xj )i, j ≤t .
It’s worth noting that in such scenario there is no need to get access to content representation. As we clarify in next section, the algorithm only requires to know the kernel value k(x, x’) for any pair (x, x’) of contents which have been recommended. Similarly, the estimates of the unknown parameters (θu )u ∈U are never explicitly expressed.
In order to represent the collaborative efect, we also assume that users and contents can be co-clustered as expressed in the following. First, for each content vector x ∈ ℜd , the set U can be 1Along the paper, we identify contexts as the concatenation of item feature representation and real contextual properties(when available). Therefore they fully characterize the available items properties. clusterized as C(x) = U ix 1≤i ≤m(x), such that (i) U = Ðmi=(1x ) U ix and U i ∩ U j = ∅ for any 1 ≤ i < j ≤ m(x), and (ii) the users belonging to the same cluster react similarly when the content with feature vector x is recommended to them. Namely, if two users u and u ′ belong to the same cluster U kx , then ϕ(x)⊤θu − ϕ(x)⊤θu′ ≤ γ for some unknown gap parameter γ ≥ 0.
Second, the content-vectors are themselves clustered in sets X 1, X 2, . . . , Xm such that two contents belonging to the same cluster induce the same clustering on U : ∀1 ≤ j ≤ m, ∀x, x′ ∈ X j , C(x) = C(x′).
Clearly the co-clustering mapping is not known and is one of
the two main learning objective of the proposed algorithm. The
novelty compared to [
The proposed algorithm (Algorithm 1) adopts the upper confidence bound paradigm to manage the exploration-exploitation tradeofs. In detail the estimation of the expected reward and of its corresponding confidence bound is done given the estimations of the clustering, which will be depicted later on. At time-step t , for a user u and an item x, we first define the estimation θˆu,t,x as the solution of the optimization problem Õ (vt − ϕ(x¯t )⊤θ )2 + λ∥θ ∥2, (2) arg min θ
s ∈Tu,t,x where Tu,t,x is composed of past time-steps s at which the user us belongs to the same (estimated) cluster as u (given x). By denoting Φu,t,x the matrix which rows correspond to the vectors {ϕ(xt )⊤, t ∈ Tu,t,x}, Ku,t,x the product Φu,t,xΦu⊤,t,x, and ru,t,x the vector [rt , t ∈ Tu,t,x]⊤, we get θˆu,t,x = Φu,t,x⊤(Ku,t,x + γ I )−1ru,t,x. This lead to the following estimate for the expected reward of content x wrt. user u at time t : (3) where ku,t,x = Φu,t,xϕ(x) = [k(x, xt ), t ∈ Tu,t,x]⊤. Note that this equation expresses vˆu,t,x only after past rewards and kernel distance between contents.
Similarly, the confidence interval on-top of vˆu,t,x is expressed as
1 q σˆu,t,x = λ 2
(k(x, x) − ku⊤,t,x(Kt + γ I )−1ku,t,x] log(t + 1). (4)
Finally, the chosen arm is the one that maximizes the upper confidence bound : xt = arg max vˆut ,t,x + ησˆu,t,x, x∈Xt (5) where η ≥ 0 is the exploration parameter.
It remains to explain the way the clusterings are estimated. The clusterings are represented by maintaining undirected graphs for which each connected component represents a cluster. One graph stands for contents, and for each contents-cluster induced thereof there is one graph to cluster users. The algorithm starts with fully connected graphs : every contents and every users are reachable each other. Thereafter, after getting feedback vt , we first delete
Algorithm 1 Collaborative Kernalized Bandits 1: Initialize the user graph as connected over U and the item graph as connected over I 2: for t = 1,2,. . . do 3: receive ut ∈ U and the set of contents Xt 4: for x ∈ Xt do //Collaborative part 5: identify the current user cluster 6: compute cluster-aggregated variables vˆu,t,x and σˆu,t,x 7: select recommended content x¯t according to Equation (5) 8: receive payof vt 9: update clustering graphs edges from the users-graph associated to the selected content. The deleted edges (ut , u) are whose such that: |vˆu′ t ,t,x¯t − vˆu′ ,t,x¯t | ≥ η′σˆu′t ,t,x¯t + η′σˆu′,t, x¯t , (6) where the prime on v and σ denotes the fact that the values are computed similarly to equations (3) and (4), while only focusing on past-iterations concerning u or u ′. Parameter η′ > 0 controls the expected gap between clusters.
Finally, for each content x in the same content-cluster as x¯t , we compute the neighborhood N (x) = {u : |vˆu′ t ,t,x − vˆu′ ,t,x | ≤ η′σˆu′t ,t,x + η′σˆu′,t,x}. We remove each edge (x¯t , x) such that this neighborhood difers from the one induced by the freshly updated users-graph. 4 CONCLUSIONS AND FUTURE WORKS In this paper we demonstrate that collaborative bandits may be extended, through kernel trick, and get out of the linearity assumption.