The Nah Bandit: Modeling User Non-compliance in Recommendation Systems

We summarize our contributions as follows:

1. 1.

   We introduce a novel bandit framework—Nah Bandit—for modeling the online preference learning problem, in which users go ‘nah’ to the recommendation and choose their originally preferred option instead. This framework distinctively incorporates user observable non-compliance, offering the potential to accelerate preference learning.

2. 2.

   We propose a user non-compliance model as the simplest way to solve the Nah Bandit problem, which parameterizes the anchoring effect. We analyze its sample complexity to show the speed at which we can learn user preference parameters. Based on this model, we propose a hierarchical contextual bandit framework, Expert with Clustering (EWC). This framework effectively utilizes non-compliance feedback and hierarchical information, enabling rapid and accurate learning of user preferences.

3. 3.

   We establish the regret bound of EWC. In a recommendation scenario with $N$ users, $T$ rounds per user, and $K$ user clusters, EWC achieves a regret bound of $O(N\sqrt{T\log K}+NT)$, achieving superior theoretical performance in the short term compared to LinUCB.

The field of recommendation systems has been significantly shaped by various supervised learning methods. A foundational approach is Collaborative Filtering (CF), which bases its recommendations on the similarity between users [18] or items [25]. Matrix Factorization (MF) [26], a specialized form of collaborative filtering, is notable for decomposing the user-item interaction matrix into lower-dimensional matrices representing the latent user and item factors. Recent advancements have led to the introduction of online versions of these traditional methods, like Online Collaborative Filtering [27] and Online Matrix Factorization [28], to address the dynamic nature of user preferences and real-time data.

Decision tree-based methods, such as Gradient Boosting Machines [29] and Random Forests [30], and their online versions [31, 32] represent another class of supervised learning methods in recommendation systems. These methods are widely used in the area of advertisements due to their ability to learn nonlinear features. XGBoost [33], an important variant of Gradient Boosting Machines, provides fast and accurate recommendations and is used as a baseline in our experiments.

However, these supervised recommendation methods often overlook the potential impact of the anchoring effect. Our research aims to address this oversight by reducing the bias introduced by the anchoring effect to make more accurate recommendations.

The contextual bandit framework offers an efficient solution for recommendation systems. This concept was initially explored by [34], focusing on the use of confidence bounds within the exploration-exploitation trade-off, particularly in contextual bandits with linear value functions. Building on this, [1] extended this framework to personalized news recommendations by introducing LinUCB algorithm, setting a benchmark in the field. More recently, advanced algorithms such as NeuralUCB [11] have been developed, leveraging neural networks to model complex, non-linear relationships in the data, further enhancing the flexibility and effectiveness of contextual bandits. The integration of clustering techniques into the contextual bandit framework represents a significant advancement in the field. The foundational unsupervised learning algorithm, K-Means clustering, introduced by [35], laid the groundwork for this development. Based on this, [36] proposed a personalized recommendation algorithm using hierarchical tag clustering. With the development of contextual bandit, [22] proposed a novel approach to cluster users within the contextual bandit framework, using graphs to depict user similarities. A notable progression in this area is the DYNUCB algorithm [21], which is a dynamic clustering bandit algorithm that divides the population of users into multiple clusters and customizes the bandits for each cluster. Additionally, [37] proposes the LOCB approach which enhances performance by focusing on the accuracy of clustering and its impact on regret minimization in bandit algorithms. Building on these works, we also adopted clustering to segment users into several groups and tailor recommendations to each group.

We refer to user non-compliance as any action taken by the user that is not among the recommended action(s). Contextual bandit methods have been extended to consider user abandonment, for example, deleting an app or leaving before re-engaging later. Users may abandon the system for a variety of reasons, including fatigue from overexposure to irrelevant content or boredom from seeing too many similar recommendations [38], lack of trust [39], or non-alignment with the user’s immediate self-interests [40]. Some solutions proposed include incorporating the risk of user abandonment into the recommendation algorithms [41, 42, 43], or never offering recommendations that would yield lower expected reward than a user would have achieved if she acted alone [40]. Our work considers a softer form of user non-compliance, in which the user still selects an option within the same action class (e.g., mobility trip option), albeit not a recommended one. Our algorithm seeks to quickly learn user preferences by acknowledging such non-compliance and learning from these user actions. This novel approach provides a holistic view of user preferences, which is crucial for understanding the comparative utility of options and accelerating preference learning, especially in scenarios with limited data.

