Off-Policy Interval Estimation with Lipschitz Value Iteration

Abstract

Off-policy evaluation provides an essential tool for evaluating the effects of different policies or treatments using only observed data. When applied to high-stakes scenarios such as medical diagnosis or financial decision-making, it is crucial to provide provably correct upper and lower bounds of the expected reward, not just a classical single point estimate, to the end-users, as executing a poor policy can be very costly. In this work, we propose a provably correct method for obtaining interval bounds for off-policy evaluation in a general continuous setting. The idea is to search for the maximum and minimum values of the expected reward among all the Lipschitz Q-functions that are consistent with the observations, which amounts to solving a constrained optimization problem on a Lipschitz function space. We go on to introduce a Lipschitz value iteration method to monotonically tighten the interval, which is simple yet efficient and provably convergent. We demonstrate the practical efficiency of our method on a range of benchmarks.

arXiv commentTo appear at NeurIPS 2020

References in corpus (8)

• Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms
• Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation
• GenDICE: Generalized Offline Estimation of Stationary Values
• Efficient Model-free Reinforcement Learning in Metric Spaces
• A Kernel Loss for Solving the Bellman Equation
• Policy Certificates: Towards Accountable Reinforcement Learning
• Learning to Control in Metric Space with Optimal Regret
• Black-box Off-policy Estimation for Infinite-Horizon Reinforcement Learning