Reinforcement Learning and Decision Making Under Uncertainty

General course information

Reinforcement learning

Reinforcement learning is the problem of learning to act through interaction with an unknown environment. It is not:

• A solution.
• Supervised learning
• Unsupervised learning.

However, algorithms for reinforcement learning can use (un)supervised learning algorithms as components.

Uncertainty and sequential decision making are central in reinforcement learning.

Course structure

The course will give a thorough introduction to reinforcement learning. The first 8 weeks will be devoted to the core theory and algorithms of reinforcement learning. The final 6 weeks will be focused on project work, during which more advanced topics will be inroduced.

The first 6 weeks will require the students to complete 5 assignments. The remainder of the term, the students will have to prepare a project, for which they will need to submit a report.

The course is run in parallel with a seminar course.

Course Schedule

Prerequisites

No previous machine learning knowledge is needed.

Mathematics

The following topics must be absolutely mastered, although a refresher will be given as needed.

1. Set theory and logic.
2. Probability and expectation.
3. Elementary calculus (limits, integration, differentiation)
4. Elementary linear algebra (vector and matrix manipulations)

Programming

• Mature programming ability, preferably in python.
• Use of git or other version control system
• Use of (La)TeX.

Course Books

• Course book Decision Making Under Uncertainty and Reinforcement Learning, Dimitrakakis and Ortner
• Basic RL Reference Reinforcement Learning: An Introduction, Sutton and Barto.
• Statistical reference Optimal Statistical Decisions, De Groot.
• MDP Reference Markov Decision Processes, Putterman.
• Quick Reference Algorithms for Reinforcement Learning, Czepesvari.
• Huge Reference Dynamic Programming and Optimal Control, Bertsekas.
• Advanced Neurodynamic Programming, Bertsekas and Tsitsiklis.
• Advanced Bandit Algorithms, Czepesvari and Lattimore

Use of External Aids (Books, LLMs, Wikipedia, etc)

In this course, the use of automated methods for writing and translating text, such generative AI models, web-based translation and code development tools is allowed under certain conditions.

The general principle is the following:

To understand it, you must do it yourself.

The recommended workflow is this: read the material, think of a solution for yourself, try and implement it, and then ask for help in the specific place you get stuck. If you remain in class during the exercises, then you will be able to solve most of the high-level problems with me or the assistant. You can also ask for help in the forums. Do so early.

The general idea for the use of advanced algorithms is the same as when you are using any other external resource, such as verbal advice, online forums, or material from books or websites. In all cases, you are not allowed to present anybody’s work as your own work. This includes both human and machine generated output. Misrepresentation will be considered misuses in this class. So, you must cite each and every use of any external tool, reference, or personal help. Here are some examples:

1. Verbal advice: Cite as “A. Student: Personal Communication”
2. Online forums: Stackoverflow is an example. Cite as “We based this part of the work on URL where we modified the code to … ”
3. Books or websites: Cite normally explaining how you used the material, e.g. “From Theorem 1 (Aardvark et al, 1975) which we reproduce here…”
4. Automated translation: Specify what you used and where. Note, however, that you can write your reports in French or English. Use [*] superscripts.
5. Advanced coding aids: Specify what you used, including generative-AI. Say where you used it exactly, so we can filter out. eg “We used X-Bot to implement to set up the data structures”.
6. Advanced models for grammar and rewriting: Specify which model you used and for which parts of the text. Highlight the edited text in a different colour.
7. Advanced models for text structuring and code architecture. You are not encouraged to do that: we can discuss this in class if needed. However, if you do make use of such models, then you must explain how you used them, including a copy of the intermediate output.
8. You must use a git repository to create your work. This way we can track changes.
9. If you do not stick to the above advice, then the automated AI-detection tools may provide false positives, or you may fail.

1. You will be tested in the oral presentation.

When using any external tool, you must be aware that the answers can be incorrect, or you may apply them in the wrong way. We have seen examples of this even before the chatbot era, when people were copying from other students, or collating answers from stackoverflow to produce a Frankestein monster of a project.

Grading

Project

There are two main types of projects, though a project can be hybrid.

Application project.

Application projects proposals need to contain the following:

• Domain description and goals: What is the problem, in general terms, and which aspect would you try and solve in an MDP/RL framework? Make sure to cite relevant literaure.
• Methodology: How would you formalise the problem mathematically? Which algorithms and/or models do you intend to apply at different stages of the project? Feel free to read widely about both the problem and algorithms and do cite relevant literature.
• Experiment design: How would you know that the method is working? How would you compare with existing solutions? In what context would you expect an improvement? How would you measure it? How will you test the robustness of your solution over variations in the problem instance?
• Expected results: What results do you expect to obtain, and what do you think might go wrong? In what way do you expect an improvement?

Algorithmic project.

• Algorithmic/theory problem and goals: What is the deficiency, in general terms, of current theory and algorithms that your method would try to improve? As an example, the goal could be reducing computational complexity, increasing data efficiency, improving robustness or applicability of a specific family of algorithms; or introducing a slightly different setting to existing ones. In other words, which is the open problem you will be addressing? Make sure to cite relevant literature to better identify the problem.
• Methodology: What kind of existing algorithms, theory or technical result would you rely on? Would you be combining various existing results? What would be the most significant novelty of your methodology? Do cite relevant literature.
• Experiment design (if applicable): How would you know that the method is working? How would you compare with existing solutions? In what context would you expect an improvement? How would you measure it?
• Expected results: What results do you expect to obtain, and what do you think might go wrong? In what way do you expect an improvement?

Grading for projects:

Grades will be adjusted based on group size with on letter grade up/down for double/half the mean group size. See also the detailed Examination rubrics.

• Environments: A. Complex, well described environment that captures all of the elements of the application or algorithmic cproblem. B. The environment is simple or lacks description. C. An adequate environment that captures the basic setting. D. Insufficient environment or description. E. Insuffcient environment and description.
• Algorithms: A. Significantly novel algorithms that are well described. B. Some novelty in the algorithms, with good descriptions. C. Some novelty in the algorithms, but descriptions are lacking. D. Insufficient novelty or descriptions. E. Insufficient novelty and descriptions.
• Experiments: A. Thorough experiments with ablation tests and comparisons over algorithms and environments, that are well-described. B. Somewhat incomplete experiments or descriptions. C. Sufficient experiments and descriptions. D. Insufficient experiments or descriptions. E. Insufficient experiments and descriptions.

Prerequisites

Essential

• Mathematics (Calculus, Linear Algebra)
• Python programming.

Recommended

• Elementary knowledge of probability and statistics.

Examination

There is one project, taking up 40% of the credit. There is one written exam, for 40% of the credit. Assignments, for 20% of the credit.

Criteria for full marks in each part of the project are the following.

1. Documenting of the work in a way that enables reproduction.
2. Technical correctness of their analysis.
3. Demonstrating that they have understood the assumptions underlying their analysis.
4. Addressing issues of reproducibility in research.
5. Consulting additional resources beyond the source material with proper citations.

