Modeling Attrition in Recommender Systems with Departing Bandits

At the heart of online services spanning such diverse industries as media consumption, dating, financial products, and more, recommendation systems (RSs) drive personalized experiences by making curation decisions informed by each user’s past history of interactions. While in practice, these systems employ diverse statistical heuristics, much of our theoretical understanding of them comes via stylized formulations within the multi-armed bandits (MABs) framework. While MABs abstract away from many aspects of real-world systems they allow us to extract crisp insights by formalizing fundamental tradeoffs, such as that between exploration and exploitation that all RSs must face (Joseph et al. 2016; Liu and Ho 2018; Patil et al. 2020; Ron, Ben-Porat, and Shalit 2021). As applies to RSs, exploitation consists of continuing to recommend items (or categories of items) that have been observed to yield high rewards in the past, while exploration consists of recommending items (or categories of items) about which the RS is uncertain but that could potentially yield even higher rewards.

In traditional formalizations of RSs as MABs, the recommender’s decisions affect only the rewards obtained. However, real-life recommenders face a dynamic that potentially alters the exploration-exploitation tradeoff: Dissatisfied users have the option to depart the system, never to return. Thus, recommendations in the service of exploration not only impact instantaneous rewards but also risk driving away users and therefore can influence long-term cumulative rewards by shortening trajectories of interactions.

In this work, we propose departing bandits which augment conventional MABs by incorporating these policy-dependent horizons. To motivate our setup, we consider the following example: An RS for recommending blog articles must choose at each time among two categories of articles, e.g., economics and sports. Upon a user’s arrival, the RS recommends articles sequentially. After each recommendation, the user decides whether to “click” the article and continue to the next recommendation, or to “not click” and may leave the system. Crucially, the user interacts with the system for a random number of rounds. The user’s departure probability depends on their satisfaction from the recommended item, which in turn depends on the user’s unknown type. A user’s type encodes their preferences (hence the probability of clicking) on the two topics (economics and sports).

When model parameters are given, in contrast to traditional MABs where the optimal policy is to play the best fixed arm, departing bandits require more careful analysis to derive an optimal planning strategy. Such planning is a local problem, in the sense that it is solved for each user. Since the user type is never known explicitly (the recommender must update its beliefs over the user types after each interaction), finding an optimal recommendation policy requires solving a specific partially observable MDP (POMDP) where the user type constitutes the (unobserved) state (more details in Section 5.1). When the model parameters are unknown, we deal with a learning problem that is global, in the sense that the recommender (learner) is learning for a stream of users instead of a particular user.

We begin with a formal definition of departing bandits in Section 2, and demonstrate that any fixed-arm policy is prone to suffer linear regret. In Section 3, we establish the UCB-based learning framework used in later sections. We instantiate this framework with a single user type in Section 4, where we show that it achieves $\tilde{O}(\sqrt{T})$ regret for $T$ being the number of users. We then move to the more challenging case with two user types and two recommendation categories in Section 5. To analyze the planning problem, we effectively reduce the search space for the optimal policy by using a closed-form of the expected return of any recommender policy. These results suggest an algorithm that achieves $\tilde{O}(\sqrt{T})$ regret in this setting. Finally, we show an efficient optimal planning algorithm for multiple user types and two recommendation categories (Appendix A) and describe a scheme to construct semi-synthetic problem instances for this setting using real-world datasets (Appendix B).

We propose a new online problem, called departing bandits, where the goal is to find the optimal recommendation algorithm for users of (unknown) types, and where the length of the interactions depends on the algorithm itself. Formally, the departing bandits problem is defined by a tuple $\langle[M],[K],\mathbf{q},\mathbf{P},\mathbf{\Lambda}\rangle$, where $M$ is the number of user types, $K$ is the number of categories, $\mathbf{q}\in[0,1]^{M}$ specifies a prior distribution over types, and $\mathbf{P}\in(0,1)^{K\times M}$ and $\mathbf{\Lambda}\in(0,1)^{K\times M}$ are the click-probability and the departure-probability matrices, respectively.¹¹1We denote by $[n]$ the set $\{1,\dots,n\}$.