In the Nah Bandit problem, users may say ‘nah’ to the recommendation and choose their originally preferred option instead. This means the losses (or rewards) come from user’s choice. We define the Nah Bandit in a recommendation problem as follows. This framework combines elements of both supervised learning and partial feedback in a bandit setting.

Conversely, in the traditional bandit framework for recommendation systems, the user is assumed to select only from the recommended options, and therefore, the losses (or rewards) are derived solely from those recommended options.

Nah Bandit differs from both traditional contextual bandit and supervised learning. Bandit framework utilizes feedback only from the recommended option, therefore its exploration-exploitation trade-off handles the anchoring effect of recommendation on users. In contrast, the supervised learning framework assumes the user’s choice and feedback are independent of the recommendation, allowing the user to choose any option. In the Nah Bandit problem, the user can choose any option, and we use the user’s feedback to learn their preferences. The feedback remains partial because different recommendations can lead to different outcomes. For example, some users might rely heavily on recommendations and are more likely to choose the recommended option, while others may carefully select from all options to choose the one that best matches their preferences. Table I compares the Nah Bandit, traditional bandit problem, and supervised learning.

If we adopt supervised learning approaches to solve the Nah Bandit problem, they may lead to sub-optimal recommendations because they do not account for the anchoring effect of recommendations on the feedback. Conversely, if we adopt traditional bandit approaches, the recommended options are viewed as the pulled arms of the bandit. In this case, we receive zero reward from the pulled arm if the user chooses none of the recommended options, and the feedback from the user’s actual choice is not used to update the recommendation system. The Nah Bandit framework offers a potential solution concept to accelerate preference learning by effectively utilizing non-compliance feedback.

We further incorporate contexts of users and options in the Nah Bandit. Additionally, we extend the recommendation from single-user to a multi-user, and assume a hierarchical structure among users. We formulate our problem as follows.

Consider a scenario where a provider is tasked with recommending a set of options, denoted as $\mathcal{O}$, to a population of users $\mathcal{U}$ with hierarchical structure, with the total number of users being $N:=|\mathcal{U}|$. Each user, identified as $i$ in the set $[N]$, is represented by a unique user context vector $u_{i}\in\mathbb{R}^{D}$. At each decision-making round $t$ within the total rounds $T$, the provider is presented with the user context $u_{i}$ and a specific subset of options $O_{i,t}\subset\mathcal{O}$, where $A:=|O_{i,t}|$ represents the number of options in the subset. For simplicity, we assume that the value of $A$ remains constant across all subsets $O_{i,t}$. Each option indexed by $a\in[A]$, is defined by an option context vector $x_{i,t,a}\in\mathbb{R}^{d}$. Upon receiving this information, the provider recommends one option, labeled $r_{i,t}$, from the set $[A]$ to the user. Subsequently, the provider observes the user’s choice, denoted as $y_{i,t}$, and incurs a loss $l(r_{i,t},y_{i,t})$, determined by a predefined loss function known to the provider. It is important to note that the user’s choice $y_{i,t}$ may be influenced by the recommended option $r_{i,t}$.

The objective of this scenario is to minimize the total cumulative regret over all users and decision rounds. This is mathematically formulated as $\min_{r_{i,t},\forall i,t}\sum_{i=1}^{N}\sum_{t=1}^{T}l(r_{i,t},y_{i,t})$.

A key assumption in our problem is that the user’s choice may be influenced by the anchoring effect. This leads to a scenario of partial feedback akin to a contextual bandit setting, where learning user preferences can be challenging. [16] uses a rating drift, defined as the actual rating minus the predicted rating, to represent the anchoring effect. They found that, in aggregate, the rating drift is linear and proportional to the size of the recommendation perturbation. This means that the more we recommend one option, the higher rating the user will give to this option. However, the slope of this linear relationship, which represents the user’s additional preference for the recommended options, is unknown. Building on [16], we propose a user non-compliance model to discern this additional preference, thereby addressing the issue of the anchoring effect.

