mlsanityData to 7 Oct 2026

Policy Certificates: Towards Accountable Reinforcement Learning

arXiv 1811.03056 ↗First posted 7 Nov 2018cs.LG cs.AI stat.MLcited by 81

Not on the map. Why?

Abstract (arXiv)

The performance of a reinforcement learning algorithm can vary drastically during learning because of exploration. Existing algorithms provide little information about the quality of their current policy before executing it, and thus have limited use in high-stakes applications like healthcare. We address this lack of accountability by proposing that algorithms output policy certificates. These certificates bound the sub-optimality and return of the policy in the next episode, allowing humans to intervene when the certified quality is not satisfactory. We further introduce two new algorithms with certificates and present a new framework for theoretical analysis that guarantees the quality of their policies and certificates. For tabular MDPs, we show that computing certificates can even improve the sample-efficiency of optimism-based exploration. As a result, one of our algorithms is the first to achieve minimax-optimal PAC bounds up to lower-order terms, and this algorithm also matches (and in some settings slightly improves upon) existing minimax regret bounds.

Key facts. Cited by 81 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Nov 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 24; 2022: 17; 2023: 16; 2024: 9; 2025: 9; 2026: 6.

81 papers.

Sort:

By area:

  1. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  2. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  3. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  4. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  5. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  6. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  7. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  8. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  9. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  10. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  11. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  12. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
38 more
  1. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  2. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  3. 2023Fast Rates for Maximum Entropy Explorationcited by 32
  4. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  5. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  6. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  7. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  8. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  9. 2021On the (In)Tractability of Reinforcement Learning for LTL Objectivescited by 18
  10. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  11. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  12. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  13. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  14. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  15. 2021Provably Efficient Multi-Task Reinforcement Learning with Model Transfercited by 16
  16. 2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
  17. 2022Understanding the Complexity Gains of Single-Task RL with a Curriculumcited by 16
  18. 2021Task-Optimal Exploration in Linear Dynamical Systemscited by 15
  19. 2021A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPscited by 15
  20. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14
  21. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  22. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
  23. 2021On Blame Attribution for Accountable Multi-Agent Sequential Decision Makingcited by 13
  24. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  25. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  26. 2023Computably Continuous Reinforcement-Learning Objectives are PAC-learnablecited by 13
  27. 2021Confidence-Budget Matching for Sequential Budgeted Learningcited by 11
  28. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  29. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  30. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  31. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  32. 2024Reinforcement Learning with Lookahead Informationcited by 8
  33. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  34. 2023Towards Instance-Optimality in Online PAC Reinforcement Learningcited by 7
  35. 2024The Value of Reward Lookahead in Reinforcement Learningcited by 6
  36. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guaranteescited by 5
  37. 2024Test-Time Regret Minimization in Meta Reinforcement Learningcited by 5
  38. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5

50 most cited of 81 All 81 (JSON)