Tree Based Discretization for Continuous State Space Reinforcement Learning

By William T. B. Uther, Manuela M. Veloso. 1998

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

Conservative Q-Improvement: Reinforcement Learning for an Interpretable Decision-Tree Policy (2019, methodology): “The UTree algorithm [McCallum and Ballard, 1996; Uther and Veloso, 1998] learns a tree, starting with a single abstract state and then continually splitting as appropriate (based on a splitting criterion), ending when a stopping criterion is reached.”
Toward Interpretable Deep Reinforcement Learning with Linear Model U-Trees (2018, methodology): “eveloped as an online reinforcement learning algorithm with a tree structure representation. A U-tree takes a set of observed feature/action values as input and maps it to a state value (or Q-value). [20] introduces the continuous Utree (CUT) for continuous state features. CUT learning dynamically g”
Non-parametric policy gradients: a unified treatment of propositional and relational domains (2008, methodology): “In this sense, it is akin to tree-based state discretization RL approaches such as (Chapman & Kaelbling, 1991; Mc-Callum, 1996; Uther & Veloso, 1998) and related approaches.”
CAQL: Continuous Action Q-Learning (2019, methodology): “…Bellman residual loss using global nonlinear optimizers, such as the cross-entropy method (CEM) for QT-Opt (Kalash-nikov et al., 2018), gradient ascent (GA) for actor-expert (Lim et al., 2018), and action discretization (Uther & Veloso, 1998; Smart & Kaelbling, 2000; Lazaric et al., 2008).”
Closed-Loop Learning of Visual Control Policies (2011, unknown): “RLVC is defined independently of any fixed RL algorithm, which is similar in spirit to Continuous U-Tree (Uther & Veloso, 1998), with the major exception that RLVC deals with Boolean features, whereas Continuous U-Tree works in a continuous input space.”
Tree based hierarchical reinforcement learning (2002, methodology): “The second group of automatic state abstraction techniques are known as regression tree techniques (Breiman et al., 1984; Quinlan, 1992; Chapman and Kaelbling, 1991; McCallum, 1995; Uther and Veloso, 1998).”
Reinforcement Learning with Decision Trees (2003, background): “Also, the rate of learning would be very slow, since each table entry must be visited many times before the approximation becomes accurate.”
Policy Tree: Adaptive Representation for Policy Gradient (2015, methodology): “Future work could deal with better ways to handle continuous features, similar to the Continuous U-Tree algorithm (Uther and Veloso 1998).”
Explainable Reinforcement Learning: A Survey (2020, unknown): “e, but complex model by mimicking the model’s Q-function using Linear Model UTrees (LMUTs). LMUTs are an extension of Continuous U-Trees (CUTs) which were developed to approximatecontinuous functions [60]. The diﬀerence between CUTs and LMUTs is that, instead of constants, LMUTs have a linear model ”
Decision Tree Function Approximation in Reinforcement Learning (1999, unknown): “Our work is very similar to the U Tree algorithm , but we explore some alternative metrics for determining when and where to subdivide the space and we analyze performance in different domains.”
Tree-Based Batch Mode Reinforcement Learning (2005, unknown): “Several authors who adapted regression trees in other ways to reinforcement learning have suggested the use of other score criteria for example based on the violation of the Markov assumption (McCallum, 1996; Uther and Veloso, 1998) or on the combination of several error terms like the supervised, t”
Improved Regret Bounds for Undiscounted Continuous Reinforcement Learning (2015, background): “While most of this work is purely experimental [12, 24], there are also some contributions with theoretical guarantees.”
TTree: Tree-Based State Generalization with Temporally Abstract Actions (2002, methodology): “Some previous state abstraction algorithms [2, 3] have generated data in a manner similar to TTree, but using single transitions rather than trajectories.”
Dynamic Programming for Structured Continuous Markov Decision Problems (2004, methodology): “In the RL literature we find approaches such as U-trees (Uther & Veloso 1998) which learns a tree-based representation of a continuous value function similar to ours.”
Extending Q-Learning to General Adaptive Multi-Agent Systems (2003, background): “Several recent function approximation schemes [11, 12] enable Q-learning to work well in continuous spaces.”
The Lumberjack Algorithm for Learning Linked Decision Forests (2000, methodology): “Most importantly as far as the authors are concerned, the algorithm is not incremental and so cannot be transferred to RL using the techniques of (Chapman and Kaelbling 1991; McCallum 1995; Uther and Veloso 1998) (see Hoey et al. (1999) for the application of OBDDs to RL).”