2017

Near Optimal Behavior via Approximate State Abstraction

Abel, David, Hershkowitz, D. Ellis, Littman, Michael L.

Understand

The combinatorial explosion that plagues planning and reinforcement learning (RL) algorithms can be moderated using state abstraction.

Prohibitively large task representations can be condensed such that essential information is preserved, and consequently, solutions are tractably computable.
However, exact abstractions, which treat only fully-identical situations as equivalent, fail to present opportunities for abstraction in environments where no two situations are exactly alike.
In this work, we investigate approximate state abstractions, which treat nearly-identical situations as equivalent.

Built on

The complexity of Markov decision processes
Christos H Papadimitriou and John N Tsitsiklis · 1987
Earlier work this paper cites.
Feudal Reinforcement Learning
Peter Dayan and Geoffrey Hinton · 1993
Earlier work this paper cites.
On the complexity of solving Markov decision problems
Michael L Littman, Thomas L Dean, and Leslie Pack Kaelbling · 1995
Earlier work this paper cites.
Artificial Intelligence A Modern Approach
Stuart Russell and Peter Norvig · 1995
Earlier work this paper cites.
Reinforcement learning: A survey
Leslie Pack Kaelbling, Michael L Littman, and Andrew W Moore · 1996
Earlier work this paper cites.
Model minimization in markov decision processes
Thomas Dean and Robert Givan · 1997
Earlier work this paper cites.
Model reduction techniques for computing approximately optimal solutions for markov decision processes
Thomas Dean, Robert Givan, and Sonia Leach · 1997
Earlier work this paper cites.
Abstraction and approximate decision-theoretic planning
Richard Dearden and Craig Boutilier · 1997
Earlier work this paper cites.
Bayesian Q-learning
Richard Dearden, Nir Friedman, and Stuart Russell · 1998
Earlier work this paper cites.
Reinforcement Learning: An Introduction
Richard S Sutton and Andrew G Barto · 1998
Earlier work this paper cites.
Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning
Richard S Sutton, Doina Precup, and Satinder Singh · 1999
Earlier work this paper cites.
Hierarchical reinforcement learning with the MAXQ value function decomposition
Thomas G Dietterich · 2000
Earlier work this paper cites.

Similar

State abstraction for programmable reinforcement learning agents
David Andre and Stuart J Russell · 2002
Cited alongside, same era.
Recent advances in hierarchical reinforcement learning
Andrew G Barto and Sridhar Mahadevan · 2003
Cited alongside, same era.
Approximate equivalence of Markov decision processes
Eyal Even-Dar and Yishay Mansour · 2003
Cited alongside, same era.
Hierarchical reinforcement learning based on subgoal discovery and subpolicy specialization
Bram Bakker and Jürgen Schmidhuber · 2004
Cited alongside, same era.
Metrics for finite markov decision processes
Norm Ferns, Prakash Panangaden, and Doina Precup · 2004
Cited alongside, same era.
State abstraction discovery from irrelevant state variables
Nicholas K Jong and Peter Stone · 2005
Cited alongside, same era.
Methods for computing state similarity in markov decision processes
Norman Ferns, Pablo Samuel Castro, Doina Precup, and Prakash Panangaden · 2006
Cited alongside, same era.
Bandit based monte-carlo planning
Levente Kocsis and Csaba Szepesvári · 2006
Cited alongside, same era.
Towards a unified theory of state abstraction for mdps
Lihong Li, Thomas J Walsh, and Michael L Littman · 2006
Cited alongside, same era.
Transferring state abstractions between mdps
Thomas J Walsh, Lihong Li, and Michael L Littman · 2006
Cited alongside, same era.
Graphstream: A tool for bridging the gap between complex systems and dynamic graphs
Original
Yoann Pigné, Antoine Dutot, Frédéric Guinand, and Damien Olivier · 2008
Cited alongside, same era.

Then

Near-optimal regret bounds for reinforcement learning
Peter Auer, Thomas Jaksch, and Ronald Ortner · 2009
Later among the works it cites.
Reinforcement Learning in Finite MDPs : PAC Analysis
Alexander L. Strehl, Lihong Li, and Michael L. Littman · 2009
Later among the works it cites.
Dynamic programming aggregation
James C Bean, John R Birge, and Robert L Smith · 2011
Later among the works it cites.
Adaptive aggregation for reinforcement learning in average reward Markov decision processes
Ronald Ortner · 2013
Later among the works it cites.
State Aggregation in Monte Carlo Tree Search
Jesse Hostetler, Alan Fern, and Tom Dietterich · 2014
Later among the works it cites.
Extreme state aggregation beyond mdps
Marcus Hutter · 2014
Later among the works it cites.
Improving uct planning via approximate homomorphisms
Nan Jiang, Satinder Singh, and Richard Lewis · 2014
Later among the works it cites.
Goal-based action priors
David Abel, David Ellis Hershkowitz, Gabriel Barth-Maron, Stephen Brawner, Kevin O’Farrell, James MacGlashan, and Stefanie Tellex · 2015
Later among the works it cites.
Abstraction Selection in Model-Based Reinforcement Learning
Nan Jiang · 2015
Later among the works it cites.
Extreme state aggregation beyond markov decision processes
Marcus Hutter · 2016
Later among the works it cites.
Efficient bayesian clustering for reinforcement learning
Travis Mandel, Yun-En Liu, Emma Brunskill, and Zoran Popovic · 2016
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…