Software rejuvenation is a preventive and proactive maintenance solution that is particularly useful for counteracting the phenomenon of software aging. Hence, it should be ideally triggered adaptively without the complete knowledge on system failure (degradation) time distribution in operational phase. In this paper we consider an operational software system with multiple degradation levels and derive the optimal software rejuvenation policy maximizing the steady-state system availability, via the semi-Markov decision process. We develop a statistically non-parametric algorithm to estimate the optimal software rejuvenation schedule. Then, the reinforcement learning algorithm, called Q learning, is used for developing an on-line adaptive algorithm. A numerical example is presented to investigate asymptotic behavior of the resulting on-line adaptive algorithm.