Chapter 12: Reinforcement Learning

Week 23-24

Explore the paradigm of learning through interaction with an environment. Master the Markov Decision Process framework, value-based methods like Q-learning, policy gradient algorithms, and understand how deep learning enables RL to tackle complex problems from game playing to robotics.

Topics: 3
Videos: 3
Min read: 27

Chapter Overview

Reinforcement Learning (RL) represents a fundamentally different paradigm from supervised and unsupervised learning. Instead of learning from labeled examples or finding patterns in data, RL agents learn by interacting with an environment and receiving feedback in the form of rewards.

The key challenge in RL is the credit assignment problem: when an agent receives a reward, it must determine which of its past actions contributed to that reward. This is complicated by delayed rewards—a good action might not produce a reward until many steps later.

RL has achieved remarkable successes: defeating world champions at Go and Chess, learning to play Atari games from raw pixels, controlling robots, optimizing data center cooling, and training the RLHF component of modern language models like ChatGPT.

The fundamental framework for RL is the Markov Decision Process (MDP), which formalizes the agent-environment interaction loop. Two main approaches exist for solving MDPs: value-based methods (learning which states/actions are valuable) and policy-based methods (directly learning which actions to take).

This chapter covers:

MDP Framework: The mathematical formalization of sequential decision-making with states, actions, rewards, and transitions
Q-Learning: A value-based algorithm that learns optimal action-values through temporal difference updates
Policy Gradients: Methods that directly parameterize and optimize the policy using gradient ascent
Deep RL: Combining neural networks with RL for high-dimensional state spaces and complex policies

Chapter Roadmap

Click any topic to jump in

Explainer video

Markov Decision Process

The mathematical framework for sequential decision-making — states, actions, rewards, transitions, and discount factors.

MDP ComponentsPolicyValue FunctionDiscount Factor γ

Solving MDPs with value and policy methods

Value-based and policy-based approaches

Q-Learning

Model-free value learning through temporal difference updates — epsilon-greedy exploration and the Bellman equation.

Q-FunctionBellman Updateε-Greedy ExplorationDQN (Deep Q-Network)

Policy Gradients

Directly optimizing the policy with REINFORCE — advantage estimation, actor-critic, and continuous action spaces.

Policy ParameterizationREINFORCE AlgorithmBaseline / AdvantageActor-Critic

Topics

3 topics in this chapter

The previous chapter, NLP Fundamentals, ended with models pretrained on fixed datasets: every training example arrived with its input and its target already written down. Many problems do not look like that. A robot vacuum, a game-playing program, or a system that sets prices must choose an action, see what happens, and choose again, and its choices change the data it sees next. Nobody labels the correct move. The only feedback is a reward, often delayed: a chess win arrives 40 moves after the decisive mistake. How do we even state such a problem precisely enough to solve it?

This chapter, Reinforcement Learning, studies agents that learn from interaction and reward. This topic builds the formal language every later method uses, the Markov Decision Process. It starts with the MDP components: states, actions, transition probabilities, rewards, and the discount factor. A policy is the agent's rule for choosing actions. A value function scores a state by the reward that policy expects to collect from it. The topic closes with the discount factor, which trades immediate reward against future reward.

Definition

A Markov Decision Process is a tuple $(S, A, P, R, \gamma)$ : a set of states $S$ , a set of actions $A$ , transition probabilities $P(s' \mid s, a)$ , a reward function $R(s, a)$ , and a discount factor $\gamma \in [0, 1)$ . The Markov property requires that the next state and reward depend only on the current state and action, not on earlier history.

In this topic

1MDP Components
2Policy
3Value Function
4Discount Factor γ

1 of 4

MDP Components

An MDP has five parts. The state set $S$ describes every situation the agent can be in; the action set $A$ lists its choices. The transition model $P(s' \mid s, a)$ gives the probability of landing in state $s'$ after taking action $a$ in state $s$ , so it captures randomness such as a wheel slipping. The reward $R(s, a)$ is a number the environment returns after each step, and it is the only signal of what we want. The discount $\gamma$ weights future rewards. The Markov property says the current state carries everything relevant, so a state that omits needed history, such as velocity, breaks the model.

Mathematical Intuition

An MDP is the tuple $(S, A, P, R, \gamma)$ where $P(s'|s,a)$ satisfies the Markov property: $P(s_{t+1}|s_t, a_t, s_{t-1}, \ldots) = P(s_{t+1}|s_t, a_t)$ . The state space can be finite ( $|S| = n$ ) or continuous ( $S \subseteq \mathbb{R}^d$ ). For finite MDPs, the transition model is a set of $|A|$ stochastic matrices $P_a \in \mathbb{R}^{|S| \times |S|}$ , each row summing to 1. The total number of parameters to fully specify the MDP is $|S| \cdot |A| \cdot (|S| + 1)$ .

Example:

Robot vacuum cleaner: identify the MDP components. States? Actions? What determines transitions?

2 of 4

Policy

$\pi(a|s) = P(A_t = a | S_t = s)$

A policy $\pi(a \mid s)$ is the agent's behavior: for each state, a probability distribution over actions. A deterministic policy puts all its probability on one action per state. The goal of reinforcement learning is an optimal policy, written $\pi^*$ , that maximizes expected discounted return from every state at once. For finite MDPs a deterministic optimal policy always exists, but stochastic policies are still useful during learning, because they explore, and in partially observed or adversarial settings. Note that 'optimal' means maximizing the expected value; the plain MDP objective is risk-neutral, so a high-variance gamble with the best average is preferred.

Mathematical Intuition

A policy $\pi: S \to \Delta(A)$ maps states to action distributions. The optimal policy $\pi^*$ satisfies $V^{\pi^*}(s) \geq V^{\pi}(s)$ for all $s$ and all $\pi$ . For finite MDPs, an optimal deterministic policy always exists — randomization is unnecessary. The policy improvement theorem guarantees that making a policy greedy with respect to its own value function produces a policy that is at least as good: $V^{\pi'}(s) \geq V^{\pi}(s)$ where $\pi'(s) = \arg\max_a Q^{\pi}(s,a)$ .

Example:

Gridworld: state A (near cliff), actions {safe_path, risky_shortcut}. Optimal policy if safe=+5, risky=+10 with 50% fall (-100)?

3 of 4

Value Function

$V^\pi(s) = E[\sum_{t=0}^{\infty} \gamma^t R_t | S_0 = s, \pi]$

The state-value function $V^\pi(s)$ is the expected discounted return when the agent starts in state $s$ and follows policy $\pi$ forever after: the sum of $\gamma^t R_t$ over all future steps $t$ , averaged over the randomness in both actions and transitions. It turns a long sequence of future rewards into one number per state, which lets the agent compare situations. Values satisfy the Bellman equation: a state's value equals the expected immediate reward plus $\gamma$ times the expected value of the next state. That recursion is what dynamic programming, temporal-difference learning, and Q-learning exploit. Values depend on the policy: a bad policy makes a good state look poor.

Mathematical Intuition

The Bellman equation $V^{\pi}(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma V^{\pi}(s')]$ is a system of $|S|$ linear equations in $|S|$ unknowns, solvable in $O(|S|^3)$ by matrix inversion: $V = (I - \gamma P_{\pi})^{-1} r_{\pi}$ . The Bellman optimality equation replaces the weighted sum over actions with a max: $V^*(s) = \max_a \sum_{s'} P(s'|s,a)[R + \gamma V^*(s')]$ , which is nonlinear and requires iterative methods like value iteration.

Example:

γ=0.9. From state A, policy gives rewards: +10 (t=0), +10 (t=1), +10 (t=2), then 0 forever. V(A)?

4 of 4

Discount Factor γ

The discount factor $\gamma$ , between 0 and 1, multiplies a reward received $t$ steps in the future by $\gamma^t$ . It makes infinite sums finite, since returns are bounded by the maximum reward divided by $1 - \gamma$ , and it encodes a preference for sooner rewards. A rough effective horizon is $1/(1 - \gamma)$ steps: about 10 for 0.9 and 100 for 0.99. With $\gamma = 0$ the agent is myopic and maximizes only the next reward; as $\gamma$ approaches 1 it becomes far-sighted but learning gets harder, because values become larger and noisier. The discount is part of the problem definition, though it is often tuned like a hyperparameter.

Mathematical Intuition

The discount factor $\gamma \in [0, 1)$ ensures the infinite sum $\sum_{t=0}^{\infty} \gamma^t R_t$ converges: $|V(s)| \leq R_{\max} / (1 - \gamma)$ . Economically, $\gamma$ represents the agent's time preference — the present value of receiving reward $R$ at time $t$ is $\gamma^t R$ . The effective planning horizon is approximately $1/(1-\gamma)$ steps: with $\gamma = 0.99$ , the agent considers the next ~100 steps; with $\gamma = 0.9$ , only ~10 steps matter.

Example:

Two paths: A gives +1 now, B gives +10 in 5 steps. Which is better for γ=0.5 vs γ=0.99?

Theory Exercise

Problem:

An agent in a 4-state MDP receives +1 reward every step until reaching a terminal state. Why must the discount factor γ be strictly less than 1 in a continuing (non-terminating) task, and what happens to the value function as γ → 1?

Hints:

Write out the value function as an infinite geometric series
Recall the convergence condition for a geometric series
Think about the effective planning horizon 1/(1-γ)

Papers

Bellman — A Markovian Decision Process (1957)Sutton & Barto — Reinforcement Learning: An Introduction (2nd ed.)

Blogs

Lil'Log: A (Long) Peek into Reinforcement Learning Hugging Face Deep RL Course: The Reinforcement Learning Framework OpenAI Spinning Up: Key Concepts in RL

Coding Exercise

Problem:

Implement iterative policy evaluation for a tiny 4-state chain MDP under a uniform-random policy, then report the converged state values for a given discount factor.

Hints:

Loop the Bellman expectation backup V(s) ← Σ_a π(a|s) Σ_s' P(s'|s,a)[R + γV(s')] until values stop changing
Represent transitions as a dict keyed by (state, action) → (next_state, reward)
Stop when the largest value change (delta) falls below a small threshold

Definition

Q-learning is a model-free, off-policy temporal-difference algorithm that estimates the optimal action-value function $Q^*(s, a)$ , the expected discounted return from taking action $a$ in state $s$ and acting optimally afterwards. After each transition $(s, a, r, s')$ it moves $Q(s, a)$ toward the target $r + \gamma \max_{a'} Q(s', a')$ ; the greedy policy with respect to $Q^*$ is optimal.

In this topic

1Q-Function
2Bellman Update
3ε-Greedy Exploration
4DQN (Deep Q-Network)

1 of 4

Q-Function

$Q^*(s, a) = E[R_t + \gamma \max_{a'} Q^*(s', a')]$

The action-value function $Q(s, a)$ scores a state-action pair: the expected discounted return from taking action $a$ in state $s$ and then following a given policy. The optimal version $Q^*$ assumes optimal play afterwards and satisfies the formula above: the expected immediate reward $R_t$ plus $\gamma$ times the best Q-value available in the next state $s'$ . Q-values are more useful than state values for acting, because choosing the best action needs only $\arg\max_a Q(s, a)$ , with no model of where each action leads. The price is size: a table needs one entry per state-action pair, which is why large problems approximate $Q$ with a function.

Mathematical Intuition

The Q-function $Q^{\pi}(s,a) = \mathbb{E}[\sum_{t=0}^{\infty} \gamma^t R_t | s_0 = s, a_0 = a, \pi]$ satisfies $V^{\pi}(s) = \sum_a \pi(a|s) Q^{\pi}(s,a)$ and $V^{\pi}(s) = \max_a Q^{\pi}(s,a)$ for the optimal policy. Q-values encode both the immediate reward and the long-term consequences of an action, making them sufficient for decision-making without knowing the transition model. For $|S|$ states and $|A|$ actions, the Q-table has $|S| \cdot |A|$ entries.

Example:

State s has actions {left, right}. Left→ reward 5, terminal. Right→ reward 2, then state s' with max Q(s',·)=10. γ=0.9. Q(s, left)? Q(s, right)?

2 of 4

Bellman Update

$Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s',a') - Q(s,a)]$

The Q-learning update turns the Bellman optimality equation into a sampling rule. After one transition, form the target $r + \gamma \max_{a'} Q(s', a')$ ; the gap between target and current estimate is the temporal-difference error, and the learning rate $\alpha$ moves the estimate that fraction of the way. Because the target uses the agent's own estimate of the next state, the method bootstraps: it learns from incomplete episodes without waiting for the final return. The max makes it off-policy: it learns the value of greedy behavior even while the agent explores. In tables it converges to $Q^*$ if every pair is visited infinitely often and $\alpha$ decays suitably.

Mathematical Intuition

The Q-learning update $Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s',a') - Q(s,a)]$ is a stochastic approximation of the Bellman optimality equation. The term $\delta = r + \gamma \max_{a'} Q(s',a') - Q(s,a)$ is the temporal-difference error. Watkins and Dayan (1992) proved that tabular Q-learning converges to $Q^*$ with probability 1 provided every state-action pair is visited infinitely often and the learning rates satisfy the Robbins-Monro conditions $\sum_t \alpha_t = \infty$ and $\sum_t \alpha_t^2 < \infty$ . The behavior policy may be exploratory, which is what makes the method off-policy. With function approximation, such as a neural network, this guarantee no longer holds.

Example:

Q(s,a)=10, α=0.1, γ=0.9. Take action a, get r=5, reach s' where max Q(s',·)=20. New Q(s,a)?

3 of 4

ε-Greedy Exploration

An agent that always takes the action it currently believes is best may never discover a better one, because it never tries the alternatives. Epsilon-greedy is the simplest fix: with probability $1 - \epsilon$ take the greedy action, and with probability $\epsilon$ pick an action uniformly at random, which can also be the greedy one. Typical schedules start near $\epsilon = 1$ and decay to about 0.01 to 0.1 as estimates improve. Exploration has a cost while learning: on Sutton and Barto's cliff-walking grid, Q-learning learns the shortest path along the cliff edge, but its random moves occasionally fall off, so its online returns are worse than a more cautious method's.

Mathematical Intuition

Epsilon-greedy selects the greedy action with probability $1 - \epsilon + \epsilon/|A|$ and each non-greedy action with probability $\epsilon/|A|$ . On the 4 by 12 cliff-walking grid with $\epsilon = 0.1$ and $\alpha = 0.5$ , Q-learning learns the optimal 13-step path along the cliff edge but averages about -49 per episode while training, because random moves knock it off the cliff. SARSA, which learns the value of its own exploratory policy, prefers a safer 17-step path and averages about -36. Decaying $\epsilon_t$ toward 0 while keeping every action tried infinitely often, a GLIE schedule, recovers convergence to the optimal greedy policy.

Example:

Q(s, left)=5, Q(s, right)=10, Q(s, up)=3. ε=0.2, 4 actions total. P(taking right)? P(taking left)?

4 of 4

DQN (Deep Q-Network)

A Deep Q-Network replaces the Q-table with a neural network that maps a state, such as four stacked Atari frames, to one Q-value per action. Training it naively is unstable, for two reasons. Consecutive transitions are strongly correlated, and the target uses the same network being updated, so every step moves the target too. DQN fixes the first with experience replay: transitions go into a buffer of up to a million, and minibatches are sampled at random. It fixes the second with a target network, a frozen copy used for the targets and refreshed every 10,000 steps. With these, Mnih et al. (2015) reached human-level play on many Atari games.

Mathematical Intuition

DQN approximates $Q(s,a; \theta)$ with a neural network, using experience replay (uniform sampling from a buffer of $(s,a,r,s')$ tuples) to break temporal correlations and a target network $\theta^-$ updated every $C$ steps to stabilize the target $r + \gamma \max_{a'} Q(s', a'; \theta^-)$ . The loss is $L = \mathbb{E}[(r + \gamma \max_{a'} Q(s', a'; \theta^-) - Q(s, a; \theta))^2]$ . Double DQN decouples action selection from evaluation: $a^* = \arg\max_{a'} Q(s', a'; \theta)$ but evaluates with $Q(s', a^*; \theta^-)$ , reducing overestimation bias.

Example:

Why does DQN need a target network updated every 10K steps instead of using the same network?

Theory Exercise

Problem:

Q-learning is described as 'off-policy.' Explain what this means by contrasting its update target with SARSA's, and state why Q-learning can learn the optimal policy even while following an exploratory ε-greedy policy.

Hints:

Write down the Q-learning target and the SARSA target side by side
Note which action's Q-value appears in each target: the max action vs the actually-taken next action
Connect 'off-policy' to learning about a policy different from the one generating behavior

Papers

Watkins & Dayan — Q-Learning (1992)Mnih et al. — Playing Atari with Deep Reinforcement Learning (DQN, 2013)van Hasselt et al. — Deep Reinforcement Learning with Double Q-Learning (2015)

Blogs

Hugging Face Deep RL Course: Introducing Q-Learning Hugging Face Deep RL Course: The Deep Q-Learning Algorithm PyTorch: Reinforcement Learning (DQN) Tutorial

Coding Exercise

Problem:

Implement tabular Q-learning with an ε-greedy policy on a simple 1D corridor environment (start at the left, reward at the right end) and print the learned greedy action for each state.

Hints:

Maintain a Q-table of shape (n_states, n_actions) initialized to zeros
Apply the update Q[s,a] += alpha*(r + gamma*max(Q[s2]) - Q[s,a]) after each step
Use np.argmax(Q[s]) to read off the greedy action once training finishes

Definition

Policy gradient methods parameterize a stochastic policy $\pi_\theta(a \mid s)$ directly and perform gradient ascent on the expected return $J(\theta)$ . The policy gradient theorem gives $\nabla_\theta J = \mathbb{E}[\nabla_\theta \log \pi_\theta(a \mid s) \, A(s, a)]$ , which can be estimated from sampled trajectories without a model of the environment, then followed uphill by stochastic gradient ascent.

In this topic

1Policy Parameterization
2REINFORCE Algorithm
3Baseline / Advantage
4Actor-Critic

1 of 4

Policy Parameterization

$\pi_\theta(a|s)$

A parameterized policy $\pi_\theta(a \mid s)$ is a function, usually a neural network with weights $\theta$ , that turns a state into a distribution over actions. For discrete actions the network outputs one logit per action and a softmax turns them into probabilities. For continuous actions it typically outputs the mean and standard deviation of a Gaussian, and the action is sampled from it. Sampling makes exploration built in, and the policy can narrow its spread as it grows confident. Bounded actions need care: sample then clip, or squash through tanh, as Soft Actor-Critic does. Changing $\theta$ changes behavior smoothly, which is what makes gradients possible.

Mathematical Intuition

A parameterized policy $\pi_{\theta}(a|s)$ outputs action probabilities (discrete: softmax over logits) or distribution parameters (continuous: $\mu, \sigma$ for Gaussian $\mathcal{N}(\mu_\theta(s), \sigma_\theta(s))$ ). The policy gradient theorem states $\nabla_\theta J = \mathbb{E}_{\pi_\theta}[\nabla_\theta \log \pi_\theta(a|s) \cdot Q^{\pi_\theta}(s,a)]$ , which can be estimated from trajectories without knowing the environment dynamics — the key advantage over model-based methods.

Example:

Robot arm with continuous torque control [-1, 1]. How does policy network output actions vs discrete case?

2 of 4

REINFORCE Algorithm

$\nabla_\theta J = E[\nabla_\theta \log \pi_\theta(a|s) \cdot G_t]$

REINFORCE, from Williams (1992), estimates the policy gradient from complete episodes. For each step, $\nabla_\theta \log \pi_\theta(a \mid s)$ is the direction in parameter space that makes the taken action more likely; it is multiplied by $G_t$ , the discounted return from that step onward. Averaging over episodes gives an unbiased estimate of $\nabla_\theta J$ , so actions followed by high returns become more likely and actions followed by low returns less likely. No value function or model is needed. The weakness is variance: $G_t$ sums many random rewards, so estimates are noisy, and learning needs many episodes, which motivates baselines.

Mathematical Intuition

REINFORCE estimates $\nabla_\theta J \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=0}^{T} \nabla_\theta \log \pi_\theta(a_t^i \mid s_t^i) \, G_t^i$ where $G_t = \sum_{k=t}^{T} \gamma^{k-t} r_k$ is the return from time $t$ . The estimator is unbiased, but each $G_t$ sums many random rewards, and every log-probability term in a long episode is weighted by those noisy returns, so the variance grows with the horizon and with the scale of the rewards. Subtracting a baseline $b(s_t)$ leaves the expectation unchanged, since $\mathbb{E}_{a \sim \pi}[\nabla_\theta \log \pi_\theta(a \mid s)] = 0$ , while removing much of that variance: $\nabla_\theta J \propto \mathbb{E}[\nabla_\theta \log \pi_\theta \cdot (G_t - b(s_t))]$ .

Example:

Episode: took action a with π(a|s)=0.3, got return G=100. How does gradient update affect π(a|s)?

3 of 4

Baseline / Advantage

$A(s,a) = Q(s,a) - V(s)$

Subtracting a baseline $b(s)$ from the return leaves the policy gradient unbiased, because the expected value of $\nabla_\theta \log \pi_\theta(a \mid s)$ times any function of the state alone is zero. A good baseline, however, cuts variance sharply. The natural choice is the state value $V(s)$ , which turns the weight into the advantage $A(s, a) = Q(s, a) - V(s)$ : how much better this action was than the policy's average in that state. Positive advantages make an action more likely and negative ones less likely, so the update finally separates good actions from bad ones instead of pushing up whatever was sampled.

Mathematical Intuition

The advantage function $A^{\pi}(s,a) = Q^{\pi}(s,a) - V^{\pi}(s)$ measures how much better action $a$ is compared to the average. Using $A$ instead of $Q$ as the policy gradient weight centers the signal: positive for better-than-average actions, negative for worse. The TD advantage estimate $\hat{A}_t = r_t + \gamma V(s_{t+1}) - V(s_t)$ has lower variance than Monte Carlo returns ( $G_t - V(s_t)$ ) but introduces bias from the value function approximation — a bias-variance tradeoff controlled by GAE( $\lambda$ ).

Example:

V(s)=50. Two actions: Q(s,a₁)=60, Q(s,a₂)=40. What are their advantages? Why is this better than raw Q?

4 of 4

Actor-Critic

Actor-critic methods learn two functions. The actor is the policy $\pi_\theta(a \mid s)$ . The critic is a value function $V_\phi(s)$ , trained by temporal-difference learning toward $r + \gamma V_\phi(s')$ . Instead of waiting for the full return, the actor uses the critic's one-step TD error $\delta = r + \gamma V(s') - V(s)$ as its advantage estimate, so it can update every step and with far less variance than REINFORCE. The cost is bias, because the critic is only an estimate. Generalized advantage estimation blends multi-step returns to tune this trade-off. A3C, PPO, and SAC are all actor-critic designs.

Mathematical Intuition

Actor-critic maintains two networks: the actor $\pi_\theta(a|s)$ and the critic $V_\phi(s)$ . The critic is trained to minimize $L_{\text{critic}} = \mathbb{E}[(r + \gamma V_\phi(s') - V_\phi(s))^2]$ via TD learning, while the actor is updated with $\nabla_\theta J \approx \nabla_\theta \log \pi_\theta(a|s) \cdot \hat{A}(s,a)$ using the critic's advantage estimate. PPO constrains actor updates with a clipped objective: $L^{\text{CLIP}} = \min(r_t(\theta) \hat{A}_t, \text{clip}(r_t, 1 \pm \epsilon) \hat{A}_t)$ where $r_t = \pi_\theta / \pi_{\theta_{\text{old}}}$ .

Example:

Actor outputs π(a|s). Critic outputs V(s)=20. Agent gets r=5, next state has V(s')=25. γ=0.9. What's the TD error for critic? Advantage for actor?

Theory Exercise

Problem:

In REINFORCE the gradient estimate is ∇J ≈ ∇log π(a|s)·G_t. Show why subtracting a state-dependent baseline b(s) reduces variance without introducing bias.

Hints:

Compute the expectation of ∇log π(a|s)·b(s) over actions for a fixed state
Use the identity Σ_a π(a|s)∇log π(a|s) = ∇ Σ_a π(a|s) = ∇1 = 0
Then argue that subtracting a correlated baseline lowers the variance of the estimator

Papers

Williams — Simple Statistical Gradient-Following Algorithms (REINFORCE, 1992)Sutton et al. — Policy Gradient Methods for RL with Function Approximation (2000)Mnih et al. — Asynchronous Methods for Deep RL (A3C, 2016)Schulman et al. — Proximal Policy Optimization Algorithms (PPO, 2017)

Blogs

Lil'Log: Policy Gradient Algorithms Andrej Karpathy: Deep Reinforcement Learning, Pong from Pixels Spinning Up in Deep RL (OpenAI)

Coding Exercise

Problem:

Implement the REINFORCE return computation: given a list of per-step rewards and a discount factor, compute the discounted return G_t at every timestep, then the variance-reducing centered (advantage-style) returns.

Hints:

Compute returns backwards: G_t = r_t + γ·G_{t+1}, starting from the episode end
Use a running accumulator and reverse iteration for an O(T) computation
Center the returns by subtracting their mean (and optionally dividing by std) as a simple baseline

Markov Decision Process

Q-Learning

Policy Gradients

3 topics in this chapter

Markov Decision Process

Definition

In this topic

MDP Components

Policy

Value Function

Discount Factor γ

Theory Exercise

Problem:

Hints:

Coding Exercise

Problem:

Hints:

Related Problems on PixelBank

Q-Learning

Definition

In this topic

Q-Function

Bellman Update

ε-Greedy Exploration

DQN (Deep Q-Network)

Theory Exercise

Problem:

Hints:

Coding Exercise

Problem:

Hints:

Related Problems on PixelBank

Policy Gradients

Definition

In this topic

Policy Parameterization

REINFORCE Algorithm

Baseline / Advantage

Actor-Critic

Theory Exercise

Problem:

Hints:

Coding Exercise

Problem:

Hints:

Related Problems on PixelBank