This paper proposes a Reinforcement Learning (RL) algorithm to synthesize policies for a Markov Decision Process (MDP), such that a linear time property is satisfied. We convert the property into a Limit Deterministic Buchi Automaton (LDBA), then construct a product MDP between the automaton and the original MDP. A reward function is then assigned to the states of the product automaton, according to accepting conditions of the LDBA. With this reward function, our algorithm synthesizes a policy that satisfies the linear time property: as such, the policy synthesis procedure is "constrained" by the given specification. Additionally, we show that the RL procedure sets up an online value iteration method to calculate the maximum probability of satisfying the given property, at any given state of the MDP - a convergence proof for the procedure is provided. Finally, the performance of the algorithm is evaluated via a set of numerical examples. We observe an improvement of one order of magnitude in the number of iterations required for the synthesis compared to existing approaches.


翻译:本文提出“强化学习”算法,以综合Markov 决策程序的政策,从而满足线性时间属性。我们将属性转换成“限制决定因素 Buchi Automaton ” (LDBA),然后在自动映射器和原始MDP之间构建产品 MDP。然后,根据LDBA的接受条件,将奖励功能分配给产品自动映射状态。有了这一奖励功能,我们的算法将满足线性时间属性的政策合成为一种政策:因此,政策合成程序受特定规格的“制约 ” 。此外,我们表明,RL程序设置了在线值迭代法,以计算在任何给定状态满足特定属性的最大概率,即提供该程序的趋同证明。最后,通过一组数字示例评估该算法的性能。我们观察到,与现有方法相比,合成所需的迭代数数量有一定的大小。

5
下载
关闭预览

相关内容

零样本文本分类,Zero-Shot Learning for Text Classification
专知会员服务
94+阅读 · 2020年5月31日
元学习(meta learning) 最新进展综述论文
专知会员服务
275+阅读 · 2020年5月8日
MIT-深度学习Deep Learning State of the Art in 2020,87页ppt
专知会员服务
61+阅读 · 2020年2月17日
【强化学习资源集合】Awesome Reinforcement Learning
专知会员服务
93+阅读 · 2019年12月23日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
54+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
25+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Risk-Aware Active Inverse Reinforcement Learning
Arxiv
7+阅读 · 2019年1月8日
Arxiv
7+阅读 · 2018年12月26日
Multi-task Deep Reinforcement Learning with PopArt
Arxiv
4+阅读 · 2018年9月12日
Arxiv
8+阅读 · 2018年7月12日
Arxiv
11+阅读 · 2018年7月8日
Arxiv
6+阅读 · 2018年4月24日
VIP会员
相关VIP内容
零样本文本分类,Zero-Shot Learning for Text Classification
专知会员服务
94+阅读 · 2020年5月31日
元学习(meta learning) 最新进展综述论文
专知会员服务
275+阅读 · 2020年5月8日
MIT-深度学习Deep Learning State of the Art in 2020,87页ppt
专知会员服务
61+阅读 · 2020年2月17日
【强化学习资源集合】Awesome Reinforcement Learning
专知会员服务
93+阅读 · 2019年12月23日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
54+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
25+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员