acceptodds
Under review as a conference paper at ICLR 2027

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 from to . 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 from to . 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.

Primary area:
reinforcement learning
Keywords:
Finite-Horizon Tabular Markov Decision Processes, Batch Simulation

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_Z9M7OpenReview ↗
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 (s,a,s′)∈S×A×S(s,a,s') \in S\times A\times S 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 mm trajectories is O~(HS2A)\tilde O(HS^2A) instead of O(Hm)O(Hm). 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
  1. 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 O(HS2A)O(HS^2A) cost required to simulate mm 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.

  2. State space dependence: the S2S^2 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.

  3. Theory is very tied to tabular MDPs, and it is not obvious that the insights can be extended to the non-tabular setting.

  4. Assumption of deterministic reward

  5. 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
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

Rebuttal by Authors (Part II)

W2: State space dependence

We agree that the S2S^2 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 SS-category transition-count vector for every active state-action-step tuple. We note, however, that such a quadratic dependence on SS 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 ⟨P^s,a,h,Vh+1⟩\langle \hat P_{s,a,h}, V_{h+1}\rangle. For dense transitions, evaluating this quantity requires summing over all SS possible next states for each of the HSAHSA state-action-step tuples, leading to an O(HS2A)O(HS^2A) 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 S2S^2 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 S2S^2 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 d≪Sd\ll S, the same forward Markov-flow construction only needs to sample over the nonzero successor states. The simulator-side cost then becomes O(HSAd)O(HSAd) for a general policy and O(HSd)O(HSd) 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 S2S^2 bound.

We also agree that the original experiments used relatively modest state spaces and therefore added a substantially larger-state-space online experiment with (H,S,A)=(20,50,5)(H,S,A)=(20,50,5). Algorithm 1 is formulated for a generic candidate size mm and does not prescribe how mm should be chosen. In our computational analysis and original UCB-Advantage implementation, after kk episodes have been accepted, we instantiate Algorithm 1 with m=K−km=K-k, so that the candidate contains all remaining episodes in the simulation horizon and therefore necessarily contains any subsequent adaptive boundary before episode KK. 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 1,2,4,…1,2,4,\ldots 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 (H,S,A)=(20,50,5)(H,S,A)=(20,50,5) experiment, even in the intermediate-budget regime K=104K=10^4-10610^6, where geometric bracketing is slower than conventional simulation, its runtime is at most about 1.26×1.26\times that of the conventional simulator. From K=107K=10^7 onward on the tested grid, geometric bracketing is consistently faster, with directly measured speedups of 1.96×1.96\times, 6.94×6.94\times, and 24.8×24.8\times at K=107K=10^7, 10810^8, and 10910^9, respectively (see Table 29).

Finally, these larger episode budgets are not chosen merely to create a favorable computational regime. On the harder (20,50,5)(20,50,5) instance, UCB-Advantage continues to incur substantial regret beyond K=107K=10^7; even at K=108K=10^8, the median cumulative regret is approximately 8.29×1068.29\times10^6, corresponding to an average regret of about 0.0830.083 per episode (Figure 8). Thus, the regime beyond K=107K=10^7 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.

AuthorsOpenReview ↗

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 Rh(⋅∣s,a,s′)R_h(\cdot\mid s,a,s'), the relevant aggregate reward statistics can be generated conditional on the transition counts Eh(s,a,s′)E_h(s,a,s'), without materializing the individual rewards, provided that such conditional aggregate sampling is tractable.

For example, if the reward conditional on (s,a,s′)(s,a,s') is Bernoulli with mean ph(s,a,s′)p_h(s,a,s'), then the total reward contributed by transitions from (s,a)(s,a) to s′s' can be generated by a single draw Yh(s,a,s′)∼Binomial(Eh(s,a,s′),ph(s,a,s′)).Y_h(s,a,s')\sim\mathrm{Binomial}\left(E_h(s,a,s'),p_h(s,a,s')\right). The total reward for (s,a,h)(s,a,h) is then obtained by summing these quantities over s′s'. 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 (s,a,h)(s,a,h), the construction simplifies further: whenever the required aggregate reward statistics admit efficient conditional sampling, they can be generated directly conditional on the visit count Ch(s,a)C_h(s,a).

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 (s,a,s′,h)(s,a,s',h) adds at most O(HS2A)O(HS^2A) work for a general policy and O(HS2)O(HS^2) under a deterministic policy, matching the leading order of the corresponding Markov-flow sampling costs. If rewards depend only on (s,a,h)(s,a,h), the additional cost can be as small as O(HSA)O(HSA) for a general policy and O(HS)O(HS) 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 (H,S,A)=(10,15,10)(H,S,A)=(10,15,10) 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.

Reviewer_jSe3OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes an exact fast simulation framework for finite-horizon tabular reinforcement learning. The key idea is to avoid explicitly generating individual trajectories when the downstream learning algorithm only depends on aggregate statistics. For predetermined batches, the paper directly samples aggregate Markov-flow counts using multinomial distributions, preserving exactly the same distribution as conventional trajectory-by-trajectory simulation. For adaptive batches with data-dependent stopping conditions, it introduces an exact multivariate-hypergeometric splitting procedure and binary refinement to locate the first update boundary. Under the stated assumptions, the simulator-side dependence on batch size is reduced from linear to constant for direct batch simulation, and from linear to logarithmic for adaptive simulation. The framework is demonstrated on model-based planning, offline VPVI, and online UCB-Advantage, with experiments supporting the claimed distributional equivalence and runtime improvements.

Critical strengths
  1. Exact rather than approximate simulation. The framework preserves the distribution of the relevant aggregate statistics, and the adaptive splitting result provides a principled way to handle data-dependent update boundaries without reverting to fully sequential simulation.
  2. Clear computational motivation and broad examples within tabular RL. The paper applies the framework to simulator-based, offline, and online RL settings, and the experiments show substantial runtime gains at large simulation budgets.
Critical weaknesses
  1. The conceptual novelty seems limited relative to the strength of the claims. For predetermined batches, the main mechanism is essentially to sample multinomial transition counts directly instead of generating the corresponding individual categorical samples. While the extension to adaptive boundaries via exact hypergeometric splitting is more interesting, I am not fully convinced that the overall contribution is sufficiently substantial for ICLR.
  2. The strongest speedup claims rely on restrictive assumptions. In particular, forward Markov-flow sampling requires direct access to the initial-state and transition probability distributions, rather than only a standard black-box simulator that returns one transition sample per query. Moreover, the claimed removal of the batch-size dependence relies on treating binomial/hypergeometric sampling and arithmetic on large counts as constant-cost primitives. These assumptions substantially narrow the settings in which the advertised O(m) to O(1) or O(log m) improvements directly apply.
Questions for authors
  1. Can the authors clarify more explicitly what practical simulator interfaces satisfy the assumed access to the full transition probability vectors Ph(⋅∣s,a)P_h(\cdot \mid s,a)? How much of the claimed computational advantage remains when only standard sample-based simulator access is available?
  2. How sensitive are the complexity comparisons to the assumption that binomial and hypergeometric random variates with very large population counts can be sampled in O(1) time? It would help to discuss whether a more bit-complexity-aware computational model would materially change the main conclusions.
5 comments
AuthorsOpenReview ↗

Rebuttal by Authors (Part I)

We thank you for your thoughtful comments. Below are our point-by-point responses.

W1: Conceptual novelty and scope of the contribution

We respectfully disagree with the characterization that the predetermined-batch component is essentially only a replacement of individual categorical samples by multinomial counts. At a single state-action-step triple, multinomial aggregation is indeed elementary. Our contribution is instead to show that an entire batch of finite-horizon trajectories can be represented and generated directly as a coupled multi-step Markov flow, while exactly preserving the joint distribution of all learner-relevant aggregate quantities.

In particular, the transition counts at different steps are not independent multinomial vectors: the state counts at step h+1h+1 are induced by the transition counts at step hh and in turn determine the sampling distribution of subsequent state-action and transition counts. Our forward construction generates this coupled flow without materializing any individual trajectory, and Theorem 3.1 establishes equality in distribution between the complete generated Markov flow and the aggregate flow obtained from mm independent trajectories. This joint-law statement is what allows any flow-measurable learner statistic or batch update to be computed directly from the generated flow while preserving its exact distribution. The generative-model example is therefore only the simplest specialization of this general trajectory-replacement principle.

The adaptive setting introduces an additional difficulty that cannot be handled by direct multinomial sampling alone. When the batch endpoint is the first data-dependent update boundary, the aggregate flow of a larger candidate batch does not reveal which prefix of the underlying trajectories first triggered the update. We address this through exact multivariate-hypergeometric conditional splitting. Conditional on a parent Markov flow, the procedure samples prefix and suffix subflows with exactly the same conditional distribution as the corresponding subsets of the latent trajectories. Recursive binary refinement then locates the first adaptive boundary without reverting to episode-by-episode simulation, while preserving the joint distribution of the resulting learner-state sequence.

Thus, the contribution is not the observation that multinomial counts can replace repeated categorical draws in isolation. It is the combination of an exact Markov-flow representation for complete trajectory batches, a direct joint-law-preserving generation procedure, and an exact conditional splitting mechanism that extends this representation to data-dependent adaptive boundaries. Together, these components provide a unified exact simulation framework for predetermined and adaptive batch RL procedures.

W2.1 and Q1: Simulator access assumption

Direct access to transition probability vectors is available in a number of practical tabular simulation settings. For example, OpenAI Gym/Gymnasium contains tabular environments such as FrozenLake, Taxi, and CliffWalking whose simulator implementations explicitly construct state-action transition tables and initial-state distributions [1]. MDPtoolbox likewise represents finite MDPs directly through transition probability matrices and provides standard and randomly generated tabular MDP instances [2]. The same interface is also common in synthetic tabular RL benchmarks and model-based simulators in which the learned or specified dynamics are stored explicitly as categorical next-state distributions. In these settings, our forward Markov-flow sampler can directly operate on the transition vectors; importantly, this access is needed only by the simulator and not by the learning algorithm.

Even when only a sample-based simulator is available, our framework still provides a computational advantage by enabling parallel simulation that would otherwise be difficult to exploit in the presence of data-dependent updates. Under the current policy, a large candidate batch of trajectories can be generated concurrently and aggregated into a Markov flow. The main difficulty is that the first adaptive update boundary may occur strictly inside this candidate batch, so simply generating trajectories in parallel does not by itself determine the correct point at which the learner should update. Our exact MHG splitting procedure resolves this issue: starting from the aggregate flow of the parallel-generated candidate batch, it recursively recovers the prefix flow corresponding to the first adaptive boundary while preserving the correct conditional distribution. The learner can then recover a boundary flow with exactly the same distribution as under sequential simulation and continue under the new policy.

(continued in the next part)

AuthorsOpenReview ↗

Rebuttal by Authors (Part II)

Thus, direct access to transition probability vectors provides the strongest form of acceleration by allowing the aggregate flow itself to be sampled directly, but it is not the only setting in which the framework is useful. With sample-based simulator access, the method converts much of the trajectory-generation work within each adaptive batch from inherently sequential simulation into parallel batch generation, while exact splitting handles the data-dependent synchronization point. Therefore, a substantial computational advantage can remain under sample-based access whenever parallel simulation resources are available.

[1] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. “OpenAI Gym.” arXiv preprint arXiv:1606.01540, 2016.

[2] Iadine Chadès, Guillaume Chapron, Marie‐Josée Cros, Frédérick Garcia, and Régis Sabbadin. “MDPtoolbox: A Multi-Platform Toolbox to Solve Stochastic Dynamic Programming Problems.” Ecography, vol. 37, no. 9, 2014, pp. 916–920.

W2.2 and Q2: Computational primitive assumption

We thank the reviewer for raising this important point. In brief, we conclude that the complexity comparison is not materially sensitive to the unit-cost convention in the regime relevant to our implementation. Our new primitive-level benchmarks in Appendix B.4 show that multinomial and MHG sampling exhibit no sustained growth with the count magnitude and are cheaper than the corresponding number of conventional transition samples. More generally, retaining explicit arithmetic, aggregate-sampling, and transition-sampling costs changes the fast-versus-conventional comparison only by a multiplicative primitive-cost ratio; our measurements show that this ratio does not disadvantage the fast simulator. Under a stricter bit-complexity model, the bounds may acquire additional polylogarithmic factors in the episode budget, but the main separation between aggregate fast simulation and linear episode-by-episode simulation remains unchanged. We provide the detailed analysis below.

Our computational convention in Section 4 is a unit-cost model: basic arithmetic on aggregate counts, scalar binomial and hypergeometric sampling, and a single environment-transition sample are each treated as O(1)O(1) operations. In the leading simulator-side complexity comparison, however, these primitives play different roles. Conventional simulation is dominated by repeatedly sampling individual environment transitions, whereas the fast simulator is dominated by multinomial and multivariate-hypergeometric (MHG) sampling of aggregate counts. The remaining count-arithmetic operations do not change the leading operation counts. Thus, the assumption most relevant to the fast-versus-conventional comparison is whether the aggregate-sampling primitives can reasonably be placed on the same cost scale as conventional transition sampling.

Under the sequential conditional constructions, a qq-category multinomial draw requires O(q)O(q) scalar binomial draws and a qq-category MHG draw requires O(q)O(q) scalar hypergeometric draws. Hence, under the unit-cost convention, both aggregate-sampling operations have O(q)O(q) cost independent of the total count nn. Correspondingly, qq conventional environment-transition samples also have O(q)O(q) cost. Thus, the theoretical comparison is between a qq-category aggregate draw in the fast simulator and qq sequential transition samples in the conventional simulator, both of which scale as O(q)O(q) under the stated convention.

To assess whether this convention hides substantial implementation-level costs, we added microbenchmarks for both the multinomial and MHG primitives used by our fast simulator. We vary the number of categories qq and the count parameter nn, and compare each qq-category aggregate draw with qq sequential transition samples generated by the same categorical routine used in our conventional simulator. For both primitives, the observed runtime scaling with qq is consistent with the stated O(q)O(q) dependence, while for fixed qq the runtime shows no sustained growth as nn increases over several orders of magnitude. Moreover, both aggregate-sampling primitives are faster in wall-clock time than the corresponding qq conventional transition samples throughout the tested range. Thus, we observe neither a substantial hidden dependence on large count parameters nor an unfavorable constant-factor overhead relative to conventional transition sampling. We have added the full benchmark setup, timing curves, and numerical results in Appendix B.4.

(continued in the next part)

AuthorsOpenReview ↗

Rebuttal by Authors (Part III)

To make the sensitivity of the complexity comparison explicit without assuming population-independent sampling cost a priori, let KK denote the total budget and retain the costs of the underlying primitives. Every aggregate count is at most KK; even a worst-case arithmetic operation on two counts of size KK involves integers of magnitude at most 2K2K and therefore O(log⁡K)O(\log K) bits. Let α(K)\alpha(K) denote the cost of one such count-arithmetic operation. Let βmult(K)\beta_{\mathrm{mult}}(K) and βMHG(K)\beta_{\mathrm{MHG}}(K) denote the effective per-category costs of multinomial and MHG sampling when the relevant counts are at most KK, and define β(K)=max⁡βmult(K),βMHG(K)\beta(K)=\max\\{\beta_{\mathrm{mult}}(K),\beta_{\mathrm{MHG}}(K)\\}. Finally, let γ\gamma denote the cost of one conventional environment-transition sample. A qq-category aggregate draw then costs O(qβ(K))O(q\beta(K)), while qq conventional transition samples cost O(qγ)O(q\gamma).

For conventional simulation, generating KK episodes requires Θ(HK)\Theta(HK) transition samples and the same order of count updates, giving Tconv=O(HK(γ+α(K))).T_{\mathrm{conv}}=O\left(HK\bigl(\gamma+\alpha(K)\bigr)\right). For direct fast simulation, the corresponding aggregate-sampling and count-arithmetic operation counts are O(HS2A)O(HS^2A), giving Tfast,direct=O(HS2A(βmult(K)+α(K))).T_{\mathrm{fast,direct}}=O\left(HS^2A\bigl(\beta_{\mathrm{mult}}(K)+\alpha(K)\bigr)\right). Therefore, Tfast,directTconv=O(S2AKβmult(K)+α(K)γ+α(K)).\frac{T_{\mathrm{fast,direct}}}{T_{\mathrm{conv}}}=O\left(\frac{S^2A}{K}\frac{\beta_{\mathrm{mult}}(K)+\alpha(K)}{\gamma+\alpha(K)}\right).

The same calculation applies to adaptive simulation. Each forward-flow generation or MHG refinement has cost O(HS2A(β(K)+α(K)))O(HS^2A(\beta(K)+\alpha(K))), and there are at most O(log⁡K)O(\log K) refinements per adaptive batch. With at most Bmax⁡B_{\max} adaptive batches, Tfast,adaptive=O(Bmax⁡HS2Alog⁡K(β(K)+α(K))),T_{\mathrm{fast,adaptive}}=O\left(B_{\max}HS^2A\log K\bigl(\beta(K)+\alpha(K)\bigr)\right), and hence Tfast,adaptiveTconv=O(Bmax⁡S2Alog⁡KKβ(K)+α(K)γ+α(K)).\frac{T_{\mathrm{fast,adaptive}}}{T_{\mathrm{conv}}}=O\left(\frac{B_{\max}S^2A\log K}{K}\frac{\beta(K)+\alpha(K)}{\gamma+\alpha(K)}\right).

These expressions show explicitly how sensitive the comparison is to the aggregate-sampling cost: any additional dependence enters only through the factor (β(K)+α(K))/(γ+α(K))(\beta(K)+\alpha(K))/(\gamma+\alpha(K)). Our microbenchmarks then provide an implementation-level estimate of this factor. For fixed qq, neither multinomial nor MHG runtime exhibits sustained growth as the count parameter increases over the tested range, so βmult(K)\beta_{\mathrm{mult}}(K) and βMHG(K)\beta_{\mathrm{MHG}}(K) are empirically nearly insensitive to KK over this range. More importantly, one qq-category multinomial or MHG draw is always faster than the corresponding qq conventional transition samples, which implies empirically that βmult(K)≤γ\beta_{\mathrm{mult}}(K)\leq\gamma and βMHG(K)≤γ\beta_{\mathrm{MHG}}(K)\leq\gamma. Consequently, β(K)+α(K)γ+α(K)≤1\frac{\beta(K)+\alpha(K)}{\gamma+\alpha(K)}\leq 1 over the tested range, irrespective of the arithmetic cost α(K)\alpha(K). The direct fast-versus-conventional rate therefore remains O(S2AK),O\left(\frac{S^2A}{K}\right), and the adaptive rate remains O(Bmax⁡S2Alog⁡KK),O\left(\frac{B_{\max}S^2A\log K}{K}\right), exactly as under the unit-cost convention up to constant factors. Thus, replacing normalized primitive costs by the measured implementation-level costs does not weaken the complexity comparison.

A strict bit-complexity model can be handled within the same framework. Since all aggregate counts have O(log⁡K)O(\log K) bits, standard integer addition and subtraction give α(K)=O(log⁡K)\alpha(K)=O(\log K). The precise bit complexity of binomial and hypergeometric random-variate generation depends on the particular sampling algorithm, so the corresponding dependence can remain represented by β(K)\beta(K). If these scalar sampling costs are polynomial in the input bit length, then β(K)=poly⁡(log⁡K)\beta(K)=\operatorname{poly}(\log K). In this case, the fast bounds acquire only additional polylogarithmic factors in KK, whereas conventional simulation still explicitly generates Θ(HK)\Theta(HK) transitions. Hence, a bit-complexity-aware model may modify logarithmic factors, but it does not change the main qualitative separation between aggregate fast simulation and linear episode-by-episode simulation.

Reviewer_hRhtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces a simulation framework for tabular MDPs under finite horizons, that should be fast for the learners that use data only via so-called “Markov-flow” counts (initial-state, state-action and transition counts), or functions of them. The authors introduce two different methods:

  • direct batch simulation: when a fixed policy collects a batch of data and the flow is sampled via sequential multinomials, given simulator-side access to the initial distribution and the transition. The simulator cost becomes independent of the batch size m (Theorem 3.1).

  • adaptive batch simulation: used for data-dependent and prefix-monotone stopping rules. In this case a candidate flow is recursively split by exact multivariate-hypergeometric sampling, so that it is possible to locate the first boundary episode. This takes a complexity logarithmic in m in the splits and preserves the conditional law (Theorems 3.3, 3.5).

The framework is applied to generative-model planning, VPVI and UCB-Advantage (with FedQ-Bernstein in the appendix). The framework is tested on synthetic MDPs of four sizes to show that relevant statistics indeed match conventional simulation, direct-batch runtime is flat in budget size while adaptive simulation is slower over most small and moderate budgets but grows much more slowly. It overtakes conventional simulation at large budgets (e.g., 1.72× at K = 10^8 at the largest scale, Table 24 Appendix) (runtimes beyond the measured range are linearly extrapolated)

Critical strengths
  • (Main reason for acceptance) Exact adaptive batch sampling is a interesting and the idea seems correct: finding a data-dependent stopping point inside an aggregated flow and keeping the exact conditional law across steps and successive boundaries seems quite complex to reach to me and it needs several interesting lemmas that I never saw before personally (Lemmas D.1 to D.5). The arguments seem correct. This point IS the point of the paper, to me.
  • Clearly stated conditions. The paper says precisely when the method applies and verifies those conditions for some algorithms. Potentially, researchers can check applicability for their own algorithm.
Critical weaknesses
  • (Main Reason to reject) Limited novelty of the direct-batch method and limited significance overall. Sampling the (aggregated) counts of independent MDP runs with multinomials seems closely related to other techniques (e.g., collective graphical models, which the paper cites). Thus, the relevance of Theorem 3.1 and the generative-model application are quite dubious. Moreover, many tabular algorithms change policy every episode or need per-visit updates (e.g., UCB-VI, Q-learning with per-visit learning rates), so they might benefit of these methods only after some reformulation which is not exactly well described in the paper.
  • The empirical evidence for practical speedup is weaker than it seems. It appears to me that baseline is only at an episode-by-episode level. A vectorized batch simulator, which samples all episodes of a fixed-policy batch at once is not benchmarked, would be the actual thing to compare against, I think. For the adaptive mode at the largest scale it is slower with low speedups, and only 1.72× faster at 10^8. The headline gains at larger budgets are actually based on extrapolated conventional runtimes, which can be discussed.
Questions for authors

How does the method compare with a vectorized batch baseline? How would the adaptive case work? If the gains are still there my assessment of significance would be raised.

9 comments
AuthorsOpenReview ↗

Rebuttal by Authors (Part I)

We thank you for your thoughtful comments. Below are our responses.

W1.1: Novelty and significance

We respectfully disagree with the characterization that the connection to collective graphical models substantially limits the novelty or significance of our contribution. Collective graphical models and related aggregate-count approaches are conceptually related to our work in that they also operate on aggregate statistics rather than individual-level data, which is why we discuss them in the paper. However, their objective and technical role are different. These approaches primarily study probabilistic inference or population-level modeling from aggregate quantities. In contrast, our goal is to use aggregate Markov flows as an exact replacement for repeated RL trajectory simulation, while guaranteeing that the resulting learner computations have the same distribution as under explicit trajectory-by-trajectory simulation.

For predetermined batches, we formalize this idea by introducing the Markov-flow representation of an entire batch and developing a forward procedure that directly generates the required state, state-action, and transition counts without materializing the underlying trajectories. Importantly, in a finite-horizon MDP, the transition counts across successive steps are coupled through the propagated state counts, so the full multi-step flow cannot be viewed simply as a collection of unrelated multinomial count vectors. Theorem 3.1 establishes that the entire Markov flow generated by our procedure has exactly the same joint distribution as the aggregate flow obtained from mm independently simulated trajectories. Consequently, any flow-measurable learner statistic or batch update can be computed from the directly generated flow while preserving its exact distribution. To our knowledge, this trajectory-replacement perspective and its formal distributional guarantee for batch RL procedures have not been established in prior aggregate-count approaches. The generative-model application is the simplest specialization of this general principle rather than the sole contribution of the direct-batch method.

Beyond predetermined batches, our framework addresses the substantially more challenging case of adaptive batches. When a batch terminates at the first data-dependent update boundary, the aggregate flow of a larger candidate batch does not identify the prefix at which the learner would have updated under sequential simulation. Direct multinomial sampling or ordinary aggregate-count representations alone therefore cannot determine the correct boundary flow. We address this problem through exact multivariate-hypergeometric splitting. Conditional on a parent Markov flow, our procedure generates prefix and suffix flows with exactly the same conditional distribution as the corresponding subsets of the underlying trajectories. By recursively applying these exact conditional splits, we can locate the first data-dependent boundary through binary refinement and recover the corresponding boundary flow without reverting to episode-by-episode simulation, while preserving the distribution induced by the original sequential learning procedure.

Taken together, our framework goes beyond representing data through aggregate counts. It provides an exact Markov-flow representation for replacing trajectory-level simulation, establishes the joint distributional equivalence needed to justify direct batch generation, and develops an exact conditional splitting mechanism for data-dependent batch boundaries. These components enable exact aggregate simulation for both predetermined and adaptive batch RL procedures.

W1.2: Applicability to algorithms with per-episode or per-visit updates

We thank the reviewer for raising this point. We believe it is important to distinguish the different settings covered by our framework. For the simulator-based and offline applications considered in our paper, per-episode learner updates are not required during data generation. In the generative-model setting, the learner repeatedly queries prescribed state-action-step tuples, and the resulting next-state samples are ultimately used only through their empirical transition counts. Similarly, in our offline RL application, the entire dataset is generated under a fixed behavior policy before the learner is applied. These data-generation procedures therefore naturally form predetermined batches and can be directly accelerated by our framework without reformulating the learning algorithm.

The issue raised by the reviewer is primarily relevant to fully adaptive online RL. Classical algorithms such as UCB-VI [1] may recompute their policies after every episode, while classical Q-learning algorithms may update their value estimates after every visit [2]. However, such fully sequential updates are one algorithmic design choice rather than an inherent requirement for statistically efficient online RL.

(continued in the next part)

AuthorsOpenReview ↗

Rebuttal by Authors (Part II)

A substantial body of literature studies precisely whether comparable learning guarantees can be maintained while substantially reducing the number of policy updates or switches. This question is motivated both theoretically and practically: reducing the number of policy updates can lower the cost of policy deployment or reconfiguration in applications such as healthcare, recommender systems, and large-scale hardware deployment [5,11,14], while longer fixed-policy batches also enable the collection or simulation of multiple trajectories in parallel before the next learner update [15--17]. For example, Bai et al. [5] explicitly study limited adaptivity in tabular RL and propose UCB2-style Q-learning that retains sublinear regret while reducing the dependence of its local switching cost on the number of episodes to logarithmic order.

A common design in this literature is to accumulate observations over multiple episodes and update the policy only after a predetermined or data-dependent batch ends. Importantly, this is not a specialized reformulation introduced to accommodate our simulation framework. Even within tabular episodic RL, there is a substantial sequence of algorithms built around limited policy updates. Bai et al. [5] introduced UCB2-style Q-learning with low local switching cost. Zhang et al. [6] subsequently proposed UCB-Advantage, which achieves almost-optimal model-free regret together with low local switching cost. On the model-based side, MVP [7] employs a batch-based doubling rule: the empirical model and policy are updated only when a visitation count reaches a doubling threshold, in contrast to UCB-VI, which recomputes its estimates every episode. Qiao et al. [8] further developed a stage-wise exploration and adaptive policy-elimination algorithm with O(HSAlog⁡log⁡T)O(HSA\log\log T) switching cost, matching their corresponding lower bound up to constant and problem-dependent factors. More recently, Q-EarlySettled-LowCost [9] simultaneously achieves near-optimal model-free regret, burn-in cost scaling linearly with SS and AA, and logarithmic policy switching cost. These results demonstrate that batch-based policy updates are recurring algorithmic principles in tabular RL rather than isolated modifications of fully adaptive algorithms.

The same objective extends well beyond tabular RL. Batched and switching-constrained learning has a long history in multi-armed bandits [3,4]. Under linear function approximation, Wang et al. [10] study both batch learning and rare policy switching for linear MDPs and show, in particular, that O(dHlog⁡T)O(dH\log T) policy switches suffice to retain the same regret order as fully adaptive LSVI-UCB. Huang et al. [11] formulate deployment-efficient RL for linear MDPs, where a fixed policy is deployed to collect a batch of data before the next deployment. Low-switching learning has also been extended to general nonlinear function approximation. Li et al. [12] develop a low-switching sample-efficient policy optimization method for general nonlinear function classes and additionally evaluate the method with deep neural networks. Zhao et al. [13] establish near-optimal regret and low switching cost for Q-learning with general function approximation. More broadly, Xiong et al. [14] develop a unified framework for rare policy switching and batch learning under general function classes, covering tabular MDPs, linear MDPs, generalized linear models, low-eluder-dimension models, and several other nonlinear sequential decision-making classes. Thus, reducing policy adaptivity while retaining statistical efficiency is an established research objective across a broad spectrum of sequential decision-making problems.

Our framework is designed to exploit exactly this batch structure. When the update schedule is predetermined, direct batch simulation generates the required aggregate statistics without materializing individual episodes. When the next update is triggered by a data-dependent condition, our adaptive procedure uses exact multivariate-hypergeometric splitting to locate the first boundary while preserving the distribution induced by sequential simulation. UCB-Advantage is one representative example of the latter class.

We therefore do not claim that every fully adaptive algorithm, such as episode-wise UCB-VI or an arbitrary per-visit Q-learning implementation, can be accelerated unchanged. Rather, our framework directly applies to simulator-based and offline data generation, as well as to the broad class of online algorithms that already employ batched low-switching designs. The extensive literature discussed above further demonstrates that limited-adaptivity designs constitute an important and widely studied algorithmic paradigm, rather than an artificial modification introduced solely to accommodate our simulation method.

(continued in the next part)

AuthorsOpenReview ↗

Rebuttal by Authors (Part III)

W2.2: Practical relevance of the adaptive-mode speedup

We agree that the original adaptive implementation incurs non-negligible overhead at small and moderate budgets because it must repeatedly generate candidate flows, locate data-dependent boundaries, and restart simulation after learner updates. At the largest of our four original problem scales, (H,S,A)=(10,15,10)(H,S,A)=(10,15,10), the original remaining-budget implementation becomes faster than conventional simulation only near K=108K=10^8, where it achieves a measured speedup of 1.72×1.72\times.

However, K=108K=10^8 should not be viewed as an excessively large budget relative to the learning difficulty of this instance. As shown in Figure 1, the cumulative-regret curve is still increasing at K=108K=10^8, indicating that UCB-Advantage has not yet learned the optimal policy by the end of the measured range. Thus, even at this moderate tabular scale, larger simulation budgets remain relevant for studying the learning process.

This is precisely the regime in which reducing the computational dependence on the number of simulated episodes becomes most consequential. Episode-by-episode simulation scales linearly with the episode budget KK, so extending the experiment substantially beyond 10810^8 episodes quickly becomes computationally prohibitive. In contrast, the runtime of the original adaptive simulator grows much more slowly with KK. We therefore view the measured 1.72×1.72\times speedup at K=108K=10^8 not as the endpoint of the computational gain, but as the point at which the advantage of the original remaining-budget implementation begins to emerge while larger budgets are still needed for the learner to reach the optimal policy.

To further reduce the finite-budget overhead of adaptive simulation, we introduce an accelerated exact implementation based on geometric bracketing. Algorithm 1 is formulated for a generic candidate size mm, while in our original UCB-Advantage implementation we instantiate it with all K−kK-k remaining episodes after kk episodes have been accepted. When the next adaptive boundary occurs much earlier than the end of this remaining horizon, the candidate can therefore be far larger than necessary, causing binary refinement to begin from an unnecessarily large range.

To address this issue, in Appendix B.6 we introduce an exact geometric-bracketing implementation of the same adaptive simulation principle, presented as Algorithm 2. Rather than taking all remaining episodes as a single candidate, it generates consecutive fixed-policy candidate blocks of sizes 1,2,4,…1,2,4,\ldots until the first block whose addition triggers the adaptive condition. All preceding non-triggering blocks are accepted in full, and the same exact MHG binary-refinement mechanism as in Algorithm 1 is then applied only within the boundary-containing block. Thus, geometric bracketing changes how the candidate containing the next boundary is identified while retaining the exact refinement mechanism once that candidate has been found. It preserves the same exact distributional guarantee and the same worst-case asymptotic upper bound, while substantially reducing practical refinement overhead.

Empirically, geometric bracketing closely matches conventional simulation in cumulative regret and adaptive-batch counts while markedly improving finite-budget efficiency (Figures 6 and 7). Across the four original problem scales and the tested budget range, it is faster than the original remaining-budget implementation in nearly all configurations, with only isolated exceptions at the very smallest budgets. It also outperforms conventional simulation across all four original problem scales from K=105K=10^5 onward on the tested grid (see Table 28). At the largest original scale, (H,S,A)=(10,15,10)(H,S,A)=(10,15,10), and K=108K=10^8, the median simulator time decreases from approximately 2.03×1032.03\times10^3 seconds for the original remaining-budget implementation to only 5.21×1015.21\times10^1 seconds with geometric bracketing, compared with 3.54×1033.54\times10^3 seconds for conventional simulation. The corresponding median paired speedups are 66.9×66.9\times over conventional simulation and 38.7×38.7\times over the original remaining-budget implementation at this directly measured budget. Detailed results are provided in Appendix B.6 of the revised manuscript.

(continued in the next part)

Reviewer_M8GDOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper points out that conventional RL simulation generates individual trajectories even when downstream procedures only use aggregate counts. They show you can directly sample the aggregate Markov flow — state counts, state-action counts, transition counts — without materializing trajectories, reducing simulator-side cost from O(m) to O(1) for fixed batches and O(log m) for adaptive batches. The distributional equivalence to standard simulation is proven. They apply it to three settings: simulator-based RL, offline RL (VPVI), and online RL (UCB-Advantage).

Critical strengths

The core observation is correct and useful: in a tabular MDP, the aggregate counts of m i.i.d. trajectories have a known distribution that can be sampled directly. This saves a lot of redundant simulation for theory papers that only care about visitation statistics. The theoretical treatment is rigorous — Theorems 3.1, 3.3, and 3.5 establish exact distributional equivalence, and the multivariate hypergeometric splitting for adaptive boundaries is a clean construction.

Critical weaknesses

The scope is narrow. This only applies to tabular MDPs where you have direct access to the transition kernel. The intro motivates with Isaac Gym, Brax, EnvPool — all deep RL simulators — but the method is irrelevant for any function-approximation setting. The O(1) claim only holds when P(s'|s,a) is known analytically. In the generative model setting where you only get next-state samples, you still need parallel aggregation, which is what Brax already does. The experimental section is thin. Main text Section 6 is half a page; all results are in Appendix B. For a paper whose main selling point is computational efficiency, there are no main-text runtime curves or concrete speedup numbers at realistic scales.

Questions for authors

Can you provide a concrete wall-clock speedup at a realistic scale? E.g., UCB-Advantage with S=50, A=5, H=20, K=10^7 episodes. What is the practical overhead of multivariate hypergeometric sampling? The cost convention says it's O(q) independent of n, but software implementations may have nontrivial constants.

3 comments
AuthorsOpenReview ↗

Rebuttal by Authors (Part I)

We thank you for your thoughtful comments. Below are our responses.

W1.1: Scope

We agree that our framework is designed for tabular MDPs and does not directly apply to general settings with function approximation. Our discussion of Isaac Gym, Brax, and EnvPool is intended to place our work in the broader context of efficient RL simulation. These systems significantly accelerate simulation through parallelism and high-throughput environment execution, but they still explicitly generate individual transitions or trajectories. Our work focuses on a complementary question: when the learning procedure ultimately depends only on aggregate statistics, is it necessary to simulate those trajectories individually in the first place? In the tabular setting, we show that in many batch-structured RL procedures, the answer is no: the required aggregate Markov flow can instead be generated directly while preserving the exact distribution needed by the learner.

However, we believe that tabular RL remains a meaningful and computationally nontrivial regime. Tabular RL experiments can involve large horizons and state/action spaces and, more importantly, extremely large simulation budgets due to long training runs, multiple random seeds, multiple MDP instances, and extensive parameter sweeps. Even with moderate-to-large H,S,AH,S,A, trajectory-by-trajectory simulation can therefore become computationally expensive when the number of episodes is large.

W1.2: Clarification of the O(1)O(1) claim and the role of parallel aggregation

The O(1)O(1) complexity with respect to batch size for forward Markov-flow sampling applies when the transition kernel is directly accessible, so that aggregate transition counts can be sampled without generating individual next-state transitions. When only a sample-based simulator is available, a candidate batch can instead be generated through parallel trajectory simulation and aggregation, as in existing high-throughput simulators such as Brax.

However, parallel aggregation alone does not address the adaptive setting considered in our framework. For algorithms whose batch endpoint is determined by a data-dependent condition, generating a large candidate batch in parallel does not by itself identify where the current batch should terminate, since the learner may need to update as soon as the first boundary is reached. Our exact multivariate hypergeometric splitting procedure addresses this issue. Starting from the aggregate flow of a candidate batch, it recursively recovers the flow up to the first data-dependent boundary while preserving the exact conditional distribution. Therefore, even when the candidate batch is obtained through parallel simulation, our splitting procedure provides an additional capability beyond parallel trajectory generation by exactly locating adaptive batch boundaries without reverting to episode-by-episode simulation.

W1.3: Main text Section 6

Due to the main-text page limit, the original submission provided only a concise summary of the experimental setup and results in Section 6, with the complete evaluations deferred to Appendix B. In the revision, we substantially strengthen Section 6 by summarizing the new primitive-level benchmark, the improved geometric-bracketing implementation, the larger-state-space experiment, and the comparison with vectorized baselines. We also include a four-scale runtime comparison between conventional simulation and geometric bracketing in Table 1, making the practical computational gains directly visible in the main text.

Q1.1: Realistic regime

We thank the reviewer for emphasizing the small- and moderate-budget regime. We agree that the implementation used in our original adaptive experiments can incur substantial overhead in this regime. Algorithm 1 is formulated for a generic candidate size mm. In our computational analysis and preceding UCB-Advantage experiments, after kk episodes have been accepted, we instantiate it with m=K−km=K-k, so that the candidate contains all remaining episodes in the simulation horizon. When the next adaptive boundary is nearby, binary refinement may therefore begin from a range that is much larger than necessary.

To directly address this implementation-level overhead, in Appendix B.6 we introduce an exact geometric-bracketing implementation of the same adaptive simulation principle. Rather than taking all K−kK-k remaining episodes as a single candidate, it generates consecutive candidate blocks of sizes 1,2,4,…1,2,4,\ldots until identifying the first block that contains an adaptive boundary. The same exact MHG binary-refinement procedure used in Algorithm 1 is then applied only within this boundary-containing block. This preserves the same exact distributional guarantee and the same worst-case asymptotic upper bound, while substantially reducing the practical refinement depth when the next boundary occurs well before the end of the remaining horizon.

(continued in the next part)

AuthorsOpenReview ↗

Rebuttal by Authors (Part II)

Empirically, geometric bracketing markedly improves finite-budget performance. Across the four original problem scales and the tested budget range, it is faster than the original remaining-budget implementation in nearly all configurations, with only isolated exceptions at the very smallest budgets (e.g., K=10K=10, see Table 28). Thus, the reduced refinement depth translates into substantial practical improvements over the original adaptive implementation.

Following your suggestion, we have also added a larger-state-space experiment with (H,S,A)=(20,50,5)(H,S,A)=(20,50,5) in Appendix B.6.1. Even in the intermediate-budget regime, K=104K=10^4--10610^6, where geometric bracketing is slower than conventional simulation, its runtime is at most about 1.26×1.26\times that of the conventional simulator, indicating that the finite-budget overhead remains modest. From K=107K=10^7 onward on the tested grid, geometric bracketing is consistently faster, and its reported speedup increases from 1.96×1.96\times at K=107K=10^7 to 6.94×6.94\times at K=108K=10^8 and 24.8×24.8\times at K=109K=10^9, with all of these runtimes directly measured (see Table 29).

Importantly, these larger budgets remain statistically meaningful for the underlying online learning problem. On the harder (20,50,5)(20,50,5) instance, UCB-Advantage continues to incur substantial regret beyond K=107K=10^7 (see Figure 8); even at K=108K=10^8, the median cumulative regret is approximately 8.29×1068.29\times10^6, corresponding to an average regret of about 0.0830.083 per episode. Thus, the regime beyond K=107K=10^7 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.

Q1.2: Overhead of the sampling

We thank the reviewer for raising this practical point. Our computational convention in Section 4 treats basic arithmetic on aggregate counts, a scalar hypergeometric draw, and a single environment-transition sample as O(1)O(1) operations. Although count arithmetic is included in this unit-cost convention, it does not determine the leading simulator-side complexity in the comparison of interest: the fast simulator is dominated by aggregate sampling, including MHG draws, whereas conventional simulation is dominated by repeated environment-transition sampling. Therefore, the relevant implementation-level question is whether treating scalar hypergeometric sampling as comparable in cost to a single conventional transition sample introduces a substantial hidden constant.

Under the sequential construction of a qq-category multivariate hypergeometric (MHG) draw, this convention gives an O(q)O(q) cost independent of the total population count nn, while qq conventional transition samples also have O(q)O(q) cost. Since this asymptotic comparison does not by itself quantify implementation-level constants, we added a direct microbenchmark of the same MHG implementation used by our fast simulator.

We vary q∈10,20,50,100q\in\\{10,20,50,100\\} and nn from 10210^2 to 10810^8, and compare the wall-clock time of one qq-category MHG draw with that of qq sequential single-transition samples generated by the same categorical routine used in our conventional simulator. Across the full grid, one MHG draw takes approximately 7.017.01--14.1514.15 microseconds. For fixed qq, the runtime remains nearly unchanged as nn increases by six orders of magnitude, with no sustained growth in nn, which is consistent with the population-independent cost assumed in our analysis. See Figure 4 for details.

The implementation-level constant is also modest relative to conventional transition sampling. At n=108n=10^8, one qq-category MHG draw takes only 0.5850.585, 0.3230.323, 0.1670.167, and 0.1130.113 times the runtime of qq sequential transition samples for q=10,20,50,100q=10,20,50,100, respectively (see Table 27). Thus, the relevant O(q)O(q)-versus-O(q)O(q) comparison is favorable: one qq-category MHG draw is substantially cheaper than qq conventional transition samples over the tested range. These results indicate that MHG sampling introduces neither a noticeable dependence on the population count nor a substantial hidden constant relative to the conventional simulation primitive used in our complexity comparison. We have added the full benchmark setup, timing curves, and numerical results in Appendix B.4.

AuthorsOpenReview ↗

Follow-up on Our Rebuttal

Dear Reviewer M8GD,

As the discussion stage is approaching its end, we would like to kindly follow up on our response. We sincerely appreciate your positive evaluation and hope that our rebuttal has addressed your remaining concerns.

If any concerns remain, we would be happy to provide further clarification before the discussion period ends.

Thank you again for your time and thoughtful feedback.

Best regards,

Authors of Submission 9348

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.