<p>More and more enterprises are increasingly gaining technical and economic benefits from the global cloud marketplace. A multi-cloud environment makes it possible to orchestrate the access and management of multiple cloud resources at the global scale. Cloud service brokers can be regarded as the ntermediate to discover, integrate, aggregate, customize, and optimize cloud services, e.g. Infrastructure as a Service (IaaS), from different cloud providers. However, the existing cloud brokering schemes rarely consider the optimization techniques of deploying cloud services with respect to various criteria, such as cost and performance. In this talk, we present some of our works using AI based approaches to the multi-cloud service brokering problem, i.e. selecting and leasing virtual machines (VMs) for cloud users with minimal cost and network latency. Experimental studies using real-world datasets show that our approaches with problem-tailored solution representation, efficient performance measurement, and smart solution initialization strategies can significantly outperform many existing approaches proposed in the literature.</p>