Efficient Online Reinforcement Learning with All-Policy Linear $Q$-Realizability and Sparse Stochastic Transitions

We study computationally efficient online reinforcement learning in potentially infinite state spaces. At each layer, every Markov policy's action-value function is linear in the same known $d$-dimensional features, and each transition has at most $K$ possible successor states. Under these assumptions, we give a polynomial-time algorithm with high-probability regret $\tilde{O}\left(dH\sqrt{A\min \{A,d\}KH(H-1)T}\right)$ for $A$ actions, horizon $H\ge 2$, and $T$ episodes. The algorithm discovers a finite set of noninitial states on which to concentrate learning, then combines a linear contextual bandit at the first layer with tabular learning on stored states and a fixed default policy elsewhere. The guarantee allows rewards in $[0,1]$ and arbitrary initial-state distributions. The algorithm uses only online episodes, without a simulator, resets to chosen states, or a policy-optimization oracle, and requires neither a linear transition model nor Bellman completeness.