  In this paper, we present a discrete-type approximation scheme to solve
continuous-time optimal stopping problems based on fully non-Markovian
continuous processes adapted to the Brownian motion filtration. The
approximations satisfy suitable variational inequalities which allow us to
construct $\epsilon$-optimal stopping times and optimal values in full
generality. Explicit rates of convergence are presented for optimal values
based on reward functionals of path-dependent SDEs driven by fractional
Brownian motion. In particular, the methodology allows us to design concrete
Monte-Carlo schemes for non-Markovian optimal stopping time problems as
demonstrated in the companion paper by Bezerra, Ohashi and Russo.
