Reinforcement Learning Fundamentals — Deep Dive

Frontier-lab interview prep. Pair with INTERVIEW_GRILL.md.

RL is the foundation underneath RLHF, agentic systems, and tool-use training. Frontier-lab interviews probe RL not because they want game-playing agents but because RLHF/PPO/GRPO fluency requires understanding the underlying machinery. This deep dive covers what you need.

1. The MDP framework

A Markov Decision Process is $(S,A,P,R,\gamma )$:

• $S$: state space.
• $A$: action space.
• $P(s^{\prime }|s,a)$: transition probability.
• $R(s,a)$ (or $R(s,a,s^{\prime })$): reward function.
• $\gamma \in [0,1)$: discount factor.

Markov property: $P(s_{t+1}|s_t,a_t,s_{t-1},\dots )=P(s_{t+1}|s_t,a_t)$. Future depends only on current state and action.

Policy $\pi$: distribution over actions given state. Deterministic: $a=\pi (s)$. Stochastic: $\pi (a|s)$.

Trajectory: $\tau =(s_0,a_0,r_0,s_1,a_1,r_1,\dots )$.

Return (cumulative discounted reward):

$$G_t=\sum _{k=0}^{\infty }{\gamma }^k{r}_{t+k}$$

The agent maximizes ${\mathbb{E}}_{\pi }[G_0]$.

2. Value functions

State-value $V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t|s_t=s]$ — expected return starting from $s$ following $\pi$.

Action-value $Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t|s_t=s,a_t=a]$ — expected return from $s$ taking $a$ first, then $\pi$.

Advantage:

$$A^{\pi }(s,a)=Q^{\pi }(s,a)-V^{\pi }(s)$$

How much better is action $a$ than the policy's average behavior in state $s$?

Bellman equations

$V^{\pi }$ satisfies (one-step decomposition):

$$V^{\pi }(s)=\sum _a\pi (a|s)\sum _{s^{\prime }}P(s^{\prime }|s,a)[R(s,a,s^{\prime })+\gamma V^{\pi }(s^{\prime })]$$

$$Q^{\pi }(s,a)=\sum _{s^{\prime }}P(s^{\prime }|s,a)[R(s,a,s^{\prime })+\gamma \sum _{a^{\prime }}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })]$$

Bellman optimality

For optimal policy ${\pi }^{\ast }$:

$$V^{\ast }(s)=\underset{a}{\max }\sum _{s^{\prime }}P(s^{\prime }|s,a)[R(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]$$

$$Q^{\ast }(s,a)=\sum _{s^{\prime }}P(s^{\prime }|s,a)[R(s,a,s^{\prime })+\gamma \underset{a^{\prime }}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })]$$

These are fixed-point equations. The Bellman operator ${\mathcal{T}}^{\ast }$ is a contraction → unique solution → value iteration converges.

3. Dynamic programming methods

When the model is known, you can compute $V^{\ast }$ and $Q^{\ast }$ exactly.

Value iteration

Iterate the Bellman optimality operator:

$$V_{k+1}(s)=\underset{a}{\max }\sum _{s^{\prime }}P(s^{\prime }|s,a)[R+\gamma V_k(s^{\prime })]$$

Converges geometrically with rate $\gamma$. Optimal policy: ${\pi }^{\ast }(s)=\arg {\max }_a{Q}^{\ast }(s,a)$.

Policy iteration

1. Policy evaluation: solve $V^{\pi }={\mathcal{T}}^{\pi }{V}^{\pi }$ (linear system).
2. Policy improvement: ${\pi }^{\prime }(s)=\arg {\max }_a{Q}^{\pi }(s,a)$.
3. Repeat until convergence.

Each step strictly improves (or terminates). Often faster than value iteration in practice.

4. Model-free methods — when you don't know $P$ and $R$

Monte Carlo

Run full episodes; average returns to estimate $V^{\pi }(s)$:

$$V^{\pi }(s)\leftarrow V^{\pi }(s)+\alpha (G_t-V^{\pi }(s))$$

Pros: unbiased. Cons: high variance, requires episodic structure.

Temporal Difference (TD) learning

Bootstrap from current value estimate:

$$V(s_t)\leftarrow V(s_t)+\alpha [r_t+\gamma V(s_{t+1})-V(s_t)]$$

The bracketed quantity is the TD error ${\delta }_t$. TD trades variance for bias.

Q-learning (off-policy)

$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha [r_t+\gamma \underset{a^{\prime }}{\max }Q(s_{t+1},a^{\prime })-Q(s_t,a_t)]$$

Update toward the greedy next-action value, even if behavior policy was exploratory. Off-policy: learn $Q^{\ast }$ while acting $ϵ$-greedy.

