A superpolynomial lower bound for strategy iteration based on snare memorization

This paper presents a superpolynomial lower bound for the recently proposed snare memorization non-oblivious strategy iteration algorithm due to Fearnley. Snare memorization is a method to train strategy iteration techniques to remember certain profitable substrategies and reapply them again. We show that there is not much hope to find a polynomial-time algorithm for solving parity games by applying such non-oblivious techniques.