# Stochastic Rising Bandits

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 39 references that are in the map.
- First posted on arXiv 7 Dec 2022.

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

- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit](https://mlsanity.com/paper/1802.03692/) (2018)
- [A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem](https://mlsanity.com/paper/1711.03539/) (2017)
- [Regret Bound Balancing and Elimination for Model Selection in Bandits and RL](https://mlsanity.com/paper/2012.13045/) (2020)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [Efficient Automatic CASH via Rising Bandits](https://mlsanity.com/paper/2012.04371/) (2020)
- [Recovering Bandits](https://mlsanity.com/paper/1910.14354/) (2019)
- [Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits](https://mlsanity.com/paper/2011.02664/) (2020)
- [Non-Stationary Bandits with Habituation and Recovery Dynamics](https://mlsanity.com/paper/1707.08423/) (2017)
- [Corralling Stochastic Bandit Algorithms](https://mlsanity.com/paper/2006.09255/) (2020)
- [Regret Balancing for Bandit and RL Model Selection](https://mlsanity.com/paper/2006.05491/) (2020)

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

- [Sliding-Window Thompson Sampling for Non-Stationary Settings](https://mlsanity.com/paper/2409.05181/) (2024)
- [Best Arm Identification for Stochastic Rising Bandits](https://mlsanity.com/paper/2302.07510/) (2023)
- [Linear Bandits with Memory: from Rotting to Rising](https://mlsanity.com/paper/2302.08345/) (2023)
- [Put CASH on Bandits: A Max K-Armed Problem for Automated Machine Learning](https://mlsanity.com/paper/2505.05226/) (2025)
- [Last Switch Dependent Bandits with Monotone Payoff Functions](https://mlsanity.com/paper/2306.00338/) (2023)
- [Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimality](https://mlsanity.com/paper/2305.02955/) (2023)
- [Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem](https://mlsanity.com/paper/2511.10619/) (2025)
- [Combinatorial Rising Bandits](https://mlsanity.com/paper/2412.00798/) (2024)
- [Generalized Linear Bandits with Memory](https://mlsanity.com/paper/2608.15848/) (2026)
- [State-Separated SARSA: A Practical Sequential Decision-Making Algorithm with Recovering Rewards](https://mlsanity.com/paper/2403.11520/) (2024)
- [Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting](https://mlsanity.com/paper/2409.05980/) (2024)
- [Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Bandits](https://mlsanity.com/paper/2410.05734/) (2024)
- [Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits](https://mlsanity.com/paper/2505.20051/) (2025)
- [Rising Multi-Armed Bandits with Known Horizons](https://mlsanity.com/paper/2602.10727/) (2026)
- [Beyond Static Bias: Adaptive Multi-Fidelity Bandits with Improving Proxies](https://mlsanity.com/paper/2605.08558/) (2026)
- [From Novice to Expert: Cost-Aware Bandits for Evolving Worker Performance in Crowdsensing](https://mlsanity.com/paper/2607.13546/) (2026)
- [CAROL: Context-Aware Online Learning for Fuzzer Scheduling](https://mlsanity.com/paper/2609.06772/) (2026)
- [Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise](https://mlsanity.com/paper/2609.17595/) (2026)

## Abstract (arXiv)

This paper is in the field of stochastic Multi-Armed Bandits (MABs), i.e., those sequential selection techniques able to learn online using only the feedback given by the chosen option (a.k.a. arm). We study a particular case of the rested and restless bandits in which the arms' expected payoff is monotonically non-decreasing. This characteristic allows designing specifically crafted algorithms that exploit the regularity of the payoffs to provide tight regret bounds. We design an algorithm for the rested case (R-ed-UCB) and one for the restless case (R-less-UCB), providing a regret bound depending on the properties of the instance and, under certain circumstances, of widetildeO(T^frac23). We empirically compare our algorithms with state-of-the-art methods for non-stationary MABs over several synthetically generated tasks and an online model selection problem for a real-world dataset. Finally, using synthetic and real-world data, we illustrate the effectiveness of the proposed approaches compared with state-of-the-art algorithms for the non-stationary bandits.