Assume that each user $i$ has a fixed but unknown preference parameter $\boldsymbol{\theta}_{i}\in\mathbb{R}^{d}$. Given $\boldsymbol{\theta}_{i}$, we can make predictions using a known function $\hat{y}(\boldsymbol{\theta}_{i},\mathbf{x}_{i,t})$. The key idea is that we assume there exists a $\theta_{i,\text{rec}}$ within $\boldsymbol{\theta}_{i}$ that quantifies the additional preference toward recommended options. Users with a high $\theta_{i,\text{rec}}$ highly rely on the recommended option, while users with $\theta_{i,\text{rec}}=0$ select the option with the highest utility for them, regardless of the recommendation. Our goal is to learn this $\theta_{i,\text{rec}}$ for each user.

We propose a user non-compliance model, which is a linear model that parameterizes the user’s dependence on the recommendation. First, we incorporate a context $x^{\text{rec}}_{i,t,a}\in\mathbb{R}$ in each option context $x_{i,t,a}$ which represents the degree to which this item is recommended to the user. For example, $x^{\text{rec}}_{i,t,a}=\mathbbm{1}_{r_{i,t}=a}$. The utility of each option is then defined as $U_{i,t,a}=x_{i,t,a}^{\intercal}\boldsymbol{\theta}_{i}$. Let $\mathbf{U}_{i,t}=[U_{i,t,1},U_{i,t,2},\ldots,U_{i,t,A}]$ represent the utility vector. The probability of selecting each option is predicted as $\mathbf{p}_{i,t}=\boldsymbol{\sigma}(\mathbf{U}_{i,t})$, where $\boldsymbol{\sigma}(\cdot)$ denotes the softmax function. Let $\mathbf{y}_{i,t}$ be the one-hot encoding of $y_{i,t}$. The discrepancy between the predicted probability and the actual choice is quantified using the KL-divergence. The detailed methodology is encapsulated in Algorithm 1.

This approach is the simplest way to solve the Nah Bandit problem. It provides a supervised learning way to learn user’s preference parameters $\theta_{i}$. It reduces the bias in the learning process that might be introduced by the anchoring effect, thereby preventing the user non-compliance model from falling into sub-optimal recommendations.

This section presents a sample complexity analysis of user preference parameter estimation in the user non-compliance model. If we let the model use the context of only two options to update the model, where one is the user’s choice and the other is not, this model is equivalent to a logistic regression.

Lemma 1 shows the sample complexity of parameter estimation in a logistic regression model. Using Lemma 1, we can get Theorem 1, which shows the sample complexity of the user preference parameter in the user non-compliance model. The proof of Theorem 1 is in Appendix A-D. This result demonstrates the speed at which we can learn user preference parameters in the Nah Bandit problem.

Another core aspect of our problem is rapidly identifying user preferences based on both compliance and non-compliance. To address this, we introduce the Expert with Clustering (EWC) algorithm, a novel hierarchical contextual bandit approach. EWC consists of both an offline training phase and an online learning phase. It transforms the recommendation problem into a prediction with expert advice problem, using clustering to get experts during the offline training phase and employing the Hedge algorithm to select the most effective expert during the online learning phase.

Prediction with expert advice is a classic online learning problem introduced by [23]. Consider a scenario in which a decision maker has access to the advice of $K$ experts. At each decision round $t$, advice from these $K$ experts is available, and the decision maker selects an expert based on a probability distribution $\mathbf{p}_{t}$ and follows his advice. Subsequently, the decision maker observes the loss of each expert, denoted as $\mathbf{l}_{t}\in[0,1]^{K}$. The primary goal is to identify the best expert in hindsight, which essentially translates to minimizing the regret: $\sum_{t=1}^{T}\left(<\mathbf{p}_{t},\mathbf{l}_{t}>-\mathbf{l}_{t}(k^{*})\right)$, where $k^{*}$ is the best expert throughout the time.

We cast the recommendation problem into the framework of prediction with expert advice in the following way. Recall the assumption that each user has a fixed but unknown preference parameter $\boldsymbol{\theta}_{i}\in\mathbb{R}^{d}$. Given $\boldsymbol{\theta}_{i}$, EWC algorithm operates under the assumption of a cluster structure within the users’ preference parameters $\{\boldsymbol{\theta}_{i}\}_{i\in[N]}$.

