The main goal of this paper is to develop accuracy estimates for stochastic programming problems by employing robust stochastic approximation (SA) type algorithms. To this end we show that while running a Robust Mirror Descent Stochastic Approximation procedure one can compute, with a small additional effort, lower and upper statistical bounds for the optimal objective value. We demonstrate that for a certain class of convex stochastic programs these bound are comparable in quality with similar bounds computed by the sample average approximation method, while their computational cost is considerably smaller.