BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Talk of Professor Nicolò Cesa-Bianchi  (University of Milan)
DTSTART:20191009T111500
DTEND:20191009T131500
DTSTAMP:20260916T044054Z
UID:d3839eca4bfd0b6f89e29d9ebdbd1fb4770108d8b1d50ec6f68af795
CATEGORIES:Conferences - Seminars
DESCRIPTION:Professor Nicolò Cesa-Bianchi\nTITLE: Nonstochastic Multiarme
 d Bandits with Unrestricted Delays\n\nABSTRACT:\nWe investigate multiarmed
  bandits with delayed feedback\, where the delays need neither be identica
 l nor bounded. We first prove that the "delayed" Exp3 achieves the [O(\\sq
 rt{(KT + D)\\ln K})]  regret bound conjectured in the case of variable\, 
 but bounded delays. Here\, [K]  is the number of actions and [D]  is the
  total delay over [T]  rounds. We then introduce a new algorithm that lif
 ts the requirement of bounded delays by using a wrapper that skips rounds 
 with excessively large delays. The new algorithm maintains the same regret
  bound\, but similar to its predecessor requires prior knowledge of [D]  
 and [T] . For this algorithm we then construct a novel doubling scheme tha
 t forgoes this requirement under the assumption that the delays are availa
 ble at action time (rather than at loss observation time). This assumption
  is satisfied in a broad range of applications\, including interaction wit
 h servers and service providers. The resulting oracle regret bound is of o
 rder [\\min_\\beta (|S_\\beta|+\\beta \\ln K + (KT + D_\\beta)\\/\\beta)] 
 \, where [|S_\\beta|]  is the number of observations with delay exceeding
  [\\beta] \, and [D_\\beta] is the total delay of observations with delay 
 below [\\beta] . The bound relaxes to [O(\\sqrt{(KT + D)\\ln K})] \, but w
 e also provide examples where [D_\\beta \\ll D]  and the oracle bound has
  a polynomially better dependence on the problem parameters..   Joint wor
 k with Tobias Thune and Yevgeny Seldin  \n\nBIO:\nNicolò Cesa-Bianchi is
  professor of Computer Science at the University of Milan\, Italy. His mai
 n research areas are: design and analysis of machine learning algorithms\;
  algorithms for multiarmed bandit problems with applications to personaliz
 ed recommendations and online auctions\; graph analytics with applications
  to social networks and bioinformatics. On these topics he published over 
 130 papers. He is co-author of the monographs "Prediction\, Learning\, and
  Games" and "Regret Analysis of Stochastic and Nonstochastic Multi-armed B
 andit Problems". He served as President of the Association for Computation
 al Learning\, and is the recipient of a Google Research Award\, a Xerox Fo
 undation UAC Award\, a Criteo Faculty Award\, and a Google Focused Award.
LOCATION:INM 200 https://plan.epfl.ch/?room==INM%20200
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR