acceptodds
Under review as a conference paper at ICLR 2027

Instance-Optimal Best Policy Identification in Decoupled Causal MDPs with a Known Graph

Abstract

We quantify the value of a known causal graph for fixed-confidence best-policy identification. Actions intervene on graph variables and rewards are Gaussian with a known variance and unknown means. A graph-aware learner can ignore every intervention on a variable that cannot influence the reward, whereas a graph-blind learner with the same feedback must rule each one out. The blind characteristic time, which governs sample complexity, grows linearly in the number of reward-irrelevant actions, while the graph-aware time does not. This separation follows from a lower bound on the number of samples any correct learner needs. In de- coupled layered causal Markov decision processes (MDPs), the characteristic time is the largest stage time under episodic sampling and the sum under per-stage sampling. An intervention-aware Track-and-Stop algorithm is correct and attains these times whenever no reward-ancestral intervention is worse than the null intervention. Simulations on synthetic causal-bandit and layered-MDP instances match the predicted times and the composition law. Both learners identified the best policy in every run at the target confidence, and with two or more reward-irrelevant actions the graph-aware learner needed 1.4 to 6.8 times fewer samples, a speed-up 15 to 43 percent larger than the leading-order prediction. All code is released at https://anonymous.4open.science/r/iats-crl-AC81.

