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

Policy Optimization (PO) algorithms are a class of methods in Reinforcement Learning (RL; Sutton and Barto, 2018; Mannor et al., 2022) in which an agent's policy is iteratively updated to minimize long-term cost, as defined by the environment's value functions. Modern applications of PO methods (e.g., Lillicrap, 2015; Schulman et al., 2015; Akkaya et al., 2019; Ouyang et al., 2022) often involve large-scale environments that lack well-defined structure, and by that require function approximation techniques in order to learn efficiently. Typically, PO algorithms represent the agent's policy using neural network models--commonly referred to as actor networks. Notably, these setups are inherently agnostic: the learner searches for an assignment of network parameters that is competitive with the best achievable under the model, without any guarantee that the optimal policy is expressible by the actor architecture. Motivated by this, we consider the problem of agnostic policy learning in the general function approximation setup (Kakade, 2003; Krishnamurthy et al., 2025), where the learner is given optimization oracle access to a policy class Π and is required to find a policy that performs nearly as well as the best in-class policy. It is well known that Π-completeness and coverage conditions allow for sample efficient policy learning (Agarwal et al., 2019, 2021; Bhandari and Russo, 2024),