This article presents a connection admission control (CAC) algorithm for UMTS networks based on the Markov decision process (MDP) approach. To deal with the non-stationary environment due to the time-varying statistical characteristics of the offered traffic, the admission policy has to be computed periodically based on on-line measurements, and the optimal policy computation is excessively time-consuming to be performed on-line. Thus, this article proposes a reduction of the policy space coupled with an aggregation of the state space for the fast computation of a sub-optimal admission policy. Theoretical results and numerical simulations show the effectiveness of the proposed approach.