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(dH 5 log |A|/ϵ 2 + dH 4 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 non-optimistic provably efficient actor-critic algorithm that only additionally requires N off ≥ c * off dH 4 /ϵ 2 in exchange for omitting optimism, where c * off is the single-policy concentrability coefficient and N off is the number of offline samples. This addresses another open problem in the literature. We further provide numerical experiments to support our theoretical findings. * Equal contribution.