Papers by:
(1)"Best Arm Identification in Multi-Armed Bandits" by Audibert and Bubeck, 2010.
(2)"Tight (Lower) Bounds for the Fixed Budget Best Arm IdentificationBandit Problem" Carpentier and Locatelli 2016.

We show EOPL=PLS PPAD. Here the class EOPL consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubacek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020).

Reconfiguring a system (generally represented by a graph) means gradually transforming one configuration of the system to another configuration by modifying it in a slow and steady step-by-step manner.

One of the fundamental components of quantum theory is measurement. one can think of measurement as the interface between the quantum world and our everyday world.

We will see how Fano's inequality, a classical result from information theory, can be used to get tight lower bounds on sample complexity of various learning problems.