Online learning with noisy side observations
Type de document :
Communication dans un congrès avec actes
Titre :
Online learning with noisy side observations
Auteur(s) :
Kocák, Tomáš [Auteur]
Sequential Learning [SEQUEL]
Neu, Gergely [Auteur]
Sequential Learning [SEQUEL]
Valko, Michal [Auteur]
Sequential Learning [SEQUEL]
Sequential Learning [SEQUEL]
Neu, Gergely [Auteur]
Sequential Learning [SEQUEL]
Valko, Michal [Auteur]
Sequential Learning [SEQUEL]
Titre de la manifestation scientifique :
International Conference on Artificial Intelligence and Statistics
Ville :
Seville
Pays :
Espagne
Date de début de la manifestation scientifique :
2016-05-09
Discipline(s) HAL :
Statistiques [stat]/Machine Learning [stat.ML]
Résumé en anglais : [en]
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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-01303377/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-01303377/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-01303377/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- kocak2016online.pdf
- Accès libre
- Accéder au document