  We prove the almost sure invariance principle with rate $o(n^{\varepsilon})$
for every $\varepsilon > 0$ for H\"older continuous observables on nonuniformly
expanding and nonuniformly hyperbolic transformations with exponential tails.
Examples include Gibbs-Markov maps with big images, Axiom A diffeomorphisms,
dispersing billiards and a class of logistic and H\'enon maps. The best
previously proved rate is $O(n^{1/4} (\log n)^{1/2} (\log \log n)^{1/4})$.
  As a part of our method, we show that nonuniformly expanding transformations
are factors of Markov shifts with simple structure and natural metric (similar
to the classical Young towers). The factor map is Lipschitz continuous and
probability measure preserving. For this we do not require the exponential
tails.
