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.
Figures & tables
Figure 1: Top: 6L -transition paths from si to si+1 and from sˉi to sˉi+1 , with labels before and after each slash, respectively. Arrows without a length label represent paths of length L . The upper 2L arrow represents either the path through si,5 with a0 at both si,4 and si,5 , or the a0 path from sˉi,4 to sˉi+1 . Bottom: action choices and path lengths at si,4,si,5,sˉi,4 .
Action a0
Action a1
Set
Starting state
Endpoint
Length
Endpoint
Length
si/sˉi
si+1/sˉi+1
6L
si,1/sˉi,1
L
si,j/sˉi,j
si+1/sˉi+1
(6−j)L
si,j+1/sˉi,j+1
L
si,4
si,5
L
sic
2L
si,5
si+1
L
siz
L
sˉi,4
sˉi+1
2L
si
L
Table 1: Paths from S1 , S2 , and S3 . Here 0≤i<d except in the row explicitly indexed by −1 , and 1≤j≤3 in the second row of the S1 block. Slashes separate corresponding states, as in si/sˉi . A dash indicates an unavailable action.
Figure 2: Selected paths and bit choices during the five iterations from π[b] to π[b+] . Circles denote states, and arrows represent paths selected by the current policy. Within each panel, the upper and lower rows show the first and second groups, respectively.
State
πt
πt+1
πt+2
πt+3
πt+4
πt+5
si
[b]i
1
[b+]i
[b+]i
[b+]i
[b+]i
si,1
1
1
[b+]i
[b+]i
[b+]i
1
si,2
1
1
[b+]i
[b+]i
1
1
si,3
1
1
[b+]i
1
1
1
si,4
0
\mathds1{i<k}
0
0
0
0
si,5
0
\mathds1{i>k,[b]i=0}
0
0
0
0
Table 2: Policy choices at all states with two actions during one binary increment. Entries 0,1 denote a0,a1 . Here 0≤i<d , 0≤j≤2 , k=min{i:[b]i=0} , and \mathds1{⋅} denotes the indicator. All remaining states have only action a0 .