The Markov Decision Process (MDP) formalizes sequential decision-making under uncertainty as a tuple (S, A, P, R, γ). The state space S contains all possible configurations the environment can be in. The action space A represents choices available to the agent. Transition probabilities P(s'|s,a) define the probability of reaching state s' after taking action a in state s. The reward function R(s,a) assigns immediate scalar feedback. The discount factor γ ∈ [0,1] weighs immediate rewards more heavily than future rewards.

The Markov property—that future evolution depends only on the current state, not history—enables efficient computation. A policy π(s) → a maps states to actions deterministically (or π(a|s) probabilistically). The return Gt = ∑ₖ γᵏrₜ₊ₖ represents total discounted future reward from time t. The value function V^π(s) = E[Gt | s] gives expected return under policy π, while the action-value function Q^π(s,a) = E[Gt | s,a] gives expected return after taking action a in state s and following π thereafter.

The Bellman equations decompose value functions recursively: V^π(s) = ∑ₐ π(a|s)[R(s,a) + γ ∑ₛ' P(s'|s,a)V^π(s')]. For optimal policies, the Bellman optimality equations become: V*(s) = maxₐ[R(s,a) + γ ∑ₛ' P(s'|s,a)V*(s')]. These recursive definitions form the foundation for dynamic programming algorithms. The advantage function A(s,a) = Q*(s,a) - V*(s) measures how much better taking action a is than the average policy action in state s.

MDPs can be finite-horizon (terminal state reached in finite time), infinite-horizon with discount (γ < 1 prevents divergence), or average-reward (optimizing long-run average reward per step). Model-based methods assume knowledge of P and R; model-free methods learn from experience. The framework elegantly captures exploration-exploitation tradeoff: exploration improves model estimates; exploitation uses current knowledge to maximize reward. Understanding MDPs is essential before applying any RL algorithm.

Value iteration solves the Bellman optimality equation V*(s) = maxₐ[R(s,a) + γ ∑ₛ' P(s'|s,a)V*(s')] by iteration. Begin with arbitrary V₀(s) (often V₀(s) = 0). Repeatedly apply the Bellman backup operator: Vₖ₊₁(s) ← maxₐ[R(s,a) + γ ∑ₛ' P(s'|s,a)Vₖ(s')] for all states. The algorithm converges to V* as k→∞ because the Bellman operator is a γ-contraction: ||T V - T V'||∞ ≤ γ||V - V'||∞.

The contraction property guarantees exponential convergence at rate O(γᵏ). For discount factor γ = 0.99, roughly 460 iterations suffice to reduce error by 10⁻². Convergence is guaranteed regardless of initialization, making value iteration robust. Practical stopping criteria include checking ||Vₖ₊₁ - Vₖ||∞ < ε. Once convergence is achieved, the optimal policy is extracted in a single sweep: π*(s) = argmaxₐ[R(s,a) + γ ∑ₛ' P(s'|s,a)V*(s')].

Value iteration's primary limitation is that it requires complete knowledge of the transition model P and reward function. For large state spaces, computing the backup for each state becomes prohibitive. In such cases, asynchronous dynamic programming (updating states in arbitrary order, possibly from samples) helps. The algorithm is the foundation for more sophisticated methods like Q-learning, which learn optimal Q-values from experience without knowing P in advance.

Convergence analysis reveals that value iteration makes global progress: V* is a fixed point, and ||Vₖ - V*||∞ ≤ γᵏ ||V₀ - V*||∞. The number of iterations needed grows logarithmically with required precision: k = O(log(1/ε)/(1-γ)). This makes value iteration practical for problems with moderate state spaces, provided the Bellman backup can be computed efficiently.

Policy iteration alternates between two phases: policy evaluation and policy improvement. Initialize a policy π arbitrarily. Evaluation phase: solve the linear system V^π(s) = R(s,π(s)) + γ ∑ₛ' P(s'|s,π(s))V^π(s') for all states. This can be done via iterative methods (value iteration on the value function for a fixed policy) or directly solving the linear system when applicable. Improvement phase: set π_new(s) ← argmaxₐ[R(s,a) + γ ∑ₛ' P(s'|s,a)V^π(s')] for each state. Repeat until π_new = π (policy convergence).

Policy improvement step is guaranteed monotonic: V^π_new(s) ≥ V^π(s) for all s. This follows from the greedy improvement step—by definition, the new action maximizes the immediate reward plus expected future value. Remarkably, policy iteration converges to π* (the optimal policy) in relatively few outer loop iterations. Empirically, policy iteration often requires 3-10 iterations to converge, while value iteration might need hundreds. The tradeoff is that each policy iteration involves solving a linear system of equations, which can be expensive for large state spaces.

Generalized Policy Iteration (GPI) relaxes the requirement for exact policy evaluation. Instead of solving the linear system exactly, perform only a few iterations of value iteration in the evaluation phase. This hybrid approach retains convergence guarantees while reducing per-iteration cost. Asynchronous GPI updates states in arbitrary order, enabling sample-based and distributed implementations. The flexibility of GPI makes it a conceptual framework encompassing value iteration (policy improvement only) and temporal-difference learning (partial evaluation from samples).

Policy iteration is less commonly used in model-free settings because evaluation requires complete model information. However, in model-based planning, policy iteration is attractive when the policy can be represented compactly (e.g., a few parameters) and evaluation cost is manageable. Theoretical convergence speed for policy iteration is superlinear: often converging in polynomially many iterations total (not per-iteration cost).

Model-based RL learns representations of the environment dynamics P(s'|s,a) and reward function R(s,a) from experience. When the agent interacts with the environment, it collects transitions (s,a,s',r). These can be used to train supervised learning models: predict s' from (s,a) for transition model, and predict r from (s,a) for reward model. Maximum likelihood estimation for multinomial transitions (discrete s') or regression for continuous transitions are standard approaches. The learned model is then used for planning: apply value iteration or policy iteration using the learned model in place of the true one.

