![\"Photo](\"\/cds-faculty\/files\/2025\/10\/Untitled-design-1024x574.jpg\")
<\/p>\n<\/p>\n
In this lecture series we study the pure exploration problem<\/strong>. This problem is also more commonly known as \u201cSequential Design of Experiments\u201d or \u201cActive Sequential Hypothesis Testing\u201d, and it is an active field of study in Reinforcement Learning problems.<\/p>\n Studying this problem allows us to understand the mechanism of information gathering: the learner\u2019s sole objective is to reduce uncertainty to a decision, disentangling exploration from exploitation. For example, the decision might be about reaching a conclusion about a certain phenomenon. Studying this problem has several applications, ranging from medical diagnosis; faulty sensor detection; A\/B testing and scientific discovery.<\/p>\n In this course we develop an information-theoretic view of pure exploration in Multi-Armed Bandit problems and tabular Reinforcement Learning. Students will learn to (i) formalize fixed-confidence Best Arm Identification (BAI) problems; (ii) derive instance-dependent lower bounds on the sample complexity via change of measure techniques; (iii) design provably correct algorithms that are instance-optimal.<\/p>\n By the end, students will be able to:<\/p>\n Attendance to all lectures is not mandatory, but highly suggested. Lecture notes will be provided before each lecture.<\/p>\n The course will run in person over the last weeks of November.<\/p>\n Prerequisites<\/strong>: knowledge of probability theory (e.g., having taken a class on multi-armed bandit problems).<\/p>\n About the Organizer<\/strong>: Alessio Russo<\/a> is a Postdoc at Boston University, where he works with Prof. Aldo Pacchiano (plaia.ai<\/a>) . He has a Ph.D. in Electrical Engineering from KTH Royal Insitute of Technology (Stockholm), where he was supervised by Prof. Proutiere Alexandre. In his research, he studies problems of adaptive exploration in RL\/Deep-RL and Bandit problems, Statistical Learning in sequential decision making problems and Robust Control\/RL. Website: alessi<\/a>orusso.net<\/a><\/p>\n Date<\/strong>: Fri., Nov. 14 Abstract<\/strong>: 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\u2019ll 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. Date<\/strong>: Mon., Nov. 17 Abstract<\/strong>: This lecture focuses on the design of optimal algorithms for the BAI problem that attain the sample complexity lower bound. We will see how to derive anytime confidence intervals, and design algorithms that are asymptotically optimal in the confidence parameter. We will derive guarantees that hold in high probability, and in expectation. Date<\/strong>: Tues., Nov. 18 Abstract<\/strong>: This lecture focuses on the design of optimal algorithms for the BAI problem that attain the sample complexity lower bound. We will see how to derive anytime confidence intervals, and design algorithms that are asymptotically optimal in the confidence parameter. We will derive guarantees that hold in high probability, and in expectation. Date<\/strong>: Wed., Nov. 19 Abstract<\/strong>: In this lecture we extend the BAI problem to tabular RL: identifying a target property (e.g., the best policy) in a controlled Markov chain. Using change-of-measure over transition kernels, we derive KL-based bounds that depend on state-action occupancy measures rather than arm pulls. The resulting characteristic time shows how mixing, reachability, and visitation constraints shape fundamental sample complexity. Date<\/strong>: Mon., Nov. 24 Abstract<\/strong>: Building on the sample complexity bounds derived in the previous lecture, we will design an algorithm that is asymptotically optimal in the confidence parameter. We will see how the proof for Markov Decision Processes is more challenging than classical Bandit models, and what are the critical aspects in the proof of the sample complexity upper bound.Learning objectives<\/h3>\n
\n
Schedule<\/h3>\n
![\"Headshot](\"\/cds-faculty\/files\/2025\/10\/Alessio-Russo-150x150.jpeg\")
\nLecture 1: Sample complexity lower bounds for iid models<\/h2>\n
\nTime and room<\/strong>: 4-6pm, CDS 164
\nRegistration form<\/strong>: https:\/\/forms.gle\/ohC8KJPPbBt6jrQH8<\/a><\/p>\n
\nLecture notes will be provided in advance.<\/p>\n
\nLecture 2: Stopping rules and design of optimal algorithms<\/h2>\n
\nTime and room<\/strong>: 4-6pm, PHO 117
\nRegistration form<\/strong>: https:\/\/forms.gle\/ohC8KJPPbBt6jrQH8<\/a><\/p>\n
\nLecture notes will be provided in advance.<\/p>\n
\nLecture 3: Stopping rules and design of optimal algorithms<\/h2>\n
\nTime and room<\/strong>: 4-6pm, STH 319
\nRegistration form<\/strong>: https:\/\/forms.gle\/ohC8KJPPbBt6jrQH8<\/a><\/p>\n
\nLecture notes will be provided in advance.<\/p>\n
\nLecture 4: Instance-dependent lower bounds for Markov Decision Processes (MDPs) and algorithm design<\/h2>\n
\nTime and room<\/strong>: 4-6pm, PHO 117
\nRegistration form<\/strong>: https:\/\/forms.gle\/ohC8KJPPbBt6jrQH8<\/a><\/p>\n
\nLecture notes will be provided in advance.<\/p>\n
\nLecture 5: Instance-dependent lower bounds for Markov Decision Processes (MDPs) and algorithm design<\/h2>\n
\nTime and room<\/strong>: 4-6pm, PHO 117
\nRegistration form<\/strong>: https:\/\/forms.gle\/ohC8KJPPbBt6jrQH8<\/a><\/p>\n
\nLecture notes will be provided in advance.<\/p>\n
\nLecture 6: Bayesian Active Sequential Hypothesis Testing<\/h2>\n