Large-scale battery storage will become an essential part of the future smart grid. This paper investigates the optimal bidding strategy for battery storage in power markets. Battery storage could increase its profitability by providing fast regulation service under a performance-based regulation mechanism, which better exploits a battery's fast ramping capability. However, battery life might be decreased by frequent charge-discharge cycling, especially when providing fast regulation service. It is profitable for battery storage to extend its service life by limiting its operational strategy to some degree. Thus, we incorporate a battery cycle life model into a profit maximization model to determine the optimal bids in day-ahead energy, spinning reserve, and regulation markets. Then a decomposed online calculation method to compute cycle life under different operational strategies is proposed to reduce the complexity of the model. This novel bidding model would help investor-owned battery storages better decide their bidding and operational schedules and investors to estimate the battery storage's economic viability. The validity of the proposed model is proven by case study results.