The follow marking guidelines are what one would expect from students attaining each grade.

A

1. Submission of a detailed report from which one can definitely reconstruct their work without referring to their code. There should be no ambiguities in the described methodology. Well-documented code where design decisions are explained.
2. Extensive analysis and discussion. Technical correctness of their analysis. Nearly error-free implementation.
3. The report should detail what models are used and what the assumptions are behind them. The conclusions of the should include appropriate caveats. When the problem includes simple decision making, the optimality metric should be well-defined and justified. Simiarly, when well-defined optimality criteria should given for the experiment design, when necessary. The design should be (to some degree of approximation, depending on problem complexity) optimal according to this criteria.
4. Appropriate methods to measure reproducibility. Use of an unbiased methodology for algorithm, model or parameter selection. Appropriate reporting of a confidence level (e.g. using bootstrapping) in their analytical results. Relevant assumptions are mentioned when required.
5. The report contains some independent thinking, or includes additional resources beyond the source material with proper citations. The students go beyond their way to research material and implement methods not discussed in the course. See section on LLMs.

B

1. Submission of a report from which one can plausibly reconstruct their work without referring to their code. There should be no major ambiguities in the described methodology.
2. Technical correctness of their analysis, with a good discussion. Possibly minor errors in the implementation.
3. The report should detail what models are used, as well as the optimality criteria, including for the experiment design. The conclusions of the report must contain appropriate caveats.
4. Use of an unbiased methodology for algorithm, model or parameter selection.
5. The report contains some independent thinking, or the students mention other methods beyond the source material, with proper citations, but do not further investigate them.

C

1. Submission of a report from which one can partially reconstruct most of their work without referring to their code. There might be some ambiguities in parts of the described methodology.
2. Technical correctness of their analysis, with an adequate discussion. Some errors in a part of the implementation.
3. The report should detail what models are used, as well as the optimality criteria and the choice of experiment design. Analysis caveats are not included.
4. Use of a possibly biased methodology for algorithm, model or parameter selection - but in a possibly inconsistent manner.
5. There is little mention of methods beyond the source material or independent thinking.

D

1. Submission of a report from which one can partially reconstruct most of their work without referring to their code. There might be serious ambiguities in parts of the described methodology.
2. Technical correctness of their analysis with limited discussion. Possibly major errors in a part of the implementation.
3. The report should detail what models are used, as well as the optimality criteria. Analysis caveats are not included.
4. Some effort for methodological algorithm/parameter selection.
5. There is little mention of methods beyond the source material or independent thinking.

E

1. Submission of a report from which one can obtain a high-level idea of their work without referring to their code. There might be serious ambiguities in all of the described methodology.
2. Technical correctness of their analysis with very little discussion. Possibly major errors in only a part of the implementation.
3. The report might mention what models are used or the optimality criteria, but not in sufficient detail and caveats are not mentioned.
4. Reproducibility is only partially addressed.
5. There is no mention of methods beyond the source material or independent thinking.

F

1. The report does not adequately explain their work.
2. There is very little discussion and major parts of the analysis are technically incorrect, or there are errors in the implementation.
3. The models used might be mentioned, but not any other details.
4. There is no effort to ensure reproducibility or robustness in the project.
5. There is no mention of methods beyond the source material or independent thinking.

cd

Course Schedule

Week	Topic	Seminar
1	Reinforcement learning
	Beliefs and Decisions
2	Bayesian Decision Rules	Sufficient statistics
	Bayesian inference and decisions exercises	Concentration inequalities
3	Bandit problems.
	Bandit problem exercises.
4	Finite Horizon MDPs
	Backwards Induction
	The Bandit MDP
5	Finite Horizon Lab
6	Infite Horizon MDPs
	Value Iteration
	Policy Iteration
7	Sarsa / Q-Learning
8	Model-Based RL
9	Function Approximation, Gradient Methods
10	Bayesian RL: Dynamic Programming, Sampling
11	UCB/UCRL/UCT.
	UCT/AlphaZero.
12	Project Lab
13	Project presentations
14	Q&A, Mock exam

Seminar Schedule

The first meeting will be jointly with the RL course. There will be scheduled progress meetings, and room B013 will be available for group work otherwise. The professor responsible and the students will normally also be available for questions during this time, but alternative times could be scheduled.

2026.02.17	8:45 A017	- Joint RL Course
2026.02.24	14:15 B013	Single-Agent Intro: Bandits, MDPs
2026.03.03	14:15 B013	Supervisor/Topic selection
2026.03.10	14:15 B013	First supervisor meeting
2026.03.17	14:15 B013	Group work
2026.03.24	14:15 B013	Group work
2026.03.31	14:15 B013	Progress meeting
2026.04.07	14:15 B013	Easter break
2026.04.14	14:15 B013	Group work
2026.04.21	14:15 B013	Group work
2026.04.28	14:15 B013	Progress meeting
2026.05.05	14:15 B013	Group work
2026.05.12	14:15 B013	Group work
2026.05.19	14:15 B013	Group work
2026.05.26	14:15 B013	Project Presentation

Modules

Beliefs and decisions

Utility theory (90’)

1. Rewards and preferences (15’)
2. Transitivity of preferences (15’)
3. Random rewards (5’)
4. Decision Diagrams (10’)
5. Utility functions and the expected utility hypothesis (15’)
6. Utility exercise: Gambling (10’ pen and paper)
7. The St. Petersburg Paradox (15’)
8. Preferences

We assume that, given a choice between items in a set of possible rewards $R$, we have a complete preference order, meaning that, for any $a, b ∈ R$, we either:

(I) Prefer $a$ to $b$, and write $a \succ^* b$ (II) Prefer $b$ to $a$, and write $a \prec^* b$ (III) We are indifferent between $a$ and $b$, and write $a \eqsim^* b$

1. Transitivity

The above assumptions do not preclude cycles. However, we can also assume that:

If $a \succ^* b$ and $b \succ^* c$ then $a \succ^* c$.

1. Random rewards.

Now consider the case where, instead of directly choosing rewards, we make a choice, and then obtain a random reward. Here, the reward depends in some way in our decision, but we are not sure exactly how.

Examples:

• Choosing between taking the train and a car.
• Gambling in a casino.
• Deciding how much to study for the exam.

Probability primer

1. Objective vs Subjective Probability: Example (5’)
2. Relative likelihood: Completeness, Consistency, Transitivity, Complement, Subset (5’)
3. Measure theory (5’)
4. Axioms of Probability (5’)
5. Random variables (5’)
6. Expectations (5’)
7. Expectations exercise (10’)
8. Objective vs Subjective probability

• Quantum Physics: There is real underlying randomness. The probabilities of all possible outcomes can be computed exactly a priori
• Coin toss: We model our uncertainty about the outcome through randomness. However, the coin is not really random, and we must experiment to determine the proportion of each possible outcome. We simply lack the information to compute the probabilities a priori.

Everything that can possibly happen is contained in the universe of events $Ω$.

Events $A, B ⊂ Ω$ are subsets of the universe. This can be visualised in the coin tosses example.

1. Relative Likelihood

$A, B$ are possible events, satisfying these properties:

(I) Completeness: $A \succ B$, $A \prec B$ or $A \eqsim B$ for any $A,B$ (II) Transitivity: If $A \succ B, B \succ C$ then $A \succ C$ (III) Complement: If $A \succ B$ then $¬ A \prec ¬ B$. (IV) Implication: $A ⊂ B ⇒ A \prec B$

1. Measure theory

We can use probability to quantify this, so that $A > B$ iff $P(A) > P(B)$. But what do we mean by this?

Measure as a concept: area, length, probability $M(A) + M(B) = M(A ∪ B)$

1. Axioms of Probability

$P : Σ → [0,1]$ $P(∅) = 0$ $P(Ω) = 1$ If $A ∩ B = ∅$, $P(A ∪ B) = P(A) + P(B)$.

1. Exercise: Prove that P satisfies the given properties of relative likelihood.
2. Random variables

If $ω$ is distributed according to $P$, then the function $f(ω)$, with $f: Ω → \Reals$, is a random variable with distribution $P_f$, where: \[ P_f(A) = P(\{ω : f(ω) ∈ A\}) \]

1. Expectations

$E_P[f] = ∑_ω f(ω) P(ω)$.

Lab: Probability, Expectation, Utility

1. Exercise Set 1. Probability introduction.
2. Exercise Set 2. Sec 2.4, Exercises 4, 5.

Assignment.

Exercise 7, 8, 9.

Further Reading:

Decision Making Under Uncertainty and Reinforcement Learning. Chapter 1, 2.

Seminar:

Utility. What is the concept of utility? Why do we want to always maximise utility?

Example:

U	w1	w2
a1	4	1
a2	3	3

Regret. Alternative notion.

L	w1	w2
a1	0	2
a2	1	0

Minimising regret is the same as maximising utility when w does not depend on a. Hint: So that if $E[L|a^*] \leq E[L|a]$ for all $a’$, $E[U|a^*] \geq E[L|a]$ for all $a’$,

The utility analysis of choices involving risk: https://www.journals.uchicago.edu/doi/abs/10.1086/256692

The expected-utility hypothesis and the measurability of utility https://www.journals.uchicago.edu/doi/abs/10.1086/257308

Statistical decisions

Simple statistical decisions (30’)

1.. MSE Estimation (5’) [not done]

1. Linearity of Expectations (5’) [not done]
2. Convexity of Bayes Decisions (5’) [not done]

Problems with Observations (35’)

1. Discrete set of models example: the meteorologists problem (15’)
2. Marginal probabilities (5’).
3. Conditional probability (5’).
4. Bayes theorem (10’).

The meteorologists problem

-$n$ metereological stations $\MDPs = \{1, \ldots, n\}$.

• $x_t$: Weather on day t (0 = dry, 1 = rain)$
• $P_\mdp(x_t | x_t-1, x_t-2, \ldots)$ station $\mdp$ prediction for dry/rain.

Station	Day 1	Day 2	Day 3	Day 4
1	60%	50%	40%	30%
2	30%	25%	20%	15%
3	40%	50%	50%	40%

• How should we combine these predictions?

Statistical decisions (45’)

Simplified notation

ML Estimation (10’)

• $ω_ML = \argmax_ω P(x | ω)$.
• $a^* = \argmax_a U(ω_ML, a)$.

MAP Estimation (10’)

• $ω_MAP = \argmax_ω P(ω | x)$
• $a^* = \argmax_a U(ω_MAP, a)$.

Bayes Estimation (10’)

• $a^* = \argmax_a ∑_ω P(ω | x) U(ω, a)$.

Statistical estimation (45’)

Model-index notation.

• A family of models $\{P_μ | μ ∈ \MDPs\}$
• Data $x$.

Maximum Likelihood Estimation

• Find $μ$ maximising $P_μ(x)$

Maximum A Posteriori Estimation

• Prior belief $\bel$
• Find $μ$ maximising $\bel(μ) P_μ(x)$

Bayesian Estimation

• Return function $\bel(μ | x) = P_μ(x) \bel(μ) / ∑_μ’ P_μ’(x) \bel(μ’)$

(Bayesian) MSE Estimation

• Find $\hat{μ}$ minimising $\E_\bel[(\hat{μ} - μ)^2 | x] = ∑_μ (\hat{μ} - μ)^2 \bel(μ | x)$

Maximum Likelihood Estimation

• Input: Data $x_1, \ldots, x_t$, A set of models $\{P_\mdp | \mdp ∈ \MDPs\}$
• Inference: The model $\mdp^*_ML$ maximising \[ P_\mdp(x_1, \ldots, x_t) \]
• Prediction: $P_{\mdp^*_{ML}}(x_t+1 | x_1, \ldots, x_t)$.

Maximum A Posteriori Estimation

• Input: Data $x_1, \ldots, x_t$, set of models $\{P_\mdp | \mdp ∈ \MDPs\}$, prior $\bel(\mdp)$ on models
• Inference: The model $\mdp^*_MAP$ maximising \[ P_\mdp(x_1, \ldots, x_t) \bel(\mdp) \]
• Prediction: $P_{\mdp^*_{MAP}}(x_t+1 | x_1, \ldots, x_t)$.

Bayesian Estimation

• Input: Data $D$, set of models $\{P_\mdp | \mdp ∈ \MDPs\}$, prior $\bel(\mdp)$ on models
• Inference: The posterior probability over models: \[ \bel(\mdp | x_1, \ldots, x_t) = \frac{P_\mdp(x_1, \ldots, x_t) \bel(\mdp)}{∑_\mdp’ P_\mdp’(x_1, \ldots, x_t) \bel(\mdp)} \]
• Prediction: $P(x_t+1 | x_1, \ldots, x_t) = ∑_\mdp P_\mdp(x_t+1 | x_1, \ldots, x_t)$.

MSE estimation

Sometimes we care about finding a point estimate for some distribution. For example, let us say we have some distribution $\bel$ over some unknown variable $\mdp$ and we need to select one $\mdp$, and we want to report a value $\mdp^*$ minimising the squared error $(\mdp - \mdp^*)^2$ in expectation \[ \E_\bel[(\mdp - \mdp^*)^2] = ∫_\MDPs (\mdp - \mdp^*)^2 d \bel(\mdp) \] To find the minimising $\mdp^*$ we can take the derivative \[ d/d\mdp^* \E_\bel[(\mdp - \mdp^*)^2] = ∫_\MDPs d/d\mdp^* (\mdp - \mdp^*)^2 d \bel(\mdp) = ∫_\MDPs 2 (\mdp - \mdp^*) d \bel(\mdp) \]

Example: Beta-Bernoulli

