Multi-armed Bandit Requiring Monotone Arm Sequences

Abstract

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}(T^{3/4})$ under the proposed algorithm, which is also shown to be the optimal rate. This deviates from the optimal rate $\tilde{O}(T^{2/3})$ in the continuous-armed bandit literature and demonstrates the cost to the learning efficiency brought by the monotonicity requirement.

References in corpus (9)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Further Optimal Regret Bounds for Thompson Sampling
• Contextual Bandits with Similarity Information
• Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms
• On Multi-Armed Bandit Designs for Dose-Finding Clinical Trials
• Bootstrapping Upper Confidence Bound
• Thresholding Bandit for Dose-ranging: The Impact of Monotonicity
• Learning and Optimization with Seasonal Patterns
• Blind Network Revenue Management and Bandits with Knapsacks under Limited Switches