- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
Authors consider simulating statistics of a batch of episodes from a tabular MDP rather than full episodes themselves; specifically, they recover the visitation statistics for each tuple under both a single fixed policy, and (certain) adaptive logging algorithms. They prove these quantities are correctly distributed. The computational cost for batch simulation of trajectories is instead of . Experiments are performed to show faster simulation of algorithms for simulation, offline learning, and online learning.
Critical strengths
Although the procedure for fixed policy logging is unsurprising, Algorithm 1 for exact adaptive batch simulation is interesting and clever. The practical problem is also interesting, and with a more carefully defined theoretical model could be a fruitful direction.
Critical weaknesses
-
The main weakness is that the paper's theoretical setting assumes access to the full MDP. As such, under the setting of the paper, one could answer any question about the MDP using numerical means; E.g. one can use value iteration for either policy evaluation or optimization with exactly the cost required to simulate trajectories. So if we already have complete information about the MDP, why are we doing RL in the first place? The only reason I can see is if we're interested in running empirical evaluations of RL algorithms themselves, rather than for any applications purpose; my understanding is that this is the positioning of the paper, but that scope is quite narrow.
-
State space dependence: the dependence in the compute cost would be extremely onerous in more realistic environments (e.g. discretizations of continuous environments). Experiments seem to use small state-space sizes throughout, but consider number of episodes growing far beyond what would reasonably be needed for those environments.
-
Theory is very tied to tabular MDPs, and it is not obvious that the insights can be extended to the non-tabular setting.
-
Assumption of deterministic reward
-
For the empirical section, data is presented as a slough of tables rather than as graphs, making it difficult to read.
Questions for authors
Please see weaknesses
4 comments
Rebuttal by Authors (Part II)
W2: State space dependence
We agree that the dependence can become costly when the transition kernel is dense, and the state space is very large. This dependence arises because, in the worst case, the simulator must generate an -category transition-count vector for every active state-action-step tuple. We note, however, that such a quadratic dependence on is not unique to our simulation procedure and also arises naturally in model-based tabular RL. For example, the minimax-optimal modified MVP algorithm [1] maintains an empirical transition distribution for each state-action-step tuple and performs Bellman backups involving terms such as . For dense transitions, evaluating this quantity requires summing over all possible next states for each of the state-action-step tuples, leading to an cost for a full value-iteration sweep; the transition-variance terms used in its Bernstein-style bonuses have the same dense-state dependence. Thus, the factor reflects a standard computational cost of operating with dense tabular transition models, rather than a dependence specific to our simulation framework.
At the same time, the dependence is a worst-case dense-transition bound rather than an unavoidable dependence for every tabular problem. If each transition distribution has support size at most , the same forward Markov-flow construction only needs to sample over the nonzero successor states. The simulator-side cost then becomes for a general policy and for a deterministic policy, with the same improvement applying to the MHG splitting procedure. Thus, for sparse or locally supported tabular dynamics, the state-space dependence can be substantially smaller than the worst-case bound.
We also agree that the original experiments used relatively modest state spaces and therefore added a substantially larger-state-space online experiment with . Algorithm 1 is formulated for a generic candidate size and does not prescribe how should be chosen. In our computational analysis and original UCB-Advantage implementation, after episodes have been accepted, we instantiate Algorithm 1 with , so that the candidate contains all remaining episodes in the simulation horizon and therefore necessarily contains any subsequent adaptive boundary before episode . When the next boundary occurs much earlier than the end of this remaining horizon, however, the exact binary refinement of Algorithm 1 begins from a range that can be much larger than necessary. This unnecessarily large refinement range is a major source of the substantial finite-budget overhead observed in the original adaptive implementation.
To reduce this overhead, in Appendix B.6 we introduce a more efficient practical implementation of Algorithm 1 based on geometric bracketing, presented as Algorithm 2. Rather than taking all remaining episodes as a single candidate, Algorithm 2 generates consecutive candidate blocks of sizes until identifying the first block that contains the next adaptive boundary, and then applies the same exact MHG binary-refinement procedure of Algorithm 1 only within that block. Thus, Algorithm 2 implements the same adaptive simulation principle as Algorithm 1, but uses geometric bracketing to select a more localized candidate for refinement. This preserves the same exact distributional guarantee and the same worst-case asymptotic upper bound while substantially reducing practical refinement overhead. In the larger experiment, even in the intermediate-budget regime -, where geometric bracketing is slower than conventional simulation, its runtime is at most about that of the conventional simulator. From onward on the tested grid, geometric bracketing is consistently faster, with directly measured speedups of , , and at , , and , respectively (see Table 29).
Finally, these larger episode budgets are not chosen merely to create a favorable computational regime. On the harder instance, UCB-Advantage continues to incur substantial regret beyond ; even at , the median cumulative regret is approximately , corresponding to an average regret of about per episode (Figure 8). Thus, the regime beyond is not one in which the learner has already learned the optimal policy, but rather remains part of the learning process in which the policy continues to improve. The computational gains of geometric aggregate simulation therefore arise at budgets that remain directly relevant for studying the learning behavior of challenging online RL instances.
[1] Zihan Zhang, Yuxin Chen, Jason Lee, and Simon S. Du. "Settling the sample complexity of online reinforcement learning". Journal of the ACM, 72(3), (2025): 1-63.
Rebuttal by Authors (Part III)
W3: Scope of tabular MDPs
We agree that our current exact theory is developed for tabular MDPs. The key reason is that our exact simulation framework relies on representing a batch by a finite collection of state, state-action, and transition counts and on conditionally splitting these counts using multivariate hypergeometric sampling. These finite-dimensional count representations are naturally available in tabular MDPs and are what allow us to prove exact equality in distribution with trajectory-by-trajectory simulation.
At the same time, we believe the broader insight is not limited to the particular tabular formulas. The general principle is to identify aggregate sufficient statistics for a batch, generate or manipulate these statistics directly rather than materializing individual trajectories, and conditionally split the aggregate representation only when finer resolution is needed to locate a data-dependent learner update. Extending this principle beyond tabular MDPs would require problem-specific aggregate representations and conditional-sampling mechanisms that preserve the learner-relevant distribution; for general function approximation, such exact representations need not exist and establishing them is a nontrivial open problem.
We have therefore clarified the scope of the paper: our contribution is an exact fast-simulation framework for finite-horizon tabular MDPs, together with exact distributional guarantees for both predetermined and adaptive batches. We view extensions to structured non-tabular settings, where suitable finite-dimensional sufficient statistics or conditional sampling schemes can be identified, as an interesting direction for future work.
W4: Assumption of deterministic reward:
Our framework can be extended to stochastic rewards whenever the learner-relevant aggregate reward statistics can be sampled efficiently from their conditional distribution given the corresponding aggregate visitation or transition counts. In the more general setting where rewards may be generated jointly with the next state, or according to a conditional reward distribution , the relevant aggregate reward statistics can be generated conditional on the transition counts , without materializing the individual rewards, provided that such conditional aggregate sampling is tractable.
For example, if the reward conditional on is Bernoulli with mean , then the total reward contributed by transitions from to can be generated by a single draw The total reward for is then obtained by summing these quantities over . More generally, finite-support reward distributions can be handled through multinomial draws conditional on the corresponding transition counts. Under the common stochastic-reward model in which the reward distribution depends only on , the construction simplifies further: whenever the required aggregate reward statistics admit efficient conditional sampling, they can be generated directly conditional on the visit count .
This extension does not change the leading simulator-side complexity. In the general case where the reward distribution may depend on the next state, sampling a constant number of aggregate reward statistics for each adds at most work for a general policy and under a deterministic policy, matching the leading order of the corresponding Markov-flow sampling costs. If rewards depend only on , the additional cost can be as small as for a general policy and under a deterministic policy. Thus, for stochastic reward models admitting efficient aggregate conditional sampling, the extension does not alter the leading computational order of the framework.
W5: Graphical presentation of the empirical results
We thank the reviewer for this presentation suggestion. To improve readability, we added a new summary figure (Figure 5) in Appendix B.5 that visualizes the experiments at for each of the three applications. The top row compares the learner-relevant outcomes under conventional and fast simulation, while the bottom row compares simulator wall-clock scaling. The figure makes the two main empirical observations visually immediate: the two simulators produce closely matched learning outcomes, while their computational scaling with the simulation budget is substantially different.
I thank the authors for their thorough response to my review. I do believe there are some interesting technical ideas in this paper.
While I recognize that this method's primary utility is basically limited to studying meta-level qualities of other RL algorithms, this strikes me as a very narrow but not nontrivial practical use case. However, as a primarily theoretical paper, I still believe that complete knowledge of the MDP trivializes the RL problem somewhat. Moreover, the practical story is undercut slightly by the strong assumptions (tabular states, known/finite-support rewards etc).
Therefore, I will keep my score.
Rebuttal by Authors (Part I)
We thank you for your thoughtful comments. Below are our point-by-point responses.
W1: Simulator-side model access and intended scope
We thank the reviewer for raising this point. We would like to clarify that access to the transition kernel in our direct Markov-flow implementation is a simulator-side assumption, not an assumption that the learning algorithm itself is given the full MDP. The learner receives exactly the same type of sample-based information as under conventional simulation; our method only changes how this information is generated. Our goal is therefore not to solve a known MDP as efficiently as possible, but to accelerate the exact execution of a prescribed sample-based procedure while preserving the distribution of the information available to that procedure.
If the objective is simply to compute an optimal policy or evaluate a fixed policy in a fully known MDP, we agree that dynamic programming or other numerical planning methods are the appropriate tools. This is not the task that our simulation framework is intended to replace. Our setting is relevant when the computational object of interest is the output of a prescribed finite-sample procedure rather than only the solution of the underlying MDP. This distinction arises in several settings. In synthetic offline RL, one may need to generate a dataset of a specified size under a prescribed behavior policy for downstream training or evaluation; directly solving the MDP does not produce such a dataset or its finite-sample variability. In simulator-based methods, the procedure may intentionally construct an empirical transition model or other estimator from a fixed number of samples, and its output depends on the sampling distribution rather than only on the true kernel. In online RL, quantities such as regret, update times, switching behavior, and the sequence of learner states are properties of the learning process itself and cannot be recovered by replacing that process with dynamic programming. More broadly, whenever the downstream procedure is defined through a sample-based interface, preserving the distribution of its finite-sample inputs and outputs can be essential. Our method accelerates this sampling stage while leaving the prescribed procedure and its induced distribution unchanged.
We also emphasize that direct access to the transition kernel is only one way of obtaining the aggregate Markov flow in our framework. When such access is unavailable but parallel simulation resources are available, a candidate batch of trajectories can instead be generated concurrently and aggregated into the same Markov-flow representation. However, parallel generation alone does not resolve the adaptive setting: if the learner is supposed to update at the first data-dependent boundary, that boundary may occur strictly inside the candidate batch, and the aggregate flow of the full batch does not by itself identify the correct prefix at which the update should occur. Our exact multivariate-hypergeometric splitting procedure addresses this issue by recursively recovering a boundary flow with the same conditional distribution as the corresponding prefix under sequential simulation. Thus, parallel simulation can be used to generate candidate batches, while our splitting mechanism resolves the data-dependent synchronization point without reverting to episode-by-episode simulation.