Learning Near Optimal Policies with Low Inherent Bellman Error

Abstract

We study the exploration problem with approximate linear action-value functions in episodic reinforcement learning under the notion of low inherent Bellman error, a condition normally employed to show convergence of approximate value iteration. First we relate this condition to other common frameworks and show that it is strictly more general than the low rank (or linear) MDP assumption of prior work. Second we provide an algorithm with a high probability regret bound $\widetilde O(\sum_{t=1}^H d_t \sqrt{K} + \sum_{t=1}^H \sqrt{d_t} \IBE K)$ where $H$ is the horizon, $K$ is the number of episodes, $\IBE$ is the value if the inherent Bellman error and $d_t$ is the feature dimension at timestep $t$. In addition, we show that the result is unimprovable beyond constants and logs by showing a matching lower bound. This has two important consequences: 1) it shows that exploration is possible using only \emph{batch assumptions} with an algorithm that achieves the optimal statistical rate for the setting we consider, which is more general than prior work on low-rank MDPs 2) the lack of closedness (measured by the inherent Bellman error) is only amplified by $\sqrt{d_t}$ despite working in the online setting. Finally, the algorithm reduces to the celebrated \textsc{LinUCB} when $H=1$ but with a different choice of the exploration parameter that allows handling misspecified contextual linear bandits. While computational tractability questions remain open for the MDP setting, this enriches the class of MDPs with a linear representation for the action-value function where statistically efficient reinforcement learning is possible.

arXiv commentBug fixes in appendix; appears in ICML 2020

References in corpus (12)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Near-optimal Reinforcement Learning in Factored MDPs
• On the Sample Complexity of Reinforcement Learning with a Generative Model
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities
• Problem Dependent Reinforcement Learning Bounds Which Can Identify Bandit Structure in MDPs
• Low-rank Bandits with Latent Mixtures

Cited by in corpus (44)

• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Model Selection in Contextual Stochastic Bandit Problems
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Nonstationary Reinforcement Learning with Linear Function Approximation
• Regret Bound Balancing and Elimination for Model Selection in Bandits and RL
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Reinforcement Learning with Function Approximation: From Linear to Nonlinear
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation
• Efficient Learning in Non-Stationary Linear Markov Decision Processes
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Representation Learning for Online and Offline RL in Low-rank MDPs
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Minimax Regret for Stochastic Shortest Path
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Towards General Function Approximation in Zero-Sum Markov Games
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
• On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function
• Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL
• Tractable contextual bandits beyond realizability
• Online Model Selection for Reinforcement Learning with Function Approximation
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Efficient Local Planning with Linear Function Approximation
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation
• Improved Algorithms for Misspecified Linear Markov Decision Processes
• Variance-Aware Off-Policy Evaluation with Linear Function Approximation
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP