# Multi-armed Bandit Requiring Monotone Arm Sequences

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 47 references that are in the map.
- First posted on arXiv 7 Jun 2021.

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

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [Bootstrapping Upper Confidence Bound](https://mlsanity.com/paper/1906.05247/) (2019)
- [Fairness in Learning-Based Sequential Decision Algorithms: A Survey](https://mlsanity.com/paper/2001.04861/) (2020)
- [Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1811.05154/) (2018)
- [Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes](https://mlsanity.com/paper/1909.02553/) (2019)
- [Thresholding Bandit for Dose-ranging: The Impact of Monotonicity](https://mlsanity.com/paper/1711.04454/) (2017)

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

- [Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2301.12366/) (2023)
- [Pure Exploration in Bandits with Linear Constraints](https://mlsanity.com/paper/2306.12774/) (2023)
- [Non-Stationary Dynamic Pricing Via Actor-Critic Information-Directed Pricing](https://mlsanity.com/paper/2208.09372/) (2022)
- [From Stream to Pool: Pricing Under the Law of Diminishing Marginal Utility](https://mlsanity.com/paper/2310.19220/) (2023)
- [Markdown Pricing Under an Unknown Parametric Demand Model](https://mlsanity.com/paper/2312.15286/) (2023)

## Abstract (arXiv)

In many online learning or multi-armed bandit problems, the taken actions or pulled arms are ordinal and required to be monotone over time. Examples include dynamic pricing, in which the firms use markup pricing policies to please early adopters and deter strategic waiting, and clinical trials, in which the dose allocation usually follows the dose escalation principle to prevent dose limiting toxicities. We consider the continuum-armed bandit problem when the arm sequence is required to be monotone. We show that when the unknown objective function is Lipschitz continuous, the regret is O(T). When in addition the objective function is unimodal or quasiconcave, the regret is tilde O(T3/4) under the proposed algorithm, which is also shown to be the optimal rate. This deviates from the optimal rate tilde O(T2/3) in the continuous-armed bandit literature and demonstrates the cost to the learning efficiency brought by the monotonicity requirement.