A Shallow Dive into Deep Reinforcement Learning

Background

Once we take an action $A_t \in \mathcal{A}$ starting at a state $S_t \in \mathcal{S}$, we get a reward $R_{t+1} \in \mathbb{R}$ from the environment, and enter a new state $S_{t+1}$. Usually the policy is stochastic, not deterministic, hence all the notions above are random variables. Define the reward function $r$ as the expected reward given a status and action:

A policy tells us which action to take at state $S_t$. It can be either deterministic $\pi (s) = a$, or stochastic $\pi (a\vert s) = \mathbb{P}_{\pi} [A = a \vert S = s]$. The future reward, a.k.a return, is the sum of discounted upcoming rewards:

The action-value, a.k.a Q-value, of a state-action pair is defined as:

The state-value, a.k.a V-value, of a state is defined as:

The difference between action-value and state-value is the action advantage function, a.k.a. A-value: $A_{\pi} (s, a) = Q_{\pi} (s, a) - V_{\pi} (s)$.

Markov Decision Process (MDP)

A Markov decision process consists of five elements $\mathcal{M} = \langle \mathcal{S}, \mathcal{A}, P, R, \gamma \rangle$, where $P$ is the transition probability function defined as:

and all states are assumed to be Markov: $\mathbb{P} [S_{t+1} \vert S_t] = \mathbb{P} [S_{t+1} \vert S_1, \ldots, S_t]$.

Bellman Equations

Value Equation

State-value:

Action-value:

Expectation Equation

State-value:

Action-value:

Optimality Equation

State-value:

Action-value:

Dynamic Programming

• Policy evaluation:

• Policy improvement:

Monte-Carlo Methods

• Generate complete episodes ${(S_t, A_t, R_{t+1}, S_{t+1})}$ from policy $\pi$, and compute returns $G_t = \sum_{k = 0}^{T-t-1} \gamma^k R_{t+k+1}$.

• Policy evaluation:

• Policy improvement:

Temporal-Difference (TD) Learning

SARSA

• Generate episode $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$ from policy $\pi$.

• Policy evaluation:

• Policy improvement after $T$ steps.

Q-Learning

• Generate episode $(s_t, a_t, r_{t+1}, s_{t+1})$ from policy $\pi$.

• Policy evaluation:

• Policy improvement after $T$ steps.

Deep Q-Network

• Generate replay buffer ${(s_t, a_t, r_{t+1}, s_{t+1})}$ from policy $\pi$.

• Freeze target network $Q_{\pi} (s, a; \bar{\theta})$.

• Update Q-network by minimizing loss:

• Policy improvement after $T$ steps.

Interactive illustration: tabular Q-learning on a gridworld

The agent (S, top-left) must reach the goal (G, +1) while avoiding the pit (P, -1); each step costs 0.04. Click “Train” to run $\varepsilon$-greedy Q-learning episodes; cells are colored by the state-value $V(s) = \max_a Q(s, a)$, and arrows show the greedy policy. Watch the value propagate backward from the goal as more episodes are played.

Things to try: click any plain cell to toggle a wall and re-train (the policy must re-route); set $\varepsilon = 0$ early in training and see the agent get stuck exploiting an incomplete $Q$; push $\gamma$ towards $0$ and see that the agent becomes myopic, so that value never reaches the start; and press “Run greedy agent” to watch the learned policy.

Policy Gradient

We parameterize the policy by $\pi_{\theta}$ and define the reward function as:

where $d_{\pi}$ is the stationary distribution of Markov chain for $\pi_{\theta}$, defined as:

The policy gradient theorem states that:

The key identity behind it is the log-derivative trick $\nabla_{\theta} \pi_{\theta} = \pi_{\theta} \nabla_{\theta} \ln \pi_{\theta}$, which turns the gradient of an expectation into an expectation of a gradient that can be estimated by sampling, without differentiating through the (unknown) environment dynamics.

REINFORCE and baselines

Replacing $Q_{\pi}$ by the sampled return $G_t$ gives the Monte-Carlo estimator REINFORCE [Williams 1992]:

It is unbiased but has high variance. Subtracting any baseline $b (S_t)$ that does not depend on the action leaves the expectation unchanged, because $\mathbb{E}{A \sim \pi} [\nabla{\theta} \ln \pi_{\theta} (A \vert s)] = \nabla_{\theta} \sum_a \pi_{\theta} (a \vert s) = 0$, while it can reduce the variance a lot. The natural choice $b = V_{\pi}$ turns the weight into the advantage $A_{\pi} (s, a) = Q_{\pi} (s, a) - V_{\pi} (s)$, which is the form used in actor-critic methods (A2C/A3C), where the critic $V_w$ is a learned value network trained with the TD loss from the previous section.

Interactive illustration: REINFORCE on a bandit

A 4-armed Gaussian bandit with true mean rewards $(0.2, 0.5, 0.8, 0.4)$ and a softmax policy $\pi_{\theta} (a) \propto e^{\theta_a}$. Each step samples one arm, receives a noisy reward $r$, and updates $\theta \leftarrow \theta + \eta (r - b) \nabla_{\theta} \ln \pi_{\theta} (a)$. With a baseline the weight is the centered reward; without one, add a reward offset and see that the estimator stays unbiased but its variance explodes, so the policy wanders far more before it commits (try a large offset, a small learning rate, and “Run 1000 steps” several times).

Beyond vanilla policy gradient

Large policy updates can collapse performance, since the samples were collected under the old policy. TRPO [Schulman et al. 2015] maximizes the surrogate advantage subject to a KL trust-region $\mathcal{D}{KL} (\pi{old} \vert\vert \pi_{\theta}) \le \delta$; PPO [Schulman et al. 2017] replaces the constraint by clipping the probability ratio $\rho_t (\theta) = \pi_{\theta} (A_t \vert S_t) / \pi_{old} (A_t \vert S_t)$:

Deterministic-policy and off-policy variants (DDPG, TD3, SAC) combine the Q-learning ideas above with a parameterized actor. In language-model alignment (RLHF), PPO and its simplified relatives optimize exactly this objective, with the reward given by a learned preference model.