  We propose a new method for solving optimal stopping problems (such as
American option pricing in finance) under minimal assumptions on the underlying
stochastic process $X$.
  We consider classic and randomized stopping times represented by linear and
non-linear functionals of the rough path signature $\mathbb{X}^{<\infty}$
associated to $X$, and prove that maximizing over these classes of signature
stopping times, in fact, solves the original optimal stopping problem. Using
the algebraic properties of the signature, we can then recast the problem as a
(deterministic) optimization problem depending only on the (truncated) expected
signature $\mathbb{E}\left[ \mathbb{X}^{\le N}_{0,T} \right]$. By applying a
deep neural network approach to approximate the non-linear signature
functionals, we can efficiently solve the optimal stopping problem numerically.
  The only assumption on the process $X$ is that it is a continuous (geometric)
random rough path. Hence, the theory encompasses processes such as fractional
Brownian motion, which fail to be either semi-martingales or Markov processes,
and can be used, in particular, for American-type option pricing in fractional
models, e.g. on financial or electricity markets.
