Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation

• URL: http://arxiv.org/abs/2002.09516v1
• Date: Fri, 21 Feb 2020 19:20:57 GMT
• Title: Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation
• Authors: Yaqi Duan, Mengdi Wang
• Abstract summary: This paper studies the statistical theory of batch data reinforcement learning with function approximation. Consider the off-policy evaluation problem, which is to estimate the cumulative value of a new target policy from logged history.
• Score: 49.502277468627035
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the statistical theory of batch data reinforcement learning with function approximation. Consider the off-policy evaluation problem, which is to estimate the cumulative value of a new target policy from logged history generated by unknown behavioral policies. We study a regression-based fitted Q iteration method, and show that it is equivalent to a model-based method that estimates a conditional mean embedding of the transition operator. We prove that this method is information-theoretically optimal and has nearly minimal estimation error. In particular, by leveraging contraction property of Markov processes and martingale concentration, we establish a finite-sample instance-dependent error upper bound and a nearly-matching minimax lower bound. The policy evaluation error depends sharply on a restricted $\chi^2$-divergence over the function class between the long-term distribution of the target policy and the distribution of past data. This restricted $\chi^2$-divergence is both instance-dependent and function-class-dependent. It characterizes the statistical limit of off-policy evaluation. Further, we provide an easily computable confidence bound for the policy evaluator, which may be useful for optimistic planning and safe policy improvement.

Related papers

• Policy Gradient with Active Importance Sampling [55.112959067035916]
  Policy gradient (PG) methods significantly benefit from IS, enabling the effective reuse of previously collected samples. However, IS is employed in RL as a passive tool for re-weighting historical samples. We look for the best behavioral policy from which to collect samples to reduce the policy gradient variance.
  arXiv  Detail & Related papers  (2024-05-09T09:08:09Z)
• Bi-Level Offline Policy Optimization with Limited Exploration [1.8130068086063336]
  We study offline reinforcement learning (RL) which seeks to learn a good policy based on a fixed, pre-collected dataset. We propose a bi-level structured policy optimization algorithm that models a hierarchical interaction between the policy (upper-level) and the value function (lower-level) We evaluate our model using a blend of synthetic, benchmark, and real-world datasets for offline RL, showing that it performs competitively with state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-10-10T02:45:50Z)
• Variance-Aware Off-Policy Evaluation with Linear Function Approximation [85.75516599931632]
  We study the off-policy evaluation problem in reinforcement learning with linear function approximation. We propose an algorithm, VA-OPE, which uses the estimated variance of the value function to reweight the Bellman residual in Fitted Q-Iteration.
  arXiv  Detail & Related papers  (2021-06-22T17:58:46Z)
• Minimax Off-Policy Evaluation for Multi-Armed Bandits [58.7013651350436]
  We study the problem of off-policy evaluation in the multi-armed bandit model with bounded rewards. We develop minimax rate-optimal procedures under three settings.
  arXiv  Detail & Related papers  (2021-01-19T18:55:29Z)
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient [62.24615324523435]
  This paper provides a statistical analysis of high-dimensional batch Reinforcement Learning (RL) using sparse linear function approximation. When there is a large number of candidate features, our result sheds light on the fact that sparsity-aware methods can make batch RL more sample efficient.
  arXiv  Detail & Related papers  (2020-11-08T16:48:02Z)
• Accountable Off-Policy Evaluation With Kernel Bellman Statistics [29.14119984573459]
  We consider off-policy evaluation (OPE), which evaluates the performance of a new policy from observed data collected from previous experiments. Due to the limited information from off-policy data, it is highly desirable to construct rigorous confidence intervals, not just point estimation. We propose a new variational framework which reduces the problem of calculating tight confidence bounds in OPE.
  arXiv  Detail & Related papers  (2020-08-15T07:24:38Z)
• Doubly Robust Off-Policy Value and Gradient Estimation for Deterministic Policies [80.42316902296832]
  We study the estimation of policy value and gradient of a deterministic policy from off-policy data when actions are continuous. In this setting, standard importance sampling and doubly robust estimators for policy value and gradient fail because the density ratio does not exist. We propose several new doubly robust estimators based on different kernelization approaches.
  arXiv  Detail & Related papers  (2020-06-06T15:52:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.