الملخص
We establish an exponential iteration lower bound in the number of states for Howard's policy iteration on deterministic discounted Markov decision processes, with at most two actions per state. This rules out strong polynomiality of Howard's policy iteration when the discount factor is part of the input and yields an exponential separation from the simplex method with Dantzig's pivoting rule, which is proved to be strongly polynomial on this class. Even when each reward is restricted to logarithmic bit length, we obtain a stretched-exponential iteration lower bound. The gap between Howard's decentralized and simultaneous selfish improvements and Dantzig's coordinated selection of a single action with the largest gain across all states reveals a ``price'' of algorithmic anarchy.
الكلمات المفتاحية
الموضوع
بيانات النشر
- المجلة
- غير متاح
- وصول مفتوح
- وصول مفتوح أخضر
اقتبس هذه المقالة
APA 7
Zhong, H., & Ye, Y. (2026). Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy. https://omanscience.com/ar/articles/policy-iteration-is-not-strongly-polynomial-for-deterministic-markov-decision-processes-the-price-of-algorithmic-anarchy
MLA 9
Zhong, Han, and Yinyu Ye. "Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy." https://omanscience.com/ar/articles/policy-iteration-is-not-strongly-polynomial-for-deterministic-markov-decision-processes-the-price-of-algorithmic-anarchy.
شيكاغو (المؤلف–التاريخ)
Zhong, Han, and Yinyu Ye. 2026. "Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy." https://omanscience.com/ar/articles/policy-iteration-is-not-strongly-polynomial-for-deterministic-markov-decision-processes-the-price-of-algorithmic-anarchy.
هارفارد
Zhong, H. and Ye, Y. (2026) 'Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy', Available at: https://omanscience.com/ar/articles/policy-iteration-is-not-strongly-polynomial-for-deterministic-markov-decision-processes-the-price-of-algorithmic-anarchy.
فانكوفر
Zhong H, Ye Y. Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy. https://omanscience.com/ar/articles/policy-iteration-is-not-strongly-polynomial-for-deterministic-markov-decision-processes-the-price-of-algorithmic-anarchy
IEEE
H. Zhong, and Y. Ye, "Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy," https://omanscience.com/ar/articles/policy-iteration-is-not-strongly-polynomial-for-deterministic-markov-decision-processes-the-price-of-algorithmic-anarchy.