Semi-Markov decision processes (SMDP) are continu- ous time generlizations of discrete time Markov Decision Process. A number of value and policy iteration algorithms have been developed for the solution of SMDP problem. But solving SMDP problem requires prior knowledge of the de- terministic kernels, and suffers from the curse of dimension- ality. In this paper, we present the steepest descent direction based on a family of parameterized policies to overcome those limitations. The update rule is based on stochastic policy gradients employing Amari's natural gradient ap- proach that is moving toward choosing a greedy optimal action. We then show considerable performance improve- ments of this method in the simple two-state SMDP problem and in the more complex SMDP of call admission control problem.