Nonexpansive Latent Dynamics Do Not Ensure Sample-Efficient Rich-Observation Reinforcement Learning

We study episodic reinforcement learning with an unknown block-decodable state representation. On the fixed latent interval [0,1], we construct a family with globally Wasserstein-nonexpansive dynamics, 1-Lipschitz latent rewards, known observation rewards, and common finite decoder classes of total log-cardinality O(H^2 log A). Every uniformly PAC learner with a worst-case episode budget requires Omega(A^(H-1) epsilon^(-2) log(1/delta)) episodes, including learners returning randomized, history-dependent policies. Prime contractions store action prefixes in distinct latent coordinates. State-only emissions return the chosen prefix, and the learner receives no feedback about its correctness before the terminal Bernoulli draw. With latent-state access, the same family is learnable in O(H A + A epsilon^(-2) log(A/delta)) episodes. For the general model class, operational latent covers and an effective reward-Lipschitz bound allow finite-policy enumeration and classical importance sampling to give a finite PAC upper bound with the same leading exponential factor. These assumptions therefore permit finite learnability without guaranteeing sample complexity polynomial in the horizon. Fixed strict contraction and the joint minimax rate remain unresolved.