Model-Based Reinforcement Learning with Value-Targeted Regression

Abstract

This paper studies model-based reinforcement learning (RL) for regret minimization. We focus on finite-horizon episodic RL where the transition model $P$ belongs to a known family of models $\mathcal{P}$, a special case of which is when models in $\mathcal{P}$ take the form of linear mixtures: $P_{\theta }={\sum }_{i=1}^d{\theta }_i{P}_i$. We propose a model based RL algorithm that is based on optimism principle: In each episode, the set of models that are `consistent' with the data collected is constructed. The criterion of consistency is based on the total squared error of that the model incurs on the task of predicting \emph{values} as determined by the last value estimate along the transitions. The next value function is then chosen by solving the optimistic planning problem with the constructed set of models. We derive a bound on the regret, which, in the special case of linear mixtures, the regret bound takes the form $\tilde{\mathcal{O}}(d\sqrt{H^{3}T})$, where $H$, $T$ and $d$ are the horizon, total number of steps and dimension of $\theta$, respectively. In particular, this regret bound is independent of the total number of states or actions, and is close to a lower bound $\Omega (\sqrt{HdT})$. For a general model family $\mathcal{P}$, the regret bound is derived using the notion of the so-called Eluder dimension proposed by Russo & Van Roy (2014).

References in corpus (17)

• Playing Atari with Deep Reinforcement Learning
• Model-Based Reinforcement Learning for Atari
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Generalization and Exploration via Randomized Value Functions
• On Lower Bounds for Regret in Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Model-based Reinforcement Learning and the Eluder Dimension
• Minimax Regret Bounds for Reinforcement Learning
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Learning with Good Feature Representations in Bandits and in RL with a Generative Model
• Posterior Sampling for Large Scale Reinforcement Learning
• Policy Certificates: Towards Accountable Reinforcement Learning
• Worst-Case Regret Bounds for Exploration via Randomized Value Functions
• Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models
• Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles

Cited by in corpus (41)

• Deep Reinforcement Learning for Efficient Measurement of Quantum Devices
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Information Theoretic Regret Bounds for Online Nonlinear Control
• Is Pessimism Provably Efficient for Offline RL?
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• 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
• Provably Efficient Exploration in Policy Optimization
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Model-free Representation Learning and Exploration in Low-rank MDPs
• The Value Equivalence Principle for Model-Based Reinforcement Learning
• Robust Policy Gradient against Strong Data Corruption
• Adaptive Discretization for Model-Based Reinforcement Learning
• 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
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
• 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
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Thompson Sampling with a Mixture Prior
• Efficient Local Planning with Linear Function Approximation
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge
• Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation
• Improved Algorithms for Misspecified Linear Markov Decision Processes
• Logistic Q-Learning
• Variance-Aware Off-Policy Evaluation with Linear Function Approximation
• Gap-Dependent Bounds for Two-Player Markov Games
• Proper Value Equivalence