I attended the Reinforcement Learning Summer School in Milan, this year. I had a fantastic time, and the lectures were very informative. While my long term goal remains, compiling all my learnings in the form of a lecture script, that is a non-trivial effort. In the meantime I have tried to write down the big ideas, as with enough effort I am sure, I am able to recall the proofs, and exact methods in the lectures. However, perhaps more useful for me (and the readers) might be the key takeaways.
MDPs and Dynamic Programming
The biggest learnings were the formal definitions of an Markov Decision Process. The fact that a Markov Decision Process is not just the environment, but rather the environment consisting of the transition kernel, and the policy.
Second the principle of Dynamic programming is breaking down a bigger problem into smaller components to solve them, it was named as such because back then it sounded cool and was a reason to get funding.
Evaluation of a policy, by introducing the value function $V$ and the $Q$ functions and by the Bellman expectation equations (which is just linear alegbra).
Proof for a unique policy was by Banach fixed point theorem, the Bellman operator $T^\pi$ is a sup-norm contraction. Intuition, from the proof we saw that $\gamma$ was hidden in the proof, and why bigger $\gamma$ implied slower convergence.
Optimizing a policy: This part provided the backbone of value based control. Essentially the thing to show here was the optimal Bellman contraction $T^\star$ also was a $\gamma$ contraction with respect to sup-norms. And consequently that the unique fixed point for $T^\star$ is $V^\star$ and $Q^\star$. The implication of this was if we solved fixed point equation $T^\star Q = Q$ then acting greedily is optimal policy.
Based on this we can make some algorithms, so we looked at the classic algorithms such as Value Iteration for evaluation a policy, again using Banach fixed point theorem to show convergence. An important insight was we need asynchronous value iteration for optimal control, with the convergence criterion being every state action pair is visited infinitely often. The big idea behind Q-learning.
We looked at policy iteration with the big insight being that we parameterise the policy and calculate the value function of that policy and with each step we greedily improve the policy and by monotinicity of the Bellman operator, we saw that if we act greedily with some policy $\pi$, thats $\pi’ = \textrm{greedy}(Q^\pi)$ then $\pi’$ is an improvement over $\pi$ and if it doesnt improve its converged.
RL 1
I am well aware that the title to this lecture is a bit uninformative, but the content wasn’t so perhaps bear with me.
In the last lecture, we assumed that the environment is known to us, the problem is with tractability of the planning procedure so to say.
However, if our model is not known to us, we must learn this from data and act according to the learn model. This comes under the purview of model-based RL. If we act according to an estimated model, the policy based on this model is bottlenecked by the estimation of the model.
What I am trying to understand
State the question in one or two sentences. Why is it worth understanding now, and what would count as a useful answer?
Working model
Write the simplest account that currently makes sense to you.
- Core claim:
- Why I currently believe it:
- Example or toy setting:
- Where this model may fail:
Use equations, diagrams, links, or small experiments when they clarify the idea. Leave uncertainty visible rather than papering it over.
Open questions
- What am I missing or conflating?
- Which assumptions deserve to be checked?
- Is there a standard result, term, or reference I should know?
- What is a good next experiment, derivation, or example?
References and next steps
- Reference or resource — why it seems useful.
- Next step:
- Revision note:
Feedback welcome
If you spot an error, know a useful reference, or have a competing intuition, I would be glad to hear from you. Email is best for now; enable giscus_comments: true above after configuring Giscus if you would like discussion directly on the post.