Timezone: »
Pure exploration in multi-armed bandits has emerged as an important framework for modeling decision making and search under uncertainty. In modern applications however, one is often faced with a tremendously large number of options and even obtaining one observation per option may be too costly rendering traditional pure exploration algorithms ineffective. Fortunately, one often has access to similarity relationships amongst the options that can be leveraged. In this paper, we consider the pure exploration problem in stochastic multi-armed bandits where the similarities between the arms is captured by a graph and the rewards may be represented as a smooth signal on this graph. In particular, we consider the problem of finding the arm with the maximum reward (i.e., the maximizing problem) or one that has sufficiently high reward (i.e., the satisficing problem) under this model. We propose novel algorithms GRUB (GRaph based UcB) and zeta-GRUB for these problems and provide theoretical characterization of their performance which specifically elicits the benefit of the graph side information. We also prove a lower bound on the data requirement that shows a large class of problems where these algorithms are near-optimal. We complement our theory with experimental results that show the benefit of capitalizing on such side information.
Author Information
Parth Thaker (Arizona State university)
Mohit Malu (Arizona State University)
Nikhil Rao (Microsoft)
Gautam Dasarathy (Arizona State University)
More from the Same Authors
-
2023 Poster: Hyperbolic Graph Neural Networks at Scale: A Meta Learning Approach »
Nurendra Choudhary · Nikhil Rao · Chandan Reddy -
2022 Poster: Learning the Structure of Large Networked Systems Obeying Conservation Laws »
Anirudh Rayas · Rajasekhar Anguluri · Gautam Dasarathy -
2022 Poster: Task-Agnostic Graph Explanations »
Yaochen Xie · Sumeet Katariya · Xianfeng Tang · Edward Huang · Nikhil Rao · Karthik Subbian · Shuiwang Ji -
2021 Poster: Probabilistic Entity Representation Model for Reasoning over Knowledge Graphs »
Nurendra Choudhary · Nikhil Rao · Sumeet Katariya · Karthik Subbian · Chandan Reddy -
2020 Poster: Finding the Homology of Decision Boundaries with Active Learning »
Weizhi Li · Gautam Dasarathy · Karthikeyan Natesan Ramamurthy · Visar Berisha -
2019 : Poster Session »
Gergely Flamich · Shashanka Ubaru · Charles Zheng · Josip Djolonga · Kristoffer Wickstrøm · Diego Granziol · Konstantinos Pitas · Jun Li · Robert Williamson · Sangwoong Yoon · Kwot Sin Lee · Julian Zilly · Linda Petrini · Ian Fischer · Zhe Dong · Alexander Alemi · Bao-Ngoc Nguyen · Rob Brekelmans · Tailin Wu · Aditya Mahajan · Alexander Li · Kirankumar Shiragur · Yair Carmon · Linara Adilova · SHIYU LIU · Bang An · Sanjeeb Dash · Oktay Gunluk · Arya Mazumdar · Mehul Motani · Julia Rosenzweig · Michael Kamp · Marton Havasi · Leighton P Barnes · Zhengqing Zhou · Yi Hao · Dylan Foster · Yuval Benjamini · Nati Srebro · Michael Tschannen · Paul Rubenstein · Sylvain Gelly · John Duchi · Aaron Sidford · Robin Ru · Stefan Zohren · Murtaza Dalal · Michael A Osborne · Stephen J Roberts · Moses Charikar · Jayakumar Subramanian · Xiaodi Fan · Max Schwarzer · Nicholas Roberts · Simon Lacoste-Julien · Vinay Prabhu · Aram Galstyan · Greg Ver Steeg · Lalitha Sankar · Yung-Kyun Noh · Gautam Dasarathy · Frank Park · Ngai-Man (Man) Cheung · Ngoc-Trung Tran · Linxiao Yang · Ben Poole · Andrea Censi · Tristan Sylvain · R Devon Hjelm · Bangjie Liu · Jose Gallego-Posada · Tyler Sypherd · Kai Yang · Jan Nikolas Morshuis -
2016 Workshop: Learning in High Dimensions with Structure »
Nikhil Rao · Prateek Jain · Hsiang-Fu Yu · Ming Yuan · Francis Bach -
2016 Poster: Structured Sparse Regression via Greedy Hard Thresholding »
Prateek Jain · Nikhil Rao · Inderjit Dhillon -
2016 Poster: Temporal Regularized Matrix Factorization for High-dimensional Time Series Prediction »
Hsiang-Fu Yu · Nikhil Rao · Inderjit Dhillon -
2015 Poster: Sparse and Low-Rank Tensor Decomposition »
Parikshit Shah · Nikhil Rao · Gongguo Tang -
2015 Poster: Collaborative Filtering with Graph Information: Consistency and Scalable Methods »
Nikhil Rao · Hsiang-Fu Yu · Pradeep Ravikumar · Inderjit Dhillon -
2015 Spotlight: Collaborative Filtering with Graph Information: Consistency and Scalable Methods »
Nikhil Rao · Hsiang-Fu Yu · Pradeep Ravikumar · Inderjit Dhillon -
2013 Poster: Sparse Overlapping Sets Lasso for Multitask Learning and its Application to fMRI Analysis »
Nikhil Rao · Christopher R Cox · Rob Nowak · Timothy T Rogers -
2013 Spotlight: Sparse Overlapping Sets Lasso for Multitask Learning and its Application to fMRI Analysis »
Nikhil Rao · Christopher R Cox · Rob Nowak · Timothy T Rogers