Lower Bounds for Ranking-Based Pivot Rules

The simplex method for linear programming is among the most well-studied algorithms in existence. To this day, the fundamental question of whether the method admits a (strongly) polynomial pivot rule remains one of the most important unsolved problems in mathematical optimization. A positive answer would address Smale’s 9th problem [51] and resolve the polynomial Hirsch conjecture [19, 48]. The question of the complexity of the simplex method also surfaced in other settings that are now known to reduce to linear programming: the complexity of strategy improvement for parity games [54] and of policy iteration for Markov decision processes [47].

Despite the importance of the question and despite numerous negative results for individual pivot rules [6, 7, 22, 31, 32, 33, 35, 38, 42, 46], a general lower bound for all rules is currently very much out of reach. Both, a polynomial bound on the diameter of polytopes and a systematic understanding of pivot rules, remain elusive. Hence, almost all results to date have been tailored to single rules with little hope of generalization. Exceptions include a recent bound for shadow vertex rules and steepest edge rules [12], as well as a bound for combinations of three classical rules [23]. While simultaneously handling a continuum of pivot rules, these latter results are still rather interpolations between pivot rules than conceptual classes that capture a meaningful subset of all rules.

We propose a classification of pivot rules according to the information they use, and provide general lower bounds for a natural family of rules. We hope that our treatment can be the basis for a systematic study of general classes of pivot rules in the future.

The simplex method solves linear programs (LPs) of the form

where $A\in {\mathbb{Q}}^{m\times n}$ has full row-rank, $𝒃\in {\mathbb{Q}}^m$, and $𝒄\in {\mathbb{Q}}^n$. A basis $B=\{b_1,\mathrm{\dots },b_m\}\subseteq [n]$, where we write $[k]:=\{1,2,\mathrm{\dots },k\}$, for all $k\in \mathbb{N}$, is a set of indices of $m$ linearly independent columns of $A$. We denote the (regular) matrix consisting of these columns by $A_{\cdot B}$. Given a basis $B$, there is a unique $𝒙\in {ℝ}^n$ such that $A𝒙=𝒃$ and $x_i=0$ for all $i\in [n]\setminus B$. If this $𝒙$ is feasible for ($L{P}_{A,𝒃,𝒄}$), i.e., $x_j\ge 0$ for all $j\in B$, we call it a basic feasible solution (BFS) with basis $B$, and $B$ is a feasible basis. In this case, $𝒙$ is a vertex of the feasible region $\{𝒙:A𝒙=𝒃,𝒙\ge \mathrm{𝟎}\}$.

In this paper, we assume (without loss of generality) that the feasible region is non-empty, that the linear program is bounded, i.e., the optimum is attained at a vertex, and that the simplex method gets an initial feasible basis $B$ as input. Then, the algorithm selects an entering index $i\in [n]\setminus B$ and a leaving index $j\in B$ such that

• $\mathrm{■}$

  $\mathrm{rc}(i)≔c_i-𝒄_{𝑩}^{}{}_{}{}^{\top }{A}_{\cdot B}^{-1}{𝑨}_{\mathbf{\cdot }𝒊}>0$,

• $\mathrm{■}$

  $B^{\prime }≔B\cup \{i\}\setminus \{j\}$ is a feasible basis,

and repeats with $B\leftarrow B^{\prime }$, until reaching the optimum. We call $\mathrm{rc}(i)$ the reduced costs of index $i$ (or variable $x_i$) and say that $i$ (or $x_i$) is an improving index (or improving variable) for $B$ if $\mathrm{rc}(i)>0$. We write ${\mathrm{\Gamma }}^{+}(B)≔\{i\in [n]\setminus B:\mathrm{rc}(i)>0\}$ to denote the set of all improving indices for $B$. Since the choices of $i$ and $j$ are in general not unique, pivot rules are used to determine the behavior of the algorithm, see Section 3.

In this paper, we mainly consider non-degenerate linear programs, where we have a one-to-one correspondence between bases and vertices of the feasible region, such that, in each iteration of the simplex method, the choice of the leaving index is uniquely determined by the entering index.

Sink parity games are two-player games that are played on the vertices of a directed graph. A sink parity game (SPG) is given by a tuple $(V_0,V_1,E,\pi )$, specifying a directed graph $G=(V_0\cup V_1\cup \{\top \},E)$ and a priority function $\pi :V_0\cup V_1\cup \{\top \}\to \mathbb{Z}\cup \{-\mathrm{\infty }\}$. We will often also refer to the sink parity game itself by $G$. We generally assume that each vertex of $G$ has at least one outgoing edge. Further, the vertex $\top$, called the sink, has precisely one outgoing edge, which is a self-loop, and is the only vertex with priority $\pi (\top )=-\mathrm{\infty }$.

The game is played between player 0 and player 1, where player $i$ owns the vertices of $V_i$. At the start of the game, a token is placed on an initial vertex $v_0$. At step $k$, the owner of the current node $v_k$ moves the token along an outgoing edge to a successor node $v_{k+1}$. The game continues infinitely, so the token travels along an infinite path $(v_0,v_1,v_2,\mathrm{\dots })$. The objective of player 0 is to maximize the outcome, given by ${\sum }_{i=0}^{\mathrm{\infty }}{(-t)}^{\pi (v_i)}$, where $t\ge |V_0\cup V_1|$ is a constant. With this objective, the strategy improvement algorithm we will define later is equivalent to the version described in [54], see also [28] for background on parity games. Therefore, player $0$ wants to collect large even priorties and avoid large odd priorities. Player $1$ aims to minimize the outcome.

It can be shown that the optimal strategy for both players is positional, meaning they always make the same choice in the same node. We can thus consider a player $i$ strategy as a function $\sigma :V_i\to V_G$, where $V_G≔V_0\cup V_1\cup \{\top \}$. So, if player $i$ commits to a strategy ${\sigma }_i$, the token can only move along the edges of $E_{{\sigma }_i}:=\{(v,{\sigma }_i(v)):v\in V_i\}\cup \{(v,w):v\in V_{1-i}\}$.

Every sink parity game is assumed to admit

• $\mathrm{■}$

  a player 0 strategy ${\sigma }_0$ such that the highest priority on any cycle in $E_{{\sigma }_0}$ is even,

• $\mathrm{■}$

  a player 1 strategy ${\sigma }_1$ such that the highest priority on any cycle in $E_{{\sigma }_1}$ is odd.

We call the strategies from these assumptions admissible strategies. These two assumptions guarantee that, with optimal play, the token travels along a simple path towards $\top$, which guarantees that the outcome is finite for every given constant $t$. It also turns out that there always exists a strategy that is optimal for all starting vertices simultaneously[54]. Hence, solving the game usually means finding such an optimal strategy.

Let $\sigma$ be an admissible player 0 strategy. Then, the optimal counterstrategy $\overline{\sigma }$ for player 1 can easily be found by a shortest path computation. If the players play according to $\sigma$ and $\overline{\sigma }$, the token will follow a simple path $(v_0,v_1,\mathrm{\dots },v_k,\top )$ that ends in the sink. This defines a valuation function ${\mathrm{Val}}_{\sigma }:V_G\to {\mathbb{N}}^{\mathbb{N}}$, where ${\mathrm{Val}}_{\sigma }(v_0)$ is given by the multiset $\{\pi (v_0),\pi (v_1),\mathrm{\dots },\pi (v_k)\}$ for every $v_0\in V_G$. We can compare these multisets by $⊲$, where $S_1⊲S_2$ if and only if ; in this summation, elements occurring multiple times are used multiple times. We call an edge $a=(v,w)\in E_0$ with ${\mathrm{Val}}_{\sigma }(w)⊳{\mathrm{Val}}_{\sigma }(\sigma (v))$ an improving move or improving switch for $\sigma$. If we apply an improving switch $a\in E_0$ to a strategy $\sigma$, we obtain a new strategy ${\sigma }^a$ by ${\sigma }^a(v)=w$ and ${\sigma }^a(v^{\prime })=\sigma (v^{\prime })$ for all $v^{\prime }\in V_0\setminus \{v\}$. The improving switch $a$ increases the value of $v$ without decreasing the value of any other state. A strategy $\sigma$ is optimal for a sink parity game if and only if there is no improving switch for $\sigma$.

Markov decision processes provide a framework for modeling the decision-making of an agent operating in an uncertain environment. The environment is described by a finite set $S$ of states and a finite set $A$ of actions representing the feasible decisions. Each action $a\in A$ is associated with a reward $\mathrm{rew}(a)\in ℝ$ and a probability distribution $P_a$ over $S$. In each state $s\in S$, the agent may choose among a non-empty subset $A_s\subseteq A$ of available actions. When an action $a\in A_s$ is chosen, the agent receives the reward $\mathrm{rew}(a)$, and the process transitions to a state $s^{\prime }\in S$, which is drawn according to $P_a$. For each $s^{\prime }\in S$, we denote the probability that action $a$ leads to $s^{\prime }$ with $P_{a,s^{\prime }}$ and call it a transition probability.

A state $s$ is reachable from another state $s^{\prime }$ if there exists a sequence of actions such that the process transitions from $s^{\prime }$ to $s$ with positive probability. A state $\top \in S$ is called sink if it is reachable from all states and if $A_{\top }=\{a\}\subseteq A$ with $\mathrm{rew}(a)=0$ and $P_{a,\top }=1$. Thus, once the agent reaches the sink, they cannot collect any further reward.

A policy is a function $\sigma :S\to A$ assigning to each state $s\in S$ an action $\sigma (s)\in A_s$. Given a policy $\sigma$, the value of each $s\in S$, denoted by ${\mathrm{Val}}_{\sigma }(s)$, is the expected total reward obtained when the process starts in $s$ and the agent follows $\sigma$ in every state. In other words, the value function ${\mathrm{Val}}_{\sigma }:S\to ℝ$ is determined by the following system of Bellman [9] equations

together with ${\mathrm{Val}}_{\sigma }(\top )=0$ if there is a sink $\top$. A policy $\sigma$ is optimal (with respect to the expected total reward criterion) if ${\mathrm{Val}}_{\sigma }(s)\ge {\mathrm{Val}}_{{\sigma }^{\prime }}(s)$ for all $s\in S$ and all policies ${\sigma }^{\prime }$. See [47] for a discussion on other optimality criteria that consider discounted or average rewards.

A policy $\sigma$ is weak unichain if there is a sink $\top$, and the agent will finally reach $\top$ with probability one when following $\sigma$ in every state, irrespective of the starting vertex. We call the process weak unichain if it admits an optimal policy that is weak unichain. We refer to [30] for more details on the weak unichain condition.

An action $a\in A_s$ is an improving switch for policy $\sigma$ if

where ${\mathrm{rc}}_{\sigma }(a)$ is called reduced costs of $a$ (with respect to $\sigma$).

If we apply an improving switch $a\in A_s$ to a policy $\sigma$, we obtain a new policy ${\sigma }^a$ by ${\sigma }^a(s)=a$ and ${\sigma }^a(s^{\prime })=\sigma (s^{\prime })$ for all $s^{\prime }\in S\setminus \{s\}$. The improving switch $a$ increases the value of $s$ without decreasing the value of any other state. A policy $\sigma$ is optimal for a weak unichain Markov decision process if and only if there is no improving switch for $\sigma$.

Strategy improvement or policy iteration is an algorithmic idea that can be used to find optimal strategies and values for many types of games on graphs, see, e.g., [28]. To avoid confusion, we use the name StrategyImprovement when it is applied to sink parity games, and the name PolicyIteration when applied to weak unichain Markov decision processes. The idea is simple: given an initial policy/strategy, iteratively apply improving switches until reaching an optimal solution, see Algorithm 1.

In this paper, we only consider a version of this algorithm that applies a single switch in each iteration. For a more general discussion, we refer to [54, 47]. The algorithm will only visit admissible strategies/weak unichain policies, and is guaranteed to return the optimal strategy/policy after a finite number of iterations. Whenever there are multiple improving switches, the choice in the algorithm is determined by an improvement rule, analogously to pivot rules for the simplex method.

It is well-known that, for every weak unichain Markov decision process $ℳ$, there is a linear program ${\mathrm{LP}}_{ℳ}$ such that the application of the simplex method to ${\mathrm{LP}}_{ℳ}$ is equivalent to the application of PolicyIteration to $ℳ$, in the following sense.

Recently, [44] provided an analogous reduction for sink parity games, based on [49].

Conveniently, it is very simple to transform a sink parity game into an equivalent sink parity game with unique priorities by repeating the following: whenever there are two nodes with priority $p$, we can keep one of them at priority $p$ and increase the priority of all other nodes with priority at least $p$ by 2. This has no effect on the run of strategy improvement, unless there are two strategies with the same value, in which case it may introduce new improving moves. We refer to this well-known transformation as the standard transformation.

