# Replicability in Reinforcement Learning

arXiv: https://arxiv.org/abs/2305.19562 · HTML: https://mlsanity.com/paper/2305.19562/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 54 references that are in the map.
- First posted on arXiv 31 May 2023.

## Builds on (most cited first, 22 of 22)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Reinforcement Learning that Matters](https://mlsanity.com/paper/1709.06560/) (2017)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Improving Reproducibility in Machine Learning Research (A Report from the NeurIPS 2019 Reproducibility Program)](https://mlsanity.com/paper/2003.12206/) (2020)
- [Reinforcement Learning in Healthcare: A Survey](https://mlsanity.com/paper/1908.08796/) (2019)
- [Reinforcement learning based recommender systems: A survey](https://mlsanity.com/paper/2101.06286/) (2021)
- [On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning](https://mlsanity.com/paper/1704.00805/) (2017)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [ELF OpenGo: An Analysis and Open Reimplementation of AlphaZero](https://mlsanity.com/paper/1902.04522/) (2019)
- [Replicable Bandits](https://mlsanity.com/paper/2210.01898/) (2022)
- [Replicable Reinforcement Learning](https://mlsanity.com/paper/2305.15284/) (2023)
- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [List and Certificate Complexities in Replicable Learning](https://mlsanity.com/paper/2304.02240/) (2023)
- [Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time](https://mlsanity.com/paper/1704.01869/) (2017)
- [Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions](https://mlsanity.com/paper/2010.11450/) (2020)
- [Replicability and stability in learning](https://mlsanity.com/paper/2304.03757/) (2023)

## Built on by (most cited first, 21 of 21)

- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [What Do Machine Learning Researchers Mean by "Reproducible"?](https://mlsanity.com/paper/2412.03854/) (2024)
- [Replicability in High Dimensional Statistics](https://mlsanity.com/paper/2406.02628/) (2024)
- [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024)
- [Replicable Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2509.08660/) (2025)
- [Stability and List-Replicability for Agnostic Learners](https://mlsanity.com/paper/2501.05333/) (2025)
- [Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2503.15294/) (2025)
- [Solving Deep Reinforcement Learning Tasks with Evolution Strategies and Linear Policy Networks](https://mlsanity.com/paper/2402.06912/) (2024)
- [Replicability is Asymptotically Free in Multi-armed Bandits](https://mlsanity.com/paper/2402.07391/) (2024)
- [The Cost of Replicability in Active Learning](https://mlsanity.com/paper/2412.09686/) (2024)
- [Replicable Distribution Testing](https://mlsanity.com/paper/2507.02814/) (2025)
- [Simplicial covering dimension of extremal concept classes](https://mlsanity.com/paper/2511.11819/) (2025)
- [The Sample Complexity of Replicable Realizable PAC Learning](https://mlsanity.com/paper/2602.19552/) (2026)
- [Model Agreement via Anchoring](https://mlsanity.com/paper/2602.23360/) (2026)
- [Behavior-Consistent Deep Reinforcement Learning](https://mlsanity.com/paper/2605.21214/) (2026)
- [Tight list replicability bounds via a novel sphere covering theorem](https://mlsanity.com/paper/2606.06148/) (2026)
- [Sign-Rank, Index, and List Replicability: Connections and Separations](https://mlsanity.com/paper/2606.18236/) (2026)
- [Generalizability of experimental studies](https://mlsanity.com/paper/2406.17374/) (2024)
- [Computationally Efficient Replicable Learning of Parities and Applications](https://mlsanity.com/paper/2602.09499/) (2026)
- [Replicable Bandits with UCB based Exploration](https://mlsanity.com/paper/2604.20024/) (2026)
- [Replicable Conformal Prediction](https://mlsanity.com/paper/2608.23638/) (2026)

## Abstract (arXiv)

We initiate the mathematical study of replicability as an algorithmic property in the context of reinforcement learning (RL). We focus on the fundamental setting of discounted tabular MDPs with access to a generative model. Inspired by Impagliazzo et al. [2022], we say that an RL algorithm is replicable if, with high probability, it outputs the exact same policy after two executions on i.i.d. samples drawn from the generator when its internal randomness is the same. We first provide an efficient ρ-replicable algorithm for (varepsilon, δ)-optimal policy estimation with sample and time complexity widetilde Oleft(fracN3·log(1/δ)(1-γ)5·varepsilon2·ρ2right), where N is the number of state-action pairs. Next, for the subclass of deterministic algorithms, we provide a lower bound of order Omegaleft(fracN3(1-γ)3·varepsilon2·ρ2right). Then, we study a relaxed version of replicability proposed by Kalavasis et al. [2023] called TV indistinguishability. We design a computationally efficient TV indistinguishable algorithm for policy estimation whose sample complexity is widetilde Oleft(fracN2·log(1/δ)(1-γ)5·varepsilon2·ρ2right). At the cost of exp(N) running time, we transform these TV indistinguishable algorithms to ρ-replicable ones without increasing their sample complexity. Finally, we introduce the notion of approximate-replicability where we only require that two outputted policies are close under an appropriate statistical divergence (e.g., Renyi) and show an improved sample complexity of widetilde Oleft(fracN·log(1/δ)(1-γ)5·varepsilon2·ρ2right).