# Non-Stationary Bandits with Habituation and Recovery Dynamics

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jul 2017.

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

- [Field Study in Deploying Restless Multi-Armed Bandits: Assisting Non-Profits in Improving Maternal and Child Health](https://mlsanity.com/paper/2109.08075/) (2021)
- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Policy Optimization for Personalized Interventions in Behavioral Health](https://mlsanity.com/paper/2303.12206/) (2023)
- [Contextual Online Uncertainty-Aware Preference Learning for Human Feedback](https://mlsanity.com/paper/2504.19342/) (2025)
- [Best Arm Identification for Stochastic Rising Bandits](https://mlsanity.com/paper/2302.07510/) (2023)
- [Regret Analysis of Learning-Based MPC with Partially-Unknown Cost Function](https://mlsanity.com/paper/2108.02307/) (2021)
- [Planning a Community Approach to Diabetes Care in Low- and Middle-Income Countries Using Optimization](https://mlsanity.com/paper/2305.06426/) (2023)
- [Last Switch Dependent Bandits with Monotone Payoff Functions](https://mlsanity.com/paper/2306.00338/) (2023)
- [Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platforms](https://mlsanity.com/paper/2307.11655/) (2023)
- [Persuading to Prepare for Quitting Smoking with a Virtual Coach: Using States and User Characteristics to Predict Behavior](https://mlsanity.com/paper/2304.02264/) (2023)
- [A Field Test of Bandit Algorithms for Recommendations: Understanding the Validity of Assumptions on Human Preferences in Multi-armed Bandits](https://mlsanity.com/paper/2304.09088/) (2023)
- [Ads that Stick: Near-Optimal Ad Optimization through Psychological Behavior Models](https://mlsanity.com/paper/2509.20304/) (2025)
- [Power Constrained Nonstationary Bandits with Habituation and Recovery Dynamics](https://mlsanity.com/paper/2511.02944/) (2025)
- [A Diffusion-Model Subpopulation Digital Twin for Mobile Health Deployment: A Case Study on the HeartSteps Intervention](https://mlsanity.com/paper/2607.21403/) (2026)
- [Offline Planning and Online Learning under Recovering Rewards](https://mlsanity.com/paper/2106.14813/) (2021)
- [An Adaptive Optimization Approach to Personalized Financial Incentives in Mobile Behavioral Weight Loss Interventions](https://mlsanity.com/paper/2307.00444/) (2023)
- [Adaptive Interventions with User-Defined Goals for Health Behavior Change](https://mlsanity.com/paper/2311.09483/) (2023)
- [Applications of 0-1 Neural Networks in Prescription and Prediction](https://mlsanity.com/paper/2402.18851/) (2024)
- [Finite-Time Guarantees for Multi-Agent Combinatorial Bandits with Nonstationary Rewards](https://mlsanity.com/paper/2508.20923/) (2025)
- [Can we use LLMs to bootstrap reinforcement learning? -- A case study in digital health behavior change](https://mlsanity.com/paper/2511.17630/) (2025)
- [Optimality of Sub-network Laplace Approximations: New Results and Methods](https://mlsanity.com/paper/2605.09075/) (2026)
- [Optimizing Digital Therapeutic Interventions: Online Learning under Endogenous Adherence](https://mlsanity.com/paper/2605.24261/) (2026)

## Abstract (arXiv)

Many settings involve sequential decision-making where a set of actions can be chosen at each time step, each action provides a stochastic reward, and the distribution for the reward of each action is initially unknown. However, frequent selection of a specific action may reduce its expected reward, while abstaining from choosing an action may cause its expected reward to increase. Such non-stationary phenomena are observed in many real world settings such as personalized healthcare-adherence improving interventions and targeted online advertising. Though finding an optimal policy for general models with non-stationarity is PSPACE-complete, we propose and analyze a new class of models called ROGUE (Reducing or Gaining Unknown Efficacy) bandits, which we show in this paper can capture these phenomena and are amenable to the design of effective policies. We first present a consistent maximum likelihood estimator for the parameters of these models. Next, we construct finite sample concentration bounds that lead to an upper confidence bound policy called the ROGUE Upper Confidence Bound (ROGUE-UCB) algorithm. We prove that under proper conditions the ROGUE-UCB algorithm achieves logarithmic in time regret, unlike existing algorithms which result in linear regret. We conclude with a numerical experiment using real data from a personalized healthcare-adherence improving intervention to increase physical activity. In this intervention, the goal is to optimize the selection of messages (e.g., confidence increasing vs. knowledge increasing) to send to each individual each day to increase adherence and physical activity. Our results show that ROGUE-UCB performs better in terms of regret and average reward as compared to state of the art algorithms, and the use of ROGUE-UCB increases daily step counts by roughly 1,000 steps a day (about a half-mile more of walking) as compared to other algorithms.