Photos taken under uneven lighting have deep shadows and bright highlights in the same frame, so a single global brightening step cannot fix them. Learned enhancers are fast, and some of them train with reinforcement learning (RL): the model improves by trial and error against a reward, which is expensive. These methods are scored almost entirely by PSNR, a pixel-error score, against reference photos. The field also has an older, slower tool that plays the role exact solvers play in combinatorial optimization. That tool is a variational model, an explicit energy function over the image's illumination and surface reflectance that a numerical solver minimizes. Nobody asks how far a fast enhancer's output is from that solver's optimum, or how much compute it takes to get close. This note proposes to ask exactly that. We treat the weighted variational Retinex model of A Weighted Variational Model for Simultaneous Reflectance and Illumination Estimation as the "Concorde" of illumination decomposition. We measure every enhancer by its gap to that solver's best-known objective as a function of compute. We then build a guided solver that closes the gap cheaply.
The guided solver follows the recipe that works best in combinatorial optimization. A small network supplies guidance, and a classical algorithm keeps the guarantees. A roughly 5,000-parameter network predicts a starting point and a step-size schedule for the solver's alternating minimization. It never changes the energy being minimized, so whatever the solver converges to is still a stationary point of the physical model. The network is trained by plain supervised regression on solver outputs, with no rollouts and no reward model. The note's second claim follows from this. Once enhancement is posed this way, RL's sequential overhead should buy nothing, and we test that directly under matched compute.
Core Claim
Two connected claims are at stake. The first is that "gap to a fixed variational objective versus wall-clock" is a meaningful axis for illumination enhancement. Lower gap should track better PSNR on paired data and better no-reference quality on unpaired data. If this correlation fails, the lens fails, and we will report that. The second is that a learned warm start plus learned solver schedule should reach within a small objective gap, on the order of one percent, at a cost close to a single feed-forward pass. That would put it ahead of three alternatives at equal compute: tuned classical solving from heuristic initializations, one-shot lightweight networks, and RL-trained iterative enhancers.
Writing $E(R, L; S)$ for the weighted variational energy of Fu et al. over reflectance $R$ and illumination $L$ given observed image $S$, the per-image gap of a method at compute budget $t$ is
$$ g(t) = \frac{E(R_t, L_t; S) - E^\star(S)}{E^\star(S)}, $$
where $(R_t, L_t)$ is the method's decomposition after spending time $t$, and $E^\star(S)$ is the lowest energy found by long multi-start runs of the classical solver. Because the model is non-convex, $E^\star$ is a best-known value rather than a certified optimum. This is the same convention combinatorial optimization uses when it reports gaps against LKH-3 on instances Concorde cannot finish. Methods that output an enhanced image rather than a decomposition, such as ReLLIE's curves or a feed-forward CNN, are mapped back to $(R, L)$ by the same fixed initialization-free projection: a fixed number of reflectance-only solver steps holding the method's implied illumination fixed. The projection is identical for all methods, so no method gains from it.
Why This Intersection
The combinatorial-optimization literature supplies both the method and a warning. Deep Policy Dynamic Programming uses a graph network's edge predictions only to restrict an exact dynamic program, which keeps feasibility. It reaches a 0.004% gap on TSP100, though only with a 100K beam. Neural Minimum Weight Perfect Matching similarly lets a transformer set edge weights while a classical matching algorithm guarantees validity. We copy this division of labor. The network guides, and the classical algorithm decides what counts as a solution.
The warning comes from Xia's analysis recent analysis and from classical branch-and-reduce solvers. Both show that neural-guided search often loses to a mature classical heuristic once compute budgets are matched. High-precision error tolerances adds that learned models alone rarely hit solver-grade precision. These results constrain the design. The proposal is only worthwhile if it beats a well-tuned classical solver at equal wall-clock, not a naively initialized one. That comparison is therefore the central experiment.
On the imaging side, Fu et al. motivate the choice of objective. Their exponential weights fix the way the log domain inflates gradients in dark regions and shrinks them in bright ones. That is precisely the non-uniform-illumination failure. Their remaining weakness is speed: an iterative solver with FFTs at every step. Fast Enhancement for Non-Uniform Illumination Images using Light-weight CNNs shows the other extreme. It is a 5,000-parameter dual-Retinex network running at 50 fps on 0.5-megapixel images, but it is a pure feed-forward heuristic with no tie to any objective. Our guidance network is deliberately this size, so the comparison isolates what the solver adds.
RL enters as the overhead under audit. ReLLIE trains an actor-critic policy to apply pixel-wise curves over $N$ sequential steps. Its reward is a sum of non-reference terms, and it adapts at test time by iterating further. It therefore pays the generation-in-the-loop cost that Is Reinforcement Learning (Not) for Natural Language Processing identifies in language RL. PromptLNet sits at the heavy end, with a segmenter, a BLIP-based reward model, a ControlNet diffusion backbone and an LLM loop. Its authors report that the aesthetic reward lowers PSNR. Neither paper asks whether its sequential, reward-driven computation moves the result closer to any physical optimum per unit of compute. Teacher Forcing Recovers Reward Functions for Text Generation motivates our choice of training signal. When targets exist, here produced by the solver, parallel supervised training is the scalable option. Producing the targets costs a one-time offline solve per training image, which we report.
The closest existing work is the pairing of Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation with ReLLIE. Both use iterative test-time computation to close a gap, and both pay heavily per instance for it. We differ in three ways. We fix an external objective, which ReLLIE lacks. We use no per-instance gradient updates, which the LRBS-plus-adaptation method relies on. And we move all learning to an offline supervised stage.
Research Program
The first component is the reference set. For every image in LOL, the 300-image collection of Fu et al., the unpaired sets (LIME, MEF, NPE, DICM) and a high-resolution subset of MIT-Adobe FiveK, we run the Fu et al. solver to tight convergence from several initializations. The initializations include the input itself, max-RGB illumination, and the outputs of each competing method. We record $E^\star$ along with the full anytime curve. This yields what does not exist today: a per-image best-known objective for illumination decomposition.
The second component is the guided solver. The guidance network sees the low-light image and outputs two things. The first is an initial illumination and reflectance pair. The second is a short per-image schedule of the solver's penalty parameter, which controls how hard the constraint-coupling step pushes and strongly affects convergence speed in alternating methods. Neither output appears in $E$, so the converged solution remains a stationary point of the unchanged model.
Training uses two losses. One is a regression loss pulling the initialization toward the reference solution. The other is a differentiable unrolled loss on $E$ after $K$ solver iterations, for small $K$ such as 3 to 10, which shapes the schedule. Both are teacher-forced and fully parallel. A deployment option adds early exit: the solver stops once its primal and dual residuals fall below tolerance. The same option exposes a fixed-budget mode that returns the iterate after $K$ steps.
The third component is the audit of RL overhead. We train an RL counterpart that has the same guidance network and the same solver. A policy chooses the schedule and the stopping time, rewarded by the negative energy reduction per unit time, in the spirit of the adaptive step policies of AdaGen. This pins down whether trial-and-error training finds anything that differentiable supervision misses, and at what training cost. We also re-evaluate ReLLIE itself under matched inference compute.
The fourth component is the validation of the lens. We correlate per-image gap with PSNR and SSIM on LOL and with NIQE and BRISQUE on unpaired sets. All decompositions are converted to an enhanced image by one fixed gamma-correction recombination of illumination and reflectance, applied identically to every method. We also run a small downstream check on DARK FACE, measuring face-detector average precision after enhancement.
Baselines
The naive reference point is the Fu et al. solver run exactly as published, from its default initialization, with a fixed penalty parameter. We cut it at matched wall-clock budgets. It anchors every gap curve, and the guided solver must dominate it at every budget below convergence.
The strongest competitor on this specific question is a tuned classical solver. This is the same Fu et al. algorithm with three changes: the best of several heuristic initializations (max-RGB illumination, a blurred max-RGB, the input), a penalty parameter tuned per dataset by grid search on the training split, and residual-based early stopping. It is the illumination-side analogue of LKH-3, the competitor Xia found neural search failing to beat. It gets the same hardware, the same implementation of the FFT step, and a tuning budget of equal GPU-hours to our guidance network's training. Beating it means a lower median gap and a lower 90th-percentile gap at every budget from one to twenty solver-iteration equivalents. The margin must also be large enough that per-image bootstrap confidence intervals do not overlap on LOL and on the Fu et al. set. No reported result found on Lacuna for the gap of any enhancer relative to this solver, so these numbers are produced here.
The strongest learned enhancers form the quality baselines. On LOL, ClassLIE reports PSNR 25.74 dB and SSIM 0.92 with 16.68M parameters. PromptLNet reports PSNR 25.22 and SSIM 0.93. ReLLIE with its refinement module reports PSNR 19.52 and SSIM 0.8268. We use released models where available at their native resolution and report both their gap (after the shared projection) and their wall-clock. The guided solver is not expected to beat ClassLIE's PSNR outright, since Fu's objective has no denoising term. The claim is narrower. It should reach a lower gap than every learned enhancer at their own cost, and a PSNR within about 1 dB of ClassLIE with roughly three orders of magnitude fewer parameters. Falling short of either is a negative result we will report.
The one-shot lightweight baseline is the Fast Enhancement CNN. It is retrained on our training split with its original losses at matched parameter count, and also used as the warm start for the classical solver. This "heuristic CNN output as initialization" variant is the key ablation. It tells us whether our gain comes from the learned schedule and the energy-shaped training, or simply from starting near a reasonable image.
The remaining ablations isolate the main ingredients. One removes the learned schedule and keeps only the learned initialization. One removes the unrolled-energy loss and keeps only regression. One swaps supervised training for the RL counterpart at equal training GPU-hours.
Why not just…?
Why not just tune the classical solver and skip learning? This is the most serious threat. Xia's compute-matched results in routing suggest it often wins. The tuned-solver baseline above is built to settle the question. If learned guidance does not dominate it at equal wall-clock, the honest conclusion is that illumination decomposition, like TSP at moderate sizes, does not need neural guidance. We would then publish the gap benchmark and the finding on their own.
Why not just use the 5,000-parameter CNN alone? It already runs at 50 fps. However, its authors acknowledge failure where information is completely lost, and nothing ties its output to any physical decomposition. Our gap measurements will show how far its implied decomposition sits from the solver optimum. The CNN-as-warm-start ablation will show whether adding a few solver steps on top recovers most of the benefit. If it does, the contribution reduces to that simpler recipe, and we would say so.
Why not just unroll the solver into a network with freely learned per-iteration weights (deep unfolding)? Unfolding usually scores well on PSNR. But it lets the network rewrite the energy at each step, so its outputs need not be stationary points of any fixed model, and running it longer gives no guarantee. We include a fully unfolded variant with the same $K$ and parameter budget. If it beats the guided solver on both gap and PSNR, the fixed-objective constraint is not earning its keep, and the proposal should drop it.
Why not just keep RL, as ReLLIE does, since it beats Zero-DCE? ReLLIE's reported advantage over Zero-DCE compares methods at different inference compute, so it cannot separate the value of RL from the value of iterating more. The matched-compute re-evaluation and the RL-trained schedule ablation separate the two. We expect RL to match supervision on gap while costing more to train, because the reward here is differentiable. Any case where RL finds better stopping decisions would be reported as the place where its overhead pays.
Proposed Experiments
The headline experiment is a set of anytime gap curves on LOL and the Fu et al. 300-image set. For every method above, we plot median and 90th-percentile gap against wall-clock and against FLOPs, at the native 600×400 resolution and at FiveK resolution. The guided solver's advantage should grow with resolution, because each classical iteration becomes more expensive.
The first decisive check is the comparison with the tuned classical solver at equal budget, described in the Baselines section. The second is the lens validation. We require a Spearman rank correlation between per-image gap and per-image PSNR on LOL that is clearly negative and significant. Without that, gap is a solver-speed metric, not a quality metric, and the paper's framing must change accordingly. The third is the RL audit. It reports training GPU-hours, peak memory, and final gap for supervised versus RL-trained guidance, plus ReLLIE's gap and PSNR when its step count is cut to match the guided solver's wall-clock.
Secondary checks cover generalization and the main gap in coverage. For generalization, we train on LOL and test on the unpaired sets and FiveK, looking for gap growth comparable to the LRBS finding that gaps widen tenfold at ten-times scale. For coverage, we examine heavily clipped regions. Fu's objective cannot invent lost texture, so we report results separately on pixels near zero or saturation, where we expect every method in the study to fail similarly.
References
- A Weighted Variational Model for Simultaneous Reflectance and Illumination Estimation
- Deep Policy Dynamic Programming for Vehicle Routing Problems
- Neural Minimum Weight Perfect Matching for Quantum Error Codes
- Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems
- On lower bounds of the density of planar periodic sets without unit distances
- On Representing Convex Quadratically Constrained Quadratic Programs via Graph Neural Networks
- Fast Enhancement for Non-Uniform Illumination Images using Light-weight CNNs
- ReLLIE: Deep Reinforcement Learning for Customized Low-Light Image Enhancement
- Is Reinforcement Learning (Not) for Natural Language Processing: Benchmarks, Baselines, and Building Blocks for Natural Language Policy Optimization
- Prompt-Guided Region-Adaptive Enhancement for Aesthetic Low-Light Imaging
- Teacher Forcing Recovers Reward Functions for Text Generation
- Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation
- AdaGen: Learning Adaptive Policy for Image Synthesis
- ClassLIE: Structure- and Illumination-Adaptive Classification for Low-Light Image Enhancement