We study the problem of optimizing admission control policies in mobile multimedia cellular networks when predictive information regarding movement is available and we evaluate the gains that can be achieved by making such predictive information available to the admission controller. We consider a general class of prediction agents which forecast the number of future handovers and we evaluate the impact on performance of aspects like: whether the prediction refers to incoming and/or outgoing handovers, inaccurate predictions, the anticipation of the prediction and the way that predictions referred to different service classes are aggregated. For the optimization process we propose a novel Reinforcement Learning approach based on the concept of afterstates. The proposed approach, when compared with conventional Reinforcement Learning, yields better solutions and with higher precision. Besides it tackles more efficiently the curse of dimensionality inherent to multimedia scenarios. Numerical results show that the performance gains measured are higher when more specific information is provided about the handover time instants, i.e. when the anticipation time is deterministic instead of stochastic. It is also shown that the utilization of the network is maintained at very high values, even when the highest improvements are observed. We also compare an optimal policy obtained deploying our approach with a previously proposed heuristic prediction scheme, showing that plenty of room for technological innovation exists.