SARSA (on-policy)

$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha [r_t+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)]$$

Update toward the action actually taken. Learns $Q^{\pi }$ for the behavior policy.

5. Function approximation and DQN

For continuous or huge state spaces, use a function approximator $Q_{\theta }$.

DQN (Deep Q-Network, Mnih et al. 2015)

Loss:

$$\mathcal{L}(\theta )={\mathbb{E}}_{(s,a,r,s^{\prime })}[(r+\gamma \underset{a^{\prime }}{\max }{Q}_{{\theta }^{-}}(s^{\prime },a^{\prime })-Q_{\theta }(s,a){)}^2]$$

Tricks that made DQN work

• Experience replay: store transitions in a buffer; sample uniformly. Breaks temporal correlations.
• Target network ${\theta }^{-}$: snapshot of $\theta$ updated infrequently. Prevents the target from chasing itself.
• Frame stacking + CNN: handles partial observability of single-frame Atari.

Improvements

• Double DQN: decouple action selection (online net) from evaluation (target net) to reduce overestimation bias.
• Dueling DQN: separate value $V(s)$ and advantage $A(s,a)$ heads.
• Prioritized experience replay: sample by TD error magnitude.
• Rainbow: combines all of these.

6. Policy gradient methods

Directly parameterize the policy ${\pi }_{\theta }(a|s)$ and optimize via gradient ascent on expected return.

Policy gradient theorem

