Lectures in Active Sequential Hypothesis Testing and Adaptive Exploration in Reinforcement Learning - Lecture 1

Lecture 1: Sample complexity lower bounds for iid models We formalize the pure exploration problem for Multi-Armed bandit models. We formalize the fixed-confidence Best Arm Identification (BAI) problem and derive information-theoretic lower bounds on the sample complexity via change-of-measure arguments. You’ll see how KL divergences between candidate instances yield the characteristic time and the optimal allocation vector. The characteristic time characterizes the complexity of learning, and we will see how to compute it for simple models. Lecture notes will be provided in advance.