The performance of the same type of cloud resources, such as virtual machines (VMs), varies over time mainly due to hardware heterogeneity, resource contention among co-located VMs, and virtualization overhead. The performance variation can be significant, introducing challenges to learn workload-specific resource provisioning policies to automatically scale the cloud-hosted applications to maintain the desired response time. Moreover, auto-scaling multi-tier applications using minimal resources is even more challenging because bottlenecks may occur on multiple tiers concurrently. We address the problem of using performance varying VMs for gracefully auto-scaling a multi-tier application using minimal resources to handle dynamically increasing workloads and satisfy the response time requirements. The proposed system uses a supervised learning method to identify the appropriate resource provisioning for multi-tier applications based on the prediction of the application response time and the request arrival rate. The supervised learning method learns a state transition configuration map which encodes a resource allocation states invariant to the underlying VMs performance variations. This configuration map helps to use performance varying resources in the predictive autoscaling method. Our experimental evaluation using a real-world multi-tier web application hosted on a public cloud shows an improved application performance with minimal resources compared to conventional predictive auto-scaling methods.