Instance-dependent ${\ell }_{\infty }$-bounds for policy evaluation in tabular reinforcement learning

Abstract

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.

Version v2 is consistent with manuscript to appear in IEEE Transactions on Information Theory

References in corpus (9)

• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Minimax Regret Bounds for Reinforcement Learning
• Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
• Variance-reduced $Q$-learning is minimax optimal
• Fastest Convergence for Q-learning
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Stochastic approximation with cone-contractive operators: Sharp ${\ell }_{\infty }$-bounds for $Q$-learning
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes

Cited by in corpus (5)

• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium