Online learning with noisy side observations - Archive ouverte HAL Access content directly
Conference Papers Year :

Online learning with noisy side observations

(1) , (2, 1) , (1)
1
2
Tomáš Kocák
  • Function : Author
  • PersonId : 955512
Michal Valko

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.
Fichier principal
Vignette du fichier
kocak2016online.pdf (821.52 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01303377 , version 1 (18-04-2016)

Identifiers

  • HAL Id : hal-01303377 , version 1

Cite

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⟩
144 View
142 Download

Share

Gmail Facebook Twitter LinkedIn More