DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2023.27

A Unified Worst Case for Classical Simplex and Policy Iteration Pivot Rules

Authors: Yann Disser and Nils Mosis

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract

We construct a family of Markov decision processes for which the policy iteration algorithm needs an exponential number of improving switches with Dantzig’s rule, with Bland’s rule, and with the Largest Increase pivot rule. This immediately translates to a family of linear programs for which the simplex algorithm needs an exponential number of pivot steps with the same three pivot rules. Our results yield a unified construction that simultaneously reproduces well-known lower bounds for these classical pivot rules, and we are able to infer that any (deterministic or randomized) combination of them cannot avoid an exponential worst-case behavior. Regarding the policy iteration algorithm, pivot rules typically switch multiple edges simultaneously and our lower bound for Dantzig’s rule and the Largest Increase rule, which perform only single switches, seem novel. Regarding the simplex algorithm, the individual lower bounds were previously obtained separately via deformed hypercube constructions. In contrast to previous bounds for the simplex algorithm via Markov decision processes, our rigorous analysis is reasonably concise.

Cite as

Yann Disser and Nils Mosis. A Unified Worst Case for Classical Simplex and Policy Iteration Pivot Rules. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{disser_et_al:LIPIcs.ISAAC.2023.27,
  author =	{Disser, Yann and Mosis, Nils},
  title =	{{A Unified Worst Case for Classical Simplex and Policy Iteration Pivot Rules}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.27},
  URN =		{urn:nbn:de:0030-drops-193292},
  doi =		{10.4230/LIPIcs.ISAAC.2023.27},
  annote =	{Keywords: Bland’s pivot rule, Dantzig’s pivot rule, Largest Increase pivot rule, Markov decision process, policy iteration, simplex algorithm}
}

Search Results

Documents authored by Mosis, Nils

A Unified Worst Case for Classical Simplex and Policy Iteration Pivot Rules

Abstract

Cite as

Thanks for your feedback!

Could not send message