Efficient Structure Learning in Factored-State MDPs

By Alexander L. Strehl, Carlos Diuk, Michael L. Littman. 2007

144 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Near-optimal Reinforcement Learning in Factored MDPs (2014, background): “Some algorithms do seek to learn this structure from experience [10], but we will assume this structure is known.”
Article in Press Information and Computation Models of Active Learning in Group-structured State Spaces a R T I C L E I N F O a B S T R a C T (unknown): “It is known that when the sensations (i.e., the representations of states) are vectors, predictive models can be learned efficiently even for stochastic environments provided that the environments' dynamics can be represented as a Bayes net in the form of a bounded depth decision tree, see Strehl et”
Autonomous Agents and Multi-agent Systems Manuscript No. Learning Potential Functions and Their Representations for Multi-task Reinforcement Learning (unknown): “The binary stock-trading domain is an attractive domain for comparison since it is an established benchmark [13,37,71], is stochastic, and has an easily varied number of states and”
Provable Rich Observation Reinforcement Learning with Combinatorial Latent States (2021, background): “Two MDPs.”
Hierarchical Approaches (2012, background): “Strehl et al (2007) learn dynamic Bayesian network (DBN) structures as part of the reinforcement learning process using a factored state representation.”
Learning and Using Models (2012, methodology): “With probability at least 1 − δ , the SLF-R-MAX algorithm's policy is ε-optimal except for at most k time steps, where: k = O n 3+2D ADln( nA δ )ln( 1 δ )ln( 1 ε(1−γ) ) ε 3 (1 − γ) 6 Here, n is the number of factors in the domain, D is the maximum in-degree in the DBN, and γ is the discount factor.”
Exploring compact reinforcement-learning representations with linear regression (2009, methodology): “We carried out reward-learning experiments on the Stocks domain [14], with 3 sectors and 2 stocks per sector.”
Reinforcement Learning in Finite MDPs: PAC Analysis (2009, methodology): “The analysis techniques are general and have proven useful in analyzing other related algorithms (Asmuth et al., 2008; Brunskill et al., 2008; Leffler et al., 2007; Strehl et al., 2007; Strehl and Littman, 2008a).”
Knows what it knows: a framework for self-aware learning (2008, background): “… algorithms that have polynomial sample complexity guarantees (Kearns & Singh, 2002; Kearns & Koller, 1999; Kakade et al., 2003; Strehl et al., 2007) lies the idea of distinguishing between instances that have been learned with su.cient accuracy and those whose…”
Sample Complexity Bounds of Exploration (2012, methodology): “…beyond ﬁnite MDPs. Examples include various rich classes of prob-26 lems like factored-state MDPs (Guestrin et al, 2002; Kearns and Koller, 1999; Strehl et al, 2007; Diuk et al, 2009), continuous-state MDPs (Strehl and Littman, 2008b; Brunskill et al, 2009), and relational MDPs (Walsh, 2010).”
AdaRL: What, Where, and How to Adapt in Transfer Reinforcement Learning (2021, methodology): “This representation is related to Factored MDPs (Kearns and Koller, 1999; Boutilier et al., 2000; Strehl et al., 2007) and Factored POMDPs (Katt et al.”
Exploiting structure and utilizing agent-centric rewards to promote coordination in large multiagent systems (2013, methodology): “This work focuses on decomposing a large MDP with a system reward into several smaller joint MDPs or Factored MDPs with localized rewards [3, 5].”
Safe Policy Improvement with Baseline Bootstrapping in Factored Environments (2019, methodology): “Factored RL algorithms can have a sample complexity that scales only polynomially in the number parameters of the FMDP (Kearns and Koller 1999; Guestrin, Patrascu, and Schuurmans 2002; Strehl 2007).”
A unifying framework for computational reinforcement learning theory (2009, background): “They always exist for finite MDPs, and also exist under certain technical assumptions for MDPs with infinite (either discrete or continuous) state or action spaces [Bertsekas and Shreve 1996; Puterman 1994].”
Off-policy Model-based Learning under Unknown Factored Dynamics (2015, methodology): “SLF-Rmax (Strehl et al., 2007), Met-Rmax (Diuk et al., 2009) and LSE-Rmax (Chakraborty & Stone, 2011) are algorithms for learning the complete structure.”
An object-oriented representation for efficient reinforcement learning (2008, unknown): “This worst-case bound can be guaranteed by a variant of SLF-Rmax, an algorithm introduced by Strehl et al. (2007).”
Generalized model learning for Reinforcement Learning on a humanoid robot (2010, background): “Looking at subsets of features allows SLF-RMAX to perform less exploration than R-MAX, but keeping counters for all possible combinations of input features is very computationally expensive.”