Multi-excited random walks on regular trees

We investigate the recurrence/transience property of a particular class of self interacting random walks called "cookie random walks". These processes have been given particular attention in the lattice cases Z and Z^d. We here consider a similar model when the state space is a regular tree. We show that such a walk can be recurrent or transient depending on the underlying cookie environment and that the limiting behaviour of the walk depends strongly on the order of the cookies in the pile (which contrast with the one-dimensional setting). The main ingredient for this study is a construction of a branching Markov chain closely related to the local time process of the walk.