Random reshuffling now has an upper bound that dominates stochastic gradient descent at every constant step $\eta\leq1/(6L)$ and every finite horizon. Its matching lower bound was left open. We solve this problem for the exact all-inner average used by the upper bound. The answer is not the published horizon-independent stochastic envelope. If $\alpha=\eta nL\leq1$, the fixed-step minimax stochastic error is $\Theta \left(\eta^2nL\sigma_\star^2 \left[K^{-1}+\min\{(\alpha K)^2,1\}\right]\right).$ It decreases, increases, and then plateaus across three horizon regimes. Its minimum occurs at $K\asymp\alpha^{-2/3}$, before the usual mixing scale $\alpha^{-1}$. For $\alpha\geq1$, the law is $\Theta(\eta\sigma_\star^2)$. The upper bound follows from an exact finite-population bridge identity and a dimension-free control of all state memory as a Lipschitz remainder. The lower bound combines a centered common-Hessian bridge with a rectifying piecewise quadratic in two dimensions. An exact telescoping identity explains why common-Hessian quadratics alone miss the eventual floor. Together with the deterministic term, this gives a complete minimax characterization for all horizons and this full step range. Optimizing the step recovers the best known tuned rate up to the unavoidable initial-error cap, while the fixed-step theorem reveals a nonmonotone transient hidden by that rate.
Keywords: random reshuffling, finite-horizon analysis, without-replacement SGD, minimax rates, step size, convex optimization