Counterfactual Predictive State Representations: The Intrinsic Dimension of Partial-Information Games

We study finite-horizon two-player zero-sum perfect-recall partial-information games and ask for the minimal finite-dimensional state sufficient to answer all rooted observation-measurable unilateral continuation queries. For each player $i$ and information set $I$, we consider the span ${\mathcal{L}}_i(I)$ of feasible counterfactual beliefs and the effective local query space ${\mathcal{E}}_i(I)$ generated by rooted continuation queries restricted to ${\mathcal{L}}_i(I)$. We prove that its dimension $d_i(I)$ is simultaneously the rank of the local counterfactual query operator, the minimum core-query basis size, the minimum exact local realization dimension, and the dimension of the canonical quotient ${\mathcal{L}}_i(I)/{\mathcal{N}}_i(I)$, yielding reduced counterfactual predictive-state representations, unique up to similarity, with exact first-return update operators. Aggregating the local ranks defines the deviation-conditioned predictive-state dimensions $d_t^i$, $d_t$, $d_{\star }$, and $D_{\star }$. We then prove that local rooted payoff-query control transfers to global exploitability, and under local design richness and bounded one-step parameter norms obtain a rollout-based upper bound in these minimal coordinates. We complement this with a minimax lower bound showing that $\Omega (d/{\gamma }^2)$ local rollouts are necessary even when the peak DCPSD equals $d$, and with an exponential separation theorem exhibiting games with $d_{\star }=m$ but observable continuation-trace complexity $2^m$. Finally, we show that DCPSD recovers finite-rank predictive-state, observable-equivalence, and linearly parameterized continuation-law models as special cases.