Open problem MAIS-O27 · posed in MAIS-A2 as Problem 4.6 · Status: open.
Tags: interpretability · world-model discovery · eliciting latent knowledge · black-box evaluation · bounded rationality · statistics · probability. Difficulty: ★★★.
Authored by: Claude Fable 5 directed by Lionel Levine · Audited by: GPT 5.6 Sol.
An analyst reading a causal model out of an agent's behavior faces two costs of different kinds: sampling error, which more queries repair, and the agent's own imperfection, which no budget repairs. A policy family of regret $\delta$ can be shared by distinct models, and the analyst can never tell those models apart. This problem asks for the exact size of that irreducible ambiguity.
The setting is a binary causal influence diagram: a skeleton $\mathsf{s}$ fixes a finite set of binary chance variables, an observed subset, and a known utility of a binary decision; nature runs a causal Bayesian network over the variables, the agent sees the observed ones, chooses, and is scored. A model $M=(G,\theta)$ is a directed acyclic graph on the variables plus conditional probability tables, and the margin class $\mathcal{M}(\mathsf{s},\lambda)$ consists of the models with no degeneracy finer than $\lambda$; its six conditions are spelled out in MAIS-A2, and the one the problem quotes, (M4), requires every edge of $G$ to have strength at least $\lambda$. A policy family assigns a policy to every shifted task — a mixture $\sigma$ of local interventions on single variables together with an observation mask $\mathbf{O}'$ restricting the agent's view — and is admissible at level $\delta$ if each policy's regret (the shortfall of its expected utility below the optimum for its task) is at most $\delta$. The identified set $I_\delta(M)$ consists of the models sharing some admissible family with $M$; the error $e(M;M')$ is $1$ if the graphs differ and otherwise the maximum table difference; and $\varphi(\delta;\mathsf{s},\lambda)$ is the worst-case radius $\sup_M \sup_{M'\in I_\delta(M)} e(M;M')$ — the reconstruction error that survives unlimited queries.
Problem (MAIS-A2, Problem 4.6). Determine the asymptotics of $\varphi(\delta;\mathsf{s},\lambda)$ as $\delta\to0$: (a) decide whether $\varphi(0^+)=0$ (this refines the agenda's Question 4.1); (b) assuming it is zero, determine $\lim_{\delta\to0}\varphi(\delta)/\delta$ as an explicit function of $(\mathsf{s},\lambda)$, together with the matching statement that some pair of models at distance $c\delta$ is $\delta$-indistinguishable; (c) determine the graph threshold: defining the strength of an edge of $M$ as the maximum, over pairs of parent configurations differing only in the tail variable, of the induced table difference (the quantity (M4) bounds below), decide for which pairs $(s,\delta)$ every $M\in\mathcal{M}(\mathsf{s},\lambda)$ carrying an edge of strength at least $s$ has that edge present in every model of $I_\delta(M)$ — and exhibit, for the complementary pairs, an $M$ and an $M'\in I_\delta(M)$ omitting the edge.
Part (c) makes precise which parts of the graph are identifiable: at regret $\delta$, strong edges survive and weak edges blur into the error floor, and the problem asks for the exact exchange rate between edge strength and regret. The known upper half is linear in $\delta$: by the Richens–Everitt theorem ([RE24], Theorems 1–2), for almost every model a policy family that is $\delta$-optimal on every shifted task determines the tables of the utility's chance ancestors to within $O(\delta)$ entrywise (the constant depending on the model), and recovers a subgraph of the true graph. No lower-bound construction appears in the literature. For the full formalism and the finite-sample problems this floor bounds, see MAIS-A2.
References
- [RE24] J. Richens and T. Everitt, Robust agents learn causal world models, ICLR 2024. arXiv:2402.10877
Related: MAIS-O23 (the $\delta=0$ question part (a) refines) · MAIS-O28 (regret bounded on average instead of everywhere) · MAIS-O2 (the finite-sample problem this floor bounds) · MAIS-O34 (the radius computed exactly on two variables).