Deep Reinforcement Learning (John Schulman, OpenAI)

Deep Reinforcement Learning: Overview and Formalism

• Core Definition: Deep Reinforcement Learning (RL) applies reinforcement learning, a branch of machine learning for sequential decision-making, using neural networks as function approximators.
  • The objective is for an agent to maximize an accumulated reward function by interacting with an unknown environment.
  • Neural networks can approximate three primary elements: the policy (action selection), value functions (state/action goodness), or system dynamics (transition models).
• Comparison to Other ML Paradigms:
  • vs. Supervised Learning: Unlike supervised learning where inputs have explicit labels, RL lacks direct analytic access to the loss function; gradients must be estimated via interaction.
  • vs. Contextual Bandits: RL introduces statefulness, where the environment evolves over time ($s_t$ depends on $s_{t-1}$ and $a_{t-1}$), creating delayed effects and non-stationary inputs.
  • Key Distinctions: The two primary differentiators are the lack of direct loss function access and the stateful nature of the environment.
• Applicability and Limitations:
  • Deep RL may be "overkill" or unstable if the problem has a small parameter space or if derivative-free optimization is sufficient.
  • Contextual bandit approaches often suffice for problems where statefulness is negligible (e.g., standard advertising) due to better theoretical guarantees.
  • Operations Research methods (e.g., policy/value iteration with feature engineering) remain competitive for structured problems.
• Success Stories:
  • Atari Games: DeepMind used Deep Q-Networks (DQN) to master multiple games from raw pixel input.
  • Go: DeepMind combined supervised learning, policy gradients, Monte Carlo Tree Search, and value functions to defeat world champions.
  • Robotics: Algorithms like Guided Policy Search and Trust Region Policy Optimization (TRPO) have enabled real-time manipulation and stable locomotion in simulated environments (e.g., MuJoCo).
  • Structured Prediction: Policy gradients have been applied to non-differentiable tasks like machine translation.

Policy Gradient Methods

• Core Intuition: These methods explicitly parameterize the policy ($\pi_\theta$) and use gradient ascent to maximize the expected cumulative reward ($\eta$).
  • The strategy involves sampling trajectories and increasing the probability of high-reward actions.
• Score Function Gradient Estimator:
  • The fundamental estimator for the gradient of an expectation is $E[f(x) \nabla_\theta \log p(x)]$, where $f(x)$ is the function value (reward) and $p(x)$ is the probability distribution.
  • This estimator is unbiased and valid even if the objective function is discontinuous or non-differentiable (e.g., robotic contact dynamics).
  • In RL, the random variable $x$ is the entire trajectory, and the gradient estimator sums $\nabla_\theta \log \pi(a_t|s_t)$ weighted by the total reward.
• Variance Reduction Techniques:
  • Temporal Structure: Instead of weighting all actions by the total episode reward, future rewards (returns) are assigned only to the actions preceding them.
  • Baseline: Subtracting a state-dependent baseline ($b(s)$) from the return reduces variance without introducing bias; the optimal baseline is the expected return ($V(s)$).
  • Discounting: Multiplying rewards by $\gamma^t$ (typically 0.95–0.99) reduces the variance associated with distant future rewards, effectively ignoring credit assignment beyond ~100 steps.
• Advanced Variants:
  • Trust Region Policy Optimization (TRPO): Constrains policy updates by limiting the Kullback-Leibler (KL) divergence between old and new policies to prevent catastrophic forgetting.
  • Actor-Critic Methods: Use a value function (critic) to aggressively reduce variance, though this introduces potential bias compared to vanilla policy gradients.
  • Re-parameterization: Differentiating directly with respect to actions (rather than just probabilities) to "push" actions toward better outcomes.

Q-Function Learning Methods

• Core Concept: Instead of optimizing a policy directly, these methods learn a Q-function ($Q(s,a)$) estimating the expected cumulative reward of taking action $a$ in state $s$.
  • The optimal policy is derived by selecting the action with the maximum Q-value.
• Bellman Equations:
  • Policy Evaluation: $Q^\pi(s,a) = E[R + \gamma Q^\pi(s', a')]$, where $a'$ is selected by the current policy.
  • Optimization: $Q^(s,a) = E[R + \gamma \max_{a'} Q^(s', a')]$, representing the value of the optimal policy.
  • Both equations define fixed points that can be reached via iterative Bellman backups.
• Algorithms:
  • Value Iteration: Repeatedly applies the Bellman backup for $Q^*$ until convergence; converges to the optimal Q-function regardless of the policy used for data collection (off-policy).
  • Policy Iteration: Alternates between evaluating the current policy's Q-function and updating the policy to be greedy with respect to that Q-function.
  • DQN (Deep Q-Network): An online variant of neural fitted Q-iteration using:
    • Experience Replay: A rolling history of past trajectories to break temporal correlations in training data.
    • Target Network: A lagged copy of the Q-network used to calculate targets, stabilizing training dynamics.
  • SARSA: An online algorithm implementing the Bellman backup for $Q^\pi$ (on-policy), which often performs competitively with DQN.

Comparative Summary and Challenges

• Method Comparison:
  • Policy Gradient: Generally more reliable and easier to apply "out of the box" for continuous control; optimizing the objective directly.
  • Q-Function: More sample-efficient when successful but less robust to failure modes; relies on indirect optimization via value estimation.
  • Trade-off: Q-methods allow off-policy learning and exploration with a separate behavior policy, which is difficult to achieve cleanly with vanilla policy gradients.
• Optimization Landscape:
  • The primary difficulty in RL is often the complex "behavior space" rather than the neural network's loss surface; local minima often correspond to sub-optimal behaviors (e.g., a robot standing still vs. diving).
• Practical Constraints:
  • Reward Sparsity: Learning is significantly harder when rewards are only observed at episode termination, as credit assignment over long horizons becomes difficult.
  • Time Discretization: The choice of time step is critical; too small a step increases the delay between action and reward, complicating credit assignment and making exploration resemble a random walk.
  • Real-World Deployment: While simulations are dominant, real-world RL is feasible but requires significant patience (e.g., weeks of training for locomotion) and robust handling of environmental noise.
• Future Directions:
  • Hierarchical RL: A promising avenue for addressing long time horizons by introducing multiple levels of temporal abstraction.
  • Model-Based RL: Using learned dynamics models for faster learning or variance reduction (e.g., Stochastic Value Gradients), though robust high-sample-efficiency results are still emerging.