Optimal Finite Memory Learning Algorithms for the Finite Sample Problem