Systems described herein may dynamically add one or more proxy data protection agents to a cloud data storage system to process a data protection job. Upon completion of the job or at some other appropriate interval, the system can power down and decommission the proxy data protection agents and/or the virtual machines on which the data protection proxies reside according to a cleanup schedule (e.g., at hourly or minute intervals). In order to improve the allocation of computing resources, the system takes into account currently existing proxies or virtual machines when processing a backup request to determine the need for new proxies to service the backup request. In this manner the system can save costs and computing resources through efficient virtual machine deployment and retirement.