# Exploration, Exploitation, and Engagement in Multi-Armed Bandits with Abandonment

arXiv: https://arxiv.org/abs/2205.13566 · HTML: https://mlsanity.com/paper/2205.13566/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 21 references that are in the map.
- First posted on arXiv 26 May 2022.

## Builds on (most cited first, 9 of 9)

- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret](https://mlsanity.com/paper/2104.11186/) (2021)
- [Minimax Regret for Stochastic Shortest Path](https://mlsanity.com/paper/2103.13056/) (2021)
- [Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path](https://mlsanity.com/paper/2106.08377/) (2021)
- [Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation](https://mlsanity.com/paper/2105.01593/) (2021)
- [Modeling Attrition in Recommender Systems with Departing Bandits](https://mlsanity.com/paper/2203.13423/) (2022)
- [Adaptive Exploration-Exploitation Tradeoff for Opportunistic Bandits](https://mlsanity.com/paper/1709.04004/) (2017)
- [Dynamic Learning of Sequential Choice Bandit Problem under Marketing Fatigue](https://mlsanity.com/paper/1903.08193/) (2019)
- [Learning with Abandonment](https://mlsanity.com/paper/1802.08718/) (2018)

## Built on by (most cited first, 5 of 5)

- [Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms](https://mlsanity.com/paper/2309.00591/) (2023)
- [Learning with Exposure Constraints in Recommendation Systems](https://mlsanity.com/paper/2302.01377/) (2023)
- [Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysis](https://mlsanity.com/paper/2406.07455/) (2024)
- [The Nah Bandit: Modeling User Non-compliance in Recommendation Systems](https://mlsanity.com/paper/2408.07897/) (2024)
- [Algorithmic Content Selection and the Impact of User Disengagement](https://mlsanity.com/paper/2410.13108/) (2024)

## Abstract (arXiv)

Multi-armed bandit (MAB) is a classic model for understanding the exploration-exploitation trade-off. The traditional MAB model for recommendation systems assumes the user stays in the system for the entire learning horizon. In new online education platforms such as ALEKS or new video recommendation systems such as TikTok and YouTube Shorts, the amount of time a user spends on the app depends on how engaging the recommended contents are. Users may temporarily leave the system if the recommended items cannot engage the users. To understand the exploration, exploitation, and engagement in these systems, we propose a new model, called MAB-A where "A" stands for abandonment and the abandonment probability depends on the current recommended item and the user's past experience (called state). We propose two algorithms, ULCB and KL-ULCB, both of which do more exploration (being optimistic) when the user likes the previous recommended item and less exploration (being pessimistic) when the user does not like the previous item. We prove that both ULCB and KL-ULCB achieve logarithmic regret, O(log K), where K is the number of visits (or episodes). Furthermore, the regret bound under KL-ULCB is asymptotically sharp. We also extend the proposed algorithms to the general-state setting. Simulation results confirm our theoretical analysis and show that the proposed algorithms have significantly lower regrets than the traditional UCB and KL-UCB, and Q-learning-based algorithms.