Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning

2020-01-29 · Ming Yin, Yu-Xiang Wang

We consider the problem of off-policy evaluation for reinforcement learning, where the goal is to estimate the expected reward of a target policy $\pi$ using offline data collected by running a logging policy $\mu$. Standard importance-sampling based approaches for this problem suffer from a variance that scales exponentially with time horizon $H$, which motivates a splurge of recent interest in alternatives that break the "Curse of Horizon" (Liu et al. 2018, Xie et al. 2019). In particular, it was shown that a marginalized importance sampling (MIS) approach can be used to achieve an estimation error of order $O(H^3/ n)$ in mean square error (MSE) under an episodic Markov Decision Process model with finite states and potentially infinite actions. The MSE bound however is still a factor of $H$ away from a Cramer-Rao lower bound of order $\Omega(H^2/n)$. In this paper, we prove that with a simple modification to the MIS estimator, we can asymptotically attain the Cramer-Rao lower bound, provided that the action space is finite. We also provide a general method for constructing MIS estimators with high-probability error bounds.

📄 PDF Abstract BibTeX arXiv:2001.10742

Code (0)

등록된 구현이 없습니다.

Tasks

Off-policy evaluationreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Bootstrapping Fitted Q-Evaluation for Off-Policy Inference

2021-02-06 · Botao Hao, Xiang Ji, Yaqi Duan, Hao Lu 외

Bootstrapping provides a flexible and effective approach for assessing the quality of batch reinforcement learning, yet its theoretical property is less understood. In this paper, we study the use of bootstrapping in off…

Off-policy evaluation

Optimal variance-reduced stochastic approximation in Banach spaces

2022-01-21 · Wenlong Mou, Koulik Khamaru, Martin J. Wainwright, Peter L. Bartlett 외

We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. Focusing on a stochastic query model that provides noisy evaluations of the operator, we analyze a varianc…

Q-Learning

Policy Gradient Method For Robust Reinforcement Learning

2022-05-15 · Yue Wang, Shaofeng Zou

This paper develops the first policy gradient method with global optimality guarantee and complexity analysis for robust reinforcement learning under model mismatch. Robust reinforcement learning is to learn a policy rob…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Lagrangian Index Policy for Restless Bandits with Average Reward

2024-12-17 · Konstantin Avrachenkov, Vivek S. Borkar, Pratik Shah

We study the Lagrange Index Policy (LIP) for restless multi-armed bandits with long-run average reward. In particular, we compare the performance of LIP with the performance of the Whittle Index Policy (WIP), both heuris…

Multi-Armed Bandits reinforcement-learning Reinforcement Learning

Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theory

2022-02-10 · Ruiqi Zhang, Xuezhou Zhang, Chengzhuo Ni, Mengdi Wang

Off-Policy Evaluation (OPE) serves as one of the cornerstones in Reinforcement Learning (RL). Fitted Q Evaluation (FQE) with various function approximators, especially deep neural networks, has gained practical success. …

Off-policy evaluation Reinforcement Learning (RL)