Online systems utilize user data, such as demographics, past performance, preferences and skillset to construct an accurate model of users and maximize personalization. Some of these user features are “shallow” traits which seldom change (e.g. age, race, gender) while others are “deep” traits that are more volatile (e.g. performance, goals, interests). In this work, we explore how reasoning about this diversity of user features can enhance performance of personalized systems. By modeling the personalization process as a Reinforcement Learning (RL) problem, we introduce Diversity Aware Bandits for Intervention Personaliztion (DABIP), a novel contextual multi-armed bandit algorithm that leverages the dynamics within user features to cluster users while maximizing outcomes. We demonstrate the eficacy of this approach using two real world datasets from diferent domains.
1. Introduction
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
bandit algorithm, as a baseline in two domains. Our results show that DABIP achieves a higher
average reward than LOCB in each domain when predicting intervention outcomes per user.
2. Background
We give an overview of CMAB algorithms and diversity.
2.1. Contextual Multi-Armed Bandits
Contextual Multi-Armed Bandit (CMAB) is an extension of the Multi-Armed Bandit (MAB)
problem where, at each timestep, the agent is presented with a list of arms (actions) and a
context vector (additional data) about the environment. The agent needs to select and perform
a single action. The agent then receives a reward for that arm only. Over time, the agent learns
the underlying reward distribution of each arm and how that distribution is influenced by the
context, and endeavors to maximize the total reward received over time [
= ∑[ ,
( =1 , ∈ , , ) − , ] (1) where, at each round, , we compute the regret by taking the reward achieved from the best possible arm choice, , , and subtracting the reward achieved from the agent’s chosen arm, . We also assume that each user, i, has a set of features, F, of length q such that at any time, t, there exists , = { ,1, , ,2, ...,
,, }.
3.2. DABIP Algorithm
The algorithm has three main steps: (1) Calculate the underlying feature dynamics of all users
over time, (2) Form clusters of users with similar feature dynamics, then (3) Utilize the clusters
and past user performance to personalize interventions to users. The full details of the algorithm
are given in Appendix A.
4. DABIP Performance in Multiple Domains
We apply the DABIP algorithm to two datasets from two diferent domains.
4.1. Eedi Dataset
Eedi1 [
Our results show that identifying and extracting feature dynamics can improve RL algorithm performance, harnessing human diversity proxy information. We argue that identifying the highly dynamic features allows DABIP to search the space of context-reward associations more completely and more quickly, thus leading to better reward. This theory requires further testing, but the results of applying DABIP to real data are promising, and further research into augmenting our clustering approach is planned for the future. 2https://github.com/banyikun/LOCB 6. Conclusion In this work, we designed, implemented, and tested DABIP, a diversity aware RL algorithm that uses feature dynamics as a proxy for underlying human-contextual diversity. We hypothesized that this technique could improve RL algorithms that operate in environments where user data is highly dynamic, and this proved true when applying DABIP to two diferent domains. We believe that extensions to DAABIP can make it an ideal tool for building more performant personalized applications.
Acknowledgements This work was supported in part by the European Union Horizon 2020 WeNet research and innovation program under grant agreement No 823783. [16] S. Li, W. Chen, K.-S. Leung, Improved algorithm on online clustering of bandits, arXiv preprint arXiv:1902.09162 (2019). [17] S. Li, A. Karatzoglou, C. Gentile, Collaborative filtering bandits, in: Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, 2016, pp. 539–548.
A. The DABIP Algorithm
We now give a detailed description of the algorithm. DABIP (Algorithm 1) is initialized with the
number of clusters to maintain () , the frequency with which to update the clusters (
frequency with which to update the user feature dynamics ( ), and an exploration parameter ( ).
), the
Then, all users are initialized (Lines 2-4) and the algorithm begins iterating over all timesteps
sequentially (Line 5). In each round, t, a user is presented along with the set of context vectors
(Line 6). DABIP begins without any user clusters. DABIP first checks if there are any clusters
(Line 7), and if there are none (length( ≤ 0 )), then the arm with the highest upper confidence
bound (UCB) is chosen. As is standard practice [
Finally, to choose an arm, we compare the UCB using the user’s unknown bandit parameter, ,̂ to the UCB using the average unknown bandit parameter of all users in cluster , , ̂ 10-12). The maximum of these two UCB values is selected (Line 13). The reasoning behind this , (Lines is that previous work has established that clustering users by unknown bandit parameter is an efective strategy for identifying users who behave similarly in a task, thus resulting in a collaborative filtering efect [
With an arm chosen and pulled, we observe the reward, , then update user parameters and cluster parameters for the cluster that user resides in (Lines 17-22). Then, any user features, , are updated (Lines 23-24). This step will be tailored to the specific implementation and dataset, as the number, type, and sophistication of the user features will be entirely dependent on the problem definition and setup. The count for how many times user has been considered is also updated (Line 25). Finally, the most up to date clusters, , are calculated and returned by the CLUSTER function (Line 26 - see Algorithm 2), which ends round t.
The second component of DABIP is clustering users based upon the similarity of their feature dynamics. The CLUSTER algorithm (Algorithm 2) assumes that each user has a set of features, F, of length q such that at any time, t, there exists , = { ,1, , ,2, ..., ,, }. The values of each individual user feature, ,,
may change over time, which can be tracked to cluster users based upon the similarity of their feature dynamics. To do this, one can observe the value of a feature at some initial timestep, then again at a later timestep, and calculate the absolute value of the diference between them. More formally, at some initial timestep, , we store the values of all features for a given user, : ,
. We also initialize a set that contains one value for each a recommendation to user . Thus, each time user is selected by the algorithm, we can update , based upon the observed user features at timestep t, and increment , by 1. Once the agent , c l u s t e r u p d a t e f r e q u e n c y , u s e r f e a t u r e d y n a m i c s R e q u i r e : u p d a t e f r e q u e n c y , e x p l o r a t i o n p a r a m e t e r
←
0 1 : e a c h f o r d
o ∈
2 : ← , ←
0 3 : , 0 , 0 ←
0 4 :
f o r d
o ← 1 , 2
... 5 :
r e c e i v e a n d o b t a i n ∈ = { , ..., } 6 : 1 , 2 ,
, l e n g t h o
f i f t h e
n ≥
0 7 :
C l u s t e r w h e r e r e s i d e s a t r o u n d
t ←
8 : ,
1 ̂ −
1 ∑ ←
9 : , −
1 , −
1 ∈ |
| , , −
1 , − 1
1 ̂ −
1 w h e r e ∑ ← + ← 1 0 : ∈ , , ,
, , , −
1 ∈
√ |
| , , , , , −
1 , − 1 ̂ −
1 ←
1 1 : , −
1 , −
1 ̂ −
1 w h e r e ← + ← 1 2 : ∈ , , ,
, , , −
1 √ ,
← ( ,
) 1 3 :
e l s e 1 4 : ̂ −
1 ←
1 5 : , −
1 , −
1 ̂ −
1 w h e r e ← + ← 1 6 : ∈ , , ,
, , , −
1 √ ,
p u l l a n d o b s e r v e r e w a r d
1 7 :
−
1 ← +
1 8 : , , − 1
← +
1 9 : , , − 1
l e n g t h o
f i f t h e
n ≥
0 2 0 : −
1 ← +
2 1 : , , − 1
,
, ← +
2 2 : , , − 1
,
, f o r d
o ∈
2 3 : , ,
, u p d a t e a c c o r d i n g t o i n f o r m a t i o n g a t h e r e d f r o m p r o b l e m s e t u p a n d 2 4 : , , ← +
1 2 5 : ,
, ← , ) 2 6 :
h a s m a d e a r e c o m m e n d a t i o n t o a u s e r t i m e s , s a y a t t i m e , t h e f e a t u r e
, d y n a m i c s f o r u s e r i , , c a n b e c o m p u t e d b a s e d u p o n h o w t h e f e a t u r e s h a v e c h a n g e d b e t w e e n a n d ( A l g o r i t h m 2
L i n e 2 ) .
T h e d ife r e n c e s a r e s u m m e d o v e r t i m e t o c o m p u t e a n d i s a h y p e r p a r a m e t e r t h a t c o n t r o l s h o w o tfe n u s e r f e a t u r e d y n a m i c s a r e u p d a t e d .
A tfe r t h i s c a l c u l a t i o n , i s s e t t o a n d i s s e t t o 0 .
T h e p r o c e s s r e p e a t s w h e n = u n t i l a l l , , t i m e s t e p s a r e c o m p l e t e .
B y p e r f o r m i n g t h i s o p e r a t i o n f o r e v e r y u s e r, w e c o n s t a n t l y h a v e a c c e s s t o w h i c h r e p r e s e n t s t h e c u r r e n t d y n a m i c s o f u s e r i ’ s f e a t u r e s .
W
e
u
s
e
t
h
e
s
i
m
i
l
a
r
i
t
y
b
e
t
w
e
e
n
u
s
e
r
’
s
v
a
l
u
e
s
t
o
c
l
u
s
t
e
r
t
h
e
m
t
o
g
e
t
h
e
r,
r
a
t
h
e
r
t
h
a
n
a
s
d
o
n
e
i
n
p
r
e
v
i
o
u
s
w
o
r
k
s
[
T o t h a t e n d o r = { ...
} 1 , 2 , , s i m p l i c i t y , w e a s s u m e t h a t e a c h u s e r m u s t a p p e a r i n e x a c t l y o n e c l u s t e r a n d a l l u s e r s a r e s p l i t 2: 3: 4: 6: 7: ← 5: if t %
== 0 then ← sort in ascending order + 1 and the rest of size ℎ() 8: return
for the full clustering pseudocode. DABIP updates clusters after a period of timesteps have passed . This is because calculating the dynamics of the user features requires observing changes in those features over a period of time. To re-cluster after every timestep would not allow suficient time to observe any true dynamics, so we update for each user after every timesteps in which that user is selected.
Algorithm 2 Require: user feature dynamics update frequency , user update counts Y, cluster update frequency
, user 1: if ==
then = ∑ =1 {| , − ,
|} ← split( ,s) where split(x,y) splits x into ℎ()% groups each of size ℎ()