This paper deals with approximation schemes for infinite horizon, discrete time, stochastic optimization problems. We construct finite horizon approximates that yield upper and lower estimates and whose optimal solutions converge to long-term optimal trajectories. The results extend those of [3] from the deterministic case to the stochastic.