Consider a coin with an unknown distribution of head or tails. We can model this as \begin{align*} x_t \mid \mdp ∼ \Bern(\mdp)
\mdp ∼ Β(α_0, β_0) \end{align*} [Drawing on board] Data: $x_1, \ldots, x_T$ with empirical mean $\hat{\mdp} = \frac{1}{t} ∑_t=1^T x_t$.

Bayesian estimate:

$α_T = α_0 + ∑_t=1^T x_t$, $β_T = β_0 + ∑_t=1^T (1 - x_t)$

ML estimation:

We can show that $\mdp^*_ML = \hat{\mdp}$.

MAP estimation:

We can show that $\mdp^*_MAP = {α_T - 1}{T}$.

MSE estimation:

We can show that $\mdp^*_MSE = {α_T}{α_T + β_T}$.

Lab: Decision problems and estimation (45’)

1. Problems with no observations. Book Exercise: 13,14,15.
2. Problems with observations. Book Exercise: 17, 18.

Assignment: James Randi

Bandit problems

$n$ meteorologists as prediction with expert advice

• Predictions $p_t= p_t,1, \ldots, p_t,n$ of all models for outcomes $y_t$
• Make decision $a_t$.
  • Observe true outcome $y_t$
• Obtain instant reward $r_t = ρ(a_t, y_t)$
• Utility $U = ∑_t=1^T r_t$.
• $T$ is the problem horizon

At each step $t$:

1. Observe $p_t$.
2. Calculate $\hat{p}_t = ∑_μ ξ_t(μ) p_t,μ$
3. Make decision $a_t = \argmax_a ∑_y \hat{p}_t(y) ρ(a, y)$.
4. Observe $y_t$ and obtain reward $r_t = ρ(a_t, y_t)$.
5. Update: $ξ_t+1(μ) \propto ξ_t(μ) p_t,μ(y_t)$.

The update does not depend on $a_t$

Prediction with expert advice

• Advice $p_t= p_t,1, \ldots, p_t,n ∈ D$
• Make prediction $\hat{p}_t ∈ D$
• Observe true outcome $y_t ∈ Y$
• Obtain instant reward $r_t = u(\hat{p}_t, y_t)$
• Utility $U = ∑_t=1^T r_t$.

Relation to $n$ meteorologists

• $D$ is the set of distributions on $Y$.
• However, there are only predictions, no actions. To add actions:

\[ u(\hat{p}_t, y_t) = ρ(a^*(\hat{p}_t), y_t), \qquad a^*(\hat{p}_t) = \argmax_a ρ(a, y_t) \]

The update does not depend on $a_t$

The Exponentially Weighted Average

MWA Algorithm

• Predict by averaging all of the predictions:

\[ \hat{p}_t(y) = ∑_μ \bel_t(μ) p_t,μ(y) \]

• Update by weighting the quality of each prediction

\[ \bel_t+1(μ) = \frac{\bel_t(μ) exp[η u(p_{t, μ} , y_t)]}{∑_μ’ \bel_t(μ’) exp[η u(p_t,μ, y_t)]} \]

Choices for $u$

• $u(p_t,μ, y_t) = ln p_t,μ(y_t)$, $η = 1$, Bayes’s theorem.
• $u(p_t,μ, y_t) = ρ(a^*(p_t,μ), y_t)$: quality of expert prediction.

The $n$ armed stochastic bandit problem

• Take action $a_t$
• Obtain reward $r_t ∼ P_{a_t}(r)$ with expected value $μ_{a_t}$.
• The utility is $U = ∑_t r_t$, while $P$ is unknown.

The Regret

-Total regret with respect to the best arm: \[ L \defn ∑_{t = 1}^T [μ^* - r_t], \qquad μ^* = max_a μ_a \]

• Expected regret of an algorithm $π$:

\[ \E^π [L] = ∑_{t = 1}^T \E^π[μ^* - r_t], = ∑_a=1^n \E^π[n_T,a](μ^* - μ_a) \]

• $n_T,a$ is the number of times $a$ has been pulled after $T$ steps.

Bernoulli bandits

A classical example of this is when the rewards are Bernoulli, i.e. \[ r_t | a_t = i ∼ \textrm{Bernoulli}(μ_i) \]

Greedy algorithm

• Take action $a_t = \argmax_a \hat{μ}_t,a$
• Obtain reward $r_t ∼ P_{a_t}(r)$ with expected value $μ_{a_t}$.
• Update arm: $s_{t, a_t} = s_{t - 1, a_t} + r_t$, $n_{t, a_t} = n_{t - 1, a_t} + 1$.
• Others stay the same: $s_t,a = s_{t-1, a}$, $n_t,a = n_{t-1, a}$ for $a ≠ a_t$.
• Update means: $\hat{μ}_t,i = s_t,i / n_t,i$.

Priors for the Bernoulli distribution

The standard prior

Policies and exploration

• $n_t,i, s_t,i$ are sufficient statistics for Bernoulli bandits.
• The more often we pull an arm, the more certain we are the mean is correct.

Upper confidence bound: exploration bonuses

• Take action $a_t = \argmax_a \hat{μ}_t,a + O(1/\sqrt{n_t,a})$.

Posterior sampling: randomisation

• Given some prior parameters $α, β > 0$ (e.g. 1).
• $\bel_t(μ_a) = \textrm{Beta}(α + s_t,a, β + n_t,a - s_t,a)$.
• Sample $\hat{μ} ∼ \bel_t(μ)$.
• Take action $a_t = \argmax_a \hat{μ}_a$.

The upper confidence bound

Let \[ \hat{μ}_n = ∑_i=1^t r_i / n, \] be the sample mean estimate of an iid RV in [0,1] with $\E[r_i] = μ$. Then we have \[ Pr(\hat{μ}_n \geq μ + ε) \leq exp(-2nε^2) \] or equivalently \[ Pr( \hat{μ}_n \geq μ_n + \sqrt{ln(1/δ)/2n} \leq δ. ) \]

Beta distributions as beliefs

• [Go through Chapter 4, Beta distribution]
• [Visualise Beta distribution]
• [Do the James Random Exercise 3]
• Note that the problem here is that this is only a point estimate: it ignores uncertainty. In fact, we can represent our uncertainty about the arms in a probabilistic way with the Beta distribution:

  If our prior over an arm’s mean is $\textrm{Beta}(α, β)$ then the -posterior at time $t$ is $\textrm{Beta}(α + s_t,i, β + n_t,i - s_t,i)$.

• [Visualise how the posterior changes for a biased coin as we obtain more data].

Exercise

1. Implement epsilon-greedy bandits (lab, 30’)
2. Implement Thompson sampling bandits (lab, 30’)

3, Implement UCB bandits (home)

1. Compare them in a benchmark (home)

Assignments

EWA as generalised Bayes:

Consider the following special case for prediction with expert advice:

At time $t$:

• Each expert $i ∈ A$ makes probabilistic predictions $p_i,t(x)$ for every possible $x ∈ X$.
• You make a choice of some expert $a_t ∈ A$
• You observe $x_t ∈ X$
• You obtain reward $r_t = - ln p_{a_t, t}(x)$
• You calculate the rewards of all experts, $r_i,t = - ln p_{i, t}(x)$.