Pivot rules specify, in each iteration of the simplex method, which index enters and which index leaves the basis. Since the inception of the simplex method by Dantzig in 1947 [20], many pivot rules have been proposed. Formally, a pivot rule is a function that gets the data of the linear program as well as the current basis as input, and returns a pair of an entering and a leaving index. Given an LP of the form ($L{P}_{A,𝒃,𝒄}$) with $m$ equality constraints and $n$ variables, its data can be written as elements of ${ℒ}_{m,n}≔\{(A,𝒃,𝒄):A\in {\mathbb{Q}}^{m\times n},𝒃\in {\mathbb{Q}}^m,𝒄\in {\mathbb{Q}}^n\}$. The basis is an element of $𝒫([n])$; here, we denote the powerset of a finite set $S$ by $𝒫(S)≔2^S$. Some pivot rules allow for ties between several options of switches, that is, instead of determining a unique pair of an entering and a leaving index, a pivot rule may suggest a set of admissible index pairs. Generalizing further, a pivot rule may return a probability distribution on the set of sets of feasible index pairs, in which case we call the rule randomized – otherwise, it is deterministic. To this end, we denote the probability simplex of a set $S$ by $\mathrm{\Delta }(S)=\{p\in {[0,1]}^S:{\sum }_{s\in S}p(s)=1\}$. Depending on whether the pivot rule has access to a finite memory of previous steps or not, we call it memory-based or memoryless, respectively. The number of available memory states may depend on the input size, so we denote it by $H_{m,n}$. The following definition gives a unified framework for pivot rules.

Note: we use $𝒫([n])$ for ease of notation. In reality, we are only concerned with the cases where the set $B$ is a feasible basis. We interpret Definition 3.1 as follows. Suppose we apply the simplex method with pivot rule $\mathrm{\Pi }$, the algorithm is currently at basis $B$, and the current memory state of $\mathrm{\Pi }$ is $h$. Then $\mathrm{\Pi }$ updates its memory state to $h^{\prime }$, we draw a set $S\in 𝒫({[n]}^2)$ according to $p$, and we choose one pair $(i,j)\in S$ of entering index $i\in {\mathrm{\Gamma }}^{+}(B)$ and leaving index $j\in B$ yielding the new basis $B\cup \{i\}\backslash \{j\}$. Note that, if $B$ is not a feasible basis for ($L{P}_{A,𝒃,𝒄}$), then we do not pose any restriction on the output of $\mathrm{\Pi }$ (since this will never occur in practice).

Given a pivot rule $\mathrm{\Pi }={\left({\mathrm{\Pi }}_{m,n}\right)}_{n\in \mathbb{N},m\in [n]}$, we may write each ${\mathrm{\Pi }}_{m,n}$ as the composition of an information function $I_{m,n}^{\mathrm{\Pi }}:{ℒ}_{m,n}\times 𝒫([n])\to {\mathrm{\Omega }}_{m,n}^{\mathrm{\Pi }}$, where ${\mathrm{\Omega }}_{m,n}^{\mathrm{\Pi }}$ can be any set, and a decision function $D_{m,n}^{\mathrm{\Pi }}:{\mathrm{\Omega }}_{m,n}^{\mathrm{\Pi }}\times [H_{m,n}]\to \mathrm{\Delta }\left(𝒫({[n]}^2)\right)\times [H_{m,n}]$ such that

for all inputs. There are many ways to decompose a given pivot rule $\mathrm{\Pi }$ into an information and a decision function, for example, we may choose ${\mathrm{\Omega }}_{m,n}^{\mathrm{\Pi }}={ℒ}_{m,n}\times 𝒫([n])$, let $I_{m,n}^{\mathrm{\Pi }}$ be the identity function, and let $D_{m,n}^{\mathrm{\Pi }}={\mathrm{\Pi }}_{m,n}$.

The purpose of this decomposition is to give a natural notion of classes of pivot rules, based on the information they may use. We focus on classes of pivot rules that use combinatorial information, where ${\mathrm{\Omega }}_{m,n}^{\mathrm{\Pi }}$ is a finite set. We can, e.g., create such a class by fixing the set ${\mathrm{\Omega }}_{m,n}$, the information function $I_{m,n}$, and the memory $H_{m,n}$, while allowing any decision function $D_{m,n}$. Of course, the fewer restrictions we pose, the broader the resulting class of pivot rules.

