Penn Researchers Crack RL's Replicability Problem Beyond Simple Tabular Settings
A team from Penn and Johns Hopkins built the first provably replicable reinforcement learning algorithms that work beyond toy tabular settings.
Takeaways
- First provably replicable RL algorithms extending beyond tabular settings, targeting linear Markov decision processes.
- Two new primitives: replicable ridge regression with random designs and replicable PSD covariance estimation.
- R-LSVI handles the generative-model case; R-LSVI-UCB handles episodic exploration with a replicable UCB bonus.
- Core technique is randomized rounding onto a shifted grid, forcing two independent runs to snap to identical outputs.
- CartPole experiments show replicability achievable at fractions of the theoretical sample budget.
- Quantizing neural Q-value outputs in PQN boosts cross-seed action agreement on Atari without harming returns.
Two runs of the same reinforcement learning algorithm on the same environment can produce wildly different policies. That instability has haunted the field for decades, and a new paper from researchers at Penn and Johns Hopkins takes a formal swing at it: Replicable Reinforcement Learning with Linear Function Approximation delivers the first provably replicable RL algorithms that work beyond the tabular setting, where you can list every state and action by hand.
The theoretical notion of replicability here is strict. A randomized algorithm is replicable if two executions on independent samples from the same distribution, coupled only through internal randomness, produce identical outputs with high probability. Not similar rewards, not comparable behavior, but the exact same policy. That bar matters because policies with similar average reward can still behave differently, which complicates verification and reuse of prior results, and the inconsistency becomes dangerous in safety-critical deployments.
Why tabular replicability fell short
Prior work established replicable algorithms for tabular RL, where you can enumerate every state-action pair. Real problems use function approximation, though, and many reliability issues in RL trace back to the difficulty of approximating value functions. Earlier replicability results simply did not cover that regime. This paper closes the gap for linear Markov decision processes, where rewards and transition probabilities are linear functions of a feature embedding of state-action pairs.