Jump to Content

Unknown mixing times in apprenticeship and reinforcement learning

Tom Zahavy
Haim Kaplan
Yishay Mansour
ICML 2019 (2020)


We derive and analyze learning algorithms for policy evaluation, policy gradient and apprenticeship learning for the 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.

Research Areas