mlsanityData to 14 Oct 2026

The Fallacy of Minimizing Cumulative Regret in the Sequential Task Setting

arXiv 2403.10946 ↗First posted 16 Mar 2024stat.ML cs.LGcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Online Reinforcement Learning (RL) is typically framed as the process of minimizing cumulative regret (CR) through interactions with an unknown environment. However, real-world RL applications usually involve a sequence of tasks, and the data collected in the first task is used to warm-start the second task. The performance of the warm-start policy is measured by simple regret (SR). While minimizing both CR and SR is generally a conflicting objective, previous research has shown that in stationary environments, both can be optimized in terms of the duration of the task, T. In practice, however, in real-world applications, human-in-the-loop decisions between tasks often results in non-stationarity. For instance, in clinical trials, scientists may adjust target health outcomes between implementations. Our results show that task non-stationarity leads to a more restrictive trade-off between CR and SR. To balance these competing goals, the algorithm must explore excessively, leading to a CR bound worse than the typical optimal rate of T1/2. These findings are practically significant, indicating that increased exploration is necessary in non-stationary environments to accommodate task changes, impacting the design of RL algorithms in fields such as healthcare and beyond.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 13 of its 25 references that are in the map. First posted on arXiv 16 Mar 2024.

Builds on

13 of 25 references.

References · 13

  1. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  2. 2021Maximum Entropy RL (Provably) Solves Some Robust RL Problemscited by 176
  3. 2019Personalized HeartSteps: A Reinforcement Learning Algorithm for Optimizing Physical Activitycited by 70
  4. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  5. 2022Deep Inventory Managementcited by 23
  6. 2022Designing Reinforcement Learning Algorithms for Digital Interventions: Pre-implementation Guidelinescited by 22
  7. 2022Online Policy Optimization for Robust MDPcited by 19
  8. 2023Reinforcement Learning Tutor Better Supported Lower Performers in a Math Taskcited by 11
  9. 2022Contextual Bandits in a Survey Experiment on Charitable Giving: Within-Experiment Outcomes versus Policy Learningcited by 7
  10. 2023Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimizationcited by 7
  11. 2024Experiment Planning with Function Approximationcited by 5
  12. 2023Online learning in bandits with predicted contextcited by 4
1 more
  1. 2024Monitoring Fidelity of Online Reinforcement Learning Algorithms in Clinical Trialscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directionscited by 5

Similar, not cited

Close in wording, no citation either way

  1. 2024A Natural Extension To Online Algorithms For Hybrid RL With Limited Coverage
  2. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPs
  3. 2025Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
  4. 2024On the Exponential Convergence for Offline RLHF with Pairwise Comparisons
  5. 2026Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferences
  6. 2024Pausing Policy Learning in Non-stationary Reinforcement Learning
  7. 2021Fast Rates for the Regret of Offline Reinforcement Learning
  8. 2025Statistical and Algorithmic Foundations of Reinforcement Learning