In this paper we consider an operational software system with multi-stage degradation levels due to software aging, and derive the optimal dynamic software rejuvenation policy maximizing the steady-state system availability, via the semi-Markov decision process. Also, we develop a reinforcement learning algorithm based on Q-learning as an on-line adaptive nonparametric estimation scheme without the knowledge of transition rate to each degradation level. In numerical examples, we present how to derive the optimal software rejuvenation policy with the decision table, and investigate the asymptotic behavior of estimates of the optimal software rejuvenation policy with the reinforcement learning.