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 (7)

• On Lower Bounds for Regret in Reinforcement Learning
• Model-based Reinforcement Learning and the Eluder Dimension
• 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
• Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles

Cited by in corpus (4)

• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Information Theoretic Regret Bounds for Online Nonlinear Control