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.
The authors adapt CFTP into three primary domains:
- 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.
- 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.
- 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.
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