Energy storage is widely used in many fields, for instance, electrical grid, electric vehicles, portable devices and so forth. Rechargeable batteries such as lithium-ion, lithium-oxygen, sodium-ion, lead acid, and more broadly, supercapacitors, are highly needed to achieve high capacity and long duration while maintaining low cost. An essential task of battery research and development, in both industry and academia, and for both simulation and experiment, is to optimize the parameters for best performance. A special property of battery cycling optimization is that we evaluate the performance as a function of cycles when calculating the score of the objective function. A huge challenge is the difficulty to query the objective function due to the cost to obtain the performance, i.e., long cycling time (in both simulation and experiment) causes battery optimization to be a time-consuming task. What is worse, the space of parameter is often large and thus a great number of queries are necessary. To shorten computation time in simulation, or reduce cost in experiment, we require powerful optimization algorithms. We aim for an asynchronously parallel algorithm which considers early stopping and is flexible to incorporate prior knowledge of the batteries. Our optimization algorithm consists of two major components, a predictor and a sampler. For battery cycling, some information is revealed before finishing all cycles, thus the predictor can predict the final outcome with uncertainty based on existing information. The uncertainty of the prediction is described by a probability distribution. The sampler determines new query points based on existing observations; the observations include finished cycles and predictions from the predictor. The next searching points are those with highest expected improvement over existing query points. We compare our algorithm with current optimization methods to show significant reduction of optimization time.