Expert with Clustering: Hierarchical Online Preference Learning
  Framework
Tianyue Zhou Jung-Hoon Cho Babak Rahimi Ardabili Hamed Tabkhi Cathy Wu
Emerging mobility systems are increasingly capable of recommending options to
mobility users, to guide them towards personalized yet sustainable system
outcomes. Even more so than the typical recommendation system, it is crucial to
minimize regret, because 1) the mobility options directly affect the lives of
the users, and 2) the system sustainability relies on sufficient user
participation. In this study, we consider accelerating user preference learning
by exploiting a low-dimensional latent space that captures the mobility
preferences of users. We introduce a hierarchical contextual bandit framework
named Expert with Clustering (EWC), which integrates clustering techniques and
prediction with expert advice. EWC efficiently utilizes hierarchical user
information and incorporates a novel Loss-guided Distance metric. This metric
is instrumental in generating more representative cluster centroids. In a
recommendation scenario with $N$ users, $T$ rounds per user, and $K$ options,
our algorithm achieves a regret bound of $O(N\sqrt{T\log K} + NT)$. This bound
consists of two parts: the first term is the regret from the Hedge algorithm,
and the second term depends on the average loss from clustering. The algorithm
performs with low regret, especially when a latent hierarchical structure
exists among users. This regret bound underscores the theoretical and
experimental efficacy of EWC, particularly in scenarios that demand rapid
learning and adaptation. Experimental results highlight that EWC can
substantially reduce regret by 27.57% compared to the LinUCB baseline. Our work
offers a data-efficient approach to capturing both individual and collective
behaviors, making it highly applicable to contexts with hierarchical
structures. We expect the algorithm to be applicable to other settings with
layered nuances of user preferences and information.