In the offline training phase, utilizing a set of offline training data $\mathcal{D}=\{\{x_{i,t,a}\}_{i\in[N^{\prime}],t\in[T],a\in[A]},\{y_{i,t}\}_{i\in[N^{\prime}],t\in[T]}\}$ where $N^{\prime}$ and $T^{\prime}$ are number of users and decision rounds in training data, we initially employ the user non-compliance model as a learning framework to determine each user’s preference parameter $\boldsymbol{\theta}_{i}$. Despite differences between training and testing data, both are sampled from the same distribution. This allows for an approximate determination of $\boldsymbol{\theta}_{i}$, providing insights into the hierarchical structure among users, albeit with some degree of approximation. Subsequently, a clustering method is applied on $\{\boldsymbol{\theta}_{i}\}_{i\in[N^{\prime}]}$ to identify centroids $\{\mathbf{c}_{k}\}_{k\in[K]}$ and user’s cluster affiliation $\{z_{i,k}\}_{i\in[N^{\prime}],k\in[K]}$, where $\mathbf{c}_{k}\in\mathbb{R}^{d}$ and $z_{i,k}\in\{0,1\}$, $\sum_{k\in[K]}z_{i,k}=1$. The number of clusters $K$ serves as a hyperparameter. We select the value of $K$ that yields the minimum regret on the offline training set.

Each centroid is considered an expert. In the online learning phase, using the Hedge algorithm, we initialize their weights and, at every online decision round, select an expert $E_{i,t}\in[K]$. An expert $E_{i,t}$ provides advice suggesting that a user’s preference parameters closely resemble the centroid $\mathbf{c}_{E_{i,t}}$. Consequently, we use this centroid to estimate the user’s preferences. The recommendation $r_{i,t}=\hat{y}(\mathbf{c}_{E_{i,t}},\mathbf{x}_{i,t})$ is then formulated. For example, $\hat{y}(\boldsymbol{\theta},\mathbf{x}_{i,t})=\arg\max_{a}x_{i,t,a}^{\intercal}\boldsymbol{\theta}$ where $\mathbf{x}_{i,t}=[x_{i,t,1},x_{i,t,2},...,x_{i,t,A}]$. Upon receiving the user’s chosen option $y_{i,t}$, we calculate the loss for each expert and update the weights in Hedge based on this loss. The loss for each expert $k$ is determined by a known loss function $\mathbf{l}_{i,t}(k)=l(\hat{y}(\mathbf{c}_{k},\mathbf{x}_{i,t}),y_{i,t})\in\mathbb{R}$. For example, $l(\hat{y}(\mathbf{c}_{k},\mathbf{x}_{i,t}),y_{i,t})=\mathbbm{1}_{\hat{y}(\mathbf{c}_{k},\mathbf{x}_{i,t})\neq y_{i,t}}$. The details of this process are encapsulated in Algorithm 2.

The EWC algorithm efficiently utilizes non-compliance feedback in both the offline training and the online learning phase. In offline training, the learning framework within EWC is an interchangeable module that can be implemented using various models, such as SVM or neural networks. Compared to other models, the user non-compliance model captures preferences from both compliance and non-compliance feedback with low bias. In online learning, the likelihood that at least one expert accurately predicts the user choice is high, regardless of compliance. This leads to rapid identification of user cluster identity in the Nah Bandit problem.

The core parameter influencing the regret in our model is the set of centroids $\{\mathbf{c}_{k}\}_{k\in[K]}$. An accurately representative set of centroids can significantly reflect users’ behaviors, whereas poorly chosen centroids may lead to suboptimal performance. In our simulations, we observed that the standard K-Means algorithm has limitations, as similar $\boldsymbol{\theta}_{i}$ values in the Euclidean space do not necessarily yield similar user preferences.

