# Multi-armed Bandit Problem with Known Trend

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Aug 2015.

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

- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [Reinforcement Learning and Bandits for Speech and Language Processing: Tutorial, Review and Outlook](https://mlsanity.com/paper/2210.13623/) (2022)
- [Generalized non-stationary bandits](https://mlsanity.com/paper/2102.00725/) (2021)
- [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)
- [Optimal Epidemic Control as a Contextual Combinatorial Bandit with Budget](https://mlsanity.com/paper/2106.15808/) (2021)
- [Regret Analysis of Learning-Based MPC with Partially-Unknown Cost Function](https://mlsanity.com/paper/2108.02307/) (2021)
- [Rotting Infinitely Many-armed Bandits](https://mlsanity.com/paper/2201.12975/) (2022)
- [Complete Policy Regret Bounds for Tallying Bandits](https://mlsanity.com/paper/2204.11174/) (2022)
- [Using Non-Stationary Bandits for Learning in Repeated Cournot Games with Non-Stationary Demand](https://mlsanity.com/paper/2201.00486/) (2022)
- [Evolutionary Multi-Armed Bandits with Genetic Thompson Sampling](https://mlsanity.com/paper/2205.10113/) (2022)
- [Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimality](https://mlsanity.com/paper/2305.02955/) (2023)
- [Generalized Linear Bandits with Memory](https://mlsanity.com/paper/2608.15848/) (2026)
- [Etat de l'art sur l'application des bandits multi-bras](https://mlsanity.com/paper/2101.00001/) (2021)
- [Batched Bandits with Crowd Externalities](https://mlsanity.com/paper/2109.14733/) (2021)
- [Bandit problems with fidelity rewards](https://mlsanity.com/paper/2111.13026/) (2021)
- [Finite-Time Guarantees for Multi-Agent Combinatorial Bandits with Nonstationary Rewards](https://mlsanity.com/paper/2508.20923/) (2025)

## Abstract (arXiv)

We consider a variant of the multi-armed bandit model, which we call multi-armed bandit problem with known trend, where the gambler knows the shape of the reward function of each arm but not its distribution. This new problem is motivated by different online problems like active learning, music and interface recommendation applications, where when an arm is sampled by the model the received reward change according to a known trend. By adapting the standard multi-armed bandit algorithm UCB1 to take advantage of this setting, we propose the new algorithm named A-UCB that assumes a stochastic model. We provide upper bounds of the regret which compare favourably with the ones of UCB1. We also confirm that experimentally with different simulations