There are $T$ users who arrive sequentially at the RS. At every episode, a new user $t\in[T]$ arrives with a type $type(t)$. We let $\mathbf{q}$ denote the prior distribution over the user types, i.e., $type(t)\sim\mathbf{q}$. Each user of type $x$ clicks on a recommended category $a$ with probability $\mathbf{P}_{a,x}$. In other words, each click follows a Bernoulli distribution with parameter $\mathbf{P}_{a,x}$. Whenever the user clicks, she stays for another iteration, and when the user does not click (no-click), she departs with probability $\mathbf{\Lambda}_{a,x}$ (and stays with probability $1-\mathbf{\Lambda}_{a,x}$). Each user $t$ interacts with the RS (the learner) until she departs.

We proceed to describe the user-RS interaction protocol. In every iteration $j$ of user $t$, the learner recommends a category $a\in[K]$ to user $t$. The user clicks on it with probability $\mathbf{P}_{a,type(t)}$. If the user clicks, the learner receives a reward of $r_{t,j}(a)=1$.²²2We formalize the reward as is standard in the online learning literature, from the perspective of the learner. However, defining the reward from the user perspective by, e.g., considering her utility as the number of clicks she gives or the number of articles she reads induces the same model. If the user does not click, the learner receives no reward (i.e., $r_{t,j}(a)=0$), and user $t$ departs with probability $\mathbf{\Lambda}_{a,type(t)}$. We assume that the learner knows the value of a constant $\epsilon>0$ such that $\max_{a,x}\mathbf{P}_{a,x}\leq 1-\epsilon$ (i.e., $\epsilon$ does not depend on $T$). When user $t$ departs, she does not interact with the learner anymore (and the learner moves on to the next user $t+1$). For convenience, the departing bandits problem protocol is summarized in Algorithm 1.

Having described the protocol, we move on to the goals of the learner. Without loss of generality, we assume that the online learner’s recommendations are made based on a policy $\pi$, which is a mapping from the history of previous interactions (with that user) to recommendation categories.

For each user (episode) $t\in[T]$, the learner selects a policy $\pi_{t}$ that recommends category $\pi_{t,j}\in[K]$ at every iteration $j\in[N^{\pi_{t}}(t)]$, where $N^{\pi_{t}}(t)$ denotes the episode length (i.e., total number of iterations policy $\pi_{t}$ interacts with user $t$ until she departs).³³3We limit the discussion to deterministic policies solely; this is w.l.o.g. (see Subsection 5.1 for further details). The return of a policy $\pi$, denoted by $V^{\pi}$ is the cumulative reward the learner obtains when executing the policy $\pi$ until the user departs. Put differently, the return of $\pi$ from user $t$ is the random variable $V^{\pi}=\sum_{j=1}^{N^{\pi}(t)}r_{t,j}(\pi_{t,j})$.

We denote by $\pi^{*}$ an optimal policy, namely a policy that maximizes the expected return, $\pi^{*}=\operatorname*{arg\,max}_{\pi}\mathbb{E}[V^{\pi}]$. Similarly, we denote by $V^{*}$ the optimal return, i.e., $V^{*}=V^{\pi^{*}}$.

We highlight two algorithmic tasks. The first is the planning task, in which the goal is to find an optimal policy $\pi^{*}$, given $\mathbf{P},\mathbf{\Lambda},\mathbf{q}$. The second is the online learning task. We consider settings where the learner knows the number of categories, $K$, the number of types, $M$, and the number of users, $T$, but has no prior knowledge regarding $\mathbf{P},\mathbf{\Lambda}$ or $\mathbf{q}$. In the online learning task, the value of the learner’s algorithm is the sum of the returns obtained from all the users, namely

The performance of the leaner is compared to that of the best policy, formally defined by the regret for $T$ episodes,

The learner’s goal is to minimize the expected regret $\mathbb{E}[R_{T}]$.

In this section, we introduce the learning framework used in the paper and provide a general regret guarantee for it.