$${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{\pi }[{\nabla }_{\theta }\log {\pi }_{\theta }(a|s)Q^{\pi }(s,a)]$$

The gradient of the return equals the expectation of (gradient of log-probability) × (Q-value).

REINFORCE

Use Monte Carlo return $G_t$ as an unbiased estimator of $Q$:

$${\nabla }_{\theta }J\approx \frac{1}{N}\sum _i{\nabla }_{\theta }\log {\pi }_{\theta }(a_i|s_i)G_i$$

Pros: simple, unbiased. Cons: high variance.

Variance reduction with baselines

$${\nabla }_{\theta }J=\mathbb{E}[{\nabla }_{\theta }\log {\pi }_{\theta }(a|s)(Q^{\pi }(s,a)-b(s))]$$

For any baseline $b(s)$ that doesn't depend on $a$. Standard choice: $b(s)=V^{\pi }(s)$, giving advantage:

$${\nabla }_{\theta }J=\mathbb{E}[{\nabla }_{\theta }\log {\pi }_{\theta }(a|s)A^{\pi }(s,a)]$$

Actor-critic

Train both:

• Actor: policy ${\pi }_{\theta }$.
• Critic: value $V_{\varphi }$ (or $Q_{\varphi }$).

Use the critic's advantage estimate $A^{\pi }$ in the policy gradient. Reduces variance vs Monte Carlo at cost of some bias.

A2C / A3C

Advantage Actor-Critic / Asynchronous A3C. Synchronous (A2C) and asynchronous (A3C) variants. Standard before PPO.

7. Trust-region and PPO

Vanilla policy gradient suffers from destructive updates: large step → policy collapses.

Natural policy gradient

Use the Fisher metric to control update magnitude:

$$\theta \leftarrow \theta +\alpha F(\theta {)}^{-1}\nabla J(\theta )$$

Step size in the KL geometry, not the parameter geometry. Computationally expensive (Fisher matrix inversion).

TRPO (Schulman et al. 2015)

Constrained optimization: maximize the surrogate objective subject to $\mathrm{KL}({\pi }_{\mathrm{old}}\Vert {\pi }_{\theta })\le \delta$. Solve via conjugate gradient + line search.

PPO (Schulman et al. 2017)

Replace the constraint with a clipped surrogate. The clean way to write it (and to code it):

r = pi_theta(a|s) / pi_old(a|s)             # importance ratio
surr1 = r * A
surr2 = clip(r, 1 - eps, 1 + eps) * A         # clipped version
loss = -min(surr1, surr2).mean()              # negate for gradient ascent

Equivalent formula:

$${\mathcal{L}}^{\mathrm{CLIP}}(\theta )=\mathbb{E}\left[\min (r_t{A}_t,\mathrm{clip}(r_t,1-ϵ,1+ϵ)A_t)\right]$$

Standard $ϵ=0.2$. When the new policy moves too far in the direction the advantage points, the clip kills the gradient — that's the trust-region effect.

PPO is simpler than TRPO, more stable than vanilla PG, and the workhorse of modern RL — including RLHF.

GAE (Generalized Advantage Estimation)

A flexible advantage estimator:

$$A_t^{\mathrm{GAE}(\lambda )}=\sum _{l=0}^{\infty }(\gamma \lambda {)}^l{\delta }_{t+l}$$

with TD error ${\delta }_t=r_t+\gamma V(s_{t+1})-V(s_t)$. $\lambda$ trades bias and variance:

• $\lambda =0$: pure TD (low variance, high bias).
• $\lambda =1$: Monte Carlo (high variance, low bias).
• Standard: $\lambda \approx 0.95$.

8. Exploration vs exploitation

Without exploration, the agent can be stuck on suboptimal policies.

• $ϵ$-greedy: with prob $ϵ$, random; else greedy.
• Boltzmann (softmax): sample from $\pi (a|s)\propto \exp (Q(s,a)/T)$.
• UCB: bonus to less-tried actions: $a=\arg \max [Q(s,a)+c\sqrt{\log t/N(s,a)}]$.
• Thompson sampling: maintain posterior over $Q$; sample and act greedily w.r.t. sample.
• Entropy bonus: add $\beta H(\pi (\cdot |s))$ to the objective. Used in PPO for LLM alignment.
• Curiosity / intrinsic motivation: reward novelty. Useful in sparse-reward tasks.

In LLM RLHF, the KL penalty serves as a regularizer that prevents over-specialization (a form of soft exploration constraint).

9. RL for LLMs (RLHF connection)

In RLHF:

• State: prompt + tokens generated so far.
• Action: next token.
• Reward: from a learned reward model (or rule-based for verifiable tasks like math).
• Policy: the LLM itself, ${\pi }_{\theta }(\mathrm{token}|\mathrm{context})$.
• Reference policy: ${\pi }_{\mathrm{ref}}$, the SFT model. KL penalty $\beta \mathrm{KL}({\pi }_{\theta }\Vert {\pi }_{\mathrm{ref}})$ prevents drift.

The PPO objective for RLHF:

$$\mathcal{L}(\theta )=\mathbb{E}\left[\mathrm{clip}\mathrm{surrogate}(\theta )-\beta \mathrm{KL}({\pi }_{\theta }\Vert {\pi }_{\mathrm{ref}})\right]$$

GRPO (DeepSeekMath/R1) is a simplification: drops the learned value/critic network. Advantage is computed from group-relative reward normalization (sample $K$ responses per prompt; advantage is $(r_i-{\mu }_{\mathrm{group}})/{\sigma }_{\mathrm{group}}$).

def grpo_advantage(rewards):
    """rewards: [B, K] — K sampled responses per prompt. Returns [B, K] advantages."""
    mu = rewards.mean(dim=-1, keepdim=True)
    sigma = rewards.std(dim=-1, keepdim=True) + 1e-8
    return (rewards - mu) / sigma     # group-relative, no critic needed

Recent follow-ups (DAPO, Dr. GRPO, 2025) drop the $\sigma$ normalization to reduce length bias.

10. Common interview gotchas

11. Eight most-asked interview questions

1. State the Bellman equation for $V^{\pi }$ and explain. (Recursive expectation; one-step decomposition.)
2. Q-learning vs SARSA — what's the difference? (Off-policy max vs on-policy actual action.)
3. Why does DQN need a target network? (Stabilize the target; prevent oscillation.)
4. Derive the policy gradient theorem. (Log-derivative trick; expectation of $\nabla \log \pi \cdot Q$.)
5. Why use a baseline in REINFORCE? (Reduce variance without changing bias.)
6. What does PPO clip and why? (Probability ratio; prevent destructive updates.)
7. GAE — what does $\lambda$ control? (Bias-variance: 0 = TD, 1 = Monte Carlo.)
8. In RLHF, what role does the KL penalty play? (Prevents the policy from drifting too far from SFT/reference; soft constraint.)

12. Drill plan

• Memorize Bellman equations (V, Q, optimal V, optimal Q).
• Derive policy gradient theorem on paper. 5 minutes.
• For each algorithm (Q-learning, SARSA, REINFORCE, A2C, PPO), recite: update rule, on/off-policy, key properties.
• Trace one episode of Q-learning with $ϵ$-greedy on a 2-state MDP.
• For RLHF, write the full PPO objective with KL penalty.

13. Further reading

• Sutton & Barto, Reinforcement Learning: An Introduction — the canonical text.
• Mnih et al. (2015), Human-level control through deep reinforcement learning — DQN.
• Schulman et al. (2015), Trust Region Policy Optimization.
• Schulman et al. (2017), Proximal Policy Optimization Algorithms.
• Schulman et al. (2016), High-Dimensional Continuous Control Using Generalized Advantage Estimation — GAE.
• Christiano et al. (2017), Deep RL from Human Preferences — RLHF foundation.