- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper investigates how known causal graphs can reduce the sample complexity of identifying optimal policies in causal Markov Decision Processes. It introduces the IATS algorithm, which filters out irrelevant interventions to achieve asymptotically optimal sample efficiency. Experimental results demonstrate that IATS improves sample efficiency by approximately 1.4–6.8 times compared to methods that do not leverage causal graphs; however, a gap remains between the observed convergence rate and theoretical predictions. Furthermore, this research is primarily limited to stage-decoupled Markov Decision Processes.
Critical strengths
-
Clear theoretical characterization of sample complexity: The paper quantifies the value of causal diagrams by showing that sample complexity grows linearly with the number of irrelevant actions without a diagram but becomes independent of this number when the diagram is available. Under stage decoupling, it further establishes that full-trajectory sampling is governed by the maximum stagewise complexity, whereas single-stage querying is governed by the sum of stagewise complexities.
-
Reproducible core experimental results: Running the provided implementation reproduces the main reported experimental values, including the 1.42–6.77× sample-efficiency gains.
Critical weaknesses
-
Restrictive theoretical scope and difficult presentation: The main results assume a known causal graph, no hidden confounding, Gaussian rewards, and stage decoupling. Stage-local rewards and action-independent visitation reduce the core model to independent causal bandits sharing a sampling budget. Despite partial extensions to coupled settings, instance-optimal identification in general coupled MDPs remains unresolved. The presentation further obscures the core intuition and contribution through weakly connected definitions, lemmas, and theorems, while the lengthy appendix lacks a roadmap or table of contents.
-
Narrow empirical coverage and consequential implementation issues: Most confirmatory experiments reuse two ancestor means, a fixed baseline, and unit noise, primarily varying branch count or horizon. This leaves robustness across reward gaps, relevant-action counts, and heterogeneous stages insufficiently explored. More seriously, the reproduction audit found that E5 initialization generates 18 observations, one per state-action pair, but records only one two-step episode, with this additional sampling absent from the protocol description. Together with its disclosed oracle allocation and unproved stopping threshold, this limits E5’s value as evidence of instance-optimal learning in general coupled MDPs. The implementation also equates ancestor-only and graph-aware characteristic times without enforcing condition (H). Small-gap tests reveal numerical saturation and, in some cases, incorrect sampling allocations: for example,
char_time([1e-6, 0], sigma=1)returns 1 × 10¹², whereas the exact two-arm formula gives 8 × 10¹².
Questions for authors
Based on the weakness and reproduction on experiment, I have the following questions:
-
Applicability beyond stage decoupling: Which forms of interstage coupling are covered by the theoretical results? In particular, which guarantees remain valid when actions affect subsequent state visitation or rewards depend across stages, and what do the partial results establish toward instance-optimal identification in general coupled MDPs?
-
Robustness of the empirical gains: Do the reported sample-efficiency gains persist across different reward gaps, numbers of relevant actions, noise levels, and heterogeneous stages? Could the authors provide broader experiments beyond the current family with two ancestor means, a fixed baseline, and unit noise?
-
Corrected E5 sample accounting: What are the corrected episode counts and speed-ups when initialization follows admissible trajectories and all observations are accounted for? The audited implementation generates 18 initialization observations but records only one two-step episode.
-
Interpretation of E5’s results: Can the reported gains be reproduced with an allocation learned from observations and a stopping rule with a proved guarantee? Given the disclosed oracle allocation and unproved stopping threshold, what conclusions about instance-optimal learning does the current experiment support?
-
Validity and numerical reliability of the characteristic-time solver: How is condition (H) checked before equating ancestor-only and graph-aware characteristic times? What numerical accuracy and parameter range does the solver support, and how can users detect saturation or incorrect sampling allocations? In particular, how do the authors explain that
char_time([1e-6, 0], sigma=1)returns 1 × 10¹², whereas the exact two-arm formula gives 8 × 10¹²?
4 comments
Response to Reviewer FKcM (part 2 of 2).
FKcM-Q4. What E5 supports with a learned allocation and a proven stop
Yes, with a smaller gain. In the rerun the design is learned from the data and recomputed every 25 episodes, with tracking and forced exploration at each state. Each decision state stops by our analysed threshold at level . By Lemma 10 and a union bound this rule is -correct on greedy-aligned instances, including the gated instance we run, but not on general coupled MDPs (Example 1). Over 300 seeds at the rerun had no errors and a speed-up of 2.06 (95% interval 2.00 to 2.12), below the oracle design's 2.64 and above the single-flip ratio 1.72.
The single-flip times and are computed exactly, but by Proposition 3 they are not lower bounds. Mean episode counts are 1,700 for the graph-aware learner, or , and 3,499 for the blind one. As released, E5 supports no conclusion about learning, and the revision says so. We claim no rate, and this instance does not test value coupling.
FKcM-Q5. Solver validity and the (H) check
Solver. Confirmed. The bisection on had an absolute floor of , so char_time returned exactly whenever exceeded it, and optimal_allocation then returned a wrong allocation. The revised solver finds the root of the equalisation equation of Garivier and Kaufmann (2016, Thm 5) after dividing the means by , with no floor. It returns and to machine precision whenever is a finite double (gaps between about and ), and inf otherwise, never a capped value. It gives char_time([1e-6, 0]) and takes 0.3 ms per call. Users can detect a wrong output by checking that every rival term equals at , as our tests do. The submitted appendix overstated the old solver's accuracy, and Appendix C.11 now reports the measured values.
Effect on results. In a replay of every submitted E2 to E4 run the floor never bound, so no reported run was affected.
(H). The released code did not check (H) and reported as . It now computes the exact graph-aware time without assuming (H) and reports both. (H) holds wherever the submitted experiments relied on it (E1 to E4 and the leaves of E5), so no reported number changes. New tests cover small gaps, scaling, (H), Theorem 2, C-tracking and the E5 accounting (exactly two reward draws per counted episode).
Thanks for author additional details and acknowledge the implementation issue. However, it also confirms the restricted theoretical scope that the main optimality guarantees still rely on a known, causally sufficient graph and stage decoupling, which reduces the sequential problem to causal bandits linked by the sampling protocol. The revised E5 is a useful improvement but its correctness guarantee is restricted to greedy-aligned instances, no matching sample-complexity rate is established, and the authors explicitly acknowledge that the tested instance does not examine value coupling.
Response to official comment by reviewer FKcM
Thank you for the follow-up and for finding the revised E5 useful. We do not share the view that our scope weakens the contribution. Of the three E5 limits you list, two we believe we answer with proofs, and the third is an open problem we state precisely and highlight for further research.
A known graph is the premise of our research question, and causal sufficiency the base case. The paper asks what knowing the graph is worth, so the graph must be known. With hidden confounders, which arms can be pruned is a prior question, studied by Lee and Bareinboim (2018, 2019). Any extension to unknown graphs or hidden confounders must recover our bounds when none is present (Appendix B). We prove that the graph-aware time does not depend on the number of branches, while a blind learner pays at least linearly in them (Theorem 1, part (i) after Garivier and Kaufmann, 2016), so the speed-up the graph buys lies between two linear functions of the branches. With a known baseline, pruning needs less than 4 times the graph-aware lower bound, and 4 cannot be improved. When pulls reveal only the reward and the baseline must be learned, pruning is exactly optimal (Theorem 2). So a learner that prunes gives up nothing when the baseline must be learned and less than a factor 4 when it is known, and we show that graph-aware Track-and-Stop recovers that factor (Theorem 5). Theorems 1(ii) and 2(i), (iii) and (iv) are, to our knowledge, new (Appendix B), and answer the two questions that pruning left open (Section 1). Our scope is therefore the base case that every harder setting must recover, not a weakness of the contribution.
Decoupling is indeed assumed, but the claims derived from it are proven. The episodic time is the largest stage time and the generative time is the sum (Theorem 3), so the protocol changes what the graph is worth. In the example of Remark 9 the graph gives no leading-order episodic speed-up for up to 222 branches, while the generative gain grows at least linearly in them. Under episodic sampling the graph therefore pays off only if it shortens the blind learner's slowest stage. The episode count is the slowest stage's stopping time, so our episodic rate rests on a tail bound that we prove with no bound on the means (Lemma 9, Theorem 4(iii)), whereas CombGame (Jourdan et al., 2021) is proved optimal only for bounded means. Under both protocols the lower bounds are attained exactly as , by IATS when the baseline must be learned (Corollary 2) and by graph-aware Track-and-Stop when it is known (Corollary 4). Thus, whilst the problem reduces to causal bandits linked by the sampling protocol, the link still changes the answer, and under each protocol we give the optimal rate and a learner that attains it, which the reduction alone does not.
On E5. Greedy alignment is the limit of local certification itself, not of our proof. An instance is greedy-aligned when every decision state has a unique local best action and these actions form the optimal policy. When they are unique but not optimal, any rule that certifies them returns a wrong policy, as Example 1(a) shows. Inside the greedy-aligned class our stop is wrong with probability at most under any sampling rule (Lemma 10 and a union bound), and forced exploration makes it stop, so it is -correct there. This class already includes value-coupled instances, such as Example 1(b) and (c). The restriction therefore marks exactly where local certification is safe, and shows that a learner correct on every coupled MDP must test alternatives that act through later-stage values.
E5 leaves decoupling, since its root action decides which leaf is visited. On its instance at , with a learned design and the proven stop for both learners, no run returned a wrong policy over 300 seeds, and the blind learner needed 2.06 times as many episodes (95% interval 2.00 to 2.12). The graph's speed-up thus holds on an MDP outside decoupling. Its root decision never binds, so it does not test value coupling, which we analyse by proof instead. In Example 1(a) the coupled lower bound is about 120 times the single-flip value, so no formula in local gaps alone can be exact, and a simulation there would only reproduce the failure the example proves.
We claim no rate for E5. What we claim for coupled MDPs are lower bounds, and these are proven. With no optimal branch, the blind lower bound grows linearly in the branches at every decision state with branches, while the graph-aware time is the same for every (Lemma 11, Proposition 2). Even with coupling, no blind learner avoids this linear cost. The matching learner is our Conjecture 1, and we show that convexity is not an obstacle (Proposition 1). Without a graph, the closest tabular-MDP results are within factors 4 and 2 of their characteristic time (Table 2), so a matching rate for coupled MDPs is a problem in its own right and highlight as an area for further research.
Response to Reviewer FKcM (part 1 of 2).
Thank you for your engagement and feedback. In particular, we appreciate your stress-test in our code implementation. We address and outline the new revision to the paper below to each theme identified by you.
FKcM-W1. Restrictive scope; difficult presentation
We agree on the scope. The main results assume a known, causally sufficient graph, Gaussian rewards of known variance and stage decoupling, under which the model is H causal bandits linked by the sampling protocol. Section 8 lists these limitations. For coupled MDPs we prove the lower bounds but not achievability (FKcM-Q1). Within this scope the revision removes condition (H) from the optimality results. IATS is optimal with no condition when the baseline is not given (Theorem 2, Corollary 2), and graph-aware Track-and-Stop with C-tracking attains the known-baseline bounds (Theorem 5, Corollary 4).
On presentation, we have revised the structure for clarity and flow. Section 1 states each contribution against prior work, and a bridge leads from the definitions into Section 3. The appendix opens with a roadmap, a table locating each result's statement, proof and experiments, and a table of contents.
FKcM-W2. Narrow experiments and implementation issues
E6 broadens the experiments (Q2). Every implementation issue is confirmed and fixed (Q3 to Q5), and the anonymous repository now holds the result files behind every number.
FKcM-Q1. Coupling covered by the theory
Appendix D covers finite-horizon causal MDPs in which actions change which states are visited, with a known transition kernel and a given branch set. An intervention that changes transitions is an ordinary arm. Rewards that depend on earlier stages are covered when the dependence passes through the state, since μ(s,a) may depend on s. Rewards that are not stage-additive remain open (Appendix D.4, problem 6).
For these MDPs we prove the change-of-measure lower bound over occupancy measures (Lemma 11). The blind lower bound grows linearly in k at every decision state with branches (Proposition 2(i)), while the graph-aware time is the same for every k≥1 (Proposition 2(ii)). These give the lower-bound half of instance optimality. Appendix D.3 adds a δ-correct per-state stop on greedy-aligned instances, and the matching rate is open (Conjectures 1 and 2). Per-state certification fails once values couple states (Example 1).
FKcM-Q2. Robustness of the gains
Yes. E6 draws 36 random instances with 2, 3, 5 or 8 ancestor arms, gaps from 0.2 to 1 and 2 to 32 branches, with baselines on both sides of the rivals. It reruns three of them under uniform and Laplace noise of the same variance and adds three heterogeneous 4-stage MDPs, for 45 cells of 100 seeds with every-round updates. Since σ is known and shared, changing it only rescales the gaps, so we vary the noise shape instead. The realized speed-up is 1.00 to 1.57 times the prediction Tblind∗/Tanc∗, never below it. Its interval excludes 1 wherever the prediction is at least 1.2, and there were no errors in 9,000 runs (Section 6, Figure 3a, Appendix F.2). E7 adds instances that violate (H), with up to 4 ancestor arms.
The excess over the prediction is the threshold's lower-order term, which is larger for the blind learner (more arms, longer runs). On the store with k=8 the realized-to-predicted ratio falls from 1.24 to 1.17 as δ goes from 10−1 to 10−4. At 10−2 and 10−4 it is close to the ratio of the thresholds the two learners cross at their mean stopping times (1.21 against 1.19, 1.17 against 1.15).
The gap between observed and predicted rates in your summary is the same lower-order term. At δ=10−4 IATS stops at 3.23T∗log(1/δ), yet its stopping time is within 3% of T∗β(τ,δ) at every δ. The proven mixture threshold lowers 3.23 to 2.32 (Section 6, Table 5).
FKcM-Q3. Corrected E5 accounting
Confirmed. The warm-up drew all 18 state–action pairs and counted them as one episode, and the protocol did not describe it. It now follows admissible trajectories and counts every warm-up episode, 4 for the graph-aware learner and 16 for the blind one (Appendix D.3). With the same oracle allocation and threshold, the speed-up over 300 seeds is 2.64 (95% interval 2.53 to 2.76), with mean episode counts of 745 (graph-aware) and 1,969 (blind). The submission reported 2.62 over 60 seeds, and counting the warm-up changes the ratio by about 0.01.