In this paper, we restrict ourselves to deterministic pivot rules, which return deterministic distributions $p\in \mathrm{\Delta }\left(𝒫({[n]}^2)\right)$, i.e., $p(S)=1$ for a unique $S\in 𝒫({[n]}^2)$. Further, we only focus on non-degenerate linear programs, where the leaving index $j$ is always uniquely determined by the entering index $i$, for our lower bounds. Therefore, we will use the simplified notation

in the following; here, if $B$ is a feasible, non-optimal basis, then $i\in S$ implies $i\in {\mathrm{\Gamma }}^{+}(B)$. Traditionally, in the worst-case analysis of pivot rules, the tie-breaking – that is, choosing an element of $S$ – is up to the adversary, whose goal is to establish lower bounds, see e.g. [22] for a discussion on this. Therefore, when proving lower bounds, we may assume that the pivot rule never outputs a tie, as we could fix a tie-breaking otherwise. Then, we have $|S|=1$ and simplify the notation even further by letting the codomain of ${\mathrm{\Pi }}_{m,n}$ be $[n]\times [H_{m,n}]$. If there is only a single memory state, i.e. $H_{m,n}=1$ for all indices $m$ and $n$, we call the pivot rule memoryless, in which case we will also leave out the memory component from the notation.

Most pivot rules from the literature select the best improving variable(s) according to some underlying measure derived from the input data. Such a measure naturally induces a total preorder¹¹1Recall that a binary relation over a set $S$ is a preorder if it is reflexive and transitive. A preorder over $S$ is total on $S^{\prime }\subseteq S$ if any two elements of $S^{\prime }$ are comparable. Thus, a total preorder is a total order without the requirement of antisymmetry, allowing for ties between distinct elements. on the set of improving variables. In our framework, this happens when the information function $I$ has a special structure, in which case we refer to $I$ as a neighbor ranking. Given a finite set $S$, we denote the set of preorders over $S$ by $𝒯(S)$.

Every neighbor ranking allows for a greedy pivot rule.

Now we are ready to introduce the class of ranking-based pivot rules, which generalizes these classical rules by relaxing their greedy behavior and, additionally, allowing the pivot rules to depend on a set $ℛ=\{R^1,\mathrm{\dots },R^k\}$ of neighbor rankings $R^i$. That is, a ranking-based rule should base its decision solely on the relative positions of the improving variables in the preorders $R_{m,n}^i((A,𝒃,𝒄),B)$. However, by definition, a pivot rule outputs improving indices, so it must have access to these indices as well. With this information, it could, say, treat variable $x_5$ differently from $x_8$, or even specify its decision for every basis. To prevent the rule from abusing this knowledge, we add an additional symmetry condition, forcing the rule to only base its decision on the relative positions in the rankings. This is done by ensuring that whenever the rule encounters two equivalent situations with equivalent rankings, it is forced to make equivalent choices.

Every deterministic memoryless pivot rule can be formulated as a ranking-based rule: choose the ranking such that the first improving variables in the ranking are the ones preferred by the pivot rule. Then, choose as the decision function the function that always picks the first variables. This gives an equivalent ranking-based rule.

Recall that the information function, which specifies a tuple of neighbor rankings in the class of ranking-based rules, is always memoryless, while the decision function may be memory-based. As an example, let Bland denote the neighbor ranking that orders by index, then a $\{\text{Bland}\}$-ranking-based pivot rule $\mathrm{\Pi }$ may select the improving variable with the second smallest index. If $\mathrm{\Pi }$ is also memory-based it may, e.g., alternatingly select the improving variable with the smallest and the largest index. We analyze the class of memory-based $\{\text{Bland}\}$-ranking-based rules, which we call index-based rules for short, in Section 4.

Recall that Bland’s rule always picks the improving variable that has the lowest index. In this section, we consider $\{\text{Bland}\}$-ranking-based rules with memory and without ties. Recalling Definition 3.7, these rules take into consideration only the order of the indices of the improving variables, and the current memory state. The purpose of this section is to show that $\{\text{Bland}\}$-ranking-based rules need a superpolynomial number of steps, even when equipped with some memory. We can let the memory only depend on $n$ without losing generality, since we always have $m\le n$, so the number of memory states is always bounded by ${\max }_{m\in [n]}{H}_{m,n}$ if $n$ is constant. We then denote the allowed memory of a pivot rule $\mathrm{\Pi }$ by $H_{m,n}=\mathrm{\ell }(n)$.