To address the limitation of K-Means clustering, researchers in fields such as federated learning [45, 46] and system identification [47] have devised bespoke objective functions to enhance clustering methodologies. Inspired by [45], we introduce a distance metric guided by the loss function which is tailored for online preference learning. Our objective is to ensure that $\theta_{i}$ values within the same cluster exhibit similar performance. Thus, we replace the traditional L₂ norm distance with the prediction loss incurred when assigning $\mathbf{c}_{k}$ to user $i$. Here, we define: $\mathbf{X}_{i}=[\mathbf{x}_{i,1},\mathbf{x}_{i,2},...,\mathbf{x}_{i,T^{\prime}}]\in\mathbb{R}^{T^{\prime}\times A\times d}$, $\mathbf{\hat{y}}(\mathbf{c}_{k},\mathbf{x}_{i,t})$ be the one-hot encodings of $\hat{y}(\mathbf{c}_{k},\mathbf{x}_{i,t})$, $\mathbf{y}_{i}=[\mathbf{y}_{i,1},\mathbf{y}_{i,2},...,\mathbf{y}_{i,T^{\prime}}]\in\mathbb{R}^{T^{\prime}\times A}$, and $\mathbf{\hat{y}}(\mathbf{c}_{k},\mathbf{X}_{i})=[\mathbf{\hat{y}}(\mathbf{c}_{k},\mathbf{x}_{i,1}),\mathbf{\hat{y}}(\mathbf{c}_{k},\mathbf{x}_{i,2}),...,\mathbf{\hat{y}}(\mathbf{c}_{k},\mathbf{x}_{i,T^{\prime}})]\in\mathbb{R}^{T^{\prime}\times A}$. The Loss-guided Distance is defined as $\text{dist}(i,\mathbf{c}_{k})=||\mathbf{\hat{y}}(\mathbf{c}_{k},\mathbf{X}_{i})-\mathbf{y}_{i}||^{2}_{F}$. The detailed clustering is presented in Algorithm 3.

In our model, we capitalize on the user context to facilitate accelerated preference learning during the initial phase. We hypothesize a latent relationship between the user context and the user’s cluster affiliation. In the offline training phase, we utilize user context vectors $\{u_{i}\}_{i\in[N^{\prime}]}$ along with the users’ cluster labels $\{z_{i,t}\}_{i\in[N^{\prime}],t\in[T]}$ to train a logistic regression model, denoted as $f:\mathbb{R}^{D}\rightarrow\mathbb{R}^{K}$. This model is designed to map the user context to a probabilistic distribution over the potential cluster affiliations.

During the online learning phase, we employ the trained logistic regression model $f(\cdot)$ to predict the probability of each user’s group affiliation based on their respective context. These predicted probabilities are then used to initialize the weights of the experts for each user, i.e., $\mathbf{p}_{i,1}\leftarrow f(u_{i})$ for all $i\in[N]$.

In our problem, we define the loss function $l(\hat{y}(\mathbf{c}_{k},\mathbf{x}_{i,t}),y_{i,t})=\mathbbm{1}_{\hat{y}(\mathbf{c}_{k},\mathbf{x}_{i,t})\neq y_{i,t}}$. We define the regret of EWC as the performance difference between EWC and recommendation with known user preference parameter $\boldsymbol{\theta}_{i}$:

Since the study in [48] shows the performance of K-Means clustering using the $L_{2}$ norm distance, we similarly adopt the $L_{2}$ norm distance to analyze regret in our framework. Theorem 2 is our main theoretical result. The proof is in Appendix A-A. The regret bound of EWC can be represented as a sum of two components: the regret from the Hedge algorithm and the bias introduced by representing users with centroids.

The Gaussian Mixture Model (GMM) aligns closely with our hypothesis of a hierarchical structure among users, which is a typical assumption in the analysis of clustering algorithms. By assuming that the distribution of users’ preferences follows a GMM, we derive Corollary 1.

The proof of Corollary 1 is provided in Appendix A-B. EWC does not achieve sublinear regret in the long term because it uses the cluster centroid as an estimate of user-specific preferences each time. However, if the estimation error is low, indicated by a small $l_{\text{centroids}}$ value, EWC achieves low regret in the short term.

We compare the regret of EWC with LinUCB. Lemma 2 is the regret bound of SupLinUCB (a variant of LinUCB). Corollary 2 is the comparison between EWC and LinUCB. The proof of Corollary 2 is provided in Appendix A-C. EWC demonstrates superior theoretical performance compared to LinUCB when $T$ is relatively small.

We compare our EWC algorithm against several baseline methods to determine its performance in online preference learning. The user non-compliance model (Non-compliance) is a linear model that parameterizes user dependence on recommendation (Algorithm 1). LinUCB refines the upper confidence bound method to suit linear reward scenarios, aiming to strike a balance between exploring new actions and exploiting known ones. We adopt the hybrid linear model in LinUCB proposed by [1] to learn from both user context and option context. DYNUCB combines LinUCB with dynamic clustering, which divides the population of users into multiple clusters and customizes the bandits for each cluster. We also use the hybrid linear model in DYNUCB. XGBoost is a highly efficient supervised learning algorithm based on gradient boosting.

We validate our algorithm in travel route recommendations. The data is collected from a community survey first, and then expanded to represent a diverse driving population.