CoinDICE: Off-Policy Confidence Interval Estimation

Abstract

We study high-confidence behavior-agnostic off-policy evaluation in reinforcement learning, where the goal is to estimate a confidence interval on a target policy's value, given only access to a static experience dataset collected by unknown behavior policies. Starting from a function space embedding of the linear program formulation of the $Q$-function, we obtain an optimization problem with generalized estimating equation constraints. By applying the generalized empirical likelihood method to the resulting Lagrangian, we propose CoinDICE, a novel and efficient algorithm for computing confidence intervals. Theoretically, we prove the obtained confidence intervals are valid, in both asymptotic and finite-sample regimes. Empirically, we show in a variety of benchmarks that the confidence interval estimates are tighter and more accurate than existing methods.

arXiv commentTo appear at NeurIPS 2020 as spotlight

References in corpus (28)

• Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms
• On Exact Computation with an Infinitely Wide Neural Net
• Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction
• Behavior Regularized Offline Reinforcement Learning
• MOPO: Model-based Offline Policy Optimization
• Empirical Bernstein Bounds and Sample Variance Penalization
• Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• Counterfactual Risk Minimization: Learning from Logged Bandit Feedback
• DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections
• Dyna-Style Planning with Linear Function Approximation and Prioritized Sweeping
• Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach
• Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes
• Evaluating Reinforcement Learning Algorithms in Observational Health Settings
• AlgaeDICE: Policy Gradient from Arbitrary Experience
• Safe Policy Improvement with Baseline Bootstrapping
• Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling
• GenDICE: Generalized Offline Estimation of Stationary Values
• Scaling Up Robust MDPs by Reinforcement Learning
• Reinforcement Learning via Fenchel-Rockafellar Duality
• The Importance of Pessimism in Fixed-Dataset Policy Optimization
• Minimax Value Interval for Off-Policy Evaluation and Policy Optimization
• Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation
• Confident Off-Policy Evaluation and Selection through Self-Normalized Importance Weighting
• Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Sampling
• Empirical Likelihood for Contextual Bandits

Cited by in corpus (6)

• Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning
• Minimax Value Interval for Off-Policy Evaluation and Policy Optimization
• Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics
• Universal Off-Policy Evaluation
• On the Optimality of Batch Policy Optimization Algorithms
• Variance-Aware Off-Policy Evaluation with Linear Function Approximation