# Unknown mixing times in apprenticeship and reinforcement learning

arXiv: https://arxiv.org/abs/1905.09704 · HTML: https://mlsanity.com/paper/1905.09704/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2019.

## Built on by (most cited first, 7 of 7)

- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Discovering Policies with DOMiNO: Diversity Optimization Maintaining Near Optimality](https://mlsanity.com/paper/2205.13521/) (2022)
- [Discovering a set of policies for the worst case reward](https://mlsanity.com/paper/2102.04323/) (2021)
- [Discovering Diverse Nearly Optimal Policies with Successor Features](https://mlsanity.com/paper/2106.00669/) (2021)
- [Inverse Reinforcement Learning with the Average Reward Criterion](https://mlsanity.com/paper/2305.14608/) (2023)
- [Transportation-Inequalities, Lyapunov Stability and Sampling for Dynamical Systems on Continuous State Space](https://mlsanity.com/paper/2205.12448/) (2022)
- [Concentration Phenomenon for Random Dynamical Systems: An Operator Theoretic Approach](https://mlsanity.com/paper/2212.03670/) (2022)

## Abstract (arXiv)

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.