Efficient and safe off-policy evaluation : from point estimation to interval estimation

Offline reinforcement learning involves training a decision-making agent based solely on historical data, without any online interaction with the real-world environment. This data-driven approach is particularly relevant in high-stakes applications, such as medical treatment and robotics, where online interaction with the environment can be prohibitively expensive, dangerous, or ethically problematic. By leveraging large datasets of previously observed behaviors, offline reinforcement learning allows practitioners to improve the performance of their decision-making algorithms without incurring the risks and costs associated with online experimentation. This has the potential to accelerate progress in fields where human lives and safety are at stake, and to enable the development of more sophisticated and reliable autonomous systems. The present dissertation is concerned with the problem of off-policy evaluation (OPE), which constitutes a central challenge in offline reinforcement learning. Specifically, OPE aims to estimate the expected return of a target policy based solely on historical data. Prior works on OPE have predominantly relied on either importance sampling (IS) based methods or value-based estimators. However, IS-based methods, especially those based on trajectory, suffer from high and even unbounded variance, particularly in the case of infinite-horizon problems. Conversely, value-based estimators are susceptible to bias arising from model assumptions and the optimization process. These limitations have motivated a need for novel and improved methods of OPE in order to facilitate more accurate and reliable estimates of policy performance in offline learning scenarios. In order to address the variance issue associated with IS-based methods, we propose a novel estimator that estimates the density ratio of the stationary distribution of each transition pair, rather than the trajectory, and uses this estimate to evaluate the average return of a given target policy (in Chapter 3). This new density-based estimator is shown to break the curse of horizon and exhibits significantly lower variance in empirical tests. To mitigate the bias issue associated with value-based methods, we introduce a doubly robust estimator that combines both value-based and density-based estimators (in Chapter 4). By leveraging the strengths of each approach, the new estimator is able to reduce the overall bias and yield more accurate estimates. Importantly, our doubly robust estimator reveals a primal-dual connection between density-based and value-based estimators in an optimization framework. This connection not only provides insight into the underlying mechanisms of the two approaches but also offers potential avenues for further improvements in OPE methodology. Traditional approaches to OPE have primarily focused on point estimation. However, in high-stakes scenarios, it is equally important to provide decision-makers with the quantification of uncertainty. In the second part of this dissertation we investigate the problem of off-policy interval estimation, which involves providing high-confidence intervals for the expected return of a target policy based on historical data. However, similar to point estimation, traditional methods based on trajectory-wise importance sampling suffer from extremely large variance, which can result in imprecise and unreliable interval estimates. Our new approach to off-policy interval estimation is based on an optimization framework that we introduce in Chapter 4. We develop two distinct approaches for solving the interval estimation problem, each of which addresses the limitations of existing methods in different ways. The first approach(in Chapter 6) involves solving a constrained optimization problem in a Lipschitz function class using an iterative algorithm. This method yields monotonic tightening of deterministic upper and lower envelopes of the action value function, in the case of deterministic transitions. The second approach (in Chapter 7) is based on a functional Bellman loss function and imposes minimal assumptions on the data and function class of the Q-function. By leveraging this loss function, we are able to provide a tight confidence interval for the average value of a target policy in stochastic transition settings. Together, these two methods provide decision-makers with reliable and accurate interval estimates for the expected return of a target policy, enabling them to make more informed decisions in high-stakes scenarios.Computer Science