# From Generative to Episodic: Sample-Efficient Replicable Reinforcement Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods.
- First posted on arXiv 16 Jul 2025.

## Placed in

- Deep reinforcement learning methods / [Deep RL algorithms and representations](https://mlsanity.com/deeprl/deep-rl-algorithms-and-representations/)

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

- [Replicable Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2509.08660/) (2025)
- [Behavior-Consistent Deep Reinforcement Learning](https://mlsanity.com/paper/2605.21214/) (2026)
- [Computationally Efficient Replicable Learning of Parities and Applications](https://mlsanity.com/paper/2602.09499/) (2026)
- [Replicable Composition](https://mlsanity.com/paper/2604.10423/) (2026)

## Abstract (arXiv)

The epidemic failure of replicability across empirical science and machine learning has recently motivated the formal study of replicable learning algorithms [Impagliazzo et al. (2022)]. In batch settings where data comes from a fixed i.i.d. source (e.g., hypothesis testing, supervised learning), the design of data-efficient replicable algorithms is now more or less understood. In contrast, there remain significant gaps in our knowledge for control settings like reinforcement learning where an agent must interact directly with a shifting environment. Karbasi et. al show that with access to a generative model of an environment with S states and A actions (the RL 'batch setting'), replicably learning a near-optimal policy costs only tildeO(S2A2) samples. On the other hand, the best upper bound without a generative model jumps to tildeO(S7 A7) [Eaton et al. (2024)] due to the substantial difficulty of environment exploration. This gap raises a key question in the broader theory of replicability: Is replicable exploration inherently more expensive than batch learning? Is sample-efficient replicable RL even possible? In this work, we (nearly) resolve this problem (for low-horizon tabular MDPs): exploration is not a significant barrier to replicable learning! Our main result is a replicable RL algorithm on tildeO(S2A) samples, bridging the gap between the generative and episodic settings. We complement this with a matching tildeOmega(S2A) lower bound in the generative setting (under the common parallel sampling assumption) and an unconditional lower bound in the episodic setting of tildeOmega(S2) showcasing the near-optimality of our algorithm with respect to the state space S.