Probabilistic methods related to reinforcement learning
Probabilistic methods related to reinforcement learning
TU Berlin Winter 2026/27
TU Berlin Winter 2026/27
Lecturer: Tejas Iyer
Exam details: Oral exam organised in consultion with me.
Class format/location: Lectures every Tuesday from 16:15–17:45. Please consult MOSES and ISIS for the precise schedule and any changes.
Contact: After lectures, or by email at firstname.lastname@wias-berlin.de.
Language: English
Credits: 5 ECTS
Reinforcement learning concerns decision-making under uncertainty when information is acquired through interaction with an environment. An agent must repeatedly choose between using actions that currently appear best and experimenting with other actions in order to learn more. This is known as the exploration–exploitation trade-off.
This course develops a rigorous, proof-based, probabilistic perspective on such problems. Our principal model will be the stochastic multi-armed bandit, the simplest setting in which the exploration–exploitation trade-off can be studied mathematically. We will formulate bandit strategies as adaptive stochastic processes, introduce regret as a measure of performance, and use probabilistic tools such as concentration inequalities to establish quantitative guarantees for learning algorithms.
A central objective will be to understand optimal regret: how well any learning algorithm can perform, and whether particular algorithms attain the best possible rates. Depending on the progress and interests of the class, we may then use bandits as a starting point for more general reinforcement-learning models in which present actions also influence future states.
The emphasis will be on mathematical definitions, probabilistic arguments, and rigorous proofs rather than programming or implementation. No previous background in machine learning or reinforcement learning is required.
The course will primarily concern the probabilistic foundations of stochastic multi-armed bandits. The precise selection and order of topics will be adjusted according to the progress and interests of the class.
Core topics:
Stochastic bandit models: actions, rewards, adaptive learning strategies, regret, and the exploration–exploitation trade-off
Probabilistic tools: sub-Gaussian random variables, concentration inequalities, conditioning, and the analysis of adaptively collected data
Bandit algorithms: selected exploration strategies and upper confidence bound methods
Optimal regret: upper and lower regret bounds, and the optimality or near-optimality of selected algorithms
Flexible topics, depending on class progress and interest:
Further bandit topics:
Model-dependent and minimax notions of optimal regret
Refined confidence-bound algorithms, such as MOSS or KL-UCB
Lai–Robbins and information-theoretic lower bounds
Boltzmann and softmax exploration
Bayesian bandits and Thompson sampling
Policy-gradient methods in the bandit setting
Adversarial or contextual bandits
Tabular reinforcement learning:
Finite Markov decision processes
State- and action-value functions and Bellman equations
Value iteration and policy iteration
Monte Carlo policy evaluation
Stochastic approximation
Temporal-difference learning, SARSA, and Q-learning
Probability I
Probability II is highly encouraged and may be taken concurrently with this course
No previous knowledge of machine learning or reinforcement learning is assumed
Please contact me by email if you have any doubts about the prerequisites
Beyond preparing students for research, this course will develop skills in advanced probabilistic reasoning, rigorous algorithmic analysis, and mathematical problem-solving applicable in statistics, machine learning, technology, finance, and other data-driven fields. Students will also develop their ability to communicate complex mathematical arguments clearly.
On satisfying the requirements of the course, students should be well-equipped to:
Formulate stochastic bandit problems and adaptive learning strategies mathematically
Explain the exploration–exploitation trade-off and the concept of regret
Apply concentration inequalities and other probabilistic tools to sequential decision problems
Analyse selected bandit algorithms and explain, through upper and lower bounds, in what sense their regret rates are optimal or near-optimal
The assessment for this course consists of a 45-minute oral exam. The exam will assess your ability to:
Explain the principal models, algorithms, probabilistic ideas, and results developed in the course, including proofs where appropriate.
Respond to follow-up questions and apply the methods from the course to examples or small variations of material encountered in the lectures and exercises.
The emphasis will be on mathematical understanding and reasoning rather than memorisation. Only topics actually covered during the course will be examinable. More detailed guidance will be provided during the semester.
Links to lecture notes and additional resources will be provided as the course progresses.
The course will draw substantially on:
Döring, L., et al. The Mathematics of Reinforcement Learning.