Dear all, I'm Alessio Russo, a Postdoc at Boston University (PLAIA group).

I’m planning a PhD-level short course on pure exploration and sequential hypothesis testing with a focus on deriving lower and upper bounds for fixed-confidence problems in best-arm identification (Multi-Armed Bandit Problems) and best-policy identification (tabular Reinforcement Learning). If time permits, we will also cover Quickest Change Detection and Bayesian Sequential Hypothesis Testing.

Core techniques include:

• Change-of-measure/KL lower bounds

• Stopping/recommendation rules

• Analysis of the sample complexity
  
  

What the course covers (concise overview):
We develop an information-theoretic view of pure exploration in bandits and tabular RL. Students will learn to (i) formalize fixed-confidence BAI/BPI, (ii) derive instance-dependent lower bounds via change of measure, (iii) design delta-correct stopping and recommendation rules, and (iv) match lower bounds with algorithms whose sample complexity is instance-optimal up to constants or logs. Optional modules introduce quickest change detection and Bayesian sequential testing to contrast frequentist vs Bayesian objectives.

Learning objectives

By the end, students will be able to:

1. Specify fixed-confidence BAI/BPI problem statements and correctness criteria.

2. Derive KL-based change-of-measure lower bounds and interpret instance complexity terms.

3. Construct sequential tests (stopping + recommendation) and prove δ-correctness.

4. Analyze sample complexity (upper bounds) for canonical algorithms and compare to lower bounds.

5. Extend BAI tools to tabular RL BPI

Schedule

The course will run in person at the faculty of Computing and Data Sciences at Boston University over the last  2 weeks of November: 3 sessions per week, 2 hours per session. 

Tentative Schedule (4-6pm EST) :

- Friday 14/11, CDS 164  

- Monday 17/11, PHO 117A (Confirmed)

- Tuesday 18/11, STH 319 (Confirmed)

- Wednesday 19/11, PHO 117A (Confirmed)

- Monday 24/11, PHO 117A (Confirmed)

- Tuesday 25/11, CAS 424 (Confirmed)

Classes will be recorded, and videos will be posted online. A zoom link will also be available for attending remotely.

Prerequisites and Registration

Prerequisites: knowledge of probability theory (e.g., having taken a class on multi-armed bandit problems).

If you’re interested, please send me an email (arusso2@bu.edu).

Disclaimer: the content/calendar of the course may change in the future.