Using relative novelty to identify useful temporal abstractions in reinforcement learning

ABSTRACT

We present a new method for automatically creating useful temporal abstractions in reinforcement learning. We argue that states that allow the agent to transition to a different region of the state space are useful subgoals, and propose a method for identifying them using the concept of relative novelty. When such a state is identified, a temporally-extended activity (e.g., an option) is generated that takes the agent efficiently to this state. We illustrate the utility of the method in a number of tasks.

REFERENCES

• 1: Ronen I. Brafman , Moshe Tennenholtz, R-max - a general polynomial time algorithm for near-optimal reinforcement learning, The Journal of Machine Learning Research, 3, p.213-231, 3/1/2003 [doi>10.1162/153244303765208377]
• 2: Dietterich, T. G. (2000). Hierarchical reinforcement learning with the MAXQ value function decomposition. Journal of Artificial Intelligence Research, 13, 227--303.
• 3: Bruce L. Digney, Learning hierarchical control structures for multiple tasks and changing environments, Proceedings of the fifth international conference on simulation of adaptive behavior on From animals to animats 5, p.321-330, September 1998, Univ. of Zurich, Zurich, Switzerland
• 4: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 5: Bernhard Hengst, Discovering Hierarchy in Reinforcement Learning with HEXQ, Proceedings of the Nineteenth International Conference on Machine Learning, p.243-250, July 08-12, 2002
• 6: Kakade, S., & Dayan, P. (2001). Dopamine bonuses. Advances in Neural Information Processing Systems (pp. 131--137). MIT Press.
• 7: Michael J. Kearns , Satinder P. Singh, Near-Optimal Reinforcement Learning in Polynominal Time, Proceedings of the Fifteenth International Conference on Machine Learning, p.260-268, July 24-27, 1998
• 8: Long-Ji Lin, Self-Improving Reactive Agents Based on Reinforcement Learning, Planning and Teaching, Machine Learning, v.8 n.3-4, p.293-321, May 1992 [doi>10.1007/BF00992699]
• 9: Elizabeth Amy Mcgovern , Andrew G. Barto, Autonomous discovery of temporal abstractions from interaction with an environment, 2002
• 10: Amy McGovern , Andrew G. Barto, Automatic Discovery of Subgoals in Reinforcement Learning using Diverse Density, Proceedings of the Eighteenth International Conference on Machine Learning, p.361-368, June 28-July 01, 2001
• 11: Ishai Menache , Shie Mannor , Nahum Shimkin, Q-Cut - Dynamic Discovery of Sub-goals in Reinforcement Learning, Proceedings of the 13th European Conference on Machine Learning, p.295-306, August 19-23, 2002
• 12: Ronald Edward Parr , Stuart Russell, Hierarchical control and learning for markov decision processes, 1998
• 13: Ronald Parr , Stuart Russell, Reinforcement learning with hierarchies of machines, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.1043-1049, July 1998, Denver, Colorado, United States
• 14: Marc Pickett , Andrew G. Barto, PolicyBlocks: An Algorithm for Creating Useful Macro-Actions in Reinforcement Learning, Proceedings of the Nineteenth International Conference on Machine Learning, p.506-513, July 08-12, 2002
• 15: Doina Precup , Richard S. Sutton, Temporal abstraction in reinforcement learning, 2000
• 16: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 17: Richard S. Sutton , Doina Precup , Satinder Singh, Between MDPs and semi-MDPs: a framework for temporal abstraction in reinforcement learning, Artificial Intelligence, v.112 n.1-2, p.181-211, Aug. 1999 [doi>10.1016/S0004-3702(99)00052-1]
• 18: Thrun, S., & Schwartz, A. (1995). Finding structure in reinforcement learning. Advances in Neural Information Processing Systems (pp. 385--392). MIT Press.