Primary area:
learning theory
Keywords:
causal Markov decision processes, causal bandits, causal graph, reinforcement learning, causal reasoning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_FKcMOpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. 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:

  1. 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?

  2. 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?

  3. 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.

  4. 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?

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

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 HH 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)\mu(s,a) may depend on ss. 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 kk at every decision state with branches (Proposition 2(i)), while the graph-aware time is the same for every k≥1k\ge1 (Proposition 2(ii)). These give the lower-bound half of instance optimality. Appendix D.3 adds a δ\delta-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 σ\sigma 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∗T^\ast_{blind}/T^\ast_{anc}, 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=8k=8 the realized-to-predicted ratio falls from 1.24 to 1.17 as δ\delta goes from 10−110^{-1} to 10−410^{-4}. At 10−210^{-2} and 10−410^{-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\delta=10^{-4} IATS stops at 3.23T∗log⁡(1/δ)3.23 T^\ast \log(1/\delta), yet its stopping time is within 3% of T∗β(τ,δ)T^\ast\beta(\tau,\delta) at every δ\delta. 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.


AuthorsOpenReview ↗

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 δ/∣Sdec∣\delta/|S_{dec}|. By Lemma 10 and a union bound this rule is δ\delta-correct on greedy-aligned instances, including the gated instance we run, but not on general coupled MDPs (Example 1). Over 300 seeds at δ=0.01\delta=0.01 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 Tsf∗=64T^\ast_{sf}=64 and 110.13110.13 are computed exactly, but by Proposition 3 they are not lower bounds. Mean episode counts are 1,700 for the graph-aware learner, or 5.77Tsf∗log⁡(1/δ)5.77 T^\ast_{sf} \log(1/\delta), 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 1/T∗1/T^\ast had an absolute floor of 10−1210^{-12}, so char_time returned exactly 101210^{12} whenever T∗T^\ast 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 σ\sigma, with no floor. It returns T∗T^\ast and w∗w^\ast to machine precision whenever T∗T^\ast is a finite double (gaps between about 10−150σ10^{-150}\sigma and 10150σ10^{150}\sigma), and inf otherwise, never a capped value. It gives char_time([1e-6, 0]) =8×1012=8\times10^{12} and takes 0.3 ms per call. Users can detect a wrong output by checking that every rival term equals 1/T∗1/T^\ast at w∗w^\ast, 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 Tanc∗T^\ast_{anc} as TG∗T^\ast_G. 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, σ\sigma 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.

AuthorsOpenReview ↗

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 δ→0\delta\to0, 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 δ\delta under any sampling rule (Lemma 10 and a union bound), and forced exploration makes it stop, so it is δ\delta-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 k=6k=6 instance at δ=0.01\delta=0.01, 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 k≥1k\ge1 (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.

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

This paper studies the best policy identification in causal bandits and decoupled causal MDPs. The author studies both known graph and unknown graph setting. For a graph-aware learner, the author shows that it can rule out all the branch arms and have a characteristic time independent of the total number of nodes kk. For a graph-blind learner, the authors provide results (Theorem 1) showing that the characteristic time should be dependent on kk. This separation provides the insight: knowing the graph is beneficial since it can identify the set of branch arms that is not related to variable YY, and then rule them out naturally. The authors also extend their results to decoupled causal MDPs, and provide empirical results to show that graph-aware learner needs fewer samples

Critical strengths
  1. The presentation is clear to me. There are not many undefined variables or confusing notations. Figure 2 is clear for showing the essential insight of this paper's theoretical result: a graph-aware learner can eliminate the branch arms.

  2. The empirical results successfully support the theoretical discovery of the paper.

Critical weaknesses
  1. The main concern is the novelty of the insight and the contribution of this paper. Basically, the only advantage of the graph-aware learner in this paper is to rule out the branch arms that are not relevant to the variable YY. This insight is expected and not something new or interesting, and previous works [1,2] have also utilized it to reduce the sample complexity with a known graph.

  2. The paper studies an extension of causal bandits called decoupled causal MDPs. However, the motivation for decoupled causal MDPs and the extra challenge is not clear. The decoupled causal MDPs eliminate the relation and transition between different states, which is the key question in MDPs (actions in the previous step influence the next state). In this case, the decoupled causal MDPs defined in this paper are more similar to multiple causal bandits, which introduces no additional challenges or requires any novel techniques.

[1]. Lee, Sanghack, and Elias Bareinboim. "Structural causal bandits: Where to intervene?." Advances in neural information processing systems 31 (2018).

[2]. Lee, Sanghack, and Elias Bareinboim. "Structural causal bandits with non-manipulable variables." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. No. 01. 2019.

Questions for authors
  1. Could the authors clarify the paper’s core contribution beyond the fact that a graph-aware learner can use the causal graph to rule out branch arms?

  2. What is the extra challenge of the decoupled causal MDPs? Why is it reasonable in the real world?

3 comments
AuthorsOpenReview ↗

Response to Reviewer UL2M.

We appreciate the engagement in our paper and the thoughtful feedback / questions you raised. Below we address each in turn.

UL2M-W1 and Q1. Pruning is known; contribution beyond it

We agree that pruning non-ancestor interventions is known. Lee and Bareinboim (2018) show that intervening on a non-ancestor of YY is equivalent to not intervening, which is our Lemma 1 for single-variable arms. With demand non-manipulable, their 2019 POMIS is exactly the set of arms IATS keeps in our example. The submission described their work inaccurately. The revision corrects this and credits them in its first paragraph.

Beyond pruning, the paper answers two questions these works leave open when pulls reveal only the reward. What is pruning worth? With kk branches the blind characteristic time is at least 2σ2k/Δ022\sigma^2k/\Delta_0^2 (Theorem 1, from the Gaussian bracket of Garivier and Kaufmann, 2016), while the graph-aware time does not depend on kk. Is pruning all the graph is worth? Within the class that pins branches to the baseline, yes, whenever the baseline must be learned. When it is known, pruning needs less than 4 times the graph-aware lower bound, a tight constant, and loses nothing unless some ancestor intervention is harmful (Theorem 2). The extra value comes from ruling out a harmful intervention against the baseline, as in the lowest-mean test of Kaufmann et al. (2018), and needs the baseline together with the graph.

The revision adds a learner that does more than prune and captures this value. Track-and-Stop that C-tracks the graph-aware allocation and stops by the certified rule attains TG∗T^\ast_G on every instance with a unique best arm (Theorem 5). In E7 at δ=10−2\delta=10^{-2} it is up to 2.59 times faster than IATS (Section 6).

Our class uses neither POMIS dominance nor constraints linking μ0\mu_0 to the ancestor means. Such constraints hold only in special cases. For example, μ0=∑xP(x)μdo(x)\mu_0=\sum_xP(x)\mu_{do(x)} needs XX unconfounded and every observed value of XX to be an arm, and in the store the baseline price is not an arm. When the other variables are observed, as in Lattimore et al. (2016) and Wei et al. (2023), the graph can be worth more. Section 8 says both.

On the unknown-graph setting in your summary, the graph-blind learner does not learn the graph. It is the benchmark that must be correct on every mean vector, so the paper quantifies the value of the graph rather than studying structure learning.

UL2M-W2 and Q2. Motivation and challenge of decoupled causal MDPs

We agree. Under Assumption 3 the model is HH causal bandits linked by the sampling protocol, as the revision now says (Sections 1 and 4). Episodic access is semi-bandit identification (Jourdan et al., 2021), and generative access is multi-bandit identification (Gabillon et al., 2011).

Two points are specific to the MDP. First, CombGame (Jourdan et al., 2021) attains the episodic time for bounded means. IATS needs no such bound but stops each stage separately, so its episode count is max⁡hτh\max_h\tau_h and its rate needs a bound on E[max⁡hτh]\mathbb E[\max_h\tau_h], not on each E[τh]\mathbb E[\tau_h]. That bound follows from the δ\delta-uniform tail bound of Lemma 9 (Theorem 4(iii), Remark 8). Second, once actions gate states, certifying each state's local best action can certify the wrong policy (Example 1). This is why Appendix D proves lower bounds but not achievability. The max law also implies that, under episodic sampling, the graph-aware and blind times are equal when the blind learner's bottleneck stage has no branches and pruning is optimal there, however many branches the other stages carry (Section 4, Remark 9).

Decoupling fits settings where each period's outcome is complete before the next begins and every unit passes through every period. Examples are web pages whose modules each have their own metric and are shown to every user, and staged benchmarks run on reset inputs. Appendix D treats coupled MDPs with known transitions.


Thank you for the response. Although the authors identify quantifying the value of pruning as a novel contribution, the conclusion is also expected and seems not very interesting: knowing the graph can eliminate the dependence of the sample complexity on kk. It still remains unclear to me what the motivation for the decoupled causal MDPs is and whether it makes the MDP problem as easy as the bandit setting. Hence, I believe the paper can be strengthened by studying MDP problem without stage decoupling assumption. I maintain my score.

AuthorsOpenReview ↗

Response to follow-on comment from Reviewer UL2M

Thank you for the follow-on comments. We would like to clarify the three points you raise in the review.

1. Removing the dependence on kk is not our only conclusion. It is the starting point. Our main results are about what else the graph is worth. Below, the baseline is the mean reward when no intervention is made, and branches are the interventions that cannot affect the reward.

  • When pulls reveal only the reward and the baseline must be learned, dropping the branches is all that knowing them is worth. Learning the baseline, by observing or by pulling a branch, never pays, so IATS, which just drops the branches, is optimal on every instance (Theorem 2(iv), Corollary 2).
  • When the baseline is known, dropping is not always enough, but it is never far off. A learner can then rule out a harmful intervention by showing that it lies below the baseline, as in the lowest-mean test of Kaufmann et al. (2018). This beats dropping only if some intervention is harmful, and always by less than 4 times, a bound that is tight (Theorem 2(i)-(iii)). Our graph-aware Track-and-Stop captures this gain (Theorem 5).
  • In an MDP, how samples are collected decides what the graph is worth. With whole episodes the cost is set by the slowest stage, and with one stage at a time it is the sum over stages (Theorem 3). So with whole episodes the graph may give no speed-up at leading order. In the example of Remark 9 it gives none for up to 222 branches, because a branch-free stage stays the slowest, while with one stage at a time the gain grows linearly in the branches.

None of these follows from removing kk or appears in Lee and Bareinboim (2018, 2019). Therefore, we believe the contribution is well beyond what is stated in the last comment.

2. Why decoupled MDPs, and are they as easy as a bandit? They model systems tested on whole units, where each stage has its own outcome and the stages do not affect each other. Examples are a web page whose modules each have their own metric and are shown together to every user, and a staged benchmark run on reset inputs. Each unit gives one sample from every stage.

And they are not as easy as bandits. The rewards split into HH bandits, but each unit samples all of them at once, and this changes two things.

  • What the graph is worth changes (result 3 above). In a bandit every dropped branch saves samples. With whole units it saves nothing unless it speeds up the slowest stage.
  • The usual per-stage bandit guarantees do not give the slowest-stage rate. A learner that stops each stage on its own, as IATS does, finishes when its slowest stage finishes, and bounds on each stage's expected stopping time give only the sum over stages (Remark 8). We prove a stronger tail bound for each stage, adapting Garivier and Kaufmann (2016). It gives the slowest-stage rate without the bounded means that CombGame (Jourdan et al., 2021) assumes (Lemma 9, Theorem 4(iii)).

This matters in practice, because it tells a designer when the graph pays off. It also matters for point 3, because decoupled MDPs are the special case of the coupled problem with one state per stage, so any coupled theory must naturally cover them.

3. Without stage decoupling. This is the next step in our research, and Appendix D already starts it, for MDPs with known transitions. We have already drawn important conclusions from it.

  • Lower bounds. When no branch is optimal, the blind lower bound still grows at least linearly in the branches at each state that has them, and the graph-aware one does not depend on them (Lemma 11, Proposition 2).
  • The difficulty coupling adds. When an action decides which states come next, the action with the best immediate reward may not be the best action. So a learner that picks the best immediate action at each state can return the wrong policy (Example 1(a)).
  • A first learner. Where the best immediate actions do form the optimal policy, our per-state stopping rule is provably δ\delta-correct (Lemma 10 and a union bound). On E5, an MDP of this kind that is not decoupled, the blind learner with the same rule needed 2.06 times as many episodes, and no run over 300 seeds returned a wrong policy.
  • Next. A learner that matches the coupled lower bound (Conjecture 1). It would track how often each state and action is visited, and stop by a likelihood-ratio test against every policy change, including those that act through later-stage values. Even without a graph, where transitions must also be learned, the closest guarantees are 4 times and 2 times an upper bound on the optimal rate, not the rate itself (Al Marjani and Proutière, 2021; Al Marjani et al., 2021).
Reviewer_DjAROpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper analyzes how much the sample complexity of best policy identification can be reduced by using a known causal graph to eliminate interventions that do not affect the reward. Under Gaussian rewards and a known observational baseline, it compares the characteristic times of graph-aware and graph-blind learners and establishes a gap proportional to the number of non-ancestor interventions. It extends this analysis to decoupled causal MDPs, proving that the stagewise characteristic times combine as a maximum under episodic access and as a sum under generative access. The proposed algorithm, IATS, applies Track-and-Stop to ancestor actions and asymptotically attains the corresponding lower bound under additional conditions.

Critical strengths

NA

Critical weaknesses
  1. The sequential decision structure covered by the main results and the additional algorithmic contribution are narrow. Under Assumption 3, each episode visits every stage once, and variables from other stages cannot be ancestors of a given stage's reward (p. 6). Thus, an action at one stage does not affect future state visitation or rewards at other stages. In this setting, IATS eliminates non-ancestor actions and runs existing Track-and-Stop separately at each stage (Section 5, p. 7). The authors also explain that the linear separation in the number of non-ancestor actions is itself the arm-count scaling of best-arm identification (Appendix C.7, Remark 4; p. 19). While the exact constants and composition analysis are valuable, my main concern is that the resulting new causal and algorithmic insights are limited.

  2. Instance-optimality holds under narrower conditions than the correctness guarantee for identification. For the characteristic time of the ancestor bandit attained by IATS to match the graph-aware lower bound, a sufficient condition is (H): all ancestor actions have means at least as large as the baseline. The paper also gives an example in which the two values differ strictly without (H) (Appendix C.6, Remark 3; p. 19). Interventions that affect the reward can naturally worsen outcomes, so this is a substantive limitation. Although some weaker sufficient conditions are also provided, the current algorithm cannot be concluded to be optimal over the entire graph-aware class analyzed. Together with the assumptions of a known baseline and reward variance, this narrows the applicability of the optimality result.

  3. The experiments primarily confirm the constructed separation and do not sufficiently establish the practical significance of the proven optimality. The main experiments focus on settings satisfying (H), such as ancestor means of (1.0, 0.5) and a baseline of 0.2 (p. 27). Moreover, allocations are updated every 20 rounds in E2 and E3 and every 50 rounds in E4, whereas the proven asymptotic rate applies to updates at every round; the authors do not claim the same rate for the cached rule (p. 24). With the analyzed threshold, the ratio of the mean stopping time of IATS to T⋆log⁡(1/δ)T^\star\log(1/\delta) is still 3.23 at δ=10−4\delta=10^{-4} (p. 27). This does not refute the asymptotic theorem, but it limits how much the leading constant explains actual costs over the current experimental range. Validation that narrows the gap between theory and implementation is needed.

Questions for authors
  1. Beyond eliminating non-ancestor actions and applying existing Track-and-Stop, which new theorems or resolutions of technical obstacles constitute the central contribution? In particular, please distinguish the new arguments needed for the stagewise maximum and sum composition laws.
  2. In the existing counterexample where (H) fails, could you quantify the gap between the constant attained by the current IATS algorithm and the exact graph-aware characteristic time? Understanding how large this gap can be would help assess the scope of optimality.
  3. In a representative existing setting, could you compare updates at every round with cached updates in terms of sample count and computation time? This would be a limited additional analysis to assess how faithfully the experiments reflect the benefits of the proven algorithm.
2 comments
AuthorsOpenReview ↗

Response to Reviewer DjAR (part 1 of 2)

Thank you for the thoughtful and engaging review. We address and outline the new revision to the paper below to each theme identified by you.

DjAR-W1. Narrow structure; limited new insight

We agree. Under Assumption 3 the model is HH bandits tied by the sampling protocol, and IATS is Track-and-Stop on the ancestor arms. Sections 1 and 4 now say so. Our new revision adds two results beyond pruning. Theorem 2 prices pruning exactly. With a known baseline, a harmful intervention can be ruled out against doing nothing. Pruning misses this but needs less than 4 times the graph-aware lower bound, a tight constant. The gain needs the baseline together with the graph. With k≥1k\ge1 branches, a blind learner told the baseline gains nothing (Lemma 5). Theorem 5 gives a learner that captures the gain. Graph-aware Track-and-Stop with C-tracking attains TG∗T^\ast_G on every instance with a unique best arm. See also DjAR-Q1.

DjAR-W2. Optimality only under (H); known baseline and variance

Theorem 5 removes this limitation on the known-baseline class MG\mathcal M_G. Track-and-Stop that C-tracks a maximiser of the graph-aware program and stops by the certified rule (Proposition 4) attains TG∗T^\ast_G on every instance with a unique best arm, with no condition (H) (Appendix E.6). Corollary 4 extends this to both protocols. The proof follows Degenne and Koolen (2019, Theorem 7). The graph-aware objective is concave, so its maximisers form a convex set, and C-tracking, which follows the running sum of the computed allocations, settles on this set. D-tracking is covered only where the maximiser is unique (Remark 10).

On MG\mathcal M_G, IATS itself needs less than 4 times the lower bound (Corollary 2). It is optimal on every instance when the baseline is not given, that is, on the class MG0\mathcal M^0_G of Section 3.1 with the null arm added (Theorem 2(iv), Corollary 2). Known variance is the standard Gaussian setting of the Track-and-Stop literature, and Section 8 lists it as a limitation.

DjAR-W3. Experiments confirm the construction; cached updates; 3.23

All bandit and layered runs now update the allocation every round (see DjAR-Q3). E6 uses 36 random instances with up to 8 ancestor arms, 13 of which violate (H). On all 36, TG∗=Tanc∗T^\ast_G=T^\ast_{anc}, so E6 tests the speed-up, which is 1.00 to 1.57 times the prediction.

E7 tests optimality where Tanc∗>TG∗T^\ast_{anc}>T^\ast_G, with a harmful rival dd below the baseline. At δ=10−2\delta=10^{-2} and d/Δ0=8d/\Delta_0=8, the certified stop speeds IATS up by 1.58 and never delays it. Tracking the graph-aware allocation gives 2.74 with D-tracking and 2.59 with the C-tracking of Theorem 5, against the predicted 3.16. On three instances with 3 or 4 ancestor arms, added after review, tracking gives 1.62 to 2.06 against predictions of 1.91 to 2.30 (Section 6, Appendix F.2).

On the 3.23, the gap is the threshold's lower-order term. At δ=10−4\delta=10^{-4} the leading term explains about 31% of the stopping time, and at every δ\delta the stopping time stays within 3% of T∗β(τ,δ)T^\ast\beta(\tau,\delta). With the δ\delta-correct mixture threshold of Jourdan and Degenne (2023, Lemma 2.1), whose rate we do not prove, the ratio falls to 2.32 with no errors (E2 in Section 6, Appendix C.14, Table 5).


AuthorsOpenReview ↗

Response to Reviewer DjAR (part 2 of 2).

DjAR-Q1. Central contribution; new arguments for the max and sum laws

The central additions are Theorems 2 and 5. Theorem 2 answers whether pruning is the whole value of knowing the reward's ancestors. The answer is yes when the baseline must be learned. With a known baseline, pruning needs less than 4 times the graph-aware lower bound, a tight constant, and Theorem 5 attains the remaining value with a learner that does more than prune.

What is standard, now explicit in our revision. Theorem 1(i) is the Gaussian bracket of Garivier and Kaufmann (2016, §2.2) applied to kk branches, each at gap Δ0\Delta_0 by Lemma 1, so the slope 2σ2/Δ022\sigma^2/\Delta_0^2 is set by the gap between the best intervention and doing nothing, not by the ancestor gaps. What Theorem 1 adds is part (ii), that the graph-aware time does not depend on kk (Remark 4). Zero weight on the best arm (Theorem 2) is the mechanism of the lowest-mean test of Kaufmann et al. (2018). New are the tight bound Tanc∗<4TG∗T^\ast_{anc}<4T^\ast_G for any number of arms and exactness when the baseline is not given.

Composition laws. The characteristic-time identities are elementary. Episodic allocations form a product of simplices, so the program separates into its worst stage. Generative allocations share one budget, so homogeneity splits it across stages in proportion to Th∗T^\ast_h. The lower bounds apply the change of measure of Kaufmann et al. (2016) to the bandit with arms (stage, arm). The episodic program is the semi-bandit program of Jourdan et al. (2021), whose CombGame attains it for bounded means. New is that per-stage Track-and-Stop attains it for Gaussian means with no bound on them. This needs a bound on E[max⁡hτh]\mathbb E[\max_h\tau_h] rather than max⁡hE[τh]\max_h\mathbb E[\tau_h]. It follows from the δ\delta-uniform tail bound of Lemma 9 and max⁡hτh≤max⁡hTh+∑h(τh−Th)+\max_h\tau_h\le\max_hT_h+\sum_h(\tau_h-T_h)^+ (Theorem 4(iii)). Lemma 9 also gives the rate T∗T^\ast for our threshold. Its exponent α=3\alpha=3 lies outside the range α∈[1,e/2]\alpha\in[1,e/2] of Garivier and Kaufmann (2016, Theorem 14), which moreover states the rate αT∗\alpha T^\ast (Remark 8).

Theorem 5 re-runs the C-tracking proof of Degenne and Koolen (2019, Theorem 7) for the certified stop and our threshold (Appendix E.6). Lemma 12 re-proves their regularity properties for the graph-aware program, including at instances where the best arm has zero weight in every maximiser.

DjAR-Q2. Gap without (H) on the counterexample

On μ=(1,−5)\mu=(1,-5), μ0=0\mu_0=0, σ=1\sigma=1, the exact graph-aware time is TG∗=2/25T^\ast_G=2/25, with optimal allocation (0,1)(0,1). The optimal learner only certifies that the rival lies below the baseline. IATS attains Tanc∗=2/9T^\ast_{anc}=2/9, a ratio of 25/9≈2.7825/9\approx2.78, and no learner that is δ\delta-correct on every Gaussian bandit over the ancestor arms does better (Fact 1).

In general TG∗≤Tanc∗<4TG∗T^\ast_G\le T^\ast_{anc}<4T^\ast_G, and 4 is approached but never reached (Theorem 2). With two ancestor arms the ratio is 1 if d≤Δ0d\le\Delta_0 and 4d2/(Δ0+d)24d^2/(\Delta_0+d)^2 otherwise, where d=μ0−μbd=\mu_0-\mu_b is the rival's distance below the baseline.

Theorem 5 removes this gap. Graph-aware Track-and-Stop with C-tracking attains TG∗T^\ast_G on every such instance. In E7 at δ=10−2\delta=10^{-2} it is 1.78, 2.46 and 2.59 times faster than IATS at d/Δ0=2d/\Delta_0=2, 4 and 8, against the predicted 1.78, 2.56 and 3.16 (Section 6).

DjAR-Q3. Every-round versus cached updates

In E2 to E4, IATS has two ancestor arms with equal σ\sigma, so its allocation is (1/2,1/2)(1/2,1/2) for every estimate and caching cannot change it. On the store with k=8k=8 and 300 seeds, its mean stopping time is 782 at δ=10−2\delta=10^{-2} and 952 at 10−410^{-4} with both every-round and cached updates, which differ only through tie-breaking (Table 4). Caching made the blind learner 4% slower at 10−210^{-2} and 3% at 10−410^{-4}. At δ=10−2\delta=10^{-2}, every-round updates cost 0.31 s (IATS) and 0.73 s (blind) per run, against 0.02 s and 0.05 s cached. The new solver takes 0.3 ms per call.

All bandit and layered runs now update every round. The E3 speed-ups become 1.35 to 6.62 (previously 1.42 to 6.77), at 1.09 to 1.40 times the prediction. With two ancestor arms IATS never exercises tracking, so E6 adds up to 8 ancestor arms and E7 up to 4.


Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to the reviewers

We thank the reviewers for their thoughtful and in-depth engagement with our work. The shared concern is that IATS only prunes and runs Track-and-Stop. The revision answers it with two new results and fixes the code bugs identified. Numbers refer to the revised PDF, where new text is in blue for easy identification. The submitted Theorems 2 and 3, Corollary 2 and Definitions 7 to 9 are now Theorems 3 and 4, Corollary 3 and Definitions 9, 7 and 8.

  1. What pruning is worth (Theorem 2, Section 3.1). With a known baseline, pruning needs less than 4 times the number of samples of the graph-aware lower bound and loses nothing under condition (H), meaning that every ancestor intervention is at least as good as doing nothing. When pulls reveal only the reward and the baseline must be learned, pruning is exactly optimal on every instance, so IATS is optimal there without (H) (Corollary 2).

  2. An optimal learner with a known baseline (Theorem 5, Corollary 4, Appendix E.6). Graph-aware Track-and-Stop removes the gap that pruning leaves. It C-tracks the graph-aware allocation, pulling the arm whose count lags furthest behind the running sum of all the allocations computed so far, so it settles on an optimal allocation even when that allocation is not unique. It stops by the certified rule, which can also rule out a rival by showing it is worse than doing nothing. On every instance with a unique best arm, without (H), it attains the graph-aware characteristic time TG∗T^\ast_G, so its expected sample count matches the lower bound, about TG∗log⁡(1/δ)T^\ast_G \log(1/\delta) for small δ\delta. Its layered version attains the lower bounds of Theorem 3 under both protocols.

  3. Positioning. We have carefully extended the related work, explicitly crediting pruning to Lee and Bareinboim (2018, 2019), the Gaussian bracket behind Theorem 1(i) to Garivier and Kaufmann (2016, §2.2), the episodic program to the semi-bandit program of Jourdan et al. (2021), whose CombGame attains it for bounded means, and zero weight on the best arm to the lowest-mean test of Kaufmann et al. (2018). Appendix B now says which proof steps are standard, and Section 8 states the limitations.

  4. Experiments. Every bandit and layered learner recomputes its allocation every round. New runs cover a proven threshold (E2), 36 random instances with up to 8 ancestor arms, misspecified noise and heterogeneous stages (E6), and instances that violate (H), with both tracking rules and up to 4 ancestor arms (E7). IATS and its variants never returned a wrong answer.

  5. Code. Bugs identified by Reviewer FKcM are fixed and tested, and the solver inconsistency did not affect any of the reported runs. With every warm-up episode counted, the E5 speed-up over 300 seeds is 2.64 (95% interval 2.53 to 2.76, against 2.62 on 60 seeds in the submission). The code repository now also holds the result files behind every number and figure.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.