Abstract: A stochastic gradient algorithm for average reward Markov decision processes (MDP) that depends on a parameter vector is proposed.A new gradient of the object function is given and a stochastic approximation algorithm that bases on a single sample path is presented.Finally,a convergence of the gradient (with probability 1) is provided.