Instance-dependent $\ell_\infty$-bounds for policy evaluation in tabular reinforcement learning

2019-09-19 · Ashwin Pananjady, Martin J. Wainwright

Markov reward processes (MRPs) are used to model stochastic phenomena arising in operations research, control engineering, robotics, and artificial intelligence, as well as communication and transportation networks. In many of these cases, such as in the policy evaluation problem encountered in reinforcement learning, the goal is to estimate the long-term value function of such a process without access to the underlying population transition and reward functions. Working with samples generated under the synchronous model, we study the problem of estimating the value function of an infinite-horizon, discounted MRP on finitely many states in the $\ell_\infty$-norm. We analyze both the standard plug-in approach to this problem and a more robust variant, and establish non-asymptotic bounds that depend on the (unknown) problem instance, as well as data-dependent bounds that can be evaluated based on the observations of state-transitions and rewards. We show that these approaches are minimax-optimal up to constant factors over natural sub-classes of MRPs. Our analysis makes use of a leave-one-out decoupling argument tailored to the policy evaluation problem, one which may be of independent interest.

📄 PDF Abstract BibTeX arXiv:1909.08749

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis

2020-03-16 · Koulik Khamaru, Ashwin Pananjady, Feng Ruan, Martin J. Wainwright 외

We address the problem of policy evaluation in discounted Markov decision processes, and provide instance-dependent guarantees on the $\ell_\infty$-error under a generative model. We establish both asymptotic and non-asy…

The Optimal Approximation Factors in Misspecified Off-Policy Value Function Estimation

2023-07-25 · Philip Amortila, Nan Jiang, Csaba Szepesvári

Theoretical guarantees in reinforcement learning (RL) are known to suffer multiplicative blow-up factors with respect to the misspecification error of function approximation. Yet, the nature of such \emph{approximation f…

Off-policy evaluation Reinforcement Learning (RL)

Data-dependent Generalization Bounds for Multi-class Classification

2017-06-29 · Yunwen Lei, Urun Dogan, Ding-Xuan Zhou, Marius Kloft

In this paper, we study data-dependent generalization error bounds exhibiting a mild dependency on the number of classes, making them suitable for multi-class learning with a large number of label classes. The bounds gen…

Classification General Classification Generalization Bounds Multi-class Classification

Accelerated and instance-optimal policy evaluation with linear function approximation

2021-12-24 · Tianjiao Li, Guanghui Lan, Ashwin Pananjady

We study the problem of policy evaluation with linear function approximation and present efficient and practical algorithms that come with strong optimality guarantees. We begin by proving lower bounds that establish bas…

Best Arm Identification in Restless Markov Multi-Armed Bandits

2022-03-29 · P. N. Karthik, Kota Srinivas Reddy, Vincent Y. F. Tan

We study the problem of identifying the best arm in a multi-armed bandit environment when each arm is a time-homogeneous and ergodic discrete-time Markov process on a common, finite state space. The state evolution on ea…

Multi-Armed Bandits