FEL3260 Sequential Decision Making under Uncertainty 8.0 credits

Overview and examples of sequential decision problems.

PART I - Stochastic models

1. Review of essential probabilistic tools. Markov chains, Martingales, basic concentration inequalities.

2. Discrete time Markov Decision Processes (MDPs).

                             2a. Finite time-horizon. Principle of optimality, backward induction.

                             2b. Infinite time-horizon. Principle of optimality, value / policy iteration, modified                      policy iteration, linear programming.  

3. Solving MDPs - part 1. Exact solutions based on structural properties of the MDP.

4. Solving MDPs - part 2. Some approximation methods.

5. Extensions. Constrained MDPs, Partially Observable MDPs, Decentralized MDPs.

6. Limit theorems. Going from MDPs to deterministic continuous-time control and back.

7. Optimal stopping time problems.

8. Kalman filter.

9. Prediction with expert advice and Multi-Armed Bandit (MAB) problems.

PART II - Adversarial models and Games.

1. Prediction with expert advice and MAB problems in adversarial scenarios.

2. Sequential decision making in games. Internal regret, Correlated equilibria, Convergence to and selection of Nash Equilibria.

3. Recent advances in online optimization.

After completing this course, students should be able to rigorously formulate and classify sequential decision problems, to estimate their tractability, and to propose and efficiently implement methods towards their solutions.

N/A

A list of books will be provided, but the lecture notes provided will contain all key concepts and points developed during the course.  

If the course is discontinued, students may request to be examined during the following two academic years.

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

N/A

·         25%: 20 min presentation in one of the lectures

·         25%: Solutions to homework problems

·         50%: Project (the project may be conducted either alone or in pair, and could be related to the students’ own research problems)

Alexandre Proutiere

• All members of a group are responsible for the group's work.
• In any assessment, every student shall honestly disclose any help received and sources used.
• In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.