Best-of-both-worlds Policy Optimization for Heavy-tailed Markov Decision Processes

We study finite-horizon tabular Markov decision processes (MDPs) with heavy-tailed loss functions (i.e., every one-step loss is assumed only to have a bounded $\epsilon$-th raw moment for a known $\epsilon \in (1,2]$). Previously, *best-of-both-worlds* (BOBW) guarantee for this problem has only been achieved by Chen et al. (2026) using an *occupancy measure* (OM)-based algorithm. In this work, we develop a *policy optimization* (PO)-based approach, which is preferable to OM-based approaches in practice because PO updates the policy locally at each state and does not require solving a global optimization problem. In addition to the computational advantage, for known transitions, the heavy-tail terms in our regret bounds improve upon those of Chen et al. (2026) by factors of $\mathcal{O}(S^{2-2/\epsilon }{A}^{2-3/\epsilon +1/{\epsilon }^2})$ and $\mathcal{O}(S^2{A}^{2-1/\epsilon })$ in the adversarial and stochastic regimes, respectively, where $S$ and $A$ denote the sizes of the state and action spaces. For unknown transitions, our method does *not* require the truncated non-negativity assumption imposed by Chen et al. (2026); moreover, our heavy-tail terms are smaller by factors of $\mathcal{O}(S^{3-2/\epsilon }{A}^{3-3/\epsilon +1/{\epsilon }^2})$ and $\mathcal{O}(H{S}^3{A}^{3-1/\epsilon }\log T)$ in the adversarial and stochastic regimes, respectively, where $T$ denotes the number of episodes.