Policy Certificates: Towards Accountable Reinforcement Learning

Abstract

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.

arXiv commentarticle appearing at ICML 2019; full version including appendix

References in corpus (11)

• (More) Efficient Reinforcement Learning via Posterior Sampling
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• Safe Policy Improvement by Minimizing Robust Baseline Regret
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Model-based Reinforcement Learning and the Eluder Dimension
• Is Q-learning Provably Efficient?
• Multi-step Off-policy Learning Without Importance Sampling Ratios
• Online learning in MDPs with side information
• Fairness in Reinforcement Learning

Cited by in corpus (13)

• Model-Based Reinforcement Learning with Value-Targeted Regression
• VariBAD: A Very Good Method for Bayes-Adaptive Deep RL via Meta-Learning
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Provably Efficient Q-Learning with Low Switching Cost
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• HARK Side of Deep Learning -- From Grad Student Descent to Automated Machine Learning
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Task-agnostic Exploration in Reinforcement Learning
• Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes
• Continuous Control with Contexts, Provably
• Efficient Policy Learning for Non-Stationary MDPs under Adversarial Manipulation
• Off-Policy Interval Estimation with Lipschitz Value Iteration