Paper by: Peter Frazier and Angela Yu (NIPS 2007).

Meta-complexity refers to the study of complexity of problems that are themselves about computational complexity. The canonical meta-complexity problem in the Boolean world is MCSP (Minimum Circuit Size Problem).

We consider two-player stochastic games on a graph. Two-player stochastic games are a generalization of  two-player games and Markov decision processes. Each state in the graph is controlled by one of the two players P1 and P2.

The "nearest neighbor (NN) classifier" labels a new data instance by taking a majority vote over the k most similar instances seen in the past. With an appropriate setting of k, it is capable of modeling arbitrary decision rules.