On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation

• URL: http://arxiv.org/abs/2402.14703v2
• Date: Thu, 03 Oct 2024 06:55:03 GMT
• Title: On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation
• Authors: Yuheng Zhang, Nan Jiang,
• Abstract summary: We develop estimators whose guarantee avoids exponential dependence on the horizon. In this paper, we discover novel coverage assumptions tailored to the structure of POMDPs. As a side product, our analyses also lead to the discovery of new algorithms with complementary properties.
• Score: 11.829110453985228
• License:
• Abstract: We study off-policy evaluation (OPE) in partially observable environments with complex observations, with the goal of developing estimators whose guarantee avoids exponential dependence on the horizon. While such estimators exist for MDPs and POMDPs can be converted to history-based MDPs, their estimation errors depend on the state-density ratio for MDPs which becomes history ratios after conversion, an exponential object. Recently, Uehara et al. [2022a] proposed future-dependent value functions as a promising framework to address this issue, where the guarantee for memoryless policies depends on the density ratio over the latent state space. However, it also depends on the boundedness of the future-dependent value function and other related quantities, which we show could be exponential-in-length and thus erasing the advantage of the method. In this paper, we discover novel coverage assumptions tailored to the structure of POMDPs, such as outcome coverage and belief coverage, which enable polynomial bounds on the aforementioned quantities. As a side product, our analyses also lead to the discovery of new algorithms with complementary properties.

Related papers

• RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation [73.2390735383842]
  We introduce the first sample-efficient algorithm for LMDPs without any additional structural assumptions. We show how these can be used to derive near-optimal guarantees of an optimistic exploration algorithm. These results can be valuable for a wide range of interactive learning problems beyond LMDPs, and especially, for partially observed environments.
  arXiv  Detail & Related papers  (2024-06-03T14:51:27Z)
• Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes [44.974100402600165]
  We study the evaluation of a policy best-parametric and worst-case perturbations to a decision process (MDP) We use transition observations from the original MDP, whether they are generated under the same or a different policy. Our estimator is also estimated statistical inference using Wald confidence intervals.
  arXiv  Detail & Related papers  (2024-03-29T18:11:49Z)
• Future-Dependent Value-Based Off-Policy Evaluation in POMDPs [67.21319339512699]
  We study off-policy evaluation (OPE) for partially observable MDPs (POMDPs) with general function approximation. We develop a novel model-free OPE method by introducing future-dependent value functions that take future proxies as inputs. We extend our methods to learning of dynamics and establish the connection between our approach and the well-known spectral learning methods in POMDPs.
  arXiv  Detail & Related papers  (2022-07-26T17:53:29Z)
• Robust and Adaptive Temporal-Difference Learning Using An Ensemble of Gaussian Processes [70.80716221080118]
  The paper takes a generative perspective on policy evaluation via temporal-difference (TD) learning. The OS-GPTD approach is developed to estimate the value function for a given policy by observing a sequence of state-reward pairs. To alleviate the limited expressiveness associated with a single fixed kernel, a weighted ensemble (E) of GP priors is employed to yield an alternative scheme.
  arXiv  Detail & Related papers  (2021-12-01T23:15:09Z)
• DP-SEP! Differentially Private Stochastic Expectation Propagation [6.662800021628275]
  We are interested in privatizing an approximate posterior inference algorithm called Expectation propagation (EP) EP approximates the posterior by iteratively refining approximations to the local likelihoods, and is known to provide better posterior uncertainties than those by variational inference (VI) To overcome this problem, expectation propagation (SEP) was proposed, which only considers a unique local factor that captures the average effect of each likelihood term to the posterior and refines it in a way analogous to EP.
  arXiv  Detail & Related papers  (2021-11-25T18:59:35Z)
• A Minimax Learning Approach to Off-Policy Evaluation in Partially Observable Markov Decision Processes [31.215206208622728]
  We consider off-policy evaluation (OPE) in Partially Observable Markov Decision Processes (POMDPs) Existing methods suffer from either a large bias in the presence of unmeasured confounders, or a large variance in settings with continuous or large observation/state spaces. We first propose novel identification methods for OPE in POMDPs with latent confounders, by introducing bridge functions that link the target policy's value and the observed data distribution.
  arXiv  Detail & Related papers  (2021-11-12T15:52:24Z)
• Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processes [65.91730154730905]
  In applications of offline reinforcement learning to observational data, such as in healthcare or education, a general concern is that observed actions might be affected by unobserved factors. Here we tackle this by considering off-policy evaluation in a partially observed Markov decision process (POMDP) We extend the framework of proximal causal inference to our POMDP setting, providing a variety of settings where identification is made possible.
  arXiv  Detail & Related papers  (2021-10-28T17:46:14Z)
• 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)
• Universal Off-Policy Evaluation [64.02853483874334]
  We take the first steps towards a universal off-policy estimator (UnO) We use UnO for estimating and simultaneously bounding the mean, variance, quantiles/median, inter-quantile range, CVaR, and the entire cumulative distribution of returns.
  arXiv  Detail & Related papers  (2021-04-26T18:54:31Z)

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.