This paper proposes a Reinforcement Learningbased lexicographic approach to the Call Admission Control (CAC) problem in communication networks. The CAC problem is modeled as a multi-constrained Markov Decision Problem (MDP). To overcome the problems of the standard approaches to the solution of constrained MDP, a multiconstraint lexicographic approach is defined, and an on-line implementation based on Reinforcement Learning techniques is proposed. Simulations validate the proposed approach. © 2013 IEEE.