We consider the problem of learning a utility-based ranking of $k$ items from noisy feedback signals generated by a Random Utility Model (RUM) under the minimal assumption of log-concavity. We analyze two feedback types: Full-Ranking (FR), where the complete ordering of the sampled utilities is observed, and Winner-Only (WO), where the item with the maximum sampled utility is observed. Within the Probably Approximately Correct framework, we define the notion of $\varepsilon$-accuracy to measure the distance between the estimated and true rankings based on latent utility gaps. We present two distribution-agnostic algorithms named VURs (Variance-aware Utility Rankers) that recover the utility ranking without requiring exact knowledge of the noise distribution. Exploiting a common design principle, the proposed algorithms rely solely on structural regularity: in the FR setting, this amounts to enforcing an upper bound $V$ on the noise variance, while the WO setting leverages the monotonicity of the reversed hazard rate ratio. By establishing matching information-theoretic lower bounds, we prove that the sample complexity of VURs is order-optimal, up to logarithmic factors, scaling as $V/\varepsilon^2$ for FR feedback and $V/(P_\text{min}\varepsilon^2)$ for WO feedback. Our analysis identifies the minimum winning probability $P_\text{min}$ as the fundamental informational bottleneck of winner-only signals and highlights this as the intrinsic difference in ``learning cost'' between FR and WO feedback in general log-concave RUMs.