  We consider a nearest-neighbor random walk on $\mathbb{Z}$ whose probability
$\omega_x(j)$ to jump to the right from site $x$ depends not only on $x$ but
also on the number of prior visits $j$ to $x$. The collection
$(\omega_x(j))_{x\in\mathbb{Z},n\ge 0}$ is sometimes called the "cookie
environment" due to the following informal interpretation. Upon each visit to a
site the walker eats a cookie from the cookie stack at that site and chooses
the transition probabilities according to the "strength" of the cookie eaten.
We assume that the cookie stacks are i.i.d. and that the cookie "strengths"
within the stack $(\omega_x(j))_{j\ge 0}$ at site $x$ follow a finite state
Markov chain. Thus, the environment at each site is dynamic, but it evolves
according to the local time of the walk at each site rather than the original
random walk time.
  The model admits two different regimes, critical or non-critical, depending
on whether the expected probability to jump to the right (or left) under the
invariant measure for the Markov chain is equal to $1/2$ or not. We show that
in the non-critical regime the walk is always transient, has non-zero linear
speed, and satisfies the classical central limit theorem. The critical regime
allows for a much more diverse behavior. We give necessary and sufficient
conditions for recurrence/transience and ballisticity of the walk in the
critical regime as well as a complete characterization of limit laws under the
averaged measure in the transient case.
  The setting considered in this paper generalizes the previously studied model
with periodic cookie stacks. Our results on ballisticity and limit theorems are
new even for the periodic model.
