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.