BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
X-WR-CALNAME: CAM Colloquium:  Alex Slivkins (Microsoft Research NYC) - Adv
 ersarial Bandits with Knapsacks
X-WR-TIMEZONE:Eastern Time (US & Canada)
BEGIN:VEVENT
DTSTAMP:20260515T052453Z
UID:tag:localist.com\,2008:EventInstance_31149800657177
DTSTART:20191122T203000Z
DTEND:20191122T213000Z
DESCRIPTION:Abstract:\n"Bandits with Knapsacks" (BwK) is a general model fo
 r multi-armed bandits under supply/budget constraints\, with motivating ex
 amples ranging from dynamic pricing to repeated auctions to dynamic ad all
 ocation to network routing and scheduling. While the prior work on BwK foc
 used on the stochastic version\, we pioneer the other extreme in which the
  outcomes can be chosen adversarially. The objective now is to minimize th
 e "competitive ratio": the ratio of the benchmark reward to algorithm's re
 ward\, as regret minimization is no longer feasible.\n\nWe design an algor
 ithm with competitive ratio O(log T) relative to the best fixed distributi
 on over actions\, where T is the time horizon\; we also prove a matching l
 ower bound. The key conceptual contribution is a new algorithm for the sto
 chastic version of the problem\, which builds on the framework of regret m
 inimization in repeated games and admits a substantially simpler analysis 
 compared to prior work. We then analyze this algorithm for the adversarial
  version\, and use it as a subroutine to solve the latter. This approach a
 lso leads to several extensions\, both for stochastic and adversarial vers
 ions.\n\nJoint work with Nicole Immorlica\, Karthik A. Sankararaman\, and 
 Robert Schapire.\n\nBio:\nAlex Slivkins is a Principal Researcher at Micro
 soft Research New York City. Previously he was a researcher at MSR Silicon
  Valley after receiving his Ph.D. from Cornell and a brief postdoc at Brow
 n. His research interests are in algorithms and theoretical computer scien
 ce\, spanning machine learning theory\, algorithmic economics\, and networ
 ks. Alex is particularly interested in exploration-exploitation tradeoff a
 nd online machine learning\, and their manifestations in mechanism design 
 and human computation. His work has been recognized with the best paper aw
 ard at ACM EC 2010\, the best paper nomination at WWW 2015\, and the best 
 student paper award at ACM PODC 2005. He is finishing a book\, Introductio
 n to Multi-armed Bandits\, to be published with Foundations and Trends in 
 Machine Learning.
GEO:42.443451;-76.481506
LOCATION:Frank H. T. Rhodes Hall\, 655
SUMMARY: CAM Colloquium:  Alex Slivkins (Microsoft Research NYC) - Adversar
 ial Bandits with Knapsacks
URL;VALUE=URI:https://events.cornell.edu/event/cam_colloquium_alex_slivkins
 _microsoft_research_nyc_-_adversarial_bandits_with_knapsacks
CATEGORIES:Colloquium
END:VEVENT
END:VCALENDAR