Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning

2025/07/06 by Sherman, Uri, Koren, Tomer, Mansour, Yishay
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2507.04406

Abstract

We study reinforcement learning (RL) in the agnostic policy learning setting, where the goal is to find a policy whose performance is competitive with the best policy in a given class of interest Π -- crucially, without assuming that Π contains the optimal policy. We propose a general policy learning framework that reduces this problem to first-order optimization in a non-Euclidean space, leading to new algorithms as well as shedding light on the convergence properties of existing ones. Specifically, under the assumption that Π is convex and satisfies a variational gradient dominance (VGD) condition -- an assumption known to be strictly weaker than more standard completeness and coverability conditions -- we obtain sample complexity upper bounds for three policy learning algorithms: (i) Steepest Descent Policy Optimization, derived from a constrained steepest descent method for non-convex optimization; (ii) the classical Conservative Policy Iteration algorithm \citepkakade2002approximately reinterpreted through the lens of the Frank-Wolfe method, which leads to improved convergence results; and (iii) an on-policy instantiation of the well-studied Policy Mirror Descent algorithm. Finally, we empirically evaluate the VGD condition across several standard environments, demonstrating the practical relevance of our key assumption.

Citations

• The Role of Environment Access in Agnostic Reinforcement Learning
• Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
• On the Second-Order Convergence of Biased Policy Gradient Algorithms
• When is Agnostic Reinforcement Learning Statistically Tractable?
• Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes
• A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence
• Policy Optimization over General State and Action Spaces
• Discovered Policy Optimisation
• Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies
• Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization
• Training language models to follow instructions with human feedback
• On the Convergence Rates of Policy Gradient Methods
• Mirror Learning: A Unifying Framework of Policy Optimisation
• A general sample complexity analysis of vanilla policy gradient
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
• Leveraging Non-uniformity in First-order Non-convex Optimization
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Mirror Descent Policy Optimization
• On the Global Convergence Rates of Softmax Policy Gradient Methods
• Solving Rubik's Cube with a Robot Hand
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Global Optimality Guarantees For Policy Gradient Methods
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Information-Theoretic Considerations in Batch Reinforcement Learning
• A Theory of Regularized Markov Decision Processes
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Continuous control with deep reinforcement learning
• High-Dimensional Continuous Control Using Generalized Advantage\n Estimation
• Approximate Policy Iteration Schemes: A Comparison
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
• Reinforcement Learning: An Introduction

Related

• Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes
• Agnostic Reinforcement Learning: Foundations and Algorithms
• An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithms
• Global Convergence of Policy Gradient Methods in Reinforcement Learning, Games and Control
• Sample Complexity of Policy Gradient Finding Second-Order Stationary Points