Dynamic abstraction in reinforcement learning via clustering

ABSTRACT

We consider a graph theoretic approach for automatic construction of options in a dynamic environment. A map of the environment is generated on-line by the learning agent, representing the topological structure of the state transitions. A clustering algorithm is then used to partition the state space to different regions. Policies for reaching the different parts of the space are separately learned and added to the model in a form of options (macro-actions). The options are used for accelerating the Q-Learning algorithm. We extend the basic algorithm and consider building a map that includes preliminary indication of the location of "interesting" regions of the state space, where the value gradient is significant and additional exploration might be beneficial. Experiments indicate significant speedups, especially in the initial learning phase.

REFERENCES

• 1: Anderberg, M. (1973). Cluster analysis for applications. Academic Press.
• 2: Andrew G. Barto , Sridhar Mahadevan, Recent Advances in Hierarchical Reinforcement Learning, Discrete Event Dynamic Systems, v.13 n.1-2, p.41-77, January-April 2003 [doi>10.1023/A:1022140919877]
• 3: Barto, A., Sutton, R., & Anderson, C. (1983). Neuronlike adaptive elements that can solve difficult learning control problems. IEEE Transactions on Systems, Man, and Cybernetics, 13, 834--846.
• 4: Baxter, J., & Bartlett, P. L. (2001). Infinite-horizon policy-gradient estimation. Journal of Artificial Intelligence Research, 15, 319--350.
• 5: Dimitri P. Bertsekas , John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996
• 6: Peter Dayan , Geoffrey E. Hinton, Feudal Reinforcement Learning, Advances in Neural Information Processing Systems 5, [NIPS Conference], p.271-278, November 30-December 03, 1992
• 7: Christopher J. C. H. Watkins , Peter Dayan, Technical Note: $\backslash cal\; Q$-Learning, Machine Learning, v.8 n.3-4, p.279-292, May 1992 [doi>10.1007/BF00992698]
• 8: Dietterich, T. G. (2000). Hierarchical reinforcement learning with the MAXQ value function decomposition. Journal of Artificial Intelligence Research, 13, 227--303.
• 9: 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
• 10: Ernst, D., Geurts, P., & Wehenkel, L. (2003). Iteratively extending time horizon reinforcement learning. Proceedings of the 14th European Conference on Machine Learning (pp. 96--107).
• 11: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 12: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 13: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 14: 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]
• 15: 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
• 16: McGovern, A., Sutton, R. S., & Fagg, A. H. (1997). Roles of macro-actions in accelerating reinforcement learning. Proceedings of the 1997 Grace Hopper Celebration of Women in Computing (pp. 13--18).
• 17: 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
• 18: Moriarty, D., Schultz, A., & Grefenstette, J. (1999). Evolutionary algorithms for reinforcement learning. Journal of Artificial Intelligence Research, 11, 199--229.
• 19: 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]
• 20: Theocharous, G., & Kaelbling, L. P. (2003). Approximate planning in POMDPs with macro-actions. To appear in Advances in Neural Processing Information Systems 17.

INDEX TERMS

Keywords:
Clustering, Hierarchical Reinforcement Learning, Options, Q-Learning, Reinforcement Learning