  We consider the problem of learning an inner approximation of the region of
attraction (ROA) of an asymptotically stable equilibrium point without an
explicit model of the dynamics. Rather than leveraging approximate models with
bounded uncertainty to find a (robust) invariant set contained in the ROA, we
propose to learn sets that satisfy a more relaxed notion of containment known
as recurrence. We define a set to be $\tau$-recurrent (resp. $k$-recurrent) if
every trajectory that starts within the set, returns to it after at most $\tau$
seconds (resp. $k$ steps). We show that under mild assumptions a
$\tau$-recurrent set containing a stable equilibrium must be a subset of its
ROA. We then leverage this property to develop algorithms that compute inner
approximations of the ROA using counter-examples of recurrence that are
obtained by sampling finite-length trajectories. Our algorithms process samples
sequentially, which allow them to continue being executed even after an initial
offline training stage. We further provide an upper bound on the number of
counter-examples used by the algorithm, and almost sure convergence guarantees.
