Spectral bandits for smooth graph functions

Abstract

Smooth functions on graphs have wide applications in manifold and semi-supervised learning. In this paper, we study a bandit problem where the payoffs of arms are smooth on a graph. This framework is suitable for solving online learning problems that involve graphs, such as content-based recommendation. In this problem, each item we can recommend is a node and its expected rating is similar to its neighbors. The goal is to recommend items that have high expected ratings. We aim for the algorithms where the cumulative regret with respect to the optimal policy would not scale poorly with the number of nodes. In particular, we introduce the notion of an effective dimension, which is small in real-world graphs, and propose two algorithms for solving our problem that scale linearly and sublinearly in this dimension. Our experiments on real-world content recommendation problem show that a good estimator of user preferences for thousands of items can be learned from just tens of nodes evaluations.

Published in International Conference on Machine Learning (ICML 2014)

References in corpus (7)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Contextual Bandits with Similarity Information
• Finite-Time Analysis of Kernelised Contextual Bandits
• Matrix Completion from a Few Entries
• Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization
• From Bandits to Experts: A Tale of Domination and Independence
• A Variant of Azuma's Inequality for Martingales with Subgaussian Tails

Cited by in corpus (22)

• Online Clustering of Bandits
• Revealing graph bandits for maximizing local influence
• Bilinear Bandits with Low-rank Structure
• Randomized Exploration in Generalized Linear Bandits
• Stochastic Rank-1 Bandits
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners
• Perturbed-History Exploration in Stochastic Linear Bandits
• Stochastic Linear Bandits Robust to Adversarial Attacks
• Graph Signal Processing: Overview, Challenges and Applications
• Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge
• Improving Offline Contextual Bandits with Distributional Robustness
• Alternating Linear Bandits for Online Matrix-Factorization Recommendation
• Multi-Armed Bandits on Partially Revealed Unit Interval Graphs
• Bandit algorithms for real-time data capture on large social medias
• Algorithms for Linear Bandits on Polyhedral Sets
• Self-Concordant Analysis of Generalized Linear Bandits with Forgetting
• Pure Exploration in Kernel and Neural Bandits
• Best Arm Identification in Graphical Bilinear Bandits
• Optimal Strategies for Graph-Structured Bandits
• Spectral bandits for smooth graph functions with applications in recommender systems
• Thresholding Graph Bandits with GrAPL
• Bandits with Temporal Stochastic Constraints