Prof. Dr. Sebastian Peitz
Chair of Safe Autonomous Systems, TU Dortmund
| Chapter | Topic | Content |
|---|---|---|
| Basics & tabular methods | ||
| 1-5 | Bandits, MDPs, Dynamic Programming, Monte Carlo, TD Learning | RL basics in finite dimensions |
| Deep-learning-based methods | ||
| 6 | Brief introduction to deep learning | The basics for what comes next |
| 7 | Value function approximation | Value estimation with function approximation |
| 8 | Deep Q-learning | Q-learning with neural networks |
| 9 | Policy gradients | Direct optimization of the policy |
| 10 | Actor-critic algorithms | Improved policy gradients via value functions |
| 11 | Advanced algorithms (Part I): From policy gradient to PPO | The PG route to modern RL algorithms |
| 12 | Advanced algorithms (Part II): From \(Q\)-learning to Soft Actor-Critic | The AC route to modern RL algorithms |
| 13 | Exploration | How to explore in complex scenarios |
| Model-Based Control | ||
| Advanced Topics |
# Initialization
for i in range(k):
Q(a) = 0
N(a) = 0
# Run forever
while(True):
# exploration versus exploitation
if rand() > epsilon:
a = argmax(Q) # exploitation
else:
a = randint(k) # exploration
r = bandit(a)
# Error correction towards target r
N(a) = N(a) + 1
Q(a) = Q(a) + (1/N(a)) * (r - Q(a))\[L_\pi(\phi)=\sum_{t=0}^{T-1}\gamma^t \Expsub{r_t + \alpha \Hc(\piphi\agivenb{\cdot}{s_t})}{(s_t,a_t)\sim\rho_{\piphi}}~\text{with entropy}~\Hc(\piphi\agivenb{\cdot}{s}) = \Expsub{-\log \piphi\agivenb{a}{s}}{a \sim \piphi\agivenb{\cdot}{s}}\]
Half cheetah (SAC). Hopper (SAC).
This is “easy”
This is very hard!
âť“ Imagine your goal was winning 50 games of Mao in a row, without knowing the rules!
\[\begin{align*} p(A \cap B) &= p\agivenb{A}{B} p(B) \fragment{ = p\agivenb{B}{A} p(A) } \\ \Leftrightarrow \quad p\agivenb{B}{A} &= \frac{p\agivenb{A}{B} p(B)}{p(A)}. \end{align*}\]
\[\text{"Posterior"} = \frac{\text{"Likelihood"} \times \text{"Prior"}}{\text{"Evidence"}}.\]
The idea behind Thompson sampling (also known as posterior sampling) is essentially Bayes’ theorem:
For each step \(t = 1, 2, 3, \ldots\)
Information gain: “Which arm will give me the most valuable information to help me make better decisions in the future?”
đź’ˇ Using the Gaussian assumption for the rewards and our beliefs, one can compute closed-form expressions for \(\Delta(a)\) and \(I(a)\).
| Type of intrinsic motivation | Core question the agent asks | Key algorithms |
|---|---|---|
| Novelty / information-theoretic | “Have I seen this specific state configuration before?” | Pseudo-counts (CTS, PixelCNN), count-based hashing |
| Prediction error / surprise | “Can I predict what happens next if I take this action?” | ICM (intrinsic curiosity module) |
| Knowledge gain / reduction of uncertainty | “How much does this experience improve my model of the world?” | RND (random network distillation), disagreement ensembles |
\[p_\theta(s_t) = \frac{\hat{N}(s_t)}{\hat{n}}, \qquad p_{\theta'}(s_t) = \frac{\hat{N}(s_t)+1}{\hat{n}+1}. \]
\(\Rightarrow\) Tow equations for two unknowns (\(\hat{N}\) and \(\hat{n}\))!
\[\begin{align*} \hat{N}(s_t) &= \hat{n} p_\theta(s_t), \qquad \hat{n} = \frac{1-p_{\theta'}(s_t)}{p_{\theta'}(s_t)-p_{\theta}(s_t)},\\ \hat{N}(s_t) &= \frac{\cbracket{1-p_{\theta'}(s_t)}p_\theta(s_t)}{p_{\theta'}(s_t)-p_{\theta}(s_t)} . \end{align*} \]
Instead of counting states, an Intrinsic Curiosity Module (ICM) (Pathak et al. 2017) uses a predictive neural network model:
Exploration: ICM (green) versus random exploration (blue).
Source: (Pathak et al. 2017).
| Feature | Novelty methods (e.g., count-based) | Intrinsic curiosity (e.g., ICM) |
|---|---|---|
| Core question | “Have I stood in this exact spot before?” | “Can I accurately predict what will happen if I push this button?” |
| Mechanism | Tracks visitation counts or state densities. | Measures the prediction error of a forward-dynamics neural network. |
| The “TV Screen” vulnerability | Vulnerable. A TV screen cycling random images represents infinite novel states. | Handled via feature encoding. It ignores randomness it cannot control. |
| Best suited for | Environments with static, clean states where visiting everything matters (e.g., Montezuma’s Revenge). | Dynamic environments with visual noise where learning the “physics” of the world is required. |
Bootstrapped DQN (Osband et al. 2016)
Approach: Single network with \(K\) heads!
\(\textcolor{green}{\mathbf{+}\text{ No change to original reward function}}\quad\textcolor{red}{\mathbf{-}\text{ Good bonuses often do better.}}\)
RND (Burda et al. 2019) uses two neural networks that consider the same state \(s\), but they have different jobs:
\[\Rightarrow\text{ Intrinsic reward:} \quad r^i = \norm{f_\theta(s) - f(s)}^2.\]
💡 In ML, knowledge distillation is the process of teaching a student network to mimic a teacher network. In RND, the predictor attempts to “distill” the frozen, random knowledge of the target network into itself.
[Source: OpenAI blog]
Discovery of new rooms to satisfy curiosity. Then revisiting those rooms to maximize the extrinsic reward. [Source: OpenAI blog]
| Feature | Intrinsic Curiosity Module (ICM) | Random Network Distillation (RND) |
|---|---|---|
| Core Mechanism | Predicts the next state given the current state and action (forward dynamics). | Predicts the output of a fixed, randomly initialized neural network on the current state. |
| The “Noisy TV” problem | Vulnerable. If a screen shows unpredictable random noise, ICM gets trapped staring at it because prediction error remains high. | Immune. The random target network outputs a completely deterministic (though random) function. The predictor network learns it quite easily, dropping the reward to zero. |
| Complexity | High. Requires training three sub-networks: an encoder, an inverse dynamics model, and a forward dynamics model. | Low. Requires training only one network (the predictor) to match a frozen, untrained target network. |
| Scalability | Harder to scale because compounding forward-prediction errors in high-dimensional state spaces create erratic reward signals. | Highly scalable. It handles raw very exceptionally well (and famously allowed PPO to crack Montezuma’s Revenge). |
The fundamental difference between exploration and reward shaping lies in who defines the reward and why.