This paper studies an optimal policy for a certain class of (s, S) inventory control systems, where the demands are characterized by the renewal arrival process. To minimize the average cost over a simulation period, we apply a stochastic optimization algorithm which uses the gradients of parameters, s and S. We obtain the gradients of objective function with respect to ordering amount S and reorder point s via a combined perturbation method. This method uses the infinitesimal perturbation analysis and the smoothed perturbation analysis alternatively according to occurrences of ordering event changes. The optimal estimates of s and S from our simulation results are quite accurate. We consider that this may be due to the estimated gradients of little noise from the regenerative system simulation, and their effect on search procedure when we apply the stochastic optimization algorithm. The directions for future study stemming from this research pertain to extension to the more general inventory system with regard to demand distribution, backlogging policy, lead time, and inter-arrival times of demands. Another direction involves the efficiency of stochastic optimization algorithm related to searching procedure for an improving point of (s, S).