Model-Based Reinforcement Learning with Value-Targeted Regression

By Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, Lin F. Yang. Conference on Learning for Dynamics & Control, 2020

329 citations recorded by the source corpus.

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

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/175a9a3f0bb4f31fa235386aff52ad18c67275d3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

In Management Science and Operations Research

Citations in the corpus

Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation (2021, methodology): “Similar to UCRL-VTR proposed by [7, 3], UCRL-RFE also uses a “value-targeted regression (VTR)" estimator, which computes θk+1 as the minimizer to a ridge regression problem with the target being the past value functions.”
On Reward-Free Reinforcement Learning with Linear Function Approximation (2020, methodology): “An interesting future direction is to generalize our results to more general function classes using techniques, e.g., in [Wen and Van Roy, 2013, Ayoub et al., 2020, Wang et al., 2020].”
The Value Equivalence Principle for Model-Based Reinforcement Learning (2020, background): “[3] proposes an algorithm that keeps a set of models that are consistent with the most recent value function estimate.”
Provably efficient representation selection in Low-rank Markov Decision Processes: from online to offline RL (2021, methodology): “This difference arises from estimating the MDP parameter Mh,φ, which is similar to that in the UCRL-VTR algorithm [Ayoub et al., 2020] for learning linear mixture MDPs.”
Sample-Efficient Reinforcement Learning for POMDPs with Linear Function Approximations (2022, background): “…run e To our best knowledge, this is the ﬁrst sample complexity upper bound for POMDPs that is independent of the number of states and observations, and the order of ε is optimal even in the MDP setting (Ayoub et al., 2020), which is a special case of POMDPs. episodes of the POMDP to collect data.”
Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL (2020, background): “Other linear models recently considered include (Ayoub et al., 2020; Zhou et al., 2020) and when the Bellman equations are linearly representable up to a low-rank error (Jiang et al., 2017); although the focus of these works is online exploration, learning should be possible in the batch setting as…”
Provably Efficient Exploration in Policy Optimization (2019, methodology): “See (Ayoub et al., 2020; Zhou et al., 2020) for various examples of linear MDPs, including the one proposed by (Yang & Wang, 2019a).”
Is Pessimism Provably Efficient for Offline RL? (2020, background): “…for promoting exploration in online RL (Jaksch et al., 2010; Abbasi-Yadkori et al., 2011; Russo and Van Roy, 2013; Osband and Van Roy, 2014; Chowdhury and Gopalan, 2017; Azar et al., 2017; Jin et al., 2018; 2020; Cai et al., 2020; Yang et al., 2020b; Ayoub et al., 2020; Wang et al., 2020b).”