In this talk, we investigate the structural properties of certain sequential decision-making problems with limited feedback (bandits) in order to bring the known algorithmic solutions closer to a practical use including, online influence maximization or sequential recommender systems. To address these structured settings, we can always ignore the graph and use known algorithms for multi-armed bandits. However, their performance scales unfavorably with the number of nodes N, which is undesirable when N means a thousand of sensors or a million of movies. We describe several graph bandit problems and show how to use their graph structure to design new algorithms with faster learning rates, scaling not with N but with graph-dependent quantities, often much smaller than N in real-world graphs.