Policy-gradient methods are central to modern reinforcement learning, including LLM post-training. When they struggle, the usual suspects are exploration, credit assignment and action-sampling noise. Classification has none of them. A classifier is a policy whose expected reward, its expected accuracy, is the probability it assigns to the correct label, and because that label is known, the policy gradient is exact and smooth. Yet exact policy gradient loses to cross-entropy, even on expected accuracy. The exact gradient is myopic: it values an update only by what it buys now, but each update also sets where the next one starts, so an update's value depends on how much learning remains. Viewed this way, cross-entropy is patient accuracy, the total error an example would pay if its log-odds rose at unit speed forever, while exact policy gradient is the zero-horizon limit. Truncating this total at the learning that remains yields the horizon loss, a one-line change that moves from cross-entropy toward exact policy gradient as training runs out. In a simple allocation model, it provably escapes the trap that catches each endpoint. On MNIST and on ImageNet with ResNet-50, ResNet-101 and ViT-S/16, the horizon loss improves top-1 accuracy over cross-entropy at a flat learning rate, and the gain grows with label noise.
Figures & tables
Figure 1: Expected test error (log scale) over training at a shared flat learning rate, MNIST (MLP) ∣ ImageNet (ResNet-50). Exact policy gradient, computed by summing over labels, falls far behind cross-entropy even on expected test accuracy. The horizon loss (Section 3.1 ) pulls ahead of cross-entropy late in training.
Figure 2: (a) Look-ahead from an example at z=−4 . Exact policy gradient uses the local slope p(1−p) , the finite horizon uses the rise σ(z+H)−p over the next H units of learning, and cross-entropy uses the full remaining rise 1−p . (b) Gain in expected accuracy from spending the whole budget H on each example of Proposition 1 ( a=2 ); the better example switches at H=a . (c) Weight on ∇z against the gap at H=4 . Exact policy gradient concentrates near even odds, cross-entropy gives nearly maximal weight to hopeless examples, and the horizon loss targets examples still within reach.
Figure 3: Relative reduction in test error over cross-entropy for expected error (left) and top-1 error (right), mean ±2 SEM over seeds, with the SEM of the ratio propagated from the two independent means. Filled: flat learning rate; open: cosine. The horizon loss has lower mean error than cross-entropy for every model and schedule shown; cosine decay shrinks the gain.
Figure 4: (a, b) Top-1 test error against the fraction of flipped training labels, mean ±2 SEM over 30 seeds on MNIST and 3 seeds per noise level on ResNet-50 (10 at 0%), for one fixed corruption of the labels. ResNet-50 has no exact-PG noise sweep. (c) Mean probability assigned to the flipped label on mislabeled training examples over training. The noise sweep is separate from the main runs of Section 4.1 .
Figure 5: (a) Final test error against κ on MNIST for shrinking, constant and growing horizons matched on mean; dashed: cross-entropy. (b) Final test error on ResNet-50 for a fixed horizon H ; dashed: cross-entropy and the shrinking horizon loss.
Figure 6: Test NLL over training at a flat learning rate: horizon cross-entropy ( κ=10 ) pulls away from cross-entropy late, as Ht shrinks. The horizon loss, built for accuracy, worsens NLL.
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
Symbol
Meaning
K
number of classes
N
number of examples in the allocation model
M
number of lost causes in the lost-cause trap
zi
logit gap of example i : correct logit minus logsumexp of the rest
pi=σ(zi)
probability of the correct label
H
total budget of logit progress in a toy problem
Appendix
Table 1: Notation. Toy-flow time τ and training step t are kept distinct.
Method
Expected
Top-1
n
cross-entropy
96.80±0.03
97.31±0.03
30
exact PG
96.30±0.31
96.43±0.31
30
switch at 0.9
97.12±0.02
97.52±0.02
30
horizon loss, κ=1
97.17±0.02
97.47±0.03
30
Appendix
Table 2: MNIST, flat learning rate: final test accuracy (%), mean ± SEM over n seeds. The switch trains with cross-entropy and switches to exact PG for the last 10% of steps. Bold: best in column.
Method
Expected
Top-1
n
cross-entropy
97.54±0.02
97.73±0.02
30
exact PG
96.82±0.31
96.90±0.31
30
horizon loss, κ=0.3
97.71±0.02
97.79±0.02
30
Appendix
Table 3: MNIST, cosine decay: final test accuracy (%), mean ± SEM over n seeds, each method at its best peak learning rate. Bold: best in column.
Model
Method
Expected
Top-1
n
ResNet-50
cross-entropy
62.1±0.17
67.4±0.17
10
exact PG
4.2±0.31
4.3±0.31
3
switch at 0.9
65.8±0.17
66.7±0.17
3
horizon loss, κ=1
67.3±0.04
68.9±0.05
10
horizon loss, κ=3
67.5±0.04
69.6±0.05
10
ResNet-101
cross-entropy
64.4±0.37
69.0±0.30
3
Appendix
Table 4: ImageNet, flat learning rate: final test accuracy (%), mean ± SEM over n seeds. The calibrated value is κ=3 . Bold: best within each model.
Setting
Method
Expected
Top-1
n
ResNet-50
cross-entropy
65.2±0.02
70.5±0.02
10
switch at 0.9
68.3±0.06
71.2±0.03
3
switch at 0.95
67.5±0.06
71.0±0.06
3
horizon loss, κ=0.3
67.8±0.04
71.1±0.05
10
horizon loss, κ=1
66.8±0.02
70.9±0.02
10
ResNet-50 + WD
cross-entropy
66.6±0.03
73.3±0.04
3
Appendix
Table 5: ImageNet, cosine decay: final test accuracy (%), mean ± SEM over n seeds. WD: weight decay 0.05 . The calibrated value is κ=0.3 . Bold: best within each setting.
Figure 7: Final error against learning rate. (a) MNIST, every method. (b) ResNet-50, cross-entropy and exact PG.
Figure 8: Final error against κ . Dashed lines: cross-entropy and exact PG.
Figure 9: Late switch from cross-entropy to exact PG. (a) MNIST, final error against the fraction of training spent on exact PG, so a switch at 0.9 in Table 2 sits at 0.1. (b) ResNet-50, expected against top-1 accuracy.
Figure 10: Expected error, top-1 error and test NLL against focal γ , ResNet-50, flat learning rate. Dashed lines: cross-entropy, horizon loss and horizon cross-entropy.
Figure 11: Final expected and top-1 error against κ , flat and cosine schedules.
Figure 12: MNIST. (a) Final error against width. (b) Relative error reduction against width. (c) Final error against training budget.
Figure 13: Horizon cross-entropy against cross-entropy on MNIST: test NLL, top-1 error and expected error against κ .