Search papers, labs, and topics across Lattice.
DeepMind
Microsoft ResearchINRIAParis-SaclaySequeL teamTechnicolor Research CenterApr 20, 2026arXiv:2604.18420This paper addresses a bandit problem involving smooth functions on graphs, focusing on the online learning challenges in content-based recommendation systems. By introducing the concept of effective dimension, which remains small in practical scenarios, the authors develop two algorithms that achieve cumulative regret scaling linearly and sublinearly with the number of nodes. Experimental results demonstrate that these algorithms can effectively estimate user preferences with minimal evaluations, significantly enhancing recommendation efficiency.
Learning user preferences for thousands of items can be achieved with just a handful of evaluations, thanks to a novel approach that leverages effective dimension in graph-based bandit problems.
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.
