Exact Fast Batch Simulation for Tabular Reinforcement Learning
Abstract
Simulation is a fundamental computational primitive in reinforcement learning (RL), yet conventional simulation explicitly generates individual trajectories even when downstream procedures use only aggregate statistics. To address this, we develop an exact fast-simulation framework for finite-horizon tabular Markov decision processes. Our framework has two complementary modes. In direct batch simulation, a batch is represented by its aggregate Markov flow. With sufficient parallel simulation resources, this flow can be obtained by trajectory aggregation; when such simulation is unavailable or costly but the initial state and transition distributions are directly accessible, we instead generate an identically distributed flow through forward Markov-flow sampling without materializing individual trajectories. The latter reduces the simulator-side computational dependence on batch size m from O(m) to O(1). In adaptive batch simulation, when batch length is determined by a data-dependent condition, exact multivariate-hypergeometric splitting recursively refines a candidate Markov flow while preserving the conditional law, reducing the cost dependence on m from O(m) to O(log m). Together, these modes accelerate simulation by keeping trajectories aggregated whenever possible and refining flows only when required to locate data-dependent boundaries. The framework applies broadly across simulator-based, offline, and online batch or stage-based RL, as illustrated with representative algorithms from each setting.
Related
- Model-based Bootstrap for Offline Policy Evaluation in Tabular Reinforcement Learning
- WTF?! Simulation-Free Reinforcement Learning with Wasserstein-Tilted Flow Maps
- Integrating YOLOv8-based disaster detection with deep reinforcement learning for closed-loop UAV emergency response scheduling: A simulation study
- Tabular foundation models are not a shortcut to calibrated clinical risk prediction: a pre-registered simulation against the true risk
- Unbiased Gradients, Moving Stability Boundaries: Exact Mini-Batch Geometry in Linear Self-Attention
BibTeX
@misc{zhang2026exact,
title = {{Exact Fast Batch Simulation for Tabular Reinforcement Learning}},
author = {Haochen Zhang and Lingzhou Xue and Zhong Zheng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04746},
eprint = {2610.04746},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04746},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact Fast Batch Simulation for Tabular Reinforcement Learning
AU - Haochen Zhang
AU - Lingzhou Xue
AU - Zhong Zheng
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04746
UR - https://arxiv.org/abs/2610.04746
AB - Simulation is a fundamental computational primitive in reinforcement learning (RL), yet conventional simulation explicitly generates individual trajectories even when downstream procedures use only aggregate statistics. To address this, we develop an exact fast-simulation framework for finite-horizon tabular Markov decision processes. Our framework has two complementary modes. In direct batch simulation, a batch is represented by its aggregate Markov flow. With sufficient parallel simulation resources, this flow can be obtained by trajectory aggregation; when such simulation is unavailable or costly but the initial state and transition distributions are directly accessible, we instead generate an identically distributed flow through forward Markov-flow sampling without materializing individual trajectories. The latter reduces the simulator-side computational dependence on batch size m from O(m) to O(1). In adaptive batch simulation, when batch length is determined by a data-dependent condition, exact multivariate-hypergeometric splitting recursively refines a candidate Markov flow while preserving the conditional law, reducing the cost dependence on m from O(m) to O(log m). Together, these modes accelerate simulation by keeping trajectories aggregated whenever possible and refining flows only when required to locate data-dependent boundaries. The framework applies broadly across simulator-based, offline, and online batch or stage-based RL, as illustrated with representative algorithms from each setting.
ER -