Multi-armed Bandit Requiring Monotone Arm Sequences
This addresses online learning problems like dynamic pricing and clinical trials where monotonic actions are required, representing an incremental theoretical advancement.
The paper tackles the continuum-armed bandit problem with a monotonicity constraint on arm sequences, showing that under Lipschitz continuity, regret is O(T), and under additional unimodality or quasiconcave conditions, regret is ˜O(T^{3/4}), which is proven optimal and deviates from the standard ˜O(T^{2/3}) rate.
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.