Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
This work addresses the challenge of robust policy learning in RL for scenarios where optimal policies may not be in the class, offering theoretical guarantees and practical insights, though it is incremental as it builds on existing methods and assumptions.
The paper tackles the problem of agnostic reinforcement learning, where the goal is to find a policy competitive with the best in a given class without assuming it contains the optimal policy, by proposing a framework that reduces it to first-order optimization and deriving sample complexity upper bounds for three algorithms under a variational gradient dominance condition.
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: \emph{(i)} Steepest Descent Policy Optimization, derived from a constrained steepest descent method for non-convex optimization; \emph{(ii)} the classical Conservative Policy Iteration algorithm \citep{kakade2002approximately} reinterpreted through the lens of the Frank-Wolfe method, which leads to improved convergence results; and \emph{(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.