Rapid Mixing Is Not Enough: Hardness of Action-Conditioned Predictive Representation Optimization

Action-conditioned self-prediction learns shared state representations for reinforcement learning by predicting future representations under different actions. However, existing spectral solutions for the associated tabular objective rely on a common eigenbasis, leaving the complexity of global optimization beyond this setting unresolved. We study this question for centered and whitened representations in finite state spaces, removing the constant component and normalizing feature covariance. We prove worst-case computational hardness of approximating the optimal objective value to inverse polynomial additive accuracy, even for strictly positive, symmetric transition kernels that mix rapidly and retain fixed signal strength after centering. Our construction embeds a hard graph problem into valid transition kernels, and a further reduction extends the hardness to every fixed representation dimension. For symmetric kernels, we give exact solutions when they commute and efficient additive approximation for a single feature when the centered operators span a space of fixed dimension. The hard instances also admit exact realizations as finite transition datasets. For the scalar empirical cross-covariance objective, polynomially many independent stationary samples preserve the hardness gap with high probability, even when centering, whitening, and representation selection use the same data.