Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization
This work addresses the challenge of narrowing the performance gap between adversarial and stochastic MDPs for reinforcement learning researchers, representing a significant theoretical advancement rather than an incremental improvement.
The paper tackles the problem of learning in adversarial Markov decision processes with an oblivious adversary, proposing the APO-MVP algorithm that achieves a regret bound of order ˜O(poly(H)√SAT), improving upon the best-known bound by a factor of √S and matching the minimax lower bound in dependencies on S, A, and T.
We consider the problem of learning in adversarial Markov decision processes [MDPs] with an oblivious adversary in a full-information setting. The agent interacts with an environment during $T$ episodes, each of which consists of $H$ stages, and each episode is evaluated with respect to a reward function that will be revealed only at the end of the episode. We propose an algorithm, called APO-MVP, that achieves a regret bound of order $\tilde{\mathcal{O}}(\mathrm{poly}(H)\sqrt{SAT})$, where $S$ and $A$ are sizes of the state and action spaces, respectively. This result improves upon the best-known regret bound by a factor of $\sqrt{S}$, bridging the gap between adversarial and stochastic MDPs, and matching the minimax lower bound $Ω(\sqrt{H^3SAT})$ as far as the dependencies in $S,A,T$ are concerned. The proposed algorithm and analysis completely avoid the typical tool given by occupancy measures; instead, it performs policy optimization based only on dynamic programming and on a black-box online linear optimization strategy run over estimated advantage functions, making it easy to implement. The analysis leverages two recent techniques: policy optimization based on online linear optimization strategies (Jonckheere et al., 2023) and a refined martingale analysis of the impact on values of estimating transitions kernels (Zhang et al., 2023).