Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processes
Not on the map. Why?
Abstract (arXiv)
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 widetildeO(T1/α) regret bound in adversarial regimes and a 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 widetildeO(T1/α + √T) regret in adversarial regimes and a O(log2(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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 26 of its 38 references that are in the map. First posted on arXiv 1 Feb 2026.
Builds on
26 of 38 references.
References · 26
- 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
- 2018Stochastic bandits robust to adversarial corruptionscited by 118
- 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
- 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
- 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
- 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
- 2018Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffscited by 31
- 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
- 2020Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffscited by 25
- 2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruptioncited by 24
- 2019Bayesian Optimization under Heavy-tailed Payoffscited by 21
- 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 17
14 more
- 2023Best of Both Worlds Policy Optimizationcited by 17
- 2021No-Regret Reinforcement Learning with Heavy-Tailed Rewardscited by 13
- 2023No-Regret Online Reinforcement Learning with Adversarial Losses and Transitionscited by 13
- 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
- 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
- 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
- 2024A Review of Reinforcement Learning in Financial Applicationscited by 11
- 2023Robust Offline Reinforcement learning with Heavy-Tailed Rewardscited by 7
- 2024uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABscited by 7
- 2025Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Updatecited by 5
- 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
- 2023Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximationcited by 4
- 2025Heavy-tailed Linear Bandits: Adversarial Robustness, Best-of-both-worlds, and Beyondcited by 4
- 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcited by 2
Built on by
Citing papers per year: 2026: 1.
1 paper.