Source-linked AI summary
Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy
Han Zhong, Yinyu Ye
TL;DR
Whether Howard’s policy iteration is strongly polynomial for deterministic MDPs when the discount factor is part of the input remained open, while known guarantees for fixed discounts depended on the discount. The paper constructs deterministic discounted MDP families with at most two actions per state and analyzes Howard’s policy iteration from specified initial policies. At least exp(Ω(N)) iterations occur on some N-state instances, and at least exp(Ω(N^1/4)) iterations persist with nonnegative integer rewards smaller than 4N.
Problem
Whether Howard’s policy iteration is strongly polynomial for deterministic MDPs when the discount factor is part of the input remained open, while known guarantees for fixed discounts depended on the discount.
Source: §1 · p. 1Method
The paper constructs deterministic discounted MDP families with at most two actions per state and analyzes Howard’s policy iteration from specified initial policies.
Source: §1 · p. 2Results
At least exp(Ω(N)) iterations occur on some N-state instances, and at least exp(Ω(N^1/4)) iterations persist with nonnegative integer rewards smaller than 4N.
Source: §1 · p. 2Takeaways & Limitations
The results rule out strong polynomiality for Howard’s rule in this setting and contrast its simultaneous local improvements with Dantzig’s coordinated single-state updates.
Source: §1 · pp. 1–2For integer d≥3, the construction assumes F_i,G_i∈Z[x] (0≤i<d), F_0(x)>0 near 1 from below, and f_0=1, f_i≥2f_{i−1}, g_0≥4f_{d−1}, g_i≥2g_{i−1} (1≤i<d).
Source: §2 · p. 2
Abstract
from arXiv · showhide
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.
1 Introduction
The paper shows that Howard’s policy iteration can require exponentially many iterations on deterministic discounted MDPs with at most two actions per state, with a stretched-exponential lower bound even for logarithmic-bit rewards. This contrasts with Dantzig’s strongly polynomial rule and highlights the cost of simultaneous local improvements.
1 Introduction
- At each iteration, Howard’s policy iteration evaluates the current policy and uses its action values to select the next policy, stopping when the policy no longer changes.The stopping policy is optimal.Source: §1 · p. 1
- Previous exponential lower bounds used stochastic transitions and a growing number of actions, while no superpolynomial bound was known for a constant action count.Prior deterministic-MDP lower bounds were quadratic.Source: §1 · p. 2
- At least exp(Ω(N)) iterations are required from a specified initial policy on some N-state deterministic discounted MDPs with at most two actions per state.Each instance has encoding length O(N^2).Source: §1 · p. 2
- At least exp(Ω(N^1/4)) iterations persist when rewards are nonnegative integers smaller than 4N, requiring only O(log N) bits per reward.The instances have encoding length O(N log N).Source: §1 · p. 2
- Howard’s simultaneous local improvements contrast with Dantzig’s single-state choice of the largest positive gain, which is strongly polynomial for deterministic MDPs independently of the discount.The paper frames this gap as a “price” of algorithmic anarchy.Source: §1 · pp. 1–2
2 Construction of the MDPs
The construction uses polynomial families and degree-based parameters to build an MDP from action-selected paths, with intermediate states and path-specific rewards.
2 Construction of the MDPs
- The construction begins with polynomial families whose near-1 behavior and limits satisfy specified conditions, including a positivity condition and a sequence of growth inequalities.The setup fixes an integer d ≥ 3 and requires f_i ≥ 2f_(i−1) and g_0 ≥ 4f_(d−1), with subsequent g_i at least doubling.Source: §2 · p. 2
- The path-length scale L is set to 2 plus the maximum degree among the F_i and G_i polynomials.This makes L at least 2.Source: §2 · p. 2
2.1 Formal construction
- Each action from a state in S1, S2, or S3 selects a path to a specified endpoint, with length a positive multiple of L and distinct intermediate states comprising S4.The paths’ intermediate states are introduced separately for each state-action pair.Source: §2.1 · p. 3
- Before the uniform reward shift, actions from S1, S2, and S3 have zero immediate reward; nonzero rewards occur only at intermediate states and follow rules determined by each path’s starting set.The construction specifies intermediate rewards for paths of the stated lengths.Source: §2.1 · p. 3
- The formal routes include 6L-transition paths from s_i to s_(i+1) and from barred s_i to barred s_(i+1), with an upper 2L branch in the illustrated choices.The figure also depicts action choices and path lengths at s_(i,4), s_(i,5), and barred s_(i,4).Source: §2.1 · p. 3, Figure 1 · p. 4
3. Paths starting in S3. Set
The construction encodes binary vectors as policies with strictly increasing values at two states for discounts sufficiently close to one. Howard’s iteration follows these policies through binary increments, taking five iterations per increment.
3. Paths starting in S3. Set
- Adding rmax to every reward preserves action comparisons, while the initial policy selects a1 at sd and the specified states and a0 elsewhere.The uniform shift makes final rewards nonnegative without changing value differences.Source: §3 · p. 4
2.2 Binary encoding and policy values
- Each vector b encodes bit choices in paired states s_i and ¯s_i, whose selected paths form two cycles of length (6d + 1)L.A zero bit selects a0 on both paths; a one bit selects the specified paths through intermediate states, each totaling 6L transitions.Source: §2.2 · pp. 4–5
- For γ sufficiently close to one, the 2^d policies have strictly increasing values at s0 and ¯s0 in binary order.A common threshold γ0 suffices for every encoding b other than the all-ones vector.Source: §2.2 · pp. 5–6
- For a one bit, the paired paths have zero rewards for their first 4L transitions, and the second reward sequence contributes −γ^L times the first sequence’s discounted reward.The contributions of set bits are summed over a cycle to compare the values of successive encodings.Source: §2.2 · pp. 5–6
- Five iterations per increment through the first 2^d − 2 binary increments yield Ω(2^d) policy-iteration steps from π[0].The 2^d encoded policies are listed in binary order.Source: §2.2 · p. 6
3 Binary counting under policy iteration
This section develops how Howard’s policy iteration implements a binary increment through successive simultaneous updates, including forming a new cycle and transferring the incremented encoding between groups. It verifies that one discount preserves the required action comparisons, then derives an iteration lower bound and contrasts Howard’s bit changes with Dantzig’s trajectory on a four-bit instance.
3 Binary counting under policy iteration
- Five simultaneous iterations transform policy π[b] into π[b+], advancing the binary encoding by one increment.Figure 2 tracks the selected paths and bit choices during this update.Source: §3 · p. 6, Figure 2 · p. 7
3.1 Iteration 1: identify the zero positions of b+
- Iteration 1 sets every si to a1 and routes si,4 through S2 exactly at the zero positions of b+.The choices at si,4 distinguish positions before the first group encodes b+ in the following iteration.Source: §3.1 · pp. 8, 10
3.2 Iteration 2: encode b+ in the first group
- In Iteration 2, every si still chooses a1, while paths from si,4 enter S2 exactly where b+ has zero bits; paths from ¯si remain unchanged.Thus the first group encodes b+ while the second group retains its previous paths.Source: §3.2 · p. 11
- Iteration 2 sets actions in the first group according to b+, while restoring a0 at si,4, si,5, sd, and the specified auxiliary states.The resulting policy also sets the barred-state actions according to b and sets a1 at barred states 2 and 3.Source: §3.2 · pp. 12–13
3.3 Iteration 3: form the new cycle
- Iteration 3 forms a new cycle encoding b+ while preserving the cycle encoding b, with policy updates selecting a1 at sd.The updates also leave specified intermediate states on a0 or a1 paths without altering either encoded cycle.Source: §3.3 · pp. 13–14
3.4 Iteration 4: connect to the new cycle
- At t+3, eV values at si and ¯si equal those under policies encoding b+ and b, respectively; Δπt+3(¯si)=γ⁴LRi(γ)>0 and Δπt+3(¯si,j)=γ⁽⁴−j⁾LRi(γ)>0 for 1≤j≤3.Source: §3.4 · pp. 14–15
3.5 Iteration 5: encode b+ in the second group
- Iteration 5 begins with the cycle through s0 still encoding b+ and barred fourth states and S3 choosing a1, then derives action-value gaps for transferring b+ to the barred group.The barred-state value gap is 8fd−1(γ)(1 −γ6L) for i < d −1 and 8fd−1(γ)(1 −γ7L) for i = d −1.Source: §3.5 · p. 15
- The updated action choices match π[b+], completing the encoding of the next binary value.At sd, the action switches to a1.Source: §3.5 · p. 16
3.6 Completing the proof
- At least 5(2d - 2) >= 2d iterations follow by induction from π0 = π[0], since each five-step block maps π[b] to π[b+].Source: §3.6 · p. 17
- O(N + log rmax) bits suffice for the discount, which preserves strict action comparisons and the inequalities in Lemma 2.1.The same discount applies to every binary increment.Source: §3.6 · p. 17
- On the d = 4 instance, Dantzig’s rule can change bits in order 0000 → 1000 → 1100 → 1110 → 1111, with each bit changing once.Howard’s rule repeatedly changes bits to implement successive binary increments.Source: §3.6 · p. 17
4 Proofs of the lower bounds
The proofs choose reward polynomials to control state counts, reward magnitudes, and encoding length while establishing large iteration lower bounds. They yield an exp(Ω(N)) bound and, with logarithmic-bit rewards, an exp(Ω(N^1/4)) bound.
4 Proofs of the lower bounds
- The proof chooses reward polynomials to determine the number of states, reward magnitudes, and input length.For Theorem 1.1, the selected polynomials give N = Θ(d) and rewards and discount with O(d) bits.Source: §4 · p. 17, §4.1 · p. 17
4.1 Proof of Theorem 1.1
- At least exp(Ω(N)) iterations occur for a deterministic family with at most two actions per state and encoding length O(N^2).The construction uses rewards and a common discount requiring O(d) bits, with N = Θ(d).Source: §4.1 · p. 17
4.2 Proof of Theorem 1.2
- The lower bound implies at least exp(Ω(N^(1/4))) iterations; with at most two actions per state, the total encoding length is O(N log N).Each reward and successor index uses O(log N) bits, while the common discount uses O(N) bits; N = O(d^4).Source: §4.2 · p. 18
5 Further results and concluding remarks
The paper gives an explicit family with an N^Ω(log N) iteration lower bound under a logarithmic reward-size restriction, alongside its exponential and stretched-exponential bounds. These iteration barriers also apply to halving the initial optimality gap, while the authors report that AI-assisted material was independently reviewed.
5 Further results and concluding remarks
- With logarithmic-bit rewards, the paper establishes a stretched-exponential lower bound and an explicit family requiring at least N^Ω(log N) iterations.The explicit family has nonnegative integer rewards smaller than 4N, encoding length O(N log N), and a polynomial-time construction.Source: §5 · p. 19
- The same lower bounds apply even to halving the initial optimality gap at s0; Dantzig’s rule reaches an optimal policy in polynomially many iterations.The explicit family’s count is 2m², with N = Θ(m^3 4^m).Source: §5 · p. 19
AI use statement
- The authors report using generative AI for derivations, literature searches, proof checking, language editing, and LaTeX formatting, then independently verifying the mathematical arguments.They state that they take full responsibility for the paper.Source: AI use statement · p. 20