Cloud computing provides the flexible delivery of computing services in a pay-as you-go manner. Customers are allowed to easily scale their infrastructure and save on the overall cost of operation. Allowing instantaneous access and flexible scaling while maintaining the service leaves and offering competitive prices poses a significant challenge to Cloud computing providers. Furthermore services will remain available only if this business generates a stable revenue stream. For these challenges we introduce novel policy-based service admission control models that is aimed at maximizing the revenue of Cloud providers while taking informational uncertainty regarding resource requirements into account. Our evaluation shows that policy-based approaches statistically and significantly outperform first come first serve approaches, which are still state of the art.