期刊文献+

Greedy feature replacement for online value function approximation

Greedy feature replacement for online value function approximation
原文传递
导出
摘要 Reinforcement learning(RL) in real-world problems requires function approximations that depend on selecting the appropriate feature representations. Representational expansion techniques can make linear approximators represent value functions more effectively; however, most of these techniques function well only for low dimensional problems. In this paper, we present the greedy feature replacement(GFR), a novel online expansion technique, for value-based RL algorithms that use binary features. Given a simple initial representation, the feature representation is expanded incrementally. New feature dependencies are added automatically to the current representation and conjunctive features are used to replace current features greedily. The virtual temporal difference(TD) error is recorded for each conjunctive feature to judge whether the replacement can improve the approximation. Correctness guarantees and computational complexity analysis are provided for GFR. Experimental results in two domains show that GFR achieves much faster learning and has the capability to handle large-scale problems. Reinforcement learning (RL) in real-world problems requires function approximations that depend on selecting the appropriate feature representations. Representational expansion techniques can make linear approximators represent value functions more effectively; however, most of these techniques function well only for low dimensional problems. In this paper, we present the greedy feature replacement (GFR), a novel online expansion technique, for value-based RL algorithms that use binary features. Given a simple initial representation, the feature representation is expanded incrementally. New feature dependencies are added automatically to the current representation and conjunctive features are used to replace current features greedily. The virtual temporal difference (TD) error is recorded for each conjunctive feature to judge whether the replacement can improve the approximation. Correctness guarantees and computational complexity analysis are provided for GFR. Experimental results in two domains show that GFR achieves much faster learning and has the capability to handle large-scale problems.
出处 《Journal of Zhejiang University-Science C(Computers and Electronics)》 SCIE EI 2014年第3期223-231,共9页 浙江大学学报C辑(计算机与电子(英文版)
基金 Project supported by the 12th Five-Year Defense Exploration Project of China(No.041202005) the Ph.D.Program Foundation of the Ministry of Education of China(No.20120002130007)
关键词 Reinforcement learning Function approximation Feature dependency Online expansion Feature replacement Reinforcement learning, Function approximation, Feature dependency, Online expansion, Feature replacement
  • 相关文献

参考文献22

  • 1Pazis, J., Lagoudakis, M.G., 2009. Binary action search for learning continuous-action control policies. Proc. 26th Annual Int. Conf. on Machine Learning, p.793-800. [doi:10.1145/1553374.1553476].
  • 2Singh, S.E, Yee, R.C., 1994. An upper bound on the loss from approximate optimal-value functions. Maeh. Learn., 16(3):227-233. [doi: 10.1007/Bf00993308].
  • 3Singh, S., Jaakkola, T., Littman, M.L., et al., 2000. Convergence results for single-step on-policy reinforcement-learning algorithms. Maeh. Learn., 38(3):287-308. [doi: 10.1023/A 1007678930559].
  • 4Watkins, C.J.C.H., Dayan, P., 1992. Q-learning. Mach. Learn., 8(3-4):279-292. [doi: 10.1007/Bf00992698].
  • 5Kaelbling, L.E, Littman, M.L., Moore, A:V, 1996. Reinforcement learning: a survey. J. Artif. Intell. Res., 4:237-285. [doi: 10.1613/jair.301 ].
  • 6Buro, M., 1999. From simple features to sophisticated evaluation functions. Proc. 1 st Int. Conf. on Computers and Games, p.126-145. [doi:10.1007/3-540-48957-6_8].
  • 7Sutton, R.S., Barto, A.G., 1998. Reinforcement Learning: an Introduction. MIT Press, Cambridge, MA, USA, p.3-25.
  • 8Albus, J.S., 1971. A theory of cerebellar function. Math. Biosci., 10(1-2):25-61. [doi:10.1016/0025-5564(71)900 51-4].
  • 9Puterman, M.L., 1994. Markov Decision Processes Discrete Stochastic Dynamic Programming. John Wiley & Sons, New York, NY, p.139-161.
  • 10Tsitsiklis, J.N., van Roy, B., 1997. An analysis of temporal- difference learning with function approximation. IEEE Trans. Automat. Contr., 42(5):674-690. [doi: 10.1109/9. 580874].

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部