We consider a nearest-neighbor random walk on $\mathbb{Z}$ whose probability $w(x,n)$ to jump to the right from site $x$ depends not only on $x$ but also on the number of prior visits $n$ to $x$. The collection $\{w(x,n): x, n \text{ are integers, } n \text{ is non-negative}\}$, is sometimes called a "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 probability according to the "flavor" of the cookie eaten. Assume that the cookie stacks are i.i.d. and that the cookie "flavors" at each stack $w(x,n)$, $n=0,1,\ldots$ follow a finite state Markov chain in $n$. 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 random walk time. We discuss recurrence/transience, ballisticity, and limit theorems for such walks. This is a joint work with Jonathon Peterson, Purdue University.