Online learning with noisy side observations

Abstract

We propose a new partial-observability model for online learning problems where the learner, besides its own loss, also observes some noisy feedback about the other actions, depending on the underlying structure of the problem. We represent this structure by a weighted directed graph, where the edge weights are related to the quality of the feedback shared by the connected nodes. Our main contribution is an efficient algorithm that guarantees a regret of $\tilde{O}(\sqrt{{\alpha }^{\ast }T})$ after $T$ rounds, where ${\alpha }^{\ast }$ is a novel graph property that we call the effective independence number. Our algorithm is completely parameter-free and does not require knowledge (or even estimation) of ${\alpha }^{\ast }$. For the special case of binary edge weights, our setting reduces to the partial-observability models of Mannor and Shamir (2011) and Alon et al. (2013) and our algorithm recovers the near-optimal regret bounds.

Published at International Conference on Artificial Intelligence and Statistics (AISTATS) 2016. 13 pages, 7 figures

References in corpus (3)

• Efficient learning by implicit exploration in bandit problems with side observations
• From Bandits to Experts: A Tale of Domination and Independence
• Prediction by Random-Walk Perturbation

Cited by in corpus (14)

• Secure Mobile Edge Computing in IoT via Collaborative Online Learning
• Online Learning with Feedback Graphs Without the Graphs
• Revealing graph bandits for maximizing local influence
• Proximal Online Gradient is Optimum for Dynamic Regret
• Analysis of Thompson Sampling for Graphical Bandits Without the Graphs
• A Closer Look at Small-loss Bounds for Bandits with Graph Feedback
• Online learning with Erdős-Rényi side-observation graphs
• Reinforcement Learning with Feedback Graphs
• Stochastic Online Learning with Probabilistic Graph Feedback
• Beyond Bandit Feedback in Online Multiclass Classification
• Bandit algorithms for real-time data capture on large social medias
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations
• Online Learning with Uncertain Feedback Graphs
• Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs