Many stochastic optimization problems are solved using the renewal reward theorem (RRT). Once a regenerative cycle is identified, the objective function is formed as the ratio of the expected cycle cost to the expected cycle time and optimized using the standard techniques. Application of the RRT requires only the first moments of the cycle-related random variables. However, if the start of a cycle corresponds to an important event, e.g., end of a period of shortages in an inventory problem, knowing only the expected time—and the cost—of the cycle may not give enough information on the functioning of the stochastic system. For example, it may be useful to know the probability that the cycle cost, or more importantly, the average cost per unit time will exceed predetermined levels. In this paper we provide a complete description of the cycle-related random variables for a stochastic inventory problem with supply interruptions. We assume a general phase-type distribution for the supplier's availability (ON) periods and an exponential distribution for the OFF periods. The first passage time of an embedded Markov chain of the ON/OFF process is used to develop the expressions for the exact distribution and the moments of the cycle time and cycle cost random variables. We then describe a method for computing the probability that the average cost per unit time will exceed a predetermined level. This method is used to construct an “efficient frontier” for the two criteria of (i) average cost and (ii) the probability of exceeding it. The efficient frontier is used to find a solution to the multiple-criteria optimization problem.