Input Generalization in Delayed Reinforcement Learning: An Algorithm and Performance Comparisons

By David Chapman, Leslie Pack Kaelbling. 1991

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 “G algorithm” [Chapman and Kaelbling, 1991] learns a decision tree incrementally as new examples are added.”
TTree: Tree-Based State Generalization with Temporally Abstract Actions (2002, result): “Some previous state abstraction algorithms [2, 3] have generated data in a manner similar to TTree, but using single transitions rather than trajectories.”
From pixels to policies: A bootstrapping agent (2008, unknown): “parti-game [24], U-Trees [20], G Algorithm [25]).”
Learning to Act Using Real-Time Dynamic Programming (1995, methodology): “For example, Chapman and Kaelbling [ 151 and Tan [76] adapt decisiontree methods, and Mahadevan and Connell [49] use a statistical clustering method.”
Stochastic dynamic programming with factored representations (2000, background): “Tree representations of policies are sometimes used in reinforcement learning as well [23], though in a somewhat different fashion.”
Reinforcement learning for closed-loop propofol anesthesia: a study in human volunteers (2014, background): “Q-learning is mathematically robust (Tsitsiklas and Van Roy, 1996; Dayan, 1992), and this robustness has contributed to the method's popularity in applied reinforcement learning.”
Speeding Up Relational Reinforcement Learning through the Use of an Incremental First Order Decision Tree Learner (2001, methodology): “We use a learning algorithm that is an extension of the G-algorithm [ 4 ].”
Planning, Learning and Coordination in Multiagent Decision Processes (1996, methodology): “Finally, we note that much research has been carried out in the RL community on generalization of learned values and action choices, as well as value function approximation (especially in continuous domains); see, for example, [22, 14, 38, 12, 36, 50].”
Closed-Loop Learning of Visual Control Policies (2011, unknown): “The idea of adaptive-resolution techniques in reinforcement learning goes back to the G Algorithm (Chapman & Kaelbling, 1991), and has inspired the other approaches that are discussed below.”
Tree Based Discretization for Continuous State Space Reinforcement Learning (1998, methodology): “The G algorithm ( Chapman & Kaelbling 1991 ) and the”
Reinforcement Learning: A Tutorial Survey and Recent Advances (2009, methodology): “Decision trees have also beed used for the same task, and the central idea underlying their use (Chapman and Kaelbling, 1991; Pyeatt and Howe, 1998) is to split the state space, via leaf nodes, into dissimilar grids, and the splitting depends on how often a part of the state space has been visited.”
Learning reactive and planning rules in a motivationally autonomous animat (1996, background): “Among the solutions that have been suggested to improve learning speed - like generalization procedures [12] or the use of an action model [47] - the most promising seem to be those that advocate a hierarchical organization of state transitions1, within which the propagation of reinforcement signals”
Integrating Guidance into Relational Reinforcement Learning (2004, methodology): “The TG-algorithm (Driessens, Ramon, and Blockeel, 2001) is an incremental first-order regression tree building algorithm that is based on the G-tree algorithm of Chapman and Kaelbling (Chapman and Kaelbling, 1991).”
Towards a Unified Theory of State Abstraction for MDPs (2006, methodology): “…policies; φ Q ∗ preserves the optimal state-action value function (e.g., stochastic dynamic programming with factored representations [3] or the G-algorithm [4]); φ a ∗ preserves the optimal action and its value (e.g., utile distinction [18]); and φ π ∗ attempts to preserve the optimal action [14].”
Reinforcement Learning with Decision Trees (2003, methodology): “The G-learning algorithm [6] uses a decision tree to generate a variable resolution discretization for a space with binary inputs.”
Decision-Theoretic Planning: Structural Assumptions and Computational Leverage (1999, methodology): “Decision trees have also been used for policies and value functions [22, 32].”