Suppose that for some LP with $100$ variables, there is a feasible basis $B$ from which there are $20$ improving moves, and that a $\{\text{Bland}\}$-ranking-based rule picks the improving move with the 12^th lowest index for this basis when the memory state is $5$. The second condition (symmetry requirement) in Definition 3.7 then forces this rule to always pick the 12^th-lowest index whenever there are 100 variables, 20 improving moves, and the memory state is 5. For this reason, the choices of the pivot rule are determined by only three parameters: the number of variables and improving variables, and the memory state.

This means we can write $\mathrm{\Pi }$ in terms of a function $P:{\mathbb{N}}^3\to {\mathbb{N}}^2$, whose inputs represent these three parameters, and its outputs represent the chosen index and the memory update. To be precise, we have $P(k,n,h)\in \{1,2,\mathrm{\dots },k\}\times \{1,2\mathrm{\dots },\mathrm{\ell }(n)\}$, for all $k,n,h\in {\mathbb{N}}^3$. Then ${\mathrm{\Pi }}_{m,n}((A,𝒃,𝒄),B,h)$ is given as follows: if $P(|{\mathrm{\Gamma }}^{+}(B)|,n,h)=(i^{\prime },h^{\prime })$, and $i$ is the $i^{\prime }$-th smallest index in ${\mathrm{\Gamma }}^{+}(B)$, then ${\mathrm{\Pi }}_{m,n}((A,𝒃,𝒄),B,h)=(i,h^{\prime })$. We refer to a function $P$ of this form as an $\mathrm{\ell }$-index-selector function, and we say $P$ induces the $\mathrm{\ell }$-index-based pivot rule ${\mathrm{\Pi }}^P$ in this manner. The function $P$ does not need $m$ as input: for different $m$ the output must still be the same by the second condition of Definition 3.7. Like the so-called normalized-weight rules in [13, Cor. 1.4], index-based rules are universal in the following sense.

Three classical simplex pivot rules are Dantzig’s original pivot rule, Bland’s rule, and the largest-increase rule, which greedily select the improving variable with the largest reduced cost, the smallest global index, and the largest associated objective improvement, respectively; see Observation 3.6. We use the names Bland, Dantzig, and LargestIncrease to refer both to the pivot rules and to the underlying neighbor rankings, see Definition 3.5. Conceptually, as we will see in the following, the inefficient worst-case behavior of these rules [6, 42, 38] arises not merely from their greedy nature but already from the fact that the information they rely on is too limited. More precisely, our main result in this section is that every $\{\text{Bland},\text{Dantzig},\text{LargestIncrease}\}$-ranking-based simplex pivot rule (see Definition 3.7) is at least subexponential. Equivalently, every deterministic, memoryless simplex pivot rule that bases its decision solely on the number of improving variables and their relative rankings by index, reduced cost, and objective improvement requires subexponential time in the worst-case.

Given the close connection between SteepestEdge and ShadowVertex [12], it is natural to ask whether our results can be extended to include these rules as well.

The remainder of this section is devoted to proving that no polynomial $\{\text{Bland},\text{Dantzig},\text{LargestIncrease}\}$-ranking-based pivot rule exists for PolicyIteration. Although ranking-based pivot rules were defined only for the simplex method, the definitions carry over directly via the correspondence between PolicyIteration and the simplex method, see Theorem 2.1. Explicitly, a neighbor ranking assigns to each policy of the Markov decision process a total preorder on the set of its improving switches. Consequently, the following lower bound for PolicyIteration implies Theorem 5.1 since the number of non-zero matrix entries in the induced linear program is linear in the number of transition probabilities in the process, see [47] or [36, Sec. 2.4]. Both theorems together prove Theorem 1.2.

We still assume, as motivated in Section 3, that $\mathrm{\Pi }$ does not return ties. Moreover, in our constructions in this section, the considered neighbor rankings always return total orders on the set of improving variables, that is, there are no ties in ${⪯}_B$.