In standard MAB problems, at each $t\in[T]$ the learner picks a single arm and receives a single sub-Gaussian reward. In contrast, in departing bandits, at each $t\in[T]$ the learner receives a return $V^{\pi}$, which is the cumulative reward of that policy. The return $V^{\pi}$ depends on the policy $\pi$ not only through the obtained rewards at each iteration but also through the total number of iterations (trajectory length). Such returns are not necessarily sub-Gaussian. Consequently, we cannot use standard MAB algorithms as they usually rely on concentration bounds for sub-Gaussian rewards. Furthermore, as we have shown in Section 2.1, in departing bandits fixed-arm policies can suffer linear regret (in terms of the number of users), which suggests considering a more expressive set of policies. This in turn yields another disadvantage for using MAB algorithms for departing bandits, as their regret is linear in the number of arms (categories) $K$.

As we show later in Sections 4 and 5, for some natural instances of the departing bandits problem, the return from each user is sub-exponential (Definition 3.1). Algorithm 2, which we propose below, receives a set of policies $\Pi$ as input, along with other parameters that we describe shortly. The algorithm is a restatement of the UCB-Hybrid Algorithm from Jia, Shi, and Shen (2021), with two modifications: (1) The input includes a set of policies rather than a set of actions/categories, and accordingly, the confidence bound updates are based on return samples (denoted by $\hat{V}^{\pi}$) rather than reward samples. (2) There are two global parameters ($\tilde{\tau}$ and $\eta$) instead of two local parameters per action. If the return from each policy in $\Pi$ is sub-exponential, Algorithm 2 not only handles sub-exponential returns, but also comes with the following guarantee: Its expected value is close to the value of the best policy in $\Pi$.

In this section, we focus on the special case of a single user type, i.e., $M=1$. For notational convenience, since we only discuss single-type users, we associate each category $a\in[K]$ with its two unique parameters $\mathbf{P}_{a}\mathrel{\mathop{\mathchar 58\relax}}=\mathbf{P}_{a,1},\mathbf{\Lambda}_{a}\mathrel{\mathop{\mathchar 58\relax}}=\mathbf{\Lambda}_{a,1}$ and refer to them as scalars rather than vectors. In addition, We use the notation $N_{a}$ for the random variable representing the number of iterations until a random user departs after being recommended by $\pi^{a}$, the fixed-arm policy that recommends category $a$ in each iteration.

To derive a regret bound for single-type users, we use two main lemmas: Lemma 4.1, which shows the optimal policy is fixed, and Lemma 4.3, which shows that returns of fixed-arm policies are sub-exponential and calculate their corresponding parameters. These lemmas allow us to use Algorithm 2 with a policy set $\Pi$ that contains all the fixed-arm policies, and derive a $\tilde{O}(\sqrt{T})$ regret bound. For brevity, we relegate all the proofs to the Appendix.

To show that there exists a category $a^{*}\in[K]$ for which $\pi^{a^{*}}$ is optimal, we rely on the assumption that all the users have the same type (hence we drop the type subscripts $t$), and as a result the rewards of each category $a\in[K]$ have an expectation that depends on a single parameter, namely $\mathbb{E}[r(a)]=\mathbf{P}_{a}$. Such a category $a^{*}\in[K]$ does not necessarily have the maximal click-probability nor the minimal departure-probability, but rather an optimal combination of the two (in a way, this is similar to the knapsack problem, where we want to maximize the reward while having as little weight as possible). We formalize it in the following lemma.

As a consequence of this lemma, the planning problem for single-type users is trivial—the solution is a fixed-arm policy $\pi^{a^{*}}$ given in the lemma. However, without access to the model parameters, identifying $\pi^{a^{*}}$ requires learning. We proceed with a simple observation regarding the random number of iterations obtained by executing a fixed-arm policy. The observation would later help us show that the return of any fixed-arm policy is sub-exponential.

Using Observation 4.2 and previously known results (stated as Lemma D.3 in the appendix), we show that $N_{a}$ is sub-exponential for all $a\in[K]$. Notice that return realizations are always upper bounded by the trajectory length; this implies that returns are also sub-exponential. However, to use the regret bound of Algorithm 2, we need information regarding the parameters $(\tau^{2}_{a},b_{a})$ for every policy $\pi^{a}$. We provide this information in the following Lemma 4.3.

An immediate consequence of Lemma 4.3 is that the parameters $\tilde{\tau}=8e/\ln(\frac{1}{1-\epsilon})$ and $\eta=1$ are valid upper bounds for $\tau_{a}$ and $b_{a}/\tau_{a}^{2}$ for each $a\in[K]$ (I.e., $\forall a\in[K]\mathrel{\mathop{\mathchar 58\relax}}\;\tilde{\tau}\geq\tau_{a}$ and $\eta\geq b_{a}^{2}/\tau_{a}^{2}$). We can now derive a regret bound using Algorithm 2 and Theorem 3.2.

