一种基于随机投影的贝叶斯时间差分算法

doi:10.3969/j.issn.0372-2112.2016.11.026

电子学报 ›› 2016, Vol. 44 ›› Issue (11): 2752-2757.DOI: 10.3969/j.issn.0372-2112.2016.11.026

一种基于随机投影的贝叶斯时间差分算法

刘全^1,2,3, 于俊^1,3, 王辉^1,3, 傅启明^1,3, 朱斐^1,3

1. 苏州大学计算机科学与技术学院, 江苏苏州 215006;
2. 吉林大学符号计算与知识工程教育部重点实验室, 吉林长春 130012:;
3. 软件新技术与产业化协同创新中心, 江苏南京 210023

收稿日期:2015-04-08 修回日期:2015-08-17 出版日期:2016-11-25 发布日期:2016-11-25
作者简介:刘全,男,1969年生于内蒙古,博士,教授,博士生导师.主要研究方向为强化学习、无线传感器网络、智能信息处理.E-mail:quanliu@suda.edu.cn;于俊,男,1989年生于江苏泰州,硕士.主要研究方向为强化学习、贝叶斯推理.
基金资助:
国家自然科学基金（No.61272005，No.61303108，No.61373094，No.61472262，No.61502323，No.61502329）；江苏省自然科学基金（No.BK2012616）；江苏省高校自然科学研究项目（No.13KJB520020）；吉林大学符号计算与知识工程教育部重点实验室项目（No.93K172014K04）；苏州市应用基础研究计划工业部分（No.SYG201422，No.SY201308）

A Bayesian Temporal Difference Algorithm Based on Random Projection

LIU Quan^1,2,3, YU Jun^1,3, WANG Hui^1,3, FU Qi-ming^1,3, ZHU Fei^1,3

1. School of Computer Science and Technology, Soochow University, Suzhou, Jiangsu 215006, China;
2. Key Laboratory of Symbolic Computation and Knowledge Engineering of Jilin University, Ministry of Education, Jilin University, Changchun, Jilin 130012, China;
3. Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing, Jiangsu 210023, China

Received:2015-04-08 Revised:2015-08-17 Online:2016-11-25 Published:2016-11-25

摘要/Abstract

摘要：

在强化学习方法中，大部分的算法都是基于值函数评估的算法.高斯过程时间差分算法利用贝叶斯方法来评估值函数，通过贝尔曼公式和贝叶斯规则，建立立即奖赏与值函数之间的概率生成模型.在状态空间中，通过在线核稀疏化并利用最小二乘方法来求解新样本的近似线性逼近，以提高算法的执行速度，但时间复杂度依然较高.针对在状态空间中近似状态的选择问题，在高斯过程框架下提出一种基于随机投影的贝叶斯时间差分算法，该算法利用哈希函数把字典状态集合中的元素映射成哈希值，根据哈希值进行分组，进而减少状态之间的比较.实验结果表明，该方法不仅能够提高算法的执行速度，而且较好地平衡了评估状态值函数精度和算法执行时间.

关键词: 强化学习, 马尔科夫决策过程, 高斯过程, 随机投影, 时间差分算法

Abstract:

Most algorithms are based on policy evaluation in reinforcement learning.The Gaussian process temporal difference is an algorithm that uses Bayesian solution to evaluate value functions.In the method,Gaussian process builds a probabilistic generative model between the immediate reward and the value function through Bellman Equation and Bayesian rule.In order to improve the efficiency of the algorithm,approximate linear approximation for new samples is solved by on-line kernel sparse and least squares in state space.However,the time complexity is still high.To deal with this problem,a Bayesian temporal difference algorithm bases on random projection algorithm is proposed.The elements in dictionary state set are mapped to hash values by hash function.According to the hash values,groups are divided and the comparison between the states is reduced.The experimental results show that this algorithm not only improves the execution speed,but also obtains balance between execution time and precision of the state value function.

Key words: reinforcement learning, markov decision process, gaussian process, random projection, temporal difference learning

中图分类号:

TP181

刘全, 于俊, 王辉, 傅启明, 朱斐. 一种基于随机投影的贝叶斯时间差分算法[J]. 电子学报, 2016, 44(11): 2752-2757.

LIU Quan, YU Jun, WANG Hui, FU Qi-ming, ZHU Fei. A Bayesian Temporal Difference Algorithm Based on Random Projection[J]. Acta Electronica Sinica, 2016, 44(11): 2752-2757.

参考文献

