Partially Observable Markov Decision Processes (POMDPs) are a natural and general model in reinforcement learning that take into account the agent's uncertainty about its current state. In the literature on POMDPs, it is customary to assume access to a planning oracle that computes an optimal policy when the parameters are known, even though the problem is known to be computationally hard. Almost all existing planning algorithms either run in exponential time, lack provable performance guarantees, or require placing strong assumptions on the transition dynamics under every possible policy. In this work, we revisit the planning problem and ask: are there natural and well-motivated assumptions that make planning easy? Our main result is a quasipolynomial-time algorithm for planning in (one-step) observable POMDPs. Specifically, we assume that well-separated distributions on states lead to well-separated distributions on observations, and thus the observations are at least somewhat informative in each step. Crucially, this assumption places no restrictions on the transition dynamics of the POMDP; nevertheless, it implies that near-optimal policies admit quasi-succinct descriptions, which is not true in general (under standard hardness assumptions). Our analysis is based on new quantitative bounds for filter stability -- i.e. the rate at which an optimal filter for the latent state forgets its initialization. Furthermore, we prove matching hardness for planning in observable POMDPs under the Exponential Time Hypothesis.


翻译:部分可观察的 Markov 决策程序( POMDPs) 是强化学习的自然和一般模式, 考虑到了代理人对当前状态的不确定性。 在POMDPs的文献中, 习惯的做法是在参数为人所知时, 接受一个计算最佳政策的准极时算法, 尽管问题已知是计算困难的。 几乎所有现有的规划算法要么在指数时间里运行, 缺乏可证实的绩效保障, 或要求在每一项可能的政策下对过渡动态进行强有力的假设。 在这项工作中, 我们重新审视规划问题, 并询问: 是否有自然和动机良好的假设使规划变得容易? 在POMDPs的文献中, 我们的主要结果是在(一步)可见的POMDPs中进行规划的准极时算算法。 具体地说, 我们假设, 州内分布得分明的分布导致观察分布得分分得分得分,因此观察每一步都至少多少有些信息。 关键是, 这一假设没有限制POMDP的过渡动态动态; 然而, 它意味着, 近为接近的市级政策承认在( ) 精确的准确的准确的准确的内, 我们的准确的精确的精确的估算是基于我们的标准的精确的精确的精确的判断。

0
下载
关闭预览

相关内容

Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
【ICIG2021】Latest News & Announcements of the Plenary Talk2
中国图象图形学学会CSIG
0+阅读 · 2021年11月2日
【ICIG2021】Latest News & Announcements of the Plenary Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年11月1日
【ICIG2021】Latest News & Announcements of the Industry Talk2
中国图象图形学学会CSIG
0+阅读 · 2021年7月29日
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Risk-Averse Receding Horizon Motion Planning
Arxiv
1+阅读 · 2022年4月20日
Risk and optimal policies in bandit experiments
Arxiv
0+阅读 · 2022年4月18日
VIP会员
相关VIP内容
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
【ICIG2021】Latest News & Announcements of the Plenary Talk2
中国图象图形学学会CSIG
0+阅读 · 2021年11月2日
【ICIG2021】Latest News & Announcements of the Plenary Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年11月1日
【ICIG2021】Latest News & Announcements of the Industry Talk2
中国图象图形学学会CSIG
0+阅读 · 2021年7月29日
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员