  The proximal policy optimization (PPO) algorithm stands as one of the most
prosperous methods in the field of reinforcement learning (RL). Despite its
success, the theoretical understanding of PPO remains deficient. Specifically,
it is unclear whether PPO or its optimistic variants can effectively solve
linear Markov decision processes (MDPs), which are arguably the simplest models
in RL with function approximation. To bridge this gap, we propose an optimistic
variant of PPO for episodic adversarial linear MDPs with full-information
feedback, and establish a $\tilde{\mathcal{O}}(d^{3/4}H^2K^{3/4})$ regret for
it. Here $d$ is the ambient dimension of linear MDPs, $H$ is the length of each
episode, and $K$ is the number of episodes. Compared with existing policy-based
algorithms, we achieve the state-of-the-art regret bound in both stochastic
linear MDPs and adversarial linear MDPs with full information. Additionally,
our algorithm design features a novel multi-batched updating mechanism and the
theoretical analysis utilizes a new covering number argument of value and
policy classes, which might be of independent interest.
