Efficient Reinforcement Learning in Factored MDPs

By Michael Kearns, Daphne Koller. 1999

How researchers see this paper

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

In Reinforcement Learning

Citations in the corpus

Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “These cases can be formalized through the Factored MDP assumption (Kearns and Koller, 1999; Boutilier, Dearden, and Goldszmidt, 2000): Definition 7 (Factored MDP Assumption): Each state is composed of n factors s := s1, s2, ..., sn ∈ S ⊆ S1 × S2 × ... × Sn and each action can be composed of m…”
Generalization and Exploration via Randomized Value Functions (2014, background): “To the best of our knowledge, this paper is the first to propose exploration schemes that randomly perturb value functions for reinforcement learning problems with value function generalization.”
Deep Exploration via Randomized Value Functions (2017, background): “Model learning algorithms exploit generalization in an underlying model of the environment (Kearns and Koller, 1999; AbbasiYadkori and Szepesvári, 2011; Ibrahimi et al., 2012; Ortner and Ryabko, 2012; Osband and Van Roy, 2014a,b; Gopalan and Mannor, 2015).”
Near-optimal Reinforcement Learning in Factored MDPs (2014, background): “M L ] 1 5 M ar 2 Any learning algorithm over Markov decision processes (MDPs) will have worst-case regret Ω( √”
On Oracle-Efficient PAC RL with Rich Observations (2018, neutral): “[24] Michael Kearns and Daphne Koller.”
Algorithm-Directed Exploration for Model-Based Reinforcement Learning in Factored MDPs (2002, methodology): “Furthermore, one can add new linear constraints to the linear program and the objective cannot decrease.”
A unifying framework for computational reinforcement learning theory (2009, methodology): “This insight can be used to derive the factored-state-MDP learning algorithm proposed by Kearns and Koller [1999].”
Efficient Exploration and Value Function Generalization in Deterministic Systems (2013, methodology): “An algorithm is proposed in [12] that fits a factored model to observed data and makes decisions based on the fitted model.”
Learning Approximate Stochastic Transition Models (2017, background): “It can also be captured by a dynamic Bayesian network (Kearns and Koller 1999; Degris, Sigaud, and Wuillemin 2006).”
Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models (2015, methodology): “Many of the pioneering algorithms in this area, such as R − Max [8] and E 3 [9], achieve efﬁcient exploration that scales polynomially with the number of parameters in the agent’s state space (see also [10, 11]).”
Reinforcement Learning: Theory and Algorithms (2019, background): “(Azar et al. [2013]) There exists (cid:15) 0 , δ 0 , c and a set of MDPs M such that for (cid:15) ∈ (0 , (cid:15) 0 ) and δ ∈ (0 , δ 0 ) if algorithm A is ( (cid:15), δ ) -good on all M ∈ M , then A must use a number of samples that is lower bounded as follows”
Learning and Using Models (2012, methodology): “The DBN-E(3) algorithm (Kearns and Koller, 1999) extends the E(3) algorithm to factored domains where the structure of the DBNmodel is known.”
An Application of Reinforcement Learning to Aerobatic Helicopter Flight (2006, background): “1 Data Collection TheE(3)-family of algorithms [12] and its extensions [11, 7, 10] are the state of the art RL algorithms for autonomous data collection.”
Off-policy Model-based Learning under Unknown Factored Dynamics (2015, background): “Early works assumed the dependency structure is known (Guestrin et al., 2002; Kearns & Koller, 1999).”
Provable Rich Observation Reinforcement Learning with Combinatorial Latent States (2021, methodology): “Two MDPs.”