  We adopt a policy optimization viewpoint towards policy evaluation for robust
Markov decision process with $\mathrm{s}$-rectangular ambiguity sets. The
developed method, named first-order policy evaluation (FRPE), provides the
first unified framework for robust policy evaluation in both deterministic
(offline) and stochastic (online) settings, with either tabular representation
or generic function approximation. In particular, we establish linear
convergence in the deterministic setting, and
$\tilde{\mathcal{O}}(1/\epsilon^2)$ sample complexity in the stochastic
setting. FRPE also extends naturally to evaluating the robust state-action
value function with $(\mathrm{s}, \mathrm{a})$-rectangular ambiguity sets. We
discuss the application of the developed results for stochastic policy
optimization of large-scale robust MDPs.
