2017/07/08 by Yanan Sui, Yisong Yue, Sui, Yanan +3 · 6 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Algorithm #Artificial intelligence #Computer science #Decision problem #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine learning #Mathematical optimization #Mathematics #Operations research #Process (computing) #Regret #Reinforcement Learning in Robotics #Space (punctuation) #cs.LG
paper · pdf · doi:10.48550/arxiv.1707.02375
published in arXiv (Cornell University) (Cornell University)
arxiv created 2017/07/08 · openalex publication_date 2017/07/08 · arxiv updated 2017/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
We consider sequential decision making under uncertainty, where the goal is to optimize over a large decision space using noisy comparative feedback. This problem can be formulated as a K-armed Dueling Bandits problem where K is the total number of decisions. When K is very large, existing dueling bandits algorithms suffer huge cumulative regret before converging on the optimal arm. This paper studies the dueling bandits problem with a large number of arms that exhibit a low-dimensional correlation structure. Our problem is motivated by a clinical decision making process in large decision space. We propose an efficient algorithm CorrDuel which optimizes the exploration/exploitation tradeoff in this large decision space of clinical treatments. More broadly, our approach can be applied to other sequential decision problems with large and structured decision spaces. We derive regret bounds, and evaluate performance in simulation experiments as well as on a live clinical trial of therapeutic spinal cord stimulation. To our knowledge, this marks the first time an online learning algorithm was applied towards spinal cord injury treatments. Our experimental results show the effectiveness and efficiency of our approach.