mlsanityData to 7 Oct 2026

Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards

arXiv 2303.05606 ↗First posted 9 Mar 2023cs.LG cs.AI math.STcited by 8

Not on the map. Why?

Abstract (arXiv)

This paper presents two algorithms, AdaOFUL and VARA, for online sequential decision-making in the presence of heavy-tailed rewards with only finite variances. For linear stochastic bandits, we address the issue of heavy-tailed rewards by modifying the adaptive Huber regression and proposing AdaOFUL. AdaOFUL achieves a state-of-the-art regret bound of widetildeObig(dbig(sumt=1T nut2big)1/2+dbig) as if the rewards were uniformly bounded, where nut2 is the observed conditional variance of the reward at round t, d is the feature dimension, and widetildeO(·) hides logarithmic dependence. Building upon AdaOFUL, we propose VARA for linear MDPs, which achieves a tighter variance-aware regret bound of widetildeO(d√HG^*K). Here, H is the length of episodes, K is the number of episodes, and G^* is a smaller instance-dependent quantity that can be bounded by other instance-dependent quantities when additional structural conditions on the MDP are satisfied. Our regret bound is superior to the current state-of-the-art bounds in three ways: (1) it depends on a tighter instance-dependent quantity and has optimal dependence on d and H, (2) we can obtain further instance-dependent bounds of G^* under additional structural conditions on the MDP, and (3) our regret bound is valid even when rewards have only finite variances, achieving a level of generality unmatched by previous works. Overall, our modified adaptive Huber regression algorithm may serve as a useful building block in the design of algorithms for online problems with heavy-tailed rewards.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 44 of its 72 references that are in the map. First posted on arXiv 9 Mar 2023.

Builds on

44 of 72 references.

References · 44

  1. 2015Continuous control with deep reinforcement learningcited by 3,279
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2016Deep Reinforcement Learning for Dialogue Generationcited by 286
  6. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  7. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  8. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  9. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  10. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  11. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  12. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
32 more
  1. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  2. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  3. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  4. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  5. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  6. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  7. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  8. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 75
  9. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  10. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
  11. 2017Adaptive Huber Regressioncited by 59
  12. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  13. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  14. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  15. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  16. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  17. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  18. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  19. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  20. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  21. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  22. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  23. 2018Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffscited by 31
  24. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  25. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  26. 2020Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffscited by 25
  27. 2019Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalitiescited by 15
  28. 2022Optimal variance-reduced stochastic approximation in Banach spacescited by 14
  29. 2021No-Regret Reinforcement Learning with Heavy-Tailed Rewardscited by 13
  30. 2017A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosiscited by 9
  31. 2022Asymptotic Instance-Optimal Algorithms for Interactive Decision Makingcited by 7
  32. 2021Do we need to estimate the variance in robust mean estimation?cited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 1; 2025: 2; 2026: 1.

8 papers.

  1. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  2. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  3. 2025Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Updatecited by 5
  4. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  5. 2023Online Estimation and Inference for Robust Policy Evaluation in Reinforcement Learningcited by 4
  6. 2023Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximationcited by 4
  7. 2025Adaptive Resolving Methods for Markov Decision Processes with Function Approximationscited by 0
  8. 2026Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noisecited by 0