Cautiously Optimistic Policy Optimization and Exploration with Linear
  Function Approximation
  Policy optimization methods are popular reinforcement learning algorithms,
because their incremental and on-policy nature makes them more stable than the
value-based counterparts. However, the same properties also make them slow to
converge and sample inefficient, as the on-policy requirement precludes data
reuse and the incremental updates couple large iteration complexity into the
sample complexity. These characteristics have been observed in experiments as
well as in theory in the recent work of~\citet{agarwal2020pc}, which provides a
policy optimization method PCPG that can robustly find near optimal polices for
approximately linear Markov decision processes but suffers from an extremely
poor sample complexity compared with value-based techniques.
  In this paper, we propose a new algorithm, COPOE, that overcomes the sample
complexity issue of PCPG while retaining its robustness to model
misspecification. Compared with PCPG, COPOE makes several important algorithmic
enhancements, such as enabling data reuse, and uses more refined analysis
techniques, which we expect to be more broadly applicable to designing new
reinforcement learning algorithms. The result is an improvement in sample
complexity from $\widetilde{O}(1/\epsilon^{11})$ for PCPG to
$\widetilde{O}(1/\epsilon^3)$ for PCPG, nearly bridging the gap with
value-based techniques.