In this section, we consider cases with two user types ($M=2$), two categories ($K=2$) and departure-probability $\mathbf{\Lambda}_{a,\tau}=1$ for every category $a\in[K]$ and type $\tau\in[M]$. Even in this relatively simplified setting, where users leave after the first “no-click”, planning is essential. To see this, notice that the event of a user clicking on a certain category provides additional information about the user, which can be used to tailor better recommendations; hence, algorithms that do not take this into account may suffer a linear regret. In fact, this is not just a matter of the learning algorithm at hand, but rather a failure of all fixed-arm policies; there are instances where all fixed-arm policies yield high regret w.r.t. the baseline defined in Equation (1). Indeed, this is what the example in Section 2.1 showcases. Such an observation suggests that studying the optimal planning problem is vital.

In Section 5.1, we introduce the partially observable MDP formulation of departing bandits along with notion of belief-category walk. We use this notion to provide a closed-form formula for policies’ expected return, which we use extensively later on. Next, in Section 5.2 we characterize the optimal policy, and show that we can compute it in constant time relying on the closed-form formula. This is striking, as generally computing optimal POMDP policies is computationally intractable since, e.g., the space of policies grows exponentially with the horizon. Conceptually, we show that there exists an optimal policy that depends on a belief threshold: It recommends one category until the posterior belief of one type, which is monotonically increasing, crosses the threshold, and then it recommends the other category. Finally, in Section 5.3 we leverage all the previously obtained results to derive a small set of threshold policies of size $O(\ln T)$ with corresponding sub-exponential parameters. Due to Theorem 3.2, this result implies a $\tilde{O}(\sqrt{T})$ regret.

This paper introduces a MAB model in which the recommender system influences both the rewards accrued and the length of interaction. We dealt with two classes of problems: A single user type with general departure probabilities (Section 4) and the two user types, two categories where each user departs after her first no-click (Section 5). For each problem class, we started with analyzing the planning task, then characterized a small set of candidates for the optimal policy, and then applied Algorithm 2 to achieve sublinear regret.

In the appendix, we also consider a third class of problems: Two categories, multiple user types ($M\geq 2)$ where user departs with their first no-click. We use the closed-form expected return derived in Theorem 5.3 to show how to use dynamic programming to find approximately optimal planning policies. We formulate the problem of finding an optimal policy for a finite horizon $H$ in a recursive manner. Particularly, we show how to find a $\nicefrac{{1}}{{2^{O(H)}}}$ additive approximation in run-time of $O(H^{2})$. Unfortunately, this approach cannot assist us in the learning task. Dynamic programming relies on skipping sub-optimal solutions to sub-problems (shorter horizons in our case), but this happens on the fly; thus, we cannot a-priori define a small set of candidates like what Algorithm 2 requires. More broadly, we could use this dynamic programming approach for more than two categories, namely for $K\geq 2$, but then the run-time becomes $O(H^{K})$.

There are several interesting future directions. First, achieving low regret for the setup in Section 5 with $K\geq 2$. We suspect that this class of problems could enjoy a solution similar to ours, where candidates for optimal policies are mixing two categories solely. Second, achieving low regret for the setup in Section 5 with uncertain departure (i.e., $\mathbf{\Lambda}\neq 1$). Our approach fails in such a case since we cannot use belief-category walks; these are no longer deterministic. Consequently, the closed-form formula is much more complex and optimal planning becomes more intricate. These two challenges are left open for future work.

LL is generously supported by an Open Philanthropy AI Fellowship. LC is supported by Ariane de Rothschild Women Doctoral Program. ZL thanks the Block Center for Technology and Society; Amazon AI; PwC USA via the Digital Transformation and Innovation Center; and the NSF: Fair AI Award IIS2040929 for supporting ACMI lab’s research on the responsible use of machine learning. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation (grant number 993/17), Tel Aviv University Center for AI and Data Science (TAD), and the Yandex Initiative for Machine Learning at Tel Aviv University.