A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes
This work provides a theoretical foundation for PPO in linear MDPs, addressing a gap in reinforcement learning theory for researchers and practitioners.
The paper tackles the lack of theoretical understanding for proximal policy optimization (PPO) in linear Markov decision processes (MDPs) by proposing an optimistic variant and establishing a regret bound of $ ilde{\mathcal{O}}(d^{3/4}H^2K^{3/4})$, achieving state-of-the-art results in both stochastic and adversarial linear MDPs.
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.