mlsanityData to 7 Oct 2026

Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learning

arXiv 2403.05385 ↗First posted 8 Mar 2024cs.LGcited by 8

On the map: Offline RL and imitation learning from data → Offline RL algorithms

Abstract (arXiv)

We propose training fitted Q-iteration with log-loss (FQI-log) for batch reinforcement learning (RL). We show that the number of samples needed to learn a near-optimal policy with FQI-log scales with the accumulated cost of the optimal policy, which is zero in problems where acting optimally achieves the goal and incurs no cost. In doing so, we provide a general framework for proving small-cost bounds, i.e. bounds that scale with the optimal achievable cost, in batch RL. Moreover, we empirically verify that FQI-log uses fewer samples than FQI trained with squared loss on problems where the optimal policy reliably achieves the goal.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 23 of its 54 references that are in the map. First posted on arXiv 8 Mar 2024.

Builds on

23 of 54 references.

Closest ancestors · 4

Same direction, newest first

  1. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning11 Feb
  2. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
  3. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  4. 2020Batch Value-function Approximation with Only Realizability11 Aug

Other references · 19

  1. 2017A Distributional Perspective on Reinforcement Learningcited by 743
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  5. 2017Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agentscited by 267
  6. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  7. 2024Stop Regressing: Training Value Functions via Classification for Scalable Deep RLcited by 136
  8. 2020The Importance of Pessimism in Fixed-Dataset Policy Optimizationcited by 99
  9. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 87
  10. 2020Instance-Wise Minimax-Optimal Algorithms for Logistic Banditscited by 56
  11. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  12. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
7 more
  1. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  2. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  3. 2015First-order regret bounds for combinatorial semi-banditscited by 25
  4. 2023First- and Second-Order Bounds for Adversarial Linear Contextual Banditscited by 19
  5. 2017Small-loss bounds for online learning with partial informationcited by 18
  6. 2018Make the Minority Great Again: First-Order Regret Bound for Contextual Banditscited by 17
  7. 2023Exploration via linearly perturbed loss minimisationcited by 13

Built on by

Cited by year (2026 to 7 Oct)

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

8 papers.

  1. 2025Qsharp: Provably Optimal Distributional RL for LLM Post-Trainingcited by 14
  2. 2025Value-Guided Search for Efficient Chain-of-Thought Reasoningcited by 12
  3. 2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
  4. 2024Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processescited by 3
  5. 2026Eluder dimension: localise it!cited by 2
  6. 2025Rectifying Regression in Reinforcement Learningcited by 1
  7. 2025RIZE: Adaptive Regularization for Imitation Learningcited by 0
  8. 2025Does Weighting Improve Matrix Factorization for Recommender Systems?cited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
  2. 2021Continuous Doubly Constrained Batch Reinforcement Learning
  3. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  4. 2020BRPO: Batch Residual Policy Optimization
  5. 2020Provably Good Batch Reinforcement Learning Without Great Exploration
  6. 2021Fast Rates for the Regret of Offline Reinforcement Learning
  7. 2023Offline Reinforcement Learning with On-Policy Q-Function Regularization
  8. 2021Approximated Multi-Agent Fitted Q Iteration