Interval Markov Decision Processes (IMDPs) are finite-state uncertain Markov models, where the transition probabilities belong to intervals. Recently, there has been a surge of research on employing IMDPs as abstractions of stochastic systems for control synthesis. However, due to the absence of algorithms for synthesis over IMDPs with continuous action-spaces, the action-space is assumed discrete a-priori, which is a restrictive assumption for many applications. Motivated by this, we introduce continuous-action IMDPs (caIMDPs), where the bounds on transition probabilities are functions of the action variables, and study value iteration for maximizing expected cumulative rewards. Specifically, we decompose the max-min problem associated to value iteration to $|\mathcal{Q}|$ max problems, where $|\mathcal{Q}|$ is the number of states of the caIMDP. Then, exploiting the simple form of these max problems, we identify cases where value iteration over caIMDPs can be solved efficiently (e.g., with linear or convex programming). We also gain other interesting insights: e.g., in certain cases where the action set $\mathcal{A}$ is a polytope, synthesis over a discrete-action IMDP, where the actions are the vertices of $\mathcal{A}$, is sufficient for optimality. We demonstrate our results on a numerical example. Finally, we include a short discussion on employing caIMDPs as abstractions for control synthesis.


翻译:区间马尔科夫决策过程(IMDPs)是有限状态的不确定马尔科夫模型,其中转移概率属于区间。最近,有越来越多的研究将IMDP作为随机系统的抽象来进行控制合成。然而,由于缺乏针对具有连续行动空间的IMDP的综合算法,因此先验地假设行动空间是离散的,这对许多应用来说是一种限制性假设。出于这个原因,我们引入了连续行动IMDP(caIMDPs),其中转移概率的界限是行动变量的函数,并研究最大化预期累积奖励的价值迭代。具体而言,我们将与价值迭代相关的max-min问题分解为$|\mathcal{Q}|$个max问题,其中$|\mathcal{Q}|$是caIMDP的状态数量。然后,利用这些max问题的简单形式,我们确定了在哪些情况下可以高效地解决caIMDP上的价值迭代(例如,使用线性或凸规划)。我们还获得了其他有趣的见解:例如,在行动集$\mathcal{A}$是多面体的某些情况下,综合离散行动IMDP,在其中行动是$\mathcal{A}$ 的顶点,足以实现最优性。我们通过数值实例展示了我们的结果。最后,我们讨论了将caIMDP用作控制综合的抽象的缩短。

0
下载
关闭预览

相关内容

【干货书】贝叶斯推理决策,195页pdf
专知会员服务
89+阅读 · 2021年12月11日
机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
【干货书】贝叶斯推断随机过程,449页pdf
专知会员服务
150+阅读 · 2020年8月27日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
生成扩散模型漫谈:一般框架之ODE篇
PaperWeekly
1+阅读 · 2022年9月1日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
基于 Carsim 2016 和 Simulink的无人车运动控制联合仿真(三)
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月25日
Arxiv
79+阅读 · 2022年7月16日
VIP会员
相关资讯
生成扩散模型漫谈:一般框架之ODE篇
PaperWeekly
1+阅读 · 2022年9月1日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
基于 Carsim 2016 和 Simulink的无人车运动控制联合仿真(三)
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员