[1] Sutton R S,Barto A G.Reinforcement Learning:An Introduction[M].Cambridge:MIT Press,1998.
[2] 傅启明,刘全,尤树华,黄蔚,章晓芳.一种新的基于值函数迁移的快速Sarsa算法[J].电子学报,2014,42(11):2157-2161. Fu Qiming,Liu Quan,You Shuhua,Huang Wei,Zhang Xiaofang.A novel fast Sarsa algorithm based on value function transfer[J].Acta Electronica Sinica,2014,42(11):2157-2161.(in Chinese)
[3] Martínez Y,Nowé A,Suárez J,et al.A Reinforcement Learning Approach for the Flexible Job Shop Scheduling Problem[M].Learning and Intelligent Optimization:Springer Berlin Heidelberg,2014.253-262.
[4] Amato C,Shani G.High-level reinforcement learning in strategy games[A].Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems[C].International Foundation for Autonomous Agents and Multiagent Systems,2010.75-82.
[5] Marco Wiering,Martijn van Otterlo.Reinforcement Learning State of the Art[M].Singapore:Springer Press,2012.
[6] Sutton R S.Learning to predict by the methods of temporal differences[J].Machine Learning,1988,3(1):9-44.
[7] Shawe-Taylor J,Cristianini N.Kernel Methods for Pattern Analysis[M].Cambridge:Cambridge University Press,2004.
[8] Scholkopf B,Smola A J.Learning with Kernels:Support Vector Machines,Regularization,Optimization,and Eyond[M].Cambridge:MIT Press,2002.
[9] Ormoneit D,Sen.Kernel-based reinforcement learning[J].Machine Learning,2012,49(2-3):161-178.
[10] Xu X,Xie T,Hu D,et al.Kernel least-squares temporal difference learning[J].International Journal of Information Technology,2005,11(9):54-63.
[11] Xu X,Hu D,Lu X.Kernel-based least squares policy iteration for reinforcement learning[J].IEEE Transactions on Neural Networks,2007,18:973-992.
[12] C E Rasmussen and C K I Williams.Gaussian Processes for Machine Learning[M].Cambridge:MIT Press,2006.
[13] Engel Y,Mannor S,Meir R.Bayes meets Bellman:the gaussian process approach to temporal difference learning[A].Proceedings of the 20th International Conference on Machine Learning[C].Washington:AAAI,2011.154-161.
[14] Engel Y,Mannor S,Meir R.Reinforcement learning with gaussian processes[A].Proceedings of the 22nd International Conference on Machine Learning[C].Bonn:ACM,2014.201-208.
[15] Engel Y,Mannor S,Meir R.Sparse Online Greedy Support Vector Regression[M].Berlin:Springer,2002.

一种基于随机投影的贝叶斯时间差分算法

A Bayesian Temporal Difference Algorithm Based on Random Projection

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	卓亚琦, 魏家辉, 李志欣. 基于双注意模型的图像描述生成方法研究[J]. 电子学报, 2022, 50(5): 1123-1130.
[2]	易令, 李泽平. 基于深度强化学习的码率自适应算法研究[J]. 电子学报, 2022, 50(5): 1192-1200.
[3]	张涛, 张文涛, 代凌, 陈婧怡, 王丽, 魏倩茹. 基于序贯博弈多智能体强化学习的综合模块化航空电子系统重构方法[J]. 电子学报, 2022, 50(4): 954-966.
[4]	肖硕, 黄珍珍, 张国鹏, 杨树松, 江海峰, 李天旭. 基于SAC的多智能体深度强化学习算法[J]. 电子学报, 2021, 49(9): 1675-1681.
[5]	管永明, 王刚, 骆凯波, 吕梁, 吕晓雯, 史玉良. 基于极端不平衡学习的泛化低压异常箱表关系识别研究与应用[J]. 电子学报, 2021, 49(8): 1507-1514.
[6]	冀大雄, 方文巍, 朱华, 李硕, 唐元贵, 田宇, 姚倩. 基于相对测量的水下机器人主动定位方法研究[J]. 电子学报, 2021, 49(7): 1249-1256.
[7]	周东明, 张灿龙, 李志欣, 王智文. 基于多层级视觉融合的图像描述模型[J]. 电子学报, 2021, 49(7): 1286-1290.
[8]	韩冲, 王俊丽, 吴雨茜, 张超波. 基于神经进化的深度学习模型研究综述[J]. 电子学报, 2021, 49(2): 372-379.
[9]	刘润滋, 吴伟华, 张文柱, 周笛, 张琰. 基于图学习的密集空间网络传输资源调度方法[J]. 电子学报, 2021, 49(11): 2133-2137.
[10]	石义乐, 杨文忠, 杜慧祥, 王丽花, 王婷, 理珊珊. 基于深度学习的图像描述综述[J]. 电子学报, 2021, 49(10): 2048-2060.
[11]	陈思光, 陈佳民, 赵传信. 基于深度强化学习的云边协同计算迁移研究[J]. 电子学报, 2021, 49(1): 157-166.
[12]	黄志清, 曲志伟, 张吉, 张严心, 田锐. 基于深度强化学习的端到端无人驾驶决策[J]. 电子学报, 2020, 48(9): 1711-1719.
[13]	杨启萌, 禹龙, 田生伟, 艾山·吾买尔. 基于深度强化学习的维吾尔语人称代词指代消解[J]. 电子学报, 2020, 48(6): 1077-1083.
[14]	吴志东, 唐涛, 王鼎. 基于磁势梯度与高斯过程的空间磁场构建方法[J]. 电子学报, 2020, 48(12): 2304-2312.
[15]	李玉, 王亚琼, 赵雪梅, 赵泉华. 基于随机投影深度函数的停车场车辆提取方法[J]. 电子学报, 2019, 47(2): 322-330.