  We study stochastic optimization algorithms for constrained nonconvex
stochastic optimization problems with Markovian data. In particular, we focus
on the case when the transition kernel of the Markov chain is state-dependent.
Such stochastic optimization problems arise in various machine learning
problems including strategic classification and reinforcement learning. For
this problem, we study both projection-based and projection-free algorithms. In
both cases, we establish that the number of calls to the stochastic first-order
oracle to obtain an appropriately defined $\epsilon$-stationary point is of the
order $\mathcal{O}(1/\epsilon^{2.5})$. In the projection-free setting we
additionally establish that the number of calls to the linear minimization
oracle is of order $\mathcal{O}(1/\epsilon^{5.5})$. We also empirically
demonstrate the performance of our algorithm on the problem of strategic
classification with neural networks.
