Order-Sensitive Sequential Interventions on Ideal Lattices

1. Problem Statement

The paper addresses sequential intervention problems where actions are constrained by prerequisite structures. In domains such as tutoring (skill dependencies), medical treatment design (state-based feasibility), and workflow control, the set of admissible action sequences is not arbitrary but governed by a partial order (poset).

• Core Challenge: In unconstrained environments, the order of actions may be irrelevant (path independence). However, in prerequisite-constrained environments, the sequence in which admissible actions are executed can significantly alter downstream outcomes (order sensitivity).
• Formal Framework: The state space is modeled as the ideal lattice $J(P)$ of a finite poset $P$. A state is a down-closed set (an ideal) of satisfied prerequisites. A valid transition adds an element whose predecessors are already present.
• Goal: To develop an exact theory for quantifying how the order of interventions affects path values, determining when path values are order-independent, and establishing conditions for identifying causal effects and planning optimal sequences.

2. Methodology and Theoretical Framework

The paper employs a synthesis of combinatorial lattice theory, algebraic topology (via chain complexes), and causal inference.

A. Structural Decomposition: Diamonds and Swaps

The authors show that the space of admissible paths between two states (ideals $I$ and $J$) is connected by elementary local moves.

• The Diamond: The minimal non-trivial structure is a "diamond," formed by two incomparable elements $u, v$ over a base ideal $I$. There are two paths: $I \to I \cup \{u\} \to I \cup \{u, v\}$ and $I \to I \cup \{v\} \to I \cup \{u, v\}$.
• Diamond Representation Theorem: Any two admissible paths with the same endpoints differ by a finite sequence of diamond swaps (swapping the order of adjacent incomparable elements). This reduces global order sensitivity to local diamond geometry.

B. Curvature and Path Independence

The paper defines a diamond curvature $\kappa_x(d)$ for a diamond $d$, representing the value difference between the two paths bounding the diamond.

• Integrability: Path independence (where value depends only on endpoints) is equivalent to vanishing curvature ($\kappa = 0$) everywhere.
• Potential Function: If curvature vanishes, the path value is determined by an endpoint potential function $\Phi_x$, which admits a canonical Möbius parametrization on the incidence algebra of the lattice.
• Exact Decomposition: With non-vanishing curvature, the value of any path $\gamma$ is exactly decomposed into a reference path score (based on a fixed reference order) plus a sum of signed local curvatures corresponding to the diamond swaps required to transform the reference path into $\gamma$.

C. Global Realizability and Cube Consistency

The paper investigates when a local field of diamond curvatures can be generated by a global, edge-based path model.

• Cube Consistency: A local curvature field is globally realizable if and only if it satisfies cube consistency (a discrete Bianchi identity on 3-cubes formed by three incomparable elements).
• Uniqueness: Once a "gauge" (reference tree scores) is fixed, the realizing edge field is unique.

D. Causal Identification

Under standard assumptions of longitudinal causal inference (consistency, sequential ignorability, positivity), the paper derives support separation theorems:

• Reference Path Scores: Identifiable if the reference path is supported (observed with positive probability).
• Local Order Effects: Identifiable only if the diamond is two-sided supported (both orders of the incomparable pair are observed).
• Implication: Order effects are harder to identify than reference scores because they require data supporting both local permutations.

3. Main Contributions

1. Exact Local-to-Global Theory: Proof that all order sensitivities in prerequisite-constrained sequential interventions are generated by local diamond swaps.
2. Curvature Decomposition: Provision of an exact formula for decomposing path values into a reference score and curvature corrections, linking the problem to Möbius inversion on distributive lattices.
3. Realizability Theorem: Establishment of cube consistency as the necessary and sufficient condition for a local diamond field to be realizable by a global edge model, with uniqueness guaranteed after gauge fixing.
4. Causal Support Separation: Demonstration that reference path scores and order-sensitive effects have distinct identification requirements, specifically that order effects require two-sided support on diamonds.
5. Planning Algorithms:
   • Derivation of an order-insensitivity bound based on maximum curvature and the number of swaps.
   • Proof that optimal planning can be performed via dynamic programming on the truncated ideal lattice (Hasse diagram).

4. Results and Empirical Validation

Theoretical results are validated using a public reviewing event log (e.g., scientific paper reviews).

• Data Structure: The dataset naturally forms local diamonds where two incomparable review activities ($r_1, r_2, r_3$) precede a target activity (e.g., "decide" or "compile").
• Support Heterogeneity: Empirical analysis confirms the theory: endpoint support (observation of the final state) is broad, but two-sided order support (observation of both $u \to v$ and $v \to u$) is sparse and heterogeneous.
• Decomposition Accuracy: The reference path decomposition ($V = \Phi^\rho + \kappa$) reconstructs observed path values with zero reconstruction error (up to numerical precision).
• Planning Performance:
  • Order-sensitive policies (using the full model) significantly outperform reference path baselines and greedy one-step policies only in families with strong local order signals (non-vanishing curvature).
  • In families with weak signals, the complex policy collapses to simpler baselines.
  • Dynamic Programming vs. Exhaustive Search: The DP algorithm on the truncated lattice yields exactly the same optimal paths as exhaustive search, confirming computational efficiency.

5. Significance and Implications

• Theoretical Unification: The paper connects combinatorial lattice theory (linear extensions, Möbius functions) with causal inference and sequential decision-making. It provides a rigorous geometric interpretation of "order effects."
• Practical Planning: It offers a computationally efficient method (dynamic programming on the lattice) for planning in constrained environments, avoiding the exponential complexity of full sequence enumeration.
• Causal Insight: The "support separation theorem" is a critical contribution to causal inference, clarifying that learning how order matters requires specific data coverage (two-sided support) often missing in real logs, even when final outcomes are well-observed.
• Limitations: The current theory is restricted to finite posets, finite horizons, and edge-summed value functions. Extensions to continuous spaces or non-additive functionals are noted as future work.

In summary, the paper provides a complete mathematical framework for understanding, identifying, and optimizing sequential interventions where the order of actions is constrained by prerequisites, proving that local geometric inconsistencies (curvature) fully determine global path differences.