BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1768
DTSTAMP:20260831T062156Z
SUMMARY:Sequential Decision-Making under Uncertainty and Constraints: A Syn
 thesis of Differential Games and Stochastic Bandits.
DESCRIPTION:Speaker: Sushant Vijayan (TIFR)\n\nAbstract: \n\nIn this thesis
 \, we study sequential decision-making problems under uncertainty and cons
 traints. We consider four different problems:\nFor online regret minimizat
 ion in linear bandits with observations\, we propose a phased elimination 
 algorithm OOPE and give its regret upper bound in terms of the offline da
 ta's Grammian eigenspectrum. We establish regret lower bounds that help es
 tablish the minimax optimality of OOPE in certain regimes and improve on e
 xisting work. This also shows that the quality of offline data is well mea
 sured by the eigenspectrum of the Grammian matrix of the offline data.\nIn
  automated bidding systems with unknown value and long-term budget and Re
 turn-on-Spend (RoS) constraints\, a UCB-based computationally efficient al
 gorithm is developed. We do away with restrictive assumptions like strict 
 Slater feasibility and truthfulness of the auction\,  and obtain optimal 
 regret and constraint violation bounds with logarithmic dependence on the 
 bid domain size.\nWe model infectious disease spread as a differential gam
 e between a planner and the populace\, characterizing open-loop Nash equil
 ibria using Pontryagin's Minimum Principle. We use the developed model to 
 study the qualitative characteristics in equilibrium and bring out the cru
 cial roles of infection detection rates and public trust in reported infec
 tion numbers. \nFor Active Simple Hypothesis Testing (ASHT) with a fixed 
 budget\, we characterise the minimax error exponent as the value of a zero
 -sum differential game. This reformulation leads to a more computationally
  tractable algorithm compared to prior work. This problem has attracted si
 gnificant interest in many different research communities like Simulation\
 , Operations Research\, Information Theory and Bandits. This characterizat
 ion of the error exponent and the development of a provably optimal\, comp
 utationally tractable algorithm constitute significant progress on the pro
 blem. However\, even this provably optimal algorithm suffers from a \\emph
 {curse of dimensionality}. We propose a more efficient algorithm leveragin
 g a novel link to Blackwell Approachability. This more efficient approacha
 bility algorithm provably outperforms non-adaptive strategies and is numer
 ically verified to attain the optimal exponent in certain instances.\nThe 
 first two problems utilize only bandit techniques\, and the third employs 
 methods of differential games\; the final problem combines differential ga
 me theory with a classical bandit setup\, showcasing a synthesis of both d
 istinct and integrated applications of these two frameworks.\n
URL:https://www.tcs.tifr.res.in/web/events/1768
DTSTART;TZID=Asia/Kolkata:20260904T163000
DTEND;TZID=Asia/Kolkata:20260904T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR