Stanford CS229 Lecture 18 (Spring 2026): Introduction to Reinforcement Learning and Policy Gradient

TL;DR

Reinforcement learning (RL) frames sequential decision‑making problems as Markov Decision Processes (MDPs) and learns policies from scalar rewards rather than supervised labels; the lecture’s core contribution is the derivation of the policy‑gradient (REINFORCE) algorithm, which enables stochastic policies to be optimized directly via gradient ascent on expected return.

1. Why Reinforcement Learning?

  • Sequential decisions: Actions affect future states, so a myopic greedy choice can be sub‑optimal. The robot‑navigation example (move left/right on a 1‑D line) illustrates that each step influences the next.
  • Exploration vs. exploitation: RL must balance gathering information (exploration) with using current knowledge to maximize reward (exploitation). In practice many applications rely on the algorithm’s inherent stochasticity rather than explicit exploration strategies.
  • Sparse supervision: Unlike classification, RL provides only a scalar reward indicating how good a trajectory is; optimal actions are not labeled.
  • Data collection loop: The agent generates actions, observes resulting states and rewards, and updates its policy to reinforce good actions and penalize bad ones.

2. The Markov Decision Process (MDP) Formalism

Component Symbol Meaning
State space (\mathcal{S}) All possible configurations of the environment (e.g., robot joint angles, board positions).
Action space (\mathcal{A}) Set of admissible actions (e.g., joint torques, Go moves).
Transition dynamics (P(s'\mid s,a)) Probability of reaching state (s') after taking action (a) in state (s). Can be deterministic or stochastic.
Reward function (r(s)) (or (r(s,a)), (r(s,a,s'))) Scalar feedback indicating desirability of a state (or state‑action pair).
Discount factor (\gamma\in[0,1)) Weights immediate rewards more heavily than distant future rewards; ensures bounded returns for infinite horizons.
  • Trajectory (episode): A sequence ((s_0,a_0,s_1,a_1,\dots)) generated by repeatedly sampling actions from a policy and transitioning via (P).
  • Return: (G = \sum_{t=0}^{T}\gamma^{t} r(s_t)). The expected return under a policy (\pi) is denoted (J(\pi) = \mathbb{E}_{\pi}[G]).
  • Policy: Mapping (\pi: \mathcal{S}\rightarrow \Delta(\mathcal{A})) (deterministic or stochastic). An optimal deterministic policy always exists, but stochastic policies are useful for exploration and for gradient‑based learning.

3. Value Functions and Optimality

  • State‑value of a policy: (V^{\pi}(s) = \mathbb{E}_{\pi}[G\mid s_0=s]).
  • Optimal value: (V^{*}(s) = \max_{\pi} V^{\pi}(s)).
  • Optimal policy: (\pi^{*} = \arg\max_{\pi} V^{\pi}(s)) for all (s).
  • Bellman equations: Provide recursive relationships, e.g., [V^{\pi}(s) = r(s) + \gamma \sum_{a}\pi(a\mid s) \sum_{s'} P(s'\mid s,a) V^{\pi}(s').] Solving these linear equations yields exact values for small, discrete MDPs; for large or continuous spaces we resort to approximation methods.

4. Reward Shaping

  • Definition: Modifying the reward function to provide smoother gradients while preserving the optimal policy.
  • Example: Instead of a binary reward ((+1) at goal, (-0.1) elsewhere), assign higher rewards to states closer to the goal. This can accelerate learning but may mislead the agent if the shaping does not reflect true task dynamics (e.g., hidden teleportation shortcuts).
  • Caution: Over‑shaping can bias the learned policy away from the true objective; designers must balance informativeness with fidelity.

5. Policy‑Gradient (REINFORCE) Derivation

  1. Stochastic policy parameterization: (\pi_{\theta}(a\mid s)) is represented by a neural network that outputs a probability density (or categorical distribution) for each action.
  2. Objective: Maximize expected return (J(\theta) = \mathbb{E}{\pi{\theta}}[G]).
  3. Gradient trick: [ \nabla_{\theta} J(\theta) = \mathbb{E}{\pi{\theta}}\big[ G ; \nabla_{\theta} \log \pi_{\theta}(a\mid s) \big]. ]
    • The derivation moves the gradient inside the expectation by writing the expectation as an integral over trajectories, then applying the identity (\nabla_{\theta} p_{\theta}(x) = p_{\theta}(x) \nabla_{\theta} \log p_{\theta}(x)).
  4. Practical estimator: Sample a batch of trajectories, compute the return (G) for each, and update (\theta) via stochastic gradient ascent using the above estimator.
  5. Variance reduction: The lecture notes that the basic REINFORCE estimator can have high variance; common techniques (baseline subtraction, advantage estimation) are mentioned but not detailed.
  6. No need for transition model: The gradient expression does not require knowledge of (P(s'\mid s,a)); only the sampled actions and rewards are needed.

6. Key Takeaways for Practitioners

  • Model the MDP: Identify states, actions, transition dynamics (even if only implicitly via simulation), and a reward that captures the true objective.
  • Choose a stochastic policy: Enables gradient‑based optimization and natural exploration.
  • Use policy‑gradient: REINFORCE provides a simple, model‑free way to improve policies; it forms the basis for more advanced algorithms used in large language model fine‑tuning.
  • Reward shaping is optional but powerful: Design smoother rewards to aid learning, but verify that shaping does not alter the optimal solution.
  • Discount factor matters: (\gamma) balances short‑term vs. long‑term reward and guarantees bounded returns for infinite‑horizon problems.

7. References & Further Reading

  • Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.
  • Williams, R. J. (1992). “Simple statistical gradient‑following algorithms for connectionist reinforcement learning.” Machine Learning, 8(3‑4), 229‑256. (Original REINFORCE paper.)
  • CS229 Spring 2026 lecture notes (available on the course website) for detailed proofs of the Bellman equations and additional policy‑gradient variants.

Sources