Model-based Reinforcement Learning and the Eluder Dimension

By Ian Osband, Benjamin Van Roy. 2014

206 citations recorded by the source corpus.

We consider the problem of learning to optimize an unknown Markov decision process (MDP). We show that, if the MDP can be parameterized within some known function class, we can obtain regret bounds that scale with the dimensionality, rather than cardinality, of the system. We characterize this dependence explicitly as $\tilde{O}(\sqrt{d_K d_E T})$ where $T$ is time elapsed, $d_K$ is the Kolmogorov dimension and $d_E$ is the \emph{eluder dimension}. These represent the first unified regret bounds for model-based reinforcement learning and provide state of the art guarantees in several important settings. Moreover, we present a simple and computationally efficient algorithm \emph{posterior sampling for reinforcement learning} (PSRL) that satisfies these bounds.

Subfields: Artificial Intelligence, Management Science and Operations Research

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 Management Science and Operations Research

Citations in the corpus

Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, background): “Inefficient exploration strategies will take Ω(2 ) episodes to learn the optimal policy (Osband et al., 2014).”
Deep Exploration via Bootstrapped DQN (2016, background): “Surprisingly, this algorithm recovers state of the art guarantees in the setting with tabular basis functions, but its performance is crucially dependent upon a suitable linear representation of the value function (Osband et al., 2014).”
Generalization and Exploration via Randomized Value Functions (2014, methodology): “Our experiments focus on learning over episodes of a finite-horizon Markov decision process and use a version of RLSVI designed for that task, but we also propose a version of RLSVI that addresses continual learning in an infinite-horizon discounted Markov decision process.”
Efficient Exploration Through Bayesian Deep Q-Networks (2018, background): “[49] Osband, I.”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, neutral): “Exploration in this class of problems has been previously considered by Osband and Van Roy [2014].”
Deep Exploration via Randomized Value Functions (2017, background): “There is work on model learning algorithms [20, 21, 22, 8, 23, 24, 25, 26], which apply to specific model classes and become statistically or computationally intractable for problems of practical scale.”
On Oracle-Efficient PAC RL with Rich Observations (2018, background): “Moreover, their analysis measures representation complexity using eluder dimension [29, 30], which is only known to be small for some simple function classes.”
Bootstrapped Thompson Sampling and Deep Exploration (2015, background): “Of those algorithms which do combine generalization with exploration, many require an intractable model-based planning step, or are restricted to unrealistic parametric domains [10, 11, 12].”
On the Optimality of Sparse Model-Based Planning for Markov Decision Processes (2019, background): “…reinforcement learning, and understanding it is essential to tackling even more complex challenges such as sample-efﬁcient exploration (see e.g. Kakade et al. (2003); Strehl et al. (2006); Strehl (2007); Jaksch et al. (2010); Osband and Van Roy (2014); Azar et al. (2017); Sidford et al. (2018b,a)).”
Regret Bounds for Kernel-Based Reinforcement Learning (2020, background): “[21] prove a Bayesian regret bound in terms of the eluder and Kolmogorov dimension, assuming access to an approximate MDP planner.”
Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds (2019, unknown): “• Regret bounds with value function approximation: (Osband & Roy, 2014) uses the Eluder dimension as a measure of the dimensionality of the problem and (Jiang et al., 2017) proposes the Bellman rank to measure the learning complexity, but such measures aim at capturing a different notion of…”
Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches (2018, background): “On the model-based side, Lattimore et al. (2013) and Osband and Van Roy (2014a) obtain sample complexity guarantees; the former makes no assumptions but the guarantee scales linearly with the model class size, and the latter makes continuity assumptions, so both results have more limited scope than…”
Thompson Sampling for Learning Parameterized Markov Decision Processes (2014, background): “Subsequent work (Osband and Van Roy, 2014; Osband and Roy, 2014) investigates more structured MDPs and develops Bayes regret bounds in terms of the eluder dimension.”