Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processes

We investigate episodic Markov Decision Processes with heavy-tailed losses (HTMDPs). Existing approaches for HTMDPs are conservative in stochastic environments and lack adaptivity in adversarial regimes. In this work, we propose algorithms HT-FTRL-OM and HT-FTRL-UOB for HTMDPs that achieve Best-of-Both-Worlds (BoBW) guarantees: instance-independent regret in adversarial environments and logarithmic instance-dependent regret in self-bounding (including the stochastic case) environments. For the known transition setting, HT-FTRL-OM applies the Follow-The-Regularized-Leader (FTRL) framework over occupancy measures with novel skipping loss estimators, achieving a $\widetilde{\mathcal{O}}(T^{1/\alpha})$ regret bound in adversarial regimes and a $\mathcal{O}(\log T)$ regret in stochastic regimes. Building upon this framework, we develop a novel algorithm HT-FTRL-UOB to tackle the more challenging unknown-transition setting. Under a mild truncative nonnegativity condition on the loss distributions, this algorithm employs a pessimistic skipping loss estimator and achieves a $\widetilde{\mathcal{O}}(T^{1/\alpha} + \sqrt{T})$ regret in adversarial regimes and a $\mathcal{O}(\log^2(T))$ regret in stochastic regimes. Our analysis overcomes key barriers through several technical insights, including a local control mechanism for heavy-tailed shifted losses, a new suboptimal-mass propagation principle, and a novel regret decomposition that isolates transition uncertainty from heavy-tailed estimation errors and skipping bias.

Many decision-making systems learn by trying actions and observing feedback, such as costs, delays, or losses. In many real applications, this feedback is not well behaved: most observations may look normal, but rare extreme events can be very large and strongly affect learning. This is common in areas such as network routing, finance, and image processing, where outliers cannot simply be ignored. Our work studies how to make reinforcement learning reliable in such heavy-tailed settings, while also adapting to different kinds of environments. We design algorithms that do not need to know in advance whether the environment is stable or changing in an adversarial way. When the environment is stable, our methods learn efficiently; when it changes adversarially, they still keep strong performance guarantees. More broadly, our results show that reinforcement learning can be made robust to extreme feedback without giving up adaptivity to benign or adversarial environments.