  We study a stochastic program where the probability distribution of the
uncertain problem parameters is unknown and only indirectly observed via
finitely many correlated samples generated by an unknown Markov chain with $d$
states. We propose a data-driven distributionally robust optimization model to
estimate the problem's objective function and optimal solution. By leveraging
results from large deviations theory, we derive statistical guarantees on the
quality of these estimators. The underlying worst-case expectation problem is
nonconvex and involves $\mathcal O(d^2)$ decision variables. Thus, it cannot be
solved efficiently for large $d$. By exploiting the structure of this problem,
we devise a customized Frank-Wolfe algorithm with convex direction-finding
subproblems of size $\mathcal O(d)$. We prove that this algorithm finds a
stationary point efficiently under mild conditions. The efficiency of the
method is predicated on a dimensionality reduction enabled by a dual
reformulation. Numerical experiments indicate that our approach has better
computational and statistical properties than the state-of-the-art methods.
