BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1594
DTSTAMP:20250723T100826Z
SUMMARY:Adversarial Bandits with Knapsacks
DESCRIPTION:Speaker: Aakash Ghosh (TIFR)\n\nAbstract: \nWe consider Bandit
 s with Knapsacks (henceforth\, BwK)\, a general model for multi-armed ba
 ndits under supply/budget constraints. In particular\, a bandit algorithm 
 needs to solve a well-known knapsack problem: find an optimal packing of 
 items into a limited-size knapsack. The BwK problem is a common generaliza
 tion of numerous motivating examples\, which range from dynamic pricing to
  repeated auctions to dynamic ad allocation to network routing and schedul
 ing. While the prior work on BwK focused on the stochastic version\, we pi
 oneer the other extreme in which the outcomes can be chosen adversarially.
  This is a considerably harder problem\, compared to both the stochastic v
 ersion and the “classic” adversarial bandits\, in that regret minimiza
 tion is no longer feasible. Instead\, the objective is to minimize the co
 mpetitive ratio: the ratio of the benchmark reward to algorithm’s reward
 .\n \nWe design an algorithm with competitive ratio O(log T) relative t
 o the best fixed distribution over actions\, where T is the time horizon
 \; we also prove a matching lower bound. The key conceptual contribution i
 s a new perspective on the stochastic version of the problem. We suggest a
  new algorithm for the stochastic version\, which builds on the framework 
 of regret minimization in repeated games and admits a substantially simple
 r analysis compared to prior work. We then analyze this algorithm for the 
 adversarial version\, and use it as a subroutine to solve the latter.\n \
 nAuthors: Nicole Immorlica\, Karthik Sankararaman\, Robert Schapire\, A
 leksandrs SlivkinsAuthors Info & Claims\nJournal of the ACM\, Volume 69
 \, Issue 6\nArticle No.: 40\, Pages 1 - 47\nhttps://doi.org/10.1145/3
 557045\n
URL:https://www.tcs.tifr.res.in/web/events/1594
DTSTART;TZID=Asia/Kolkata:20250723T163000
DTEND;TZID=Asia/Kolkata:20250723T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR