  We derive and analyze learning algorithms for apprenticeship learning, policy
evaluation, and policy gradient for average reward criteria. Existing
algorithms explicitly require an upper bound on the mixing time. In contrast,
we build on ideas from Markov chain theory and derive sampling algorithms that
do not require such an upper bound. For these algorithms, we provide
theoretical bounds on their sample-complexity and running time.
