We introduce a new face representation, the shape Trace transform (STT), for recognizing faces in an authentication system. The STT offers an alternative representation for faces that has a very high discriminatory power. We estimate the dissimilarity between two shapes by a new measure we propose, the Hausdorff context. The reinforcement learning is used to search the optimal parameters of the algorithm, for which the within-class variance of the STT is minimized. This research demonstrates that the proposed method provides a new way for face representation. Our system is verified with experiments on the XM2VTS database.