Show that the EWA algorithm, which updates the weights according to: \[ w_t+1(i) = \frac{w_t(j) exp[η r_i,t)]}{∑_j w_t(j) exp[η r_j,t]} \] Corresponds to a modified posterior update of the form, \[ \bel_t+1(i) = \frac{P_i(x_t)^η \bel_t(i)}{∑_j P_j(x_t)^η \bel_t(j)} \] where $η > 0$ changes the importance of the likelihood function.

Approximation to the Beta prior

• Implement an approximation of the Beta distribution prior, where the

you instead have a prior distribution on a finite set of $1 + 1/ε$ values, that is $\{0, ε, \ldots, 1 - ε, 1\}$.

• Starting with a uniform prior on these values, calculate the posterior distribution after you observe 100 throws of a fair coin.
• How does this posterior compare to the one resulting from the Beta(1,1) prior?

Confidence bounds

Where you toss a coin of unknown bias $θ$ 100 times. Calculate the empirical mean $\hat{θ}$ and compare it with the true expected value $θ$. How often is $|\hat{θ} - θ| \leq \sqrt{\frac{ln(2/δ)}{2t}}$, where $t$ is the number of throws? Do the calculation by running the experiment 10,000 times and counting the fraction of the time where this fails, for values of $t ∈ \{1, \ldots, 100\}$, and for values of $δ ∈ \{0.001, 0.01, 0.1\}$. How close are the estimates?

Markov Decision Processes: Finite horizon

1. The bandit MDP (30’)
2. MDP definitions (15’)
3. MDP examples (15’)
4. Monte Carlo Policy Evaluation (15’)
5. DP: Finite Horizon Policy Evaluation (15’)
6. DP: Finite Horizon Backward Induction (15’)
7. DP: Proof of Backwards Induction (15’)
8. DP: Implementation of Backwards Induction (30’)

The Markov decision process

Interaction at time $t$

• Observe state $s_t ∈ S$
• Take action $a_t ∈ A$.
• Obtain reward $r_t ∈ \Reals$.

The MDP model $μ$

• Transition kernel $P_μ(s_t+1 | s_t, a_t)$.
• Reward with mean $ρ_μ(s_t, a_t)$

Policies

• Markov policies $\pol(a_t | s_t)$

Utility

Total reward up to a finite (but not necessarily fixed) horizon $T$ \[ U_1 = ∑_t=1^T r_t \]

MDP examples

Shortest path problems

• Goal state $s^* ∈ S$.
• Reward $r_t = -1$ for all $s ≠ s^*$
• Game ends time $T$ where $s_T = s^*$.

Blackjack against a croupier

• Croupier shows one card.
• Current state is croupier’s card and your cards.
• Reward is $r_T = 1$ if you win, $r_T = -1$ if you lose at the end, otherwise $0$.

Monte Carlo Policy Evaluation

\begin{align*} V^π_t(s) & = \E^π[U_t | s_t = s]
& ≈ \frac{1}{N} ∑_n=1^N U⁽ⁿ⁾_t \end{align*}

Monte-Carlo bound

• Markov inequality

\[ Pr(x \geq t) \leq \E[x] / t \]

• For general $x$, use $e^x$:

\[ Pr(x \geq t) = Pr(e^x \geq e^t) \leq \E[e^x] / e^t. \]

Policy Evaluation

\begin{align*} V^π_t(s) &= \E^π[U_t | s_t = s]
&= \E^π[∑_k=t^T r_k | s_t=s]\ &= \E^π[r_t | s_t = s] + \E^π[∑_k=t+1^T r_k | s_t=s]\ &= \E^π[r_t | s_t = s] + \E^π[U_t+1 | s_t=s]\ &= \E^π[r_t | s_t = s] + ∑_s’ \E^π[U_t+1 | s_t+1=s’] Pr^π(s_t+1 = s’ | s_t = s)\ &= \E^π[r_t | s_t = s] + ∑_s’ V^π_t+1(s’) Pr^π(s_t+1 = s’ | s_t = s)\ &= \E^π[r_t | s_t = s] + ∑_s’ V^π_t+1(s’) ∑_a Pr(s_t+1 = s’ | s_t = s, a_t = a) π_t( a | s). \end{align*}

Backwards induction

Let $v_t$ be the estimates of the backwards induction algorithm. We want to prove that $v_t = V^*_t$. This is true for $t = T$. Let us assume by induction that $v_t+1 > V^*_t+1$. Then it must hold for $t$ as well: \begin{align*} v_t(s) &= max_a {r(s) + ∑_j p(j|s,a) v_t+1(j)}
& \geq max_a {r(s) + ∑_j p(j|s,a) V^*_t+1(j)}\ & \geq max_a {r(s) + ∑_j p(j|s,a) V^π_t+1(j)} & & ∀ π\ & \geq V_t^π(s) \end{align*}

If $π^*$ is the policy returned by backwards induction, then $v_t = V^{π^*}$. Consequently \[ V^* \geq V^*{π^*} = v \geq V^* ⇒ v = V^*. \]

Markov Decision Processes: Infinite horizon

Plan

1. DP: Value Iteration (45’)
2. DP: Policy Iteration (45’)

Infinite horizon setting

Utility

\[ U = ∑_t=0^∞ γ^t r_t \]

Discount factor $γ ∈ (0,1)$

Tells us how much we care about the future. Note that \[ ∑_t=0^∞ γ^t = \frac{1}{1 - γ} \]

Value iteration

Idea: Run backwards induction, discounting by $γ$ until convergence.

Algorithm

• Input: MDP $μ$, discount factor $γ$, threshold $ε$
• $v_0(s) = ρ_μ(s)$ for all $s$
• For $n=1, \ldots$

\[ v_n+1(s) = ρ_μ(s) + γ ∑_j P_μ(j | s, a) v_n(j). \]

• Until $\|v_n+1 - v_n\|_∞ \leq ε$.

Norms

• $\|x\|_1 = ∑_t |x_t|$
• $\|x\|_∞ = max_t |x_t|$
• $\|x\|_p = \left(∑_t |x_t|^p\right)^1/p$

Matrix notation for finite MDPs

• $r$: reward vector.
• $P_π$: transition matrix.
• $v$: value function vector.

Stationary policies

\[ π(a_t | s_t) = π(a_k | s_k) \]

Matrix formula for value function

\[ v^π = ∑_t=0^∞ γ^t P_π^t r. \] Note that $(P_π r)(s) = ∑_j P_π(s, j) r(j)$.

Convergence of value iteration

Proof idea

1. Define the VI operator $L$ so that $v_n+1 = L v_n$.
2. Show that if $v = V^*$ then $v = L v$.
3. Show that $lim_{n → ∞} v = V^*$.

Further questions

• How fast does it converge?
• When is the policy actually optimal?