Let $ℛ=\{R_1,\mathrm{\dots },R_k\}$ be a fixed set of neighbor rankings. Then, by Definition 3.7, a memoryless $ℛ$-ranking-based rule $\mathrm{\Pi }$ bases its decisions only on the neighbor rankings in $ℛ$. Consider the special case where the simplex method is at a basis $B$ such that all neighbor rankings in $ℛ$ induce the same total preorder ${⪯}_B$ on the set of improving neighbors ${\mathrm{\Gamma }}^{+}(B)$, that is, we have ${⪯}_B^{R_1}=\mathrm{\cdots }={⪯}_B^{R_k}={⪯}_B$. In this situation, the only information that $\mathrm{\Pi }$ has about improving switches is their relative positions in the common preorder ${⪯}_B$. At such bases, $\mathrm{\Pi }$ effectively only sees a single ranking of the improving variables. Thus, since $\mathrm{\Pi }$ has no access to the underlying data and due to our symmetry condition in Definition 3.7, its decisions are of the form ‘whenever given 20 improving variables, choose the 12^th-lowest index in ${⪯}_B$’.

We can use a similar idea to $\mathrm{\ell }$-improving functions from Section 4. In the case where all neighbor rankings agree, we can write $\mathrm{\Pi }$ in terms of a function $f_{\mathrm{\Pi }}:\mathbb{N}\to \mathbb{N}$ with $f_{\mathrm{\Pi }}(k)\in \{1,2,\mathrm{\dots },k\}$, for all $k\in \mathbb{N}$, such that ${\mathrm{\Pi }}_{m,n}((A,𝒃,𝒄),B)=i$, where $i$ is the index of the $f_{\mathrm{\Pi }}(|{\mathrm{\Gamma }}^{+}(B)|)$-th smallest improving variable in ${\mathrm{\Gamma }}^{+}(B)$ according to ${⪯}_B$. Note that $f_{\mathrm{\Pi }}$ is independent of $m$ and $n$, since $\mathrm{\Pi }$ does not depend on $m,n$ by Definition 3.7.

Now fix an arbitrary $\{\text{Bland},\text{Dantzig},\text{LargestIncrease}\}$-ranking-based pivot rule $\mathrm{\Pi }$. We analyze the running time of PolicyIteration with pivot rule $\mathrm{\Pi }$ depending on the structure of the function $f_{\mathrm{\Pi }}$, which determines the choice of $\mathrm{\Pi }$ at policies where all three neighbor rankings agree. More precisely, depending on the behavior of $f_{\mathrm{\Pi }}$, we construct four different families of Markov decision processes. Then, we argue that, on each of these families, PolicyIteration with pivot rule $\mathrm{\Pi }$ visits a (sub-)exponential number of policies when started at a suitable initial policy. The common key feature of the constructed families is that the three neighbor rankings agree at each of the visited policies, such that the behavior of $\mathrm{\Pi }$ is fully determined by $f_{\mathrm{\Pi }}$ during the run of the algorithm.

First, we consider the case $f_{\mathrm{\Pi }}\equiv 1$. That is, whenever the neighbor rankings Bland, Dantzig, and LargestIncrease agree, the pivot rule $\mathrm{\Pi }$ chooses the least-preferred improving switch in the common ranking. We prove an exponential lower bound for such $\mathrm{\Pi }$. The core structure of the constructed family of Markov decision processes is based on a lower bound construction for parity games given in [43]. As in Section 4, we divide the processes into levels, or bits, and prove that the algorithm simulates a binary counter. Since $f_{\mathrm{\Pi }}$ selects the least-preferred switch, the main feature of our processes is that improving switches in low levels are less improving than those in higher levels.

Second, we prove a subexponential lower bound for the case $f_{\mathrm{\Pi }}(k)=o(\sqrt{k})$. The key observation for the proof is the following: if $ℳ$ is one of our processes from the first case, where $f_{\mathrm{\Pi }}\equiv 1$, and we copy each of its $n$ actions $n$ times, then we obtain a new process ${ℳ}^{\prime }$ with $n^{\prime }=n^2$ actions such that switching the least-preferred action in $ℳ$ corresponds to switching one of its $n=\sqrt{n^{\prime }}$ copies in ${ℳ}^{\prime }$. Thus, if $n$ is large enough, the condition $f_{\mathrm{\Pi }}(k)=o(\sqrt{k})$ yields that $\mathrm{\Pi }$ on the new process ${ℳ}^{\prime }$ mimics the behavior from the first case. Since the number $n^{\prime }$ of actions in ${ℳ}^{\prime }$ is quadratic in $n$, we obtain a subexponential lower bound of $\mathrm{\Omega }(2^n)=\mathrm{\Omega }(2^{\sqrt{n^{\prime }}})$.