Online learning with noisy side observations

Tomáš Kocák 1 Gergely Neu 2, 1 Michal Valko 1
1 SEQUEL - Sequential Learning
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
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 O(√ α * T) after T rounds, where α * 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 α *. For the special case of binary edge weights, our setting reduces to the partial-observability models of Mannor & Shamir (2011) and Alon et al. (2013) and our algorithm recovers the near-optimal regret bounds.
Type de document :
Communication dans un congrès
International Conference on Artificial Intelligence and Statistics, May 2016, Seville, Spain
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger
Contributeur : Michal Valko <>
Soumis le : lundi 18 avril 2016 - 10:03:59
Dernière modification le : mardi 3 juillet 2018 - 11:43:25
Document(s) archivé(s) le : mardi 15 novembre 2016 - 04:57:07


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01303377, version 1



Tomáš Kocák, Gergely Neu, Michal Valko. Online learning with noisy side observations. International Conference on Artificial Intelligence and Statistics, May 2016, Seville, Spain. 〈hal-01303377〉



Consultations de la notice


Téléchargements de fichiers