Greedy feature replacement for online value function approximation

Feng-fei ZHAO; Zheng QIN; Zhuo SHAO; Jun FANG; Bo-yan REN

doi:10.1631/jzus.C1300246

Your Location：

Home >

Browse articles >

Greedy feature replacement for online value function approximation

Computer & Automation | Updated：2022-05-19

- Greedy feature replacement for online value function approximation
- 用于在线值函数近似的贪婪特征替换方法
- Frontiers of Information Technology & Electronic Engineering Vol. 15, Issue 3, Pages: 223-231(2014)
- Affiliations：
  
  1.Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
  2.School of Software, Tsinghua University, Beijing 100084, China
  3.Department of Physics and State Key Laboratory of Low-Dimensional Quantum Physics, Tsinghua University, Beijing 100084, China
- Author bio：
  
  [ "Feng-fei ZHAO, E-mail: zhaofengfei@gmail.com" ]
  [ " Zheng QIN, E-mail: qingzh@tsinghua.edu.cn" ]
  [ "Zhuo SHAO, E-mail: shaoz09@mails.tsinghua.edu.cn" ]
- Funds：
- DOI：10.1631/jzus.C1300246
  CLC： TP181
- Received：06 September 2013，
  
  Revised：2014-2-21，
  
  Accepted：14 January 2014，
  
  Published：2014-03
- Accepted：
Scan QR Code
Feng-fei ZHAO, Zheng QIN, Zhuo SHAO, et al. Greedy feature replacement for online value function approximation[J]. Frontiers of Information Technology & Electronic Engineering, 2014, 15(3): 223-231.
DOI：

Feng-fei ZHAO, Zheng QIN, Zhuo SHAO, et al. Greedy feature replacement for online value function approximation[J]. Frontiers of Information Technology & Electronic Engineering, 2014, 15(3): 223-231. DOI： 10.1631/jzus.C1300246.

摘要

研究目的

强化学习需要使用值函数近似来处理真实世界中的高维度状态空间问题，而值函数近似的效果很大程度上取决于合适特征表示的选取。表示扩展技术可使线性近似器更有效地表示值函数，然而现有的表示扩展技术或者只适用于低维度问题，或者在学习过程中不能及时发现重要的特征依赖。因此，本文提出了一种新型在线特征扩展技术——贪婪特征替换（GFR）。

创新要点

通过发现替换区域来执行特征替换的方式，贪婪特征替换方法增量地扩展特征表示，可以处理高维度状态空间问题，解决了传统在线扩展技术的局限。通过识别替换区域，贪婪特征替换方法优化了特征组合的加入顺序，提高了特征表示扩展的性能。

研究方法

引入虚拟时序差的概念，模拟新特征组合加入特征表示后的时序差，通过分析实际时序差与虚拟时序差累积情况的差距，选择新的特征组合。如差距超过给定阈值，这个特征组合将被作为新特征。在每次特征替换中，两个原有的特征被一个新的特征组合取代。

重要结论

理论分析表明，使用贪婪特征替换方法的值函数近似可以渐进地得到最优近似结果。对两个有代表性的学习问题的实验结果显示，贪婪特征替换可以达到更快的学习效果，而且具备处理大规模状态空间的能力。贪婪特征替换方法可以应用于各种在线值函数近似。

Abstract

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.

关键词

Keywords

references

J.S. Albus . A theory of cerebellar function . Math. Biosci. , 1971 . 10 ( 1-2 ): 25 - 61 . DOI: 10.1016/0025-5564(71)90051-4 http://doi.org/10.1016/0025-5564(71)90051-4 .

A.G. Barto , S.J. Bradtke , S.P. Singh . Learning to act using real-time dynamic programming . Artif. Intell. , 1995 . 72 ( 1-2 ): 81 - 138 . DOI: 10.1016/0004-3702(94)00011-O http://doi.org/10.1016/0004-3702(94)00011-O .

M. Buro . From simple features to sophisticated evaluation functions . Proc. 1st Int. Conf. on Computers and Games , 1999 . p.126 - 145 . DOI: 10.1007/3-540-48957-6_8 http://doi.org/10.1007/3-540-48957-6_8 .

Y.M. de Hauwere , P. Vrancx , A. Nowé . Generalized learning automata for multi-agent reinforcement learning . AI Commun. , 2010 . 23 ( 4 ): 311 - 324 . DOI: 10.3233/AIC-2010-0476 http://doi.org/10.3233/AIC-2010-0476 .

A. Geramifard , F. Doshi , J. Redding , 等 . Online discovery of feature dependencies . Proc. 28th Int. Conf. on Machine Learning , 2011 . p.881 - 888 . .

A. Geramifard , C. Dann , J.P. How . Off-policy learning combined with automatic feature expansion for solving large MDPs . Proc. 1st Multidisciplinary Conf. on Reinforcement Learning and Decision Making , 2013 . p.29 - 33 . .

L.P. Kaelbling , M.L. Littman , A.W. Moore . Reinforcement learning: a survey . J. Artif. Intell. Res. , 1996 . 4 237 - 285 . DOI: 10.1613/jair.301 http://doi.org/10.1613/jair.301 .

