SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation

Abstract

When function approximation is used, solving the Bellman optimality equation with stability guarantees has remained a major open problem in reinforcement learning for decades. The fundamental difficulty is that the Bellman operator may become an expansion in general, resulting in oscillating and even divergent behavior of popular algorithms like Q-learning. In this paper, we revisit the Bellman equation, and reformulate it into a novel primal-dual optimization problem using Nesterov's smoothing technique and the Legendre-Fenchel transformation. We then develop a new algorithm, called Smoothed Bellman Error Embedding, to solve this optimization problem where any differentiable function class may be used. We provide what we believe to be the first convergence guarantee for general nonlinear function approximation, and analyze the algorithm's sample complexity. Empirically, our algorithm compares favorably to state-of-the-art baselines in several benchmark control problems.

28 pages, 13 figures. To appear at the 35th International Conference on Machine Learning (ICML 2018)

Cited by in corpus (75)

• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections
• AlgaeDICE: Policy Gradient from Arbitrary Experience
• Information-Theoretic Considerations in Batch Reinforcement Learning
• GenDICE: Generalized Offline Estimation of Stationary Values
• Off-Policy Policy Gradient with State Distribution Correction
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• Value Propagation for Decentralized Networked Deep Multi-agent Reinforcement Learning
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost
• Mirror Descent Policy Optimization
• Off-Policy Evaluation via the Regularized Lagrangian
• First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
• Tsallis Reinforcement Learning: A Unified Framework for Maximum Entropy Reinforcement Learning
• CoinDICE: Off-Policy Confidence Interval Estimation
• On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach
• A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
• A hybrid learning method for system identification and optimal control
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
• Improved Algorithms for Convex-Concave Minimax Optimization
• Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Newton-type Methods for Minimax Optimization
• On the Suboptimality of Negative Momentum for Minimax Optimization
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• On Computation and Generalization of Generative Adversarial Imitation Learning
• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems
• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
• Instrumental Variable Value Iteration for Causal Offline Reinforcement Learning
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality
• Zap Q-Learning With Nonlinear Function Approximation
• Generalized Second Order Value Iteration in Markov Decision Processes
• Geometric Insights into the Convergence of Nonlinear TD Learning
• Stochastic Primal-Dual Q-Learning
• Stable Policy Optimization via Off-Policy Divergence Regularization
• Deep Residual Reinforcement Learning
• Average-Reward Off-Policy Policy Evaluation with Function Approximation
• Implicit Under-Parameterization Inhibits Data-Efficient Deep Reinforcement Learning
• Optimality and Stability in Non-Convex Smooth Games
• Convergent and Efficient Deep Q Network Algorithm
• Mean-Variance Policy Iteration for Risk-Averse Reinforcement Learning
• On Value Functions and the Agent-Environment Boundary
• On the Analysis of Model-free Methods for the Linear Quadratic Regulator
• DIPPA: An improved Method for Bilinear Saddle Point Problems
• Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation
• Fast Rates for the Regret of Offline Reinforcement Learning
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Planning in entropy-regularized Markov decision processes and games
• Target-Based Temporal Difference Learning
• Reinforcement Learning with Dynamic Boltzmann Softmax Updates
• Borrowing From the Future: Addressing Double Sampling in Model-free Control
• A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning
• A Generalized Projected Bellman Error for Off-policy Value Estimation in Reinforcement Learning
• Finding the Near Optimal Policy via Adaptive Reduced Regularization in MDPs
• A Convergence Result for Regularized Actor-Critic Methods
• Estimating Optimal Infinite Horizon Dynamic Treatment Regimes via pT-Learning
• Market Self-Learning of Signals, Impact and Optimal Trading: Invisible Hand Inference with Free Energy
• Randomized Stochastic Gradient Descent Ascent
• ISL: A novel approach for deep exploration
• Stabilizing Q Learning Via Soft Mellowmax Operator
• Logistic Q-Learning
• Ranking Policy Gradient
• Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch
• Primal-Dual First-Order Methods for Affinely Constrained Multi-Block Saddle Point Problems
• On Generalized Bellman Equations and Temporal-Difference Learning
• Parameterized MDPs and Reinforcement Learning Problems -- A Maximum Entropy Principle Based Framework
• Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Games
• Borrowing From the Future: An Attempt to Address Double Sampling
• Convex-Concave Min-Max Stackelberg Games