Introduction
In modern recommendation systems, medical treatments, and financial services, the primary objective is often to maximize cumulative short-term rewards. However, this approach overlooks a critical real-world constraint: user "reneging." A single poor experience—such as a significant financial loss or a highly irrelevant recommendation—can cause a user to abandon the platform permanently. This paper, originally presented at ICML 2019, introduces a framework for maximizing user lifetime by accounting for both context-dependent rewards and the inherent risks that lead to user attrition.
Problem Formulation
The authors define the Heteroscedastic Linear Bandit with Reneging to capture two essential phenomena:
- Reneging Risk: Each user $t$ has a satisfaction threshold $eta_t$. If the realized reward $r_{t,a}$ from an action $a$ is less than $eta_t$, the user leaves the system forever. The goal is to maximize the total expected reward over the entire sequence of users, which requires keeping each user engaged for as long as possible.
- Heteroscedasticity: Unlike standard bandit models that assume constant noise, this framework recognizes that variance is context-dependent. Both the expected reward and the variance are modeled as linear functions of the context vector $x_{t,a}$.
As illustrated above, the mean reward follows a linear trend, but the spread (variance) of the potential outcomes changes significantly depending on the context $x_{t,a}$.
The HR-UCB Algorithm
To address these challenges, the authors propose the Heteroscedastic Reneging Upper Confidence Bound (HR-UCB) algorithm. HR-UCB differs from traditional UCB approaches in several key ways:
- Joint Estimation: It employs Generalized Least Squares (GLSE) to simultaneously estimate parameters for the mean ($\theta_*$) and the variance ($\phi_*$).
- Risk-Aware Exploration: The algorithm incorporates estimated variance into its confidence bounds. Instead of simply seeking the highest mean, it evaluates actions based on their "best-case" lifetime, factoring in the probability that a high-variance outcome might trigger a reneging event.
- Scalable Learning: By maintaining a dynamic regression sample set, HR-UCB ensures that its estimates improve over time without incurring prohibitive computational costs.
Key Insights: The Mean-Variance Trade-off
The fundamental "aha moment" of this research is that maximizing lifetime is distinct from maximizing immediate reward. In a standard bandit setting, an action with a high mean and high variance might be preferred for its exploration potential. In a reneging setting, that same action could be disastrous.
As shown in the figure, even if Action 2 has a higher mean ($\mu_2 > \mu_1$), its higher variance ($\sigma_2 > \sigma_1$) can lead to a higher probability of falling below the satisfaction threshold $\beta$ ($P_2(r < \beta) > P_1(r < \beta)$). Consequently, Action 1 may be the optimal choice for maximizing user lifetime despite its lower expected immediate return.
Experimental Evaluation and Results
The algorithm was tested using synthetic simulations involving 30,000 sequential users and 20 available actions. HR-UCB demonstrated superior performance compared to several baselines:
- LinUCB: Failed by consistently choosing high-reward, high-variance actions that caused premature user reneging.
- CMDP (Contextual Markov Decision Process): Struggled with efficiency as the context space grew.
- $\sigma_{max}$-UCB: Incurred linear regret by being overly conservative and failing to explore effectively.
The authors proved that HR-UCB achieves a sub-linear regret bound of $O(\sqrt{T}(\log T)^3)$, confirming its theoretical and practical effectiveness in balancing exploration, exploitation, and risk.
Conclusion
By treating variance as a critical signal rather than mere noise, the Heteroscedastic Linear Bandit with Reneging framework provides a robust solution for long-term user engagement. While future work may relax assumptions regarding known satisfaction levels or linear mappings, HR-UCB represents a significant step toward building recommendation systems that truly value the user's long-term experience.
Summary updated