Actor-Critics Can Achieve Optimal Sample Efficiency

Actor-critic algorithms have become a cornerstone in reinforcement learning (RL), leveraging the strengths of both policy-based and value-based methods. Despite recent progress in understanding their statistical efficiency, no existing work has successfully learned an ε-optimal policy with a sample complexity of O(1/ε2) trajectories with general function approximation when strategic exploration is necessary. We address this open problem by introducing a novel actor-critic algorithm that attains a sample-complexity of O(dH5 log|A|/ε2 + d H4 log|F|/ ε2) trajectories, and accompanying √T regret when the Bellman eluder dimension d does not increase with T at more than a log T rate. Here, F is the critic function class, A is the action space, and H is the horizon in the finite horizon MDP setting. Our algorithm integrates optimism, off-policy critic estimation targeting the optimal Q-function, and rare-switching policy resets. We extend this to the setting of Hybrid RL, showing that initializing the critic with offline data yields sample efficiency gains compared to purely offline or online RL. Further, utilizing access to offline data, we provide a textitnon-optimistic provably efficient actor-critic algorithm that only additionally requires Noff ≥ coff^*dH4/ε2 in exchange for omitting optimism, where coff^* is the single-policy concentrability coefficient and Noff is the number of offline samples. This addresses another open problem in the literature. We further provide numerical experiments to support our theoretical findings.