BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1538
DTSTAMP:20250327T045814Z
SUMMARY:On minimax optimality in the active simple hypotheses testing probl
 em.
DESCRIPTION:Speaker: Sushant Vijayan (TIFR)\n\nAbstract: \nIn this talk\, w
 e consider the following online decision making problem: Given a set of un
 certain alternatives how must one take decisions so that one minimizes the
  error probability of choosing a suboptimal alternative given a fixed samp
 le budget. This is motivated by practical applications in diverse fields l
 ike drug trials\, online advertising and sensor placement and more general
 ly in areas of online decision making where the samples cannot be generate
 d in a sequential manner and have a fixed limited budget. This problem is 
 called the Fixed Budget Best Arm identification (FB-BAI) in the Multi Arme
 d Bandit (MAB) community but has also been studied by the research communi
 ties in online decision making\, simulation\, operations research and info
 rmation theory.In Komiyama et. al (2022) an information theoretic lower bo
 und and a matching algorithm assuming access to a computationally and anal
 ytically intractable oracle was proposed. As this is a difficult problem t
 o handle in this level of generality\, we instead study a special case of 
 FB-BAI: Active Simple Hypothesis Testing (ASHT). Even in this simplified s
 etting\, optimal algorithms and their information theoretic limits are not
  well understood. In the ASHT setting\, we place Komiyama et al's bounds i
 n a game theoretic framework and show that it is the value function of a c
 ertain differential game. We show that this value function is the viscosit
 y solution to an associated Hamilton-Jacobi-Isaac(HJI) Partial Differentia
 l Equation (PDE). This PDE formulation allows us to derive new bounds on e
 rror exponents\, produce a counterexample to a conjecture of Komiyama et a
 l and create a computationally tractable $\\epsilon$-optimal algorithm whe
 n the action set (A) of the hypotheses is small. As the PDE approach is co
 mputationally difficult for moderate size A\, we use a novel link of ASHT 
 with approachability problems to propose a new approachability algorithm t
 hat is provably better than the best static algorithms. Further\, we numer
 ically observe that in certain problem instances\, the proposed algorithm 
 attains the optimal exponent.We will give a broad introduction to the prob
 lem. The technical details will be kept to a minimum to make the talk more
  accessible.Reference: Komiyama et al.: https://arxiv.org/pdf/2206.04646
 \n
URL:https://www.tcs.tifr.res.in/web/events/1538
DTSTART;TZID=Asia/Kolkata:20250328T160000
DTEND;TZID=Asia/Kolkata:20250328T170000
LOCATION:Screening in A-201 with Zoom
END:VEVENT
END:VCALENDAR