The exploration-exploitation dilemma is central to model-based learning. Exploitation uses the current model to choose actions that seem best: a = argmaxₐ V_model(s,a). Exploration deliberately selects actions providing information to improve the model's accuracy. Methods include ε-greedy (take random action with probability ε), upper confidence bound (UCB) selection based on optimism under uncertainty, and Thompson sampling (sample model from posterior, act optimally under sampled model). Each trades off short-term reward for long-term model improvement.

Dyna algorithms elegantly combine model learning and planning. They interleave: (i) real world transitions for model training and reward collection, (ii) simulated transitions using the learned model to expand exploration. Pseudocode: For each real transition (s,a,s',r): Store in replay buffer, Train model on batch, Take m planning steps simulating model, Execute real action. This architecture efficiently uses both real and simulated experience. Dyna-style algorithms can accelerate learning by one to two orders of magnitude.

Challenges in model learning include distributional shift (model predicts on states unlike those seen during training) and compounding error (mistakes in short-term predictions compound into large errors for long-horizon planning). Uncertainty quantification helps: represent model uncertainty via Bayesian methods or ensemble models, use pessimistic/robust planning under uncertainty. The interplay between model quality and planning horizon is subtle; longer plans accumulate error unless model uncertainty is managed. Modern approaches like latent variable models and world models in deep RL address these challenges.

Continuous state spaces (e.g., robot pose, economic indicators) are ubiquitous in applications. Discretizing an n-dimensional state space with m grid points per dimension requires mⁿ states, leading to curse of dimensionality. Value function approximation mitigates this by parameterizing V(s;θ) with a compact representation. Linear approximators V(s;θ) = θᵀφ(s) with hand-crafted basis functions φ(s) offer interpretability and convergence guarantees. Neural networks enable learning feature representations automatically but lack theoretical convergence guarantees.

Fitted value iteration (FVI) adapts value iteration to function approximation: (1) Sample state transitions {sᵢ, aᵢ, sᵢ', rᵢ}, (2) Compute targets: tᵢ = rᵢ + γ maxₐ V(sᵢ';θ_old), (3) Update θ by minimizing loss: L(θ) = ∑ᵢ (V(sᵢ;θ) - tᵢ)². FVI is popular in deep RL but convergence is not guaranteed, especially with nonlinear approximators. Off-policy learning (learning from experience collected under a different policy) exacerbates challenges: target values may lie outside the support of the current value function approximation.

Linear basis functions with convergence guarantees: If φ(s) are linearly independent and "persistent excitation" conditions hold (states are sampled persistently across the space), then gradient descent on linear approximation V(s;θ) = θᵀφ(s) converges to the solution of the projected Bellman equation: V(s;θ*) = ΠV*, where Π is projection onto the linear subspace spanned by φ. This suggests careful feature engineering is important. Polynomials, Fourier features, and RBF kernels are common basis function choices.

Nonlinear approximation (neural networks) dramatically increases expressiveness but introduces new challenges: (1) Overfit risk, addressed by regularization and dropout, (2) Instability from correlation in experience and moving target values, addressed by experience replay and target networks (freezing old parameters), (3) Off-policy divergence where function approximation error accumulates unboundedly. Modern deep RL methods like DQN and A3C address these via engineering techniques: prioritized replay, gradient clipping, double Q-learning. Theoretical understanding of when deep RL converges remains an active research area.

The Linear Quadratic Regulator (LQR) solves the optimal control problem for linear dynamics and quadratic costs. System dynamics: xₜ₊₁ = Axₜ + Buₜ. Cost function: ∑ₜ(xₜᵀQxₜ + uₜᵀRuₜ) with Q ≥ 0 (positive semidefinite) and R > 0 (positive definite). The optimal policy is linear: u*ₜ = -Kₜxₜ where the gain matrix K is derived from the algebraic Riccati equation. For infinite-horizon problems, K is constant (time-invariant).

The Riccati equation: P = AᵀPA - AᵀPB(R + BᵀPB)⁻¹BᵀPA + Q. The optimal feedback gain is K = (R + BᵀPB)⁻¹BᵀPA. The closed-loop system xₜ₊₁ = (A - BK)xₜ is asymptotically stable when Q, R are chosen appropriately. The value function is quadratic: V*(x) = xᵀPx, where P satisfies the Riccati equation. Computational complexity is O(n³) for n-dimensional state, making LQR scalable to moderately high dimensions.

Finite-horizon LQR is solved via backward dynamic programming. Define Vₜ(x) = xᵀPₜx. At the terminal time T, Pₜ = Q. Backward from T-1 to 0: Pₜ = AᵀPₜ₊₁A - AᵀPₜ₊₁B(R + BᵀPₜ₊₁B)⁻¹BᵀPₜ₊₁A + Q. Forward simulate: uₜ = -Kₜxₜ where Kₜ = (R + BᵀPₜ₊₁B)⁻¹BᵀPₜ₊₁A. Finite-horizon problems are particularly useful for trajectory tracking and constrained prediction horizons.

LQR forms the foundation for advanced control algorithms. Iterative LQR (iLQR) extends LQR to nonlinear systems by successive linearization, and LQG extends it to partially observed systems (Gaussian uncertainty). Robustness can be addressed via H-infinity control or μ-synthesis. Constraints can be incorporated via quadratic programming or penalty methods. The closed-form optimal solution, computational efficiency, and theoretical guarantees make LQR the gold standard in linear control.

Differential Dynamic Programming (DDP) extends LQR to nonlinear systems via successive linearization. Given nonlinear dynamics f(x,u) and cost ∑ᵢ c(xᵢ,uᵢ), DDP optimizes a specific trajectory. Initialize with an arbitrary trajectory {x̄₀,ū₀,...,ū_{T-1}}. At each DDP iteration: (1) Linearize dynamics around trajectory: f(x,u) ≈ A(t)x + B(t)u + c, (2) Linearize cost around trajectory, (3) Solve the resulting finite-horizon LQR subproblem backward, (4) Execute forward pass with computed feedback gains to generate a new trajectory.

The backward pass computes value function and feedback gains using Riccati recursion analogous to finite-horizon LQR. Define Qₜ(δx,δu) = c(x̄ₜ,ūₜ) + (∇c)ᵀ[δx;δu] + ½[δx;δu]ᵀHₜ[δx;δu] where Hₜ is the Hessian of Q (value + linearized dynamics cost). Backward: Qₜ = Qₜ(x,u) + Vₜ₊₁(f(x,u)). The forward pass executes: xₜ₊₁ = f(xₜ,ūₜ + Kₜδxₜ + kₜ) where Kₜ, kₜ come from LQR solution. This improves the trajectory toward a locally optimal solution.

DDP converges quadratically near local optima, meaning error squared at each iteration—very rapid convergence. However, convergence is only guaranteed locally; far from optima, divergence is possible. Heuristics like step-size reduction ("line search") improve robustness. Iterative LQR (iLQR) simplifies DDP by ignoring second-order terms, making each iteration cheaper. Modern implementations use regularization to ensure numerical stability of Riccati recursion.

Applications in robotics are widespread: trajectory optimization for manipulation, locomotion, and legged control. DDP works well when an initial trajectory is available (from human demonstrations or simpler heuristics) and when the nonlinearity is moderate. For highly nonlinear systems or unstructured problems, DDP may require good initialization. Extensions include time-varying systems, constraints (e.g., joint limits), and probabilistic variants formulating control as inference. iLQR is now the practical standard in robotics for nonlinear trajectory optimization.

Policy gradient methods directly optimize the policy π(a|s;θ) parameterized by θ using gradient ascent on the objective J(θ) = E[∑ᵗγᵗrₜ | π_θ]. The policy gradient theorem (Sutton et al.) states that ∇J(θ) = E[∇log π(a|s;θ) Q^π(s,a)]. This remarkable result shows gradient can be computed by sampling actions from the policy, computing log probabilities, and weighting by Q-values. No knowledge of transition model P is required.

REINFORCE algorithm implements policy gradient via stochastic gradient ascent: θ ← θ + α ∇log π(aₜ|sₜ;θ) Gₜ where Gₜ = ∑ₖγᵏ rₜ₊ₖ is the sampled return. This is an unbiased gradient estimator: E[∇log π(aₜ|sₜ;θ) Gₜ] = ∇J(θ). However, Gₜ can be high variance because it's a single sample of stochastic returns. Reducing variance is critical for sample efficiency. A baseline function b(s) reduces variance without introducing bias: ∇J(θ) = E[∇log π(a|s;θ) (Q^π(s,a) - b(s))]. Choosing b(s) = V^π(s) is optimal for minimizing variance, yielding advantage estimates A^π(s,a) = Q^π(s,a) - V^π(s).

Actor-critic methods learn both policy π(a|s;θ) and value function V(s;φ). The critic (value function) provides low-variance estimates of advantage; the actor updates policy using these estimates. Generalized Advantage Estimation (GAE) combines n-step returns with exponentially decaying weights: Âₜ = ∑_{l=0}^∞ (γλ)ˡ δₜ₊ₗ where δₜ = rₜ + γV(sₜ₊₁) - V(sₜ) is the temporal difference error. GAE offers a bias-variance tradeoff controlled by λ ∈ [0,1].

Advanced policy gradient methods address optimization stability. Trust region methods (TRPO, PPO) constrain updates to stay near the old policy to prevent catastrophic forgetting. PPO: θ ← argmaxθ E[min(rₜ(θ) Âₜ, clip(rₜ(θ), 1-ε, 1+ε) Âₜ)] where rₜ(θ) = π(aₜ|sₜ;θ)/π(aₜ|sₜ;θ_old) is the probability ratio. Clipping prevents excessive policy updates. Natural policy gradient methods use Fisher information matrix to account for policy geometry. Policy gradient's ability to handle continuous action spaces, combined with variance reduction techniques, makes them dominant in modern deep RL for both continuous and discrete control.

Course Materials

Sutton & Barto — Reinforcement Learning: An Introduction (2nd ed.) — Comprehensive textbook on MDPs, value functions, policy gradients, and temporal difference learning

Textbooks & Papers

CS229 Main Lecture Notes — Introduction to reinforcement learning, control problems, and learning algorithms

Reinforcement Learning — Overview of learning agents, policies, rewards, and decision processes