# Stochastic Bandits with Delay-Dependent Payoffs

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2019.

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

- [Accounting for AI and Users Shaping One Another: The Role of Mathematical Models](https://mlsanity.com/paper/2404.12366/) (2024)
- [Non-Stationary Bandits with Auto-Regressive Temporal Dependency](https://mlsanity.com/paper/2210.16386/) (2022)
- [A Last Switch Dependent Analysis of Satiation and Seasonality in Bandits](https://mlsanity.com/paper/2110.11819/) (2021)
- [Linear Bandits with Memory: from Rotting to Rising](https://mlsanity.com/paper/2302.08345/) (2023)
- [Exploiting Curvature in Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2506.07595/) (2025)
- [Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret](https://mlsanity.com/paper/2205.14790/) (2022)
- [Combinatorial Blocking Bandits with Stochastic Delays](https://mlsanity.com/paper/2105.10625/) (2021)
- [Complete Policy Regret Bounds for Tallying Bandits](https://mlsanity.com/paper/2204.11174/) (2022)
- [Last Switch Dependent Bandits with Monotone Payoff Functions](https://mlsanity.com/paper/2306.00338/) (2023)
- [Recurrent Submodular Welfare and Matroid Blocking Bandits](https://mlsanity.com/paper/2102.00321/) (2021)
- [Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When Partial Feedback Counts](https://mlsanity.com/paper/2206.00586/) (2022)
- [Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimality](https://mlsanity.com/paper/2305.02955/) (2023)
- [Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platforms](https://mlsanity.com/paper/2307.11655/) (2023)
- [Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics](https://mlsanity.com/paper/2510.16208/) (2025)
- [Decentralized Online Convex Optimization with Unknown Feedback Delays](https://mlsanity.com/paper/2601.07901/) (2026)
- [Bandits with Dynamic Arm-acquisition Costs](https://mlsanity.com/paper/2110.12118/) (2021)
- [Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback](https://mlsanity.com/paper/2204.12764/) (2022)
- [Stochastic Contextual Bandits with Long Horizon Rewards](https://mlsanity.com/paper/2302.00814/) (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)
- [Generalized Linear Bandits with Memory](https://mlsanity.com/paper/2608.15848/) (2026)
- [Offline Planning and Online Learning under Recovering Rewards](https://mlsanity.com/paper/2106.14813/) (2021)
- [Continuous Time Bandits With Sampling Costs](https://mlsanity.com/paper/2107.05289/) (2021)
- [Bandit problems with fidelity rewards](https://mlsanity.com/paper/2111.13026/) (2021)
- [Block Optimism for Nonstationary Bandits with Latent Linear Dynamics](https://mlsanity.com/paper/2610.00911/) (2026)

## Abstract (arXiv)

Motivated by recommendation problems in music streaming platforms, we propose a nonstationary stochastic bandit model in which the expected reward of an arm depends on the number of rounds that have passed since the arm was last pulled. After proving that finding an optimal policy is NP-hard even when all model parameters are known, we introduce a class of ranking policies provably approximating, to within a constant factor, the expected reward of the optimal policy. We show an algorithm whose regret with respect to the best ranking policy is bounded by widetildeObig(!√kTbig), where k is the number of arms and T is time. Our algorithm uses only Obig(klnln Tbig) switches, which helps when switching between policies is costly. As constructing the class of learning policies requires ordering the arms according to their expectations, we also bound the number of pulls required to do so. Finally, we run experiments to compare our algorithm against UCB on different problem instances.