J.Z. Kolter , A.Y. Ng . Near-Bayesian exploration in polynomial time . Proc. 26th Annual Int. Conf. on Machine Learning , 2009 . p.513 - 520 . DOI: 10.1145/1553374.1553441 http://doi.org/10.1145/1553374.1553441 .

M.G. Lagoudakis , R. Parr . Least-squares policy iteration . J. Mach. Learn. Res. , 2003 . 4 ( 6 ): 1107 - 1149 . .

J. Pazis , M.G. Lagoudakis . Binary action search for learning continuous-action control policies . Proc. 26th Annual Int. Conf. on Machine Learning , 2009 . p.793 - 800 . DOI: 10.1145/1553374.1553476 http://doi.org/10.1145/1553374.1553476 .

M.L. Puterman . Markov Decision Processes-Discrete Stochastic Dynamic Programming . John Wiley & Sons, New York, NY , 1994 . p.139 - 161 . .

B. Ratitch , D. Precup . Sparse distributed memories for on-line value-based reinforcement learning . Proc. 15th European Conf. on Machine Learning , 2004 . p.347 - 358 . DOI: 10.1007/978-3-540-30115-8_33 http://doi.org/10.1007/978-3-540-30115-8_33 .

G.A. Rummery , M. Niranjan . On-line Q-learning Using Connectionist Systems . Technical Report No. cued/ f-infeng/tr166, Engineering Department, Cambridge University , 1994 .

S. Singh , T. Jaakkola , M.L. Littman , 等 . Convergence results for single-step on-policy reinforcement-learning algorithms . Mach. Learn. , 2000 . 38 ( 3 ): 287 - 308 . DOI: 10.1023/A:1007678930559 http://doi.org/10.1023/A:1007678930559 .

S.P. Singh , R.S. Sutton . Reinforcement learning with replacing eligibility traces . Mach. Learn. , 1996 . 22 ( 1-3 ): 123 - 158 . DOI: 10.1023/A:1018012322525 http://doi.org/10.1023/A:1018012322525 .

S.P. Singh , R.C. Yee . An upper bound on the loss from approximate optimal-value functions . Mach. Learn. , 1994 . 16 ( 3 ): 227 - 233 . DOI: 10.1007/Bf00993308 http://doi.org/10.1007/Bf00993308 .

N. Sprague , D. Ballard . Multiple-goal reinforcement learning with modular sarsa(0) . Proc. 18th Int. Joint Conf. on Artificial Intelligence , 2003 . p.1445 - 1447 . .

N.R. Sturtevant , A.M. White . Feature construction for reinforcement learning in hearts . Proc. 5th Int. Conf. on Computers and Games , 2006 . p.122 - 134 . DOI: 10.1007/978-3-540-75538-8_11 http://doi.org/10.1007/978-3-540-75538-8_11 .

R.S. Sutton . Generalization in reinforcement learning: successful examples using sparse coarse coding . Adv. Neur. Inform. Process. Syst. , 1996 . 8 1038 - 1044 . .

R.S. Sutton , A.G. Barto . Reinforcement Learning: an Introduction , : Cambridge, MA, USA MIT Press , 1998 . p.3 - 25 . .

J.N. Tsitsiklis . Asynchronous stochastic approximation and Q-learning . Mach. Learn. , 1994 . 16 ( 3 ): 185 - 202 . DOI: 10.1007/Bf00993306 http://doi.org/10.1007/Bf00993306 .

J.N. Tsitsiklis , B. van Roy . An analysis of temporal- difference learning with function approximation . IEEE Trans. Automat. Contr. , 1997 . 42 ( 5 ): 674 - 690 . DOI: 10.1109/9.580874 http://doi.org/10.1109/9.580874 .

C.J.C.H. Watkins , P. Dayan . Q-learning . Mach. Learn. , 1992 . 8 ( 3-4 ): 279 - 292 . DOI: 10.1007/Bf00992698 http://doi.org/10.1007/Bf00992698 .

S. Whiteson , M.E. Taylor , P. Stone . Adaptive Tile Coding for Value Function Approximation . Technical Report No. AI-TR-07-339, University of Texas at Austin , 2007 .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Jiu fusion artificial intelligence (JFA): a two-stage reinforcement learning model with hierarchical neural networks and human knowledge for Tibetan Jiu chess

Efficient learning of robust multigait quadruped locomotion for minimizing the cost of transport

Reinforcement learning based privacy-preserving consensus tracking control of nonstrict-feedback discrete-time multi-agent systems

Domain adaptation in reinforcement learning: a comprehensive and systematic study

Multi-agent reinforcement learning behavioral control for nonlinear second-order systems

Related Author

Xiali LI

Xiaoyu FAN

Junzhi YU

Xianmu CAIRANG

Ping LAN

Zhicheng DONG

Zhicheng WANG

Xin ZHAO

Related Institution

School of Information Science and Technology, Xizang University

State Key Laboratory of General Artificial Intelligence, Peking University

State Key Laboratory for Turbulence and Complex Systems, Peking University

School of Information Engineering, Minzu University of China

Key Laboratory of Ethnic Language Intelligent Analysis and Security Governance of MOE, Minzu University of China

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