Exponential Lower Bounds for Policy Iteration

被引：0

作者：

Fearnley, John ^{[1
]}

机构：

[1] Univ Warwick, Dept Comp Sci, Coventry CV4 7AL, W Midlands, England

来源：

AUTOMATA, LANGUAGES AND PROGRAMMING, PT II | 2010年 / 6199卷

基金：

英国工程与自然科学研究理事会;

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study policy iteration for infinite-horizon Markov decision processes. It has recently been shown policy iteration style algorithms have exponential lower bounds in a. two player game setting. We extend these lower bounds to Markov decision processes with the total reward and average-reward optimality criteria.

引用

页码：551 / 562

页数：12

共 50 条

[1] Lower Bounds for Policy Iteration on Multi-action MDPs
Ashutosh, Kumar
Consul, Sarthak
Dedhia, Bhishma
Khirwadkar, Parthasarathi
Shah, Sahil
Kalyanakrishnan, Shivaram
2020 59TH IEEE CONFERENCE ON DECISION AND CONTROL (CDC), 2020, : 1744 - 1749
[2] On lower bounds of exponential frames
Lindner, AM
JOURNAL OF FOURIER ANALYSIS AND APPLICATIONS, 1999, 5 (2-3) : 185 - 192
[3] Lower bounds of exponential sums
Michel, P
DUKE MATHEMATICAL JOURNAL, 1998, 95 (02) : 227 - 240
[4] Exponential Lower Bounds via Exponential Sums
Chennai Mathematical Institute, India
不详
不详
Leibniz Int. Proc. Informatics, LIPIcs,
[5] On lower bounds of exponential frames
Alexander M. Lindner
Journal of Fourier Analysis and Applications, 1999, 5 : 185 - 192
[6] Tight Double Exponential Lower Bounds
Bliznets, Ivan
Hecher, Markus
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2024, 2024, 14637 : 124 - 136
[7] Exponential Lower Bounds for AC(0)-Frege Imply Superpolynomial Frege Lower Bounds
Filmus, Yuval
Pitassi, Toniann
Santhanam, Rahul
ACM TRANSACTIONS ON COMPUTATION THEORY, 2015, 7 (02)
[8] EXPONENTIAL LOWER BOUNDS TO SOLUTIONS OF THE SCHRODINGER-EQUATION - LOWER BOUNDS FOR THE SPHERICAL AVERAGE
FROESE, R
HERBST, I
COMMUNICATIONS IN MATHEMATICAL PHYSICS, 1983, 92 (01) : 71 - 80
[9] Exponential Lower Bounds and Separation for Query Rewriting
Kikot, Stanislav
Kontchakov, Roman
Podolskii, Vladimir
Zakharyaschev, Michael
AUTOMATA, LANGUAGES, AND PROGRAMMING, ICALP 2012, PT II, 2012, 7392 : 263 - 274
[10] Exponential Lower Bounds for Polytopes in Combinatorial Optimization
Fiorini, Samuel
Massar, Serge
Pokutta, Sebastian
Tiwary, Hans Raj
De Wolf, Ronald
JOURNAL OF THE ACM, 2015, 62 (02)

← 1 2 3 4 5 →