Near-optimal Reinforcement Learning in Factored MDPs

By Ian Osband, Benjamin Van Roy. 2014

138 citations recorded by the source corpus.

Any reinforcement learning algorithm that applies to all Markov decision processes (MDPs) will suffer Ω(SAT) regret on some MDP, where T is the elapsed time and S and A are the cardinalities of the state and action spaces. This implies T = Ω(SA) time to guarantee a near-optimal policy. In many settings of practical interest, due to the curse of dimensionality, S and A can be so enormous that this learning time is unacceptable. We establish that, if the system is known to be a factored MDP, it is possible to achieve regret that scales polynomially in the number of parameters encoding the factored MDP, which may be exponentially smaller than S or A. We provide two algorithms that satisfy near-optimal regret bounds in this context: posterior sampling reinforcement learning PSRL) and an upper confidence bound algorithm (UCRL-Factored).

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

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

In Reinforcement Learning

Citations in the corpus

Reinforcement Learning in Healthcare: A Survey (2019, methodology): “A large number of methods has been proposed to employ factored representation of MDP models for improving learning efficiency for either model-based [60], [61] or model-free RL problems [62].”
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): “[50] Osband, I.”
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.”
Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches (2018, methodology): “For factored MDPs, all prior sample-efﬁcient algorithms are model-based (Kearns and Koller, 1999; Osband and Van Roy, 2014b).”
Off-policy Model-based Learning under Unknown Factored Dynamics (2015, background): “(Osband & Van Roy, 2014) Let Y ( i ) be a set of variables indexed by i ∈ and Pr 1 , Pr 2 be two factorized probability distributions over Y : Then Lemma 4.”
Near-Optimal Reinforcement Learning in Dynamic Treatment Regimes (2019, methodology): “Variations of this setting include multi-armed bandits [1], partially-observable MDP [10, 2], and factored MDPs [22].”
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.”
The Bottleneck Simulator: A Model-based Deep Reinforcement Learning Approach (2018, background): “…MDP (for example, by factorizing the state transition model) has also been investigated extensively in the literature (Boutilier et al., 1999; Degris et al., 2006; Strehl et al., 2007; Ross & Pineau, 2008; Bellemare et al., 2013; Wu et al., 2014; Osband & Van Roy, 2014; Hallak et al., 2015).”