Open problem MAIS-O25 · posed in MAIS-A2 as Problem 4.3 · Status: open.
Tags: interpretability · world-model discovery · eliciting latent knowledge · black-box evaluation · complexity theory · statistics. Difficulty: ★★.
Authored by: Claude Fable 5 directed by Lionel Levine · Audited by: GPT 5.6 Sol.
Each question to an optimal agent — what do you do in this tampered environment? — returns a single bit. Mixing two interventions with weight $q$ and bisecting on the weight at which the agent's action switches converts those bits into binary digits of an interventional probability, and sweeping over interventions recovers the agent's whole causal model. That is the algorithm of Richens and Everitt [RE24], run with unlimited exact queries. For an evaluator who wants to read a black-box agent's world model off its behavior, the accounting question comes first in any finite theory: how many queries?
The framework (a finite causal influence diagram with binary variables and known utility): a skeleton $\mathsf{s}=(\mathbf{C},\mathbf{O},\mathbf{Z},u)$ fixes $m$ binary chance variables, an observation set, utility parents, and the utility; a single binary decision $D$ with parents $\mathbf{O}$ completes the diagram, so a policy assigns to each observation the probability of playing $D=1$. A model $M=(G,\theta)$ is a directed acyclic graph with conditional probability tables, $K(G)$ free entries in all; the margin class $\mathcal{M}(\mathsf{s},\lambda)$ is cut out by explicit margin conditions at scale $\lambda$, bounding probabilities, utility gaps, and edge strengths away from the degeneracies that make behavior uninformative (the agenda's (M1)–(M6)). The analyst adaptively issues queries $(\sigma,\mathbf{O}',w)$ — a mixture of local interventions, an observation mask, an observed value — and the policy-probability oracle answers with the exact probability that an optimal policy, pre-committed by an adversary, plays $D=1$ on observing $w$; at $\delta=0$, away from ties, that is a bit. The minimax risk at budget $N$ is the best worst-case expected error in graph and tables, and packing plus Fano gives an information-theoretic floor $N=\Omega(K(G)\log(1/\varepsilon))$ (the agenda's Remark 3.3).
Problem (MAIS-A2, Problem 4.3). Let $\mathcal{N}\subseteq\mathcal{M}(\mathsf{s},\lambda)$ be a compact semialgebraic class satisfying conclusions (a)–(b) of the agenda's Problem 4.2 with modulus $\omega(\delta)=L\delta$. Assume also a richness condition: for some graph $G$ and $\rho>0$, its table-parameter projection contains a $K(G)$-dimensional box of side $\rho$. Determine, up to constants depending on $(m,K,\lambda,L,\rho)$, the minimal budget $N(\varepsilon)$ such that the minimax risk over $\mathcal{N}$ at budget $N(\varepsilon)$, with $\delta=0$ and the policy-probability oracle, is at most $\varepsilon$. In particular: decide whether $N(\varepsilon)\le \mathrm{poly}(K,1/\lambda,L,1/\rho)\log(1/\varepsilon)$, and whether adaptive queries outperform non-adaptive ones by more than a constant factor.
The hypotheses imported from Problem 4.2 (MAIS-O24) say that on the class $\mathcal{N}$, behavior determines the model, with recovery Lipschitz in the regret — a policy's shortfall in expected utility from the best policy for its task. The upper-bound side looks like bookkeeping (bisect each of the $O(K)$ needed critical weights to precision $\varepsilon\cdot\mathrm{poly}(\lambda)$), but it is not: the reconstruction of Richens and Everitt [RE24] solves for table entries recursively outward from $\mathbf{Z}$, and errors compound through quotients whose denominators are the quantities the margins bound. Whether the compounding is polynomial or exponential in the depth of the diagram is the real question, and a negative answer would be just as interesting. For the query formalism and the margin conditions in full, see MAIS-A2.
References
- [RE24] J. Richens and T. Everitt, Robust agents learn causal world models, ICLR 2024. arXiv:2402.10877
- [EGS05] F. Eberhardt, C. Glymour, and R. Scheines, On the number of experiments sufficient and in the worst case necessary to identify all causal relations among N variables, UAI 2005.
Related: MAIS-O26 (the conjectured answer) · MAIS-O24 (supplies the hypotheses) · MAIS-O2 (sampled actions replace the oracle).