Policy evaluation

Policy evaluation theorem

For any stationary policy $\pol$, the unique solution of \[ v = r + γ P_π v \qquad \textrm{is} \qquad v^\pol = (I - γ P_π)^-1 r \]

Proof

If $\|A\| < 1$, then $(I - A)^-1$ exists and \[ (I - A)^-1 = lim_{T → ∞} ∑_t=0^T A^t. \]

Interpretation: $X = (I - P)^-1$

Is the total discounted number of times reaching a state \[ X(i, j) = \E ∑_t=0^∞ γ^t \ind{s_t = j | s_0 = i} \]

Optimality equations

Policy operator

\[ L_π v = r + γ P_π v. \]

Bellman operator

\[ L v = max_π \{r + γ P_π v\}. \]

Bellman optimality equation

\[ v = Lv \]

Contraction mapping

Contraction mapping

$M$ is a contraction mapping if there is $γ < 1$ so that \[ \|Mx - My\| \leq γ \|x - y\| \qquad ∀ x, y. \]

Banach fixed point theorem

If $M$ is a contraction mapping

1. There is a unique $x^*$ so that $Mx^* = x^*$.
2. If $x_n+1 = M x_n$ then $x_n → x^*$.

Solving $\sqrt(x)$

• The mapping has the property $f(x) = x$ for the solution.
• So if $x = \sqrt{x_0}$, we can write $x^2 - x_0 = 0$.
• Rewrite as $2 x^2 = x^2 + x_0$ $⇒$ $x = \frac{1}{2} \left(x + x_0/x \right)$.
• Or.. $(c+1) x^2 = c x^2 + x_0$ $⇒$ $x = \frac{1}{c+1} \left(c x + x_0/x \right)$.

Value iteration convergence proof

Value iteration is a contraction mapping

Value iteration convergence

• Since $L$ is a contraction mapping, it converges to $v^* = L v^*$ (Theorem 6.5.7)
• If $v = L v$ then $v = max_π v^π$ (Theorem 6.5.3)
• Hence, value iteration converges to $v^*$.

Speed of convergence of value iteration

Theorem

If $r_t ∈ [0,1]$, $v_0 = 0$, then \[ \|v_n - v^*\| \leq γ^n / (1 - γ). \]

Proof

Note that $\|v_0 - v^*\| = γ^0 / (1 - γ)$, and \[ \|v_n+1- v^*\| = \|L v_n - Lv^*\| \leq γ \|v_n - v^*\|. \] Induction: $\|v_n - v^*\| \leq γⁿ / (1 - γ)$ \[ \|v_n+1- v^*\| \leq γ \|v_n - v^*\| \leq γⁿ⁺¹ / (1 - γ). \]

Policy Iteration

Algorithm

• Input: MDP $\mdp$, discount factor $γ$, initial policy $\pol_0$.
• For $n = 0, 1,\ldots$
• $v_n = (I - γ P_{\pol_n})^-1 r = V^\pol_n$.
• $π_n+1 = \argmax_\pol \{r + γ P_\pol v_n$.
• Until $π_n+1 = π_n$.

Policy iteration terminates with the optimal policy in a finite number of steps.

• $v_n \leq v_n+1$ (Theorem 6.5.10)
• There is a finite number of policies.
• $v_n = max_\pol \{r + γ P_π v_n\}$

RL: Stochastic Approximation

1. Sarsa (45’)
2. Q-learning (45’)

Two reinforcement learning setting

Online learning

• Observe state $s_t$
• Take action $a_t$
• Get reward $r_t+1$
• See next state $s_t+1$

Simulator access

• Select a state $s_t$
• Take action $a_t$
• Get reward $r_t+1$
• See next state $s_t+1$

Learning goals

Value function estimation

\[ v^π_t → V^π \qquad q^π_t → Q^π \] \[ v^*_t → V^* \qquad q^*_t → Q^* \]

Optimal policy approximation

\[ π_t → π^* \]

Bayes-optimal policy approximation

\[ π_t ≈ \argmax_π ∫_μ \bel_t(μ) \]

Monte Carlo Policy Evaluation

Direct Monte Carlo

• For all states $s$
• For $k= 1, \ldots, K$
• Run policy $π$, obtain $U^(k) = ∑_t=1^T r^(k)_t$

\[ v_K(s) = \frac{1}{K} U^(k) \]

Online update

• For each $k$

\[ v_k(s) = v_k-1(s) + α_k[U^(k)- v_k-1(s)] \]

• For $α_k = 1/k$, the algorithm is the same as direct MC.

Monte Carlo Updates

Every-visit Monte Carlo

• Observe trajectory $(s_t, r_t)_t$, set $U = 0$.
• For $t = T, T-1, \ldots$
• $U = U + r_t$
• $n(s_t) = n(s_t) + 1$
• $v(s_t) = v(s_t) + \frac{1}{n(s_t)}[U - v(s_t)]$.

First-visit Monte Carlo

• Observe trajectory $(s_t, r_t)_t$, set $U = 0$.
• For $t = T, T-1, \ldots$
• $U = U + r_t$
• If $s_t$ not observed before
• $n(s_t) = n(s_t) + 1$
• $v(s_t) = v(s_t) + \frac{1}{n(s_t)}[U - v(s_t)]$.

Temporal Differences

• Idea: Replace actual $U$ with an estimate: $r_t + γ v(s_t+1)$.
• Temporal difference error: $d_t = r_t + γ v(s_t+1) - v(s_t)$.

Temporal difference learning

\[ v(s_t) = v(s_t) + α_t d_t \]

TD (λ)

\[ v(s_t) = v(s_t) + α_t ∑_\ell=t^∞ (γ λ)^{\ell - t} d_t \]

Online TD (λ)

• $n(s_t+1) = n(s_t+1) + 1$
• For all $s$

\[ v(s_t) = v(s_t) + α_t n(s) d_t \]

• $n = λ n$

Stochastic state-action value approximation

SARSA

• Input policy $π$
• Generate $s_t, a_t, r_t, s_t+1, a_t+1$
• Update value

\[ q(s_t, a_t) = q(s_t, a_t) + α[r_t + γ q(s_t+1, a_t+1) - q(s_t, a_t)] \]

QLearning

• Observe $s_t, a_t, r_t, s_t+1$
• Update value

\[ q(s_t, a_t) = q(s_t, a_t) + α[r_t + γ max_a q(s_t+1, a) - q(s_t, a_t)] \] \[ q(s_t, a_t) += α[r_t + γ max_a q(s_t+1, a) - q(s_t, a_t)] \] \[ q(s_t, a_t) = (1 - α) q(s_t, a_t) + α[r_t + γ max_a q(s_t+1, a) \]

QLearning($λ)$

• Observe $s_t, a_t, r_t, s_t+1$
• $e_{s_t, a_t} += 1$
• Update value

For every state-action $s,a$: \[ q(s, a) += (e_s,a α) [r_t + γ max_a q(s_t+1, a) - q(s, a)] \]

• $e = λ e$ , $λ < 1$.

When $λ → 1$, then you have Monte-Carlo.

Experience Replay

Run any of these algorithm repeatedly on a dataset you have collected so far.

Model-based RL

Model-Based RL

Model $\hat{\mdp_t}$

Built using data $h_t = \{(s_1, a_1, r_1), \ldots, (s_t, a_t, r_t)\}$. \[ P_t(s’|s,a) \defn P_{\hat{\mdp_t}}(s’|s,a) \]

Algorithm

At time $t$

• $\hat{\mdp}_t = f(h_t)$
• $\pol_t = \argmax_\pol V_\hat{\mdp}^\pol$.

Example 1: Model-Based Value Iteration

Model

\[ P_t(s’|s,a) = \frac{∑_t \ind{s_t+1 = s’ ∧ s_t = s ∧ a_t = a}}{∑_t \ind{s_t = s ∧ a_t = a}} = \frac{N_t(s,a,s’)}{N_t(s,a)} \] \[ ρ_t(s,a) = \frac{∑_t r_t \ind{s_t = s, a_t = a}}{N_t(s,a)} \]

Asynchronous Value Iteration

For $n = 1, \ldots, n_max$, all $s$ \[ v(s) := max_a ρ_t(s,a) + γ ∑_s’ P_t(s’|s,a) v(s’) \]

Greedy actions

\[ a_t = \argmax_a ρ_t(s,a) γ ∑_s’ P_t(s’|s,a) v_{n_max}(s’ | s,a) \]

Example 2: Dyna-Q Learning

Why do value full iteration at every step?

Model

$P_t, ρ_t$

Q-iteration

For some $s ∈ S$, e.g. $s = s_t$, update: \[ q_t(s,a) = ρ_t(s,a) + γ ∑_s’ P_t(s’|s,a) v_t-1(s’), \qquad v_t(s,a) = max_a q_t(s,a) \]

Greedy actions

\[ a_t = \argmax_a q_t(s,a) \]

Questions

• Is a point-estimate of the MDP enough?
• How fully do we need to update the value function?
• Which states should we update?
• How fast should the policy change?

Approximate Dynamic Programming

1. Fitted Value Iteration (45’)
2. Approximate Policy Iteration (45’)

RL in continuous spaces

• From Tables to Functions

Value Function Representations

• Linear feature representation

\[ v_θ(s) = ∑_i φ_i(s) θ_i \]

Policy Representations

• Linear-softmax (Discrete Actions)

\[ \pol_θ(a | s) = exp{∑_i φ_i(s) θ_i} \]

Approximating a function $f$

Approximation error of a function $g$

\[ \|f - g\| \defn ∫_x |f(x) - g(x)| dx \]

The optimisation problem

\[ min_g \|f - g\| \]

Fitting a value function to data

Monte-Carlo fitting

• Input $\pol, K, N, γ, ε$
• Sample $N$ states $s_n$
• Calculate $\hat{V}_n$ through $K$ rollouts of depth $T > ln_1/γ[1/ε (1 - γ)]$
• Call $θ = \textsc{Regression}(Θ, (s_n, \hat{V}_n))$

Regression (linear, with SGD)

• Initialise $θ ∈ Θ$.
• For $n = 1, \ldots, N$
• $θ

Approximate Value Iteration

• For $s ∈ S$
• Calculate $u(s) = max_a r(s,a) + γ ∫_S dP(s’|s,a) v_θ(s’)$ for all $s ∈ \hat{S}$.
• $min_\param \| v_\param - u\|_\hat{S}$, e.g.

\[ \|v_\param(s) - u\|_\hat{S} = ∑_{s ∈ \hat{S}} |v_\param(s) - u(s)|^2 \]

Q-learning with function approximation

Standard Q-update:

\[ q_t+1(s_t, a_t) = (1 - α_t) q_t(s_t, a_t) + α_t [r_t + γ max_a q_t(s_t+1, a)] \]

Gradient Q-update

Minimise the squared TD-error \[ d_t = r_t + γ max_a q_t(s_t+1, a) - q_t(s_t, a_t) \] \[ ∇_\param d_t^2 = 2 d_t ∇_\param q_t(s_t, a_t) \]

Approximate policy iteration

• $π_k = \argmin_{π ∈ Π} \|\hat{L} v_k-1 - \hat{L} v_k-1\|$
• $v_k = \argmin_{v ∈ V} \|v - \hat{V}^π_k\|$

Bellman error methods

\[ \|v - Lv\| = ∑_s D(s)^2 \] \[ D(s) = v(s) - max_a ∫_S v(j) dP(j | s,a) \]

Policy Gradient

1. Direct Policy Gradient, i.e. REINFORCE (45’)
2. Actor-Critic Methods, e.g. Soft Actor Critic (45’)

Policy gradient

We want to solve the problem \[ max_θ \E_θ[U], \qquad \E_θ[U] = ∫_S dy(s) ∫_H p_θ(h \mid s_1 = s) U(h), \] where

• $θ$ parametrises a policy
• $y(s)$ is a starting-state distribution
• $h = (s_t, a_T, r_t)_t=1^T$ is a trajectory and
• $U(h) = ∑_t r_t γ^t-1$ is its utility

Policy Gradient Theorem I: Analytic Gradients

\[ V = (I - γ P)^-1 r \] First of all, $∇ A^-1 = - A^-1 ∇ A A^-1$ and so \[ ∇_θ V = γ (I - γ P)^-1 ∇ P (I - γ P)^-1 \] Finally, \[ ∇ P_ij = ∇ ∑_a P(s’ = j | s = i , a) \pol (a \mid s) \]

Policy Gradient Theorem II: State-Visitations

• $X = (I - γ P)^-1$ discounted state-visitation matrix
• $x = y^\top X$ expected state visitations from starting state distribution

Then \[ ∇ \E[U] = ∑_x x(s) ∑_a ∇ \pol(a | s) Q^\pol(s,a) \]

• We can approximate $x$ and $Q$ for the gradient update.

Policy Gradient Theorem III: Reinforce

\[ ∇ \E[U] = ∑_h U(h) ∇ P(h) = ∑_h U(h) P(h) ∇ ln P(h). \] This allows us to use the approximation \[ ∇ \E[U] ≈ \frac{1}{K} ∑_k=1^K ∑_h U(h^(k)) ∇ ln P(h^(k)), \qquad h^(k) ∼ P(h) \]

Two-Player Games

One-shot normal-form games

Given a utility function $U(a, ω)$, we need to find the value of the game \[ U^* = max_a min_ω U(a, ω) = max_a min_ω U(a, ω). \] There is no guarantee that there is a solution. However, when we define \[ U(π, ξ) = ∑_a ∑_ω π(a) U(a, ω) ξ(ω) \] a solution is guaranteed by the minimax theorem

Extensive-form alternating-move zero sum games

• At time $t$:
• The state is $s_t$, players receive rewards $ρ(s_t), -ρ(s_t)$
• Player chooses action $a_t$, which is revealed.
• The state changes to $s_t+1$, and is revealed.
• Players receive reward $ρ(s_t+1), -ρ(s_t+1)$
• Player chooses action $ω_t+1$.
• The state changes to $s_t+2$.
• Player $a$ receives $ρ(s_t)$ and $b$ receives $-ρ(s_t)$.

The utility for player $a$ is \[ U¹ = ∑_t ρ(s_t), \] while for $ω$ it is \[ U² = -∑_t ρ(s_t) \]

Backwards induction for Alternating Zero Sum Games

Let $π_1$ and $π_2$ be the policies of each player and $π$ the joint policy.

The value function of a policy $π = (π_1, π_2)$

For the utility of player 1, we get: \begin{align} V^1,\pol_t(s) &\defn \E_π [U¹_t \mid s_t = s] = ρ(s) + \E[U¹_t+1 \mid s_t = s]
&= ρ(s) + ∑_a \pol(a \mid s) ∑_j V^1,π_t+1(j) P(j\mid s, a)\ V^1,\pol_t+1(j) &= ρ(j) + ∑_b \pol(b \mid j) ∑_j V^1,π_t+2(j) P(k \mid j, b) \end{align}

We can define the optimal value function analogously to MDPs: \begin{align} V^1,*_t(s) &= max_{π_1} min_{π_2} \E_π [U⁺_t \mid s_t = s]
&= ρ(s) + max_a ∑_j V^1,*_t+1(j) P(j\mid s, a)\ V^1,*_t+1(j) &= ρ(j) + min_ω ∑_j V^1,*_t+1(j) P(k \mid j, ω) \end{align} The above recursion can be used to calculate the minimax value function.

Example: Chicken

$ρ^1, ρ^2$	turn	dare
/	<	<
turn	0, 0	-5, -1
dare	1, -5	-10, -10

Example: Prisoner’s dilemma

$ρ^1, ρ^2$	cooperate	defect
/	<	<
cooperate	0, 0	-5, -1
defect	1, -5	-10, -10

Example: penalty shot

$ρ^1, ρ^2$	kick left	kick right
/	<	<
dive left	1, -1	-1, 1
dive right	-1 1	1, -1

Extensive-form general sum games

• At time $t$:
• The state is $s_t$, players receive rewards $ρ^i(s_t)$.
• Player $i = I(s_t)$ chooses an action.
• The state changes to $s_t+1$, and is revealed.

The utility for each player is \[ Uⁱ = ∑_t ρ^i(s_t) \]

Backwards induction for Alternating General Sum Games

Let $π_i$ be the policy of the \(i\)-th player and $π$ the joint policy.

The value function of a policy $π = (π_i)_i=1^n$

For any player $i$, we can define their value at time $t$ as: \begin{align} V^i,\pol_t(s) &\defn \E_π [Uⁱ_t \mid s_t = s]
&= ρ^i(s) + ∑_{a ∈ A} \pol_I(s)(a \mid s) ∑_j V^1,π_t+1(j) P(j\mid s, a) \end{align}

Optimal policies

For perfect information games, we can use this recursion: \begin{align} a^*_t(s) &= \argmax_{a ∈ A} ∑_j V^I(s),*_t+1(j)P(j\mid s, a)
V^i,*_t &= ρ^i(s) + ∑_j V^i,π_t+1(j) P(j\mid s, a^*_t(s)) &&∀ i \end{align} This ensures that we update the values of all players at each step.

Approximate methods in games

General architecture

• Board representation
• Rollouts
• Monte-Carlo Tree Search
• Value approximation
• Policy approximation
• Model approximation

Example: DeepMind engines

1. Alpha Go (MCTS, value approximation)
2. Alpha Go Zero (MCTS, value and policy approximation)
3. Alpha Zero (almost the same)
4. Mu Zero (MCTS, value, policy and model approximation)

Monte-Carlo Tree Search

For each state $s$, select moves according to:

• Number of visits
• Move probability
• Expected value

Rollouts

Plain MCTS

• Start from $s_t$
• Generate $a_t = \argmax_a Q_θ(s, a) + U(s_t, a)$ where

\[ U(s,a) = P(s,a) / N(s,a) \]

• Update $Q_θ(s,a) → 1/N(s,a) ∑_{s’ ∈ S_T} V(s’)
• Loses

Bayesian methods

1. Thompson sampling (25’)
2. Bayesian Policy Gradient (20’)
3. BAMDPs (25’)
4. POMDPs (20’)

Priors

• Maximising expected utility

Policy types

• Memoryless policies
• Adaptive policies

Counterexamples

• Mixed MDP
• Many bandit problems

Bayesian update

• Just Bayes’s theorem
• Example: Discrete MDPs

Gradient ascent

\[ ∇_\pol E^\pol_\bel[U] = ∫_\MDPs ∇_\pol \E^\pol_\mdp[U] d \bel(\mdp) ≈ \frac{1}{K} ∑_k=1^K ∇_\pol \E^\pol_\mdp^{k}[U], ∼ \mdp^k ∼ \bel \]

Bayesian value function

\[ U^*(\bel) = max_\pol U(\pol, \bel) \] \[ U(\pol, \bel) \leq U^*(\bel) \leq ∫_\MDPs max_\pol U(\pol, \mdp) d \bel(\mdp) \]

Hyperstates

• Exact solution: Bayes-Adaptive Markov Decision Processesx

Branch and bound

POMDPs

• In POMDPs, the state is unknown, so we must infer both $\mdp, s$.

Regret bounds

1. UCB (45’)
2. UCRL (45’)

MCTS

1. UCT (45’)
2. Alphazero (45’)

Generic Monte-Carlo Planning

MCPlanner(state)

• repeat {
• search(state, 0)
• } until TimeOut
• return BestAction(state, 0)

search(state, depth)

• if Terminal(state) return 0
• if Leaf(state) return Evaluate(state)
• a = SelectAction(state, depth)
• (NextState, reward) = Simulate(state, action)
• q = reward + γ search(NextState, depth + 1)
• UpdateValue(state, action, q, depth)
• return q

Bandit-Based Monte-Carlo Planning

SelectAction(s, d)

• $N_s,d(t)$: Visits of state $s$
• $N_s,a,d(t)$: Number of times $s,a$ is selected

\[ a^*(s,t) = \argmax_a Q_t(s, a, d) + C \sqrt{ln(N_s,d(t))/N_s,a,d(t)} \]

Search(s, d)

• $a = SelectAction(s,d)$
• $q = ρ(s, a) + Search(S+1)$
• $Q_t(s, a, d) = Q_t-1(s,a, d) (1 - α) + α q$
• Return $q$

Advanced Bayesian Models

1. Linear Models (20’)
2. Gaussian Processes (25’)
3. GPTD (45’)

Inverse Reinforcment Learning

1. Apprenticeship learning (45’)
2. Probabilistic IRL (45’)

Multiplayer games

Bayesian games (90’)