Rebounding Bandits for Modeling Satiation Effects

Abstract

Psychological research shows that enjoyment of many goods is subject to satiation, with short-term satisfaction declining after repeated exposures to the same item. Nevertheless, proposed algorithms for powering recommender systems seldom model these dynamics, instead proceeding as though user preferences were fixed in time. In this work, we introduce rebounding bandits, a multi-armed bandit setup, where satiation dynamics are modeled as time-invariant linear dynamical systems. Expected rewards for each arm decline monotonically with consecutive exposures to it and rebound towards the initial reward whenever that arm is not pulled. Unlike classical bandit settings, methods for tackling rebounding bandits must plan ahead and model-based methods rely on estimating the parameters of the satiation dynamics. We characterize the planning problem, showing that the greedy policy is optimal when the arms exhibit identical deterministic dynamics. To address stochastic satiation dynamics with unknown parameters, we propose Explore-Estimate-Plan (EEP), an algorithm that pulls arms methodically, estimates the system dynamics, and then plans accordingly.

References in corpus (9)

• Counterfactual Risk Minimization: Learning from Logged Bandit Feedback
• Near optimal finite time identification of arbitrary linear dynamical systems
• Online Regret Bounds for Undiscounted Continuous Reinforcement Learning
• Regret Bounds for Restless Markov Bandits
• Naive Exploration is Optimal for Online LQR
• Rotting Bandits
• Blocking Bandits
• Rotting bandits are not harder than stochastic ones
• Recovering Bandits

Cited by in corpus (4)

• Measuring Commonality in Recommendation of Cultural Content: Recommender Systems to Enhance Cultural Citizenship
• Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits
• Combinatorial Blocking Bandits with Stochastic Delays
• A Field Test of Bandit Algorithms for Recommendations: Understanding the Validity of Assumptions on Human Preferences in Multi-armed Bandits