The Smoothed Complexity of Policy Iteration for Markov Decision Processes
The Smoothed Complexity of Policy Iteration for Markov Decision Processes
复制标题
马尔可夫决策过程的策略迭代的平滑复杂度
DOI：
10.1145/3564246.3585220
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Yannakakis, Mihalis
中科院分区：
文献类型：
--
作者：
Christ, Miranda;Yannakakis, Mihalis
我们证明了经典的马氏决策过程的霍华德策略迭代算法的光滑复杂度的次指数下界(即2Ω(NC))。这一界限适用于总奖励标准和平均奖励标准。这种构造是稳健的，因为次指数界不仅对于MDP参数的独立随机扰动(转移概率和报酬)的平均值成立，而且对于逆多项式范围内的所有任意扰动都成立。对于简单的可达性目标，我们还证明了最坏情况复杂性的一个指数下界。
We show subexponential lower bounds (i.e., 2Ω (nc)) on the smoothed complexity of the classical Howard’s Policy Iteration algorithm for Markov Decision Processes. The bounds hold for the total reward and the average reward criteria. The constructions are robust in the sense that the subexponential bound holds not only on the average for independent random perturbations of the MDP parameters (transition probabilities and rewards), but for all arbitrary perturbations within an inverse polynomial range. We show also an exponential lower bound on the worst-case complexity for the simple reachability objective.
登录
查看更多内容
马尔可夫决策过程的策略改进算法的复杂性
影响因子：
2.1
作者：
Mary Melekopoglou;A. Condon
通讯作者：
A. Condon
Zadeh 枢轴规则的指数下界
影响因子：
2.7
作者：
Y. Disser;Oliver Friedmann;Alexander V. Hopp
通讯作者：
Alexander V. Hopp
模型检查概率系统
DOI：
--
发表时间：
2018
期刊：
Handbook of Model Checking
影响因子：
--
作者：
C. Baier;L. D. Alfaro;Vojtěch Forejt;M. Kwiatkowska
通讯作者：
M. Kwiatkowska
局部最大割和二值最大 CSP 的平滑复杂度
DOI：
10.1145/3357713.3384325
发表时间：
2020
期刊：
Proceedings of the 52th ACM Symposium on Theory of Computing
影响因子：
--
作者：
Chen, Xi;Guo, Chenghao;Vlatakis-Gkaragkounis, Emmanouil V.;Yannakakis, Mihalis;Zhang, Xinzhi
通讯作者：
Zhang, Xinzhi
提高 FLIP 最大割问题的平滑复杂度
影响因子：
1.3
作者：
Bibak, Ali;Carlson, Charles;Chandrasekaran, Karthekeyan
通讯作者：
Chandrasekaran, Karthekeyan