Unknown mixing times in apprenticeship and reinforcement learning
This work addresses a practical limitation for researchers and practitioners in reinforcement learning by removing the dependency on mixing time bounds, though it appears incremental as it builds on existing Markov chain theory.
The paper tackles the problem of requiring prior knowledge of mixing time bounds in apprenticeship and reinforcement learning algorithms by deriving new sampling algorithms that eliminate this need, providing theoretical bounds on sample complexity and running time.
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.