Open problem MAIS-O2 · headline problem 2 of the survey MAIS-P1 · canonically formalized in MAIS-A2 as Problem 4.5 · Status: open.
Tags: interpretability · world-model discovery · eliciting latent knowledge · black-box evaluation · statistics · probability · complexity theory. Difficulty: ★★.
Authored by: Claude Fable 5 directed by Lionel Levine · Audited by: GPT 5.6 Sol.
Tomography reconstructs the inside of a body from measurements taken outside it. Here the body is an agent, the measurements are its actions, and the object to reconstruct is the causal model its behavior relies on. Richens and Everitt [RE24] proved the analogue of Radon's inversion formula: a policy family that stays near-optimal across all local interventions on its environment determines an approximate causal model of that environment. Their algorithm consumes an oracle for the entire policy family, but an auditor probing a trained AI system gets finitely many sampled actions. Missing is what a working tomographer needs: how many sampled actions buy how many digits of the reconstruction.
The setting is a finite causal influence diagram with binary variables and known utility. A skeleton $\mathsf{s}=(\mathbf{C},\mathbf{O},\mathbf{Z},u)$ lists the binary chance variables $\mathbf{C}$, the subset $\mathbf{O}$ the agent observes, the utility parents $\mathbf{Z}$, and a known utility $u(d,z)\in[0,1]$ of the binary decision $d$; a model $M=(G,\theta)$ is a directed acyclic graph on $\mathbf{C}$ together with its conditional probability tables, constrained to a class $\mathcal{M}(\mathsf{s},\lambda)$ by explicit margin conditions (all table entries, utility gaps, and edge strengths at least $\lambda$ from degeneracy; MAIS-A2, Definition 3.1). A query names a mixture $\sigma$ of local interventions on the chance variables (each fixing or flipping a single variable, leaving all other mechanisms unchanged), an observation mask $\mathbf{O}'\subseteq\mathbf{O}$, and an observation $w$; an adversary has pre-committed, for every such shifted task, a stochastic policy $\pi_{\sigma,\mathbf{O}'}$ of regret at most $\delta$, and the answer to the query is one action sampled from $\mathrm{Bernoulli}(\pi_{\sigma,\mathbf{O}'}(w))$. Two quantities frame the problem, both measured in the error that counts a wrong graph as $1$ and is otherwise the largest entrywise difference of the tables: the minimax budget, the number of queries needed to output graph and tables to error $\varepsilon$ against the worst model and adversary, and the identified-set radius $\varphi(\delta;\mathsf{s},\lambda)$, the ambiguity that survives unlimited queries because distinct models can share a $\delta$-optimal policy family.
Problem (MAIS-A2, Problem 4.5). In the setting of the agenda's Problem 4.3 (a compact semialgebraic class of models on which exact behavior determines the model with Lipschitz modulus), replace the policy-probability oracle by sampled actions and allow $\delta\ge0$. Determine the minimax budget $N(\varepsilon,\delta)$ for recovering the graph and tables to error at most $\varepsilon$, or prove that the target lies below the identified-set radius $\varphi(\delta;\mathsf{s},\lambda)$ and is therefore impossible. Separate three contributions: locating the switching surfaces of the optimal policy family, estimating the probabilities of genuinely stochastic policies, and the irreducible ambiguity caused by regret. Then add independent response corruption at a known level $\zeta<\tfrac12$ and determine its cost.
At $\delta=0$ optimal policies are deterministic away from switching surfaces, so sampled actions are noiseless bits and the one-dimensional core is binary search; positive regret smears behavior into a band the analyst must estimate rather than locate. The problem thus interpolates between bisection and Bernoulli regression, with Rényi–Ulam lie-tolerant search [RMKWS80] and noisy binary search [KK07] supplying the endpoints; the coupled causal reconstruction is the open part. (Response corruption at level $\zeta$ flips each returned action independently with probability $\zeta$.) For the behavioral transform being inverted and the full query formalism, see MAIS-A2.
References
- [RE24] J. Richens and T. Everitt, Robust agents learn causal world models, ICLR 2024. arXiv:2402.10877
- [RMKWS80] R. L. Rivest, A. R. Meyer, D. J. Kleitman, K. Winklmann, and J. Spencer, Coping with errors in binary search procedures, Journal of Computer and System Sciences 20(3) (1980), 396–404.
- [KK07] R. M. Karp and R. Kleinberg, Noisy binary search and its applications, SODA 2007, 881–890.
Related: MAIS-O25 (the exact-oracle version this builds on) · MAIS-O27 (the regret floor $\varphi$) · MAIS-O26 (conjectured rate for the exact oracle) · MAIS-O35 (the two-variable starter case).