Unknown mixing times in apprenticeship and reinforcement learning

Tom Zahavy, Alon Cohen, Haim Kaplan, Yishay MansourUAI 2020 · OpenReview

Abstract: 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 of the underlying Markov process. This paper introduces algorithms that utilize "Coupling From The Past" (CFTP) to obtain unbiased samples without prior knowledge of the mixing time, providing stronger theoretical guarantees and improved practical efficiency.

Introduction

In Reinforcement Learning (RL), many real-world control problems—such as power grid management or elevator scheduling—are best modeled as infinite-horizon tasks where the objective is to maximize the average reward in a steady state. A fundamental challenge in these "average-reward" settings is the mixing time ($T_{mix}$), which represents the time required for the system to reach its stationary distribution.

Standard algorithms typically require a predefined upper bound on $T_{mix}$. This requirement creates a significant bottleneck: an underestimate leads to biased results, while an overestimate results in computational inefficiency. This paper addresses this "blind spot" by introducing algorithms that do not require prior knowledge of the mixing time, leveraging the "Coupling From The Past" (CFTP) technique to achieve unbiased sampling.

Methods and the CFTP Framework

The core innovation of this work is the application of Coupling From The Past (CFTP) to RL. CFTP is a technique from Markov chain theory designed to produce "perfect" samples from a stationary distribution.

The intuition behind CFTP involves simulating the system from every possible starting state at a point in the distant past. If all these trajectories "coalesce" (merge into the same state) by time zero, that state is guaranteed to be an unbiased sample from the stationary distribution.

Algorithm 1: Coupling from the past (CFTP) provides a framework for perfect sampling without knowing mixing times.

The authors adapt CFTP into three primary domains:

  1. Apprenticeship Learning (AL): By extending the Multiplicative Weights Apprenticeship Learning (MWAL) algorithm, the authors use CFTP to obtain unbiased estimates of an expert's feature expectations without guessing the observation duration.
  2. Policy Evaluation: The paper proposes estimating the difference in average rewards between two policies by running trajectories until they coalesce. This approach avoids calculating absolute rewards for each policy individually.
  3. Policy Gradient: The authors derive an unbiased estimator for the policy gradient under average-reward criteria, a task traditionally plagued by bias when mixing times are unknown.

Theoretical Insights

  • Perfect Sampling: Unlike standard Markov Chain Monte Carlo (MCMC) methods that only asymptotically approach the target distribution, CFTP provides a definitive signal when a perfect sample has been obtained.
  • Eliminating Parameter Tuning: CFTP allows algorithms to "discover" the necessary simulation length automatically, removing the need for practitioners to guess $T_{mix}$.
  • Computational Complexity: The authors prove that the expected time for coalescence is $O(|S|T_{mix})$, where $|S|$ is the state space size. This establishes a formal link between mixing time and computational cost.
  • Unbiased Differences: A key theoretical contribution (Lemma 7) demonstrates that reward differences can be estimated by starting policies at the same state and accumulating rewards until their paths merge.

Experimental Evaluation

The authors evaluate their approach using a synthetic two-state Markov Reward Process. This setup allows for a clear demonstration of the bias-variance trade-offs inherent in "guessing" mixing times versus using CFTP.

Experimental results on a two-state chain comparing CFTP (Propp-Wilson) against various fixed-time guessing strategies.

The results show that CFTP-based approaches (labeled as Propp-Wilson in the figures) achieve zero bias. In contrast, strategies that guess the mixing time ($T_{guess}$) suffer from significant Mean Squared Error (MSE) if the guess is inaccurate. Furthermore, when $T_{guess}$ is set high enough to minimize bias, it becomes significantly less sample-efficient than the CFTP approach.

Conclusion and Future Work

This paper provides the first sample complexity bounds for apprenticeship learning in average-reward settings that do not require prior knowledge of mixing times. While the theoretical results are robust, a primary limitation is the dependency on the state-space size, as standard CFTP requires simulating from every state. Future research could explore "Monotone CFTP" or other variants to scale these unbiased methods to high-dimensional or continuous state spaces common in modern deep RL.

Summary updated

Abstract

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 th...
BibTeX
@inproceedings{zahavy2020unknown,
  author = {Tom Zahavy and Alon Cohen and Haim Kaplan and Yishay Mansour},
  title = {{Unknown mixing times in apprenticeship and reinforcement learning}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=8lsNksCQsf},
}
Figure