mlsanityData to 14 Oct 2026

Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions

arXiv 2307.10524 ↗First posted 20 Jul 2023cs.LG cs.PFcited by 8

Not on the map. Why?

Abstract (arXiv)

We study the tradeoff between consistency and robustness in the context of a single-trajectory time-varying Markov Decision Process (MDP) with untrusted machine-learned advice. Our work departs from the typical approach of treating advice as coming from black-box sources by instead considering a setting where additional information about how the advice is generated is available. We prove a first-of-its-kind consistency and robustness tradeoff given Q-value advice under a general MDP model that includes both continuous and discrete state/action spaces. Our results highlight that utilizing Q-value advice enables dynamic pursuit of the better of machine-learned advice and a robust baseline, thus result in near-optimal performance guarantees, which provably improves what can be obtained solely with black-box advice.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 42 of its 69 references that are in the map. First posted on arXiv 20 Jul 2023.

Builds on

42 of 69 references.

References · 42

  1. 2017Deep reinforcement learning from human preferencescited by 3,912
  2. 2022Scaling Laws for Reward Model Overoptimizationcited by 1,095
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  4. 2018Is Q-learning Provably Efficient?cited by 487
  5. 2021Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learningcited by 371
  6. 2017Safe Model-based Reinforcement Learning with Stability Guaranteescited by 366
  7. 2019A Theory of Regularized Markov Decision Processescited by 286
  8. 2018Provably Efficient Maximum Entropy Explorationcited by 242
  9. 2018Competitive caching with machine learned advicecited by 195
  10. 2017Bridging the Gap Between Value and Policy Based Reinforcement Learningcited by 182
  11. 2017Interactive Learning from Policy-Dependent Human Feedbackcited by 158
  12. 2020Algorithms with Predictionscited by 153
30 more
  1. 2017DARLA: Improving Zero-Shot Transfer in Reinforcement Learningcited by 149
  2. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  3. 2019Online Control with Adversarial Disturbancescited by 92
  4. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 80
  5. 2020Online metric algorithms with untrusted predictionscited by 75
  6. 2019Near-Optimal Bounds for Online Caching with Machine Learned Advicecited by 73
  7. 2020Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithmscited by 64
  8. 2021Contraction Theory for Nonlinear Stability Analysis and Learning-based Control: A Tutorial Overviewcited by 45
  9. 2020Widening the Pipeline in Human-Guided Reinforcement Learning with Explanation and Context-Aware Data Augmentationcited by 42
  10. 2021On the Sample Complexity of Stability Constrained Imitation Learningcited by 38
  11. 2019Control Regularization for Reduced Variance Reinforcement Learningcited by 37
  12. 2022Trustworthy Reinforcement Learning Against Intrinsic Vulnerabilities: Robustness, Safety, and Generalizabilitycited by 36
  13. 2019Model-Based Reinforcement Learning with Adversarial Training for Online Recommendationcited by 33
  14. 2021Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systemscited by 25
  15. 2021On the Regret Analysis of Online LQR Control with Predictionscited by 22
  16. 2022Online Algorithms with Multiple Predictionscited by 22
  17. 2019Deep Value Model Predictive Controlcited by 20
  18. 2022Parsimonious Learning-Augmented Cachingcited by 19
  19. 2022Chasing Convex Bodies and Functions with Black-Box Advicecited by 19
  20. 2020Non-Stochastic Control with Bandit Feedbackcited by 17
  21. 2022Bounded-Regret MPC via Perturbation Analysis: Prediction Error, Constraints, and Nonlinearitycited by 16
  22. 2020Sample Efficient Reinforcement Learning through Learning from Demonstrations in Minecraftcited by 15
  23. 2021Robustness and Consistency in Linear Quadratic Control with Untrusted Predictionscited by 14
  24. 2022Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbationscited by 14
  25. 2021Can Q-Learning be Improved with Advice?cited by 13
  26. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  27. 2021Competitive Controlcited by 8
  28. 2020Learning-Based Predictive Control via Real-Time Aggregate Flexibilitycited by 7
  29. 2021Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systemscited by 4
  30. 2022Optimal Competitive-Ratio Controlcited by 2

Built on by

Cited by year (2026 to 14 Oct)

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

8 papers.

  1. 2024Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scalecited by 8
  2. 2025On the Hardness of Reinforcement Learning with Transition Look-Aheadcited by 4
  3. 2025Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approachcited by 3
  4. 2025Efficiently Solving Discounted MDPs with Predictions on Transition Matricescited by 2
  5. 2023Out-of-Distribution-Aware Electric Vehicle Chargingcited by 1
  6. 2024Safe Exploitative Play with Untrusted Type Beliefscited by 0
  7. 2026Learning Augmented Exact Exponential Algorithmscited by 0
  8. 2026Near-Optimal Reinforcement Learning with Multi-Step Transition Lookaheadcited by 0