Heteroscedastic Bandits with Reneging

Ping-Chun Hsieh, Xi Liu, Anirban Bhattacharya, P. R. KumararXiv 2018 · arXiv

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:

  1. 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.
  2. 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

Abstract

Sequential decision making for lifetime maximization is a critical problem in many real-world applications, such as medical treatment and portfolio selection. In these applications, a "reneging" phenomenon, where participants may disengage from future interactions after observing an unsatisfiable outcome, is rather prevalent. To address the above issue, this paper proposes a model of heteroscedastic linear bandits with reneging, which allows each participant to have a distinct "satisfaction level," with any interaction outcome falling short of that level resulting in that participant reneging. Moreover, it allows the variance of the outcome to be context-dependent. Based on this model, we develop a UCB-type policy, namely HR-UCB, and prove that it achieves $\mathcal{O}\big(\sqrt{{T}(\log({T}))^{3}}\big)$ regret. Finally, we validate the performance of HR-UCB via simulations.
BibTeX
@misc{hsieh2018heteroscedastic,
  author = {Ping-Chun Hsieh and Xi Liu and Anirban Bhattacharya and P. R. Kumar},
  title = {{Heteroscedastic Bandits with Reneging}},
  year = {2018},
  eprint = {1810.12418},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.12418},
}
Figure