Analytic Budget Sets for Reward-Free Rate Control

Video encoders must decide, frame by frame, how coarsely to quantize each picture. The quantization parameter (QP) is the knob that trades bits for picture quality, and the whole sequence must land on a fixed bit budget. Reinforcement learning (RL) has recently produced strong per-frame bit allocators for the HEVC/H.265 standard. All of them run into the core problem of reward engineering. The agent must be told both "look good" and "stay within budget", and every known way of combining those two goals is a manual compromise. Options so far include a hand-weighted sum of terms, two critics with a hard switch between them, or a learned neural model of the rate boundary. This proposal removes the rate term from the reward entirely.

The rate term can go because video coding already has a cheap, accurate analytical model of how bits depend on quantization. This is the second-order rate model, bits ≈ $a/Q + b/Q^2$, whose two parameters can be fitted online. From that model we compute, in closed form at every frame, the interval of quantization step sizes that still leaves the rest of the sequence able to meet its budget. The policy acts only inside that interval, through a smooth reparameterization rather than clipping, and is rewarded for visual quality alone. The claim is that a physically grounded feasible set can replace the hand-tuned parts of the reward. It should do so more reliably than a neural rate critic and without the zero-gradient problems attributed to projection.

Core Claim and Mechanism

Let $Q_t$ be the quantization step chosen for frame $t$ of an $N$-frame group of pictures, and $B_t$ the bits still unspent before frame $t$. Let $\hat R_j(Q) = a_j/Q + b_j/Q^2$ be the fitted bit model for frame $j$. Its parameters $(a_j, b_j)$ are updated by recursive least squares from the bits actually produced by previously coded frames at the same temporal layer. The lower end of the feasible interval, $Q_t^{lo}$, is the smallest step that leaves enough bits for all remaining frames even if they are coded as coarsely as allowed:

$$\frac{a_t}{Q_t^{lo}} + \frac{b_t}{(Q_t^{lo})^2} = B_t - \sum_{j>t} \hat R_j(Q_{max}) - m_t ,$$

Here $Q_{max}$ is the coarsest permitted step and $m_t$ is a safety margin. The equation is a quadratic in $1/Q$, so it has an exact root. The upper end $Q_t^{hi}$ is defined symmetrically, using $Q_{min}$ and the margin added, to prevent large undershoot. The margin $m_t$ is set to an empirical upper quantile of the model's recent relative prediction errors. When content becomes unpredictable, as at scene cuts or under high motion, the interval tightens automatically.

The policy outputs $u_t \in (0,1)$, and we encode with $Q_t = Q_t^{lo} + u_t (Q_t^{hi} - Q_t^{lo})$. This map is differentiable everywhere, so gradients never vanish at a boundary. The reward is per-frame quality only (negative MSE, or VMAF, a learned perceptual quality score) with no weight to tune. Rate adherence is enforced by construction up to model error, rather than learned from penalties. What the RL agent still has to learn is the part the analytic model does not capture: how a quality decision on a reference frame changes the cost and quality of the frames that predict from it.

Relation to Prior Work

Three RL bit allocators motivate this work, and each shows the reward-design gap from a different side. A Dual-Critic Reinforcement Learning Framework for Frame-level Bit Allocation in HEVC/H.265 uses separate rate and distortion critics and hard-switches between them depending on whether the budget is exceeded. It reports 18.8% BD-rate savings over x265 versus about 8.8% for a single scalarized critic, but with 6.2% average rate deviation. Action-Constrained Reinforcement Learning for Frame-Level Bit Allocation in HEVC/H.265 through Frank-Wolfe Policy Optimization (NFWPO) learns the feasible action set with a neural rate critic and solves a Frank-Wolfe step inside it. It reaches 2.1–2.5% deviation and reports matching x265 two-pass encoding. It also argues that clipping or plain projection breaks training through zero gradients. Reinforced Rate Control for Neural Video Compression via Inter-Frame Rate-Distortion Awareness poses neural-codec rate control as a constrained decision process, but its tempered reward shaping keeps manual rate-versus-distortion weights. None of these use the analytic rate model. Our proposal keeps their RL setting, replaces the learned or weighted handling of the rate constraint with a closed-form interval, and drops the rate term from the reward.

The method's ingredients come from the quadratic modeling line. Dong Il Park et al. showed that quadratic rate models support stable constant-bitrate control in HEVC under hierarchical prediction. Referenceless Rate-Distortion Modeling with Learning from Bitstream and Pixel Features showed that a quadratic curve anchored by a small CNN tracks the heavy-tailed, Cauchy-like statistics of transform coefficients at higher resolutions. We reuse the quadratic form, and optionally that paper's predictor, to initialize $(a_j, b_j)$ for frames not yet coded.

Two works constrain the design. High Efficiency Rate Control for Versatile Video Coding Based on Composite Cauchy Distribution gets better rate accuracy from a richer residual model but at about 20% compute overhead, and it still hand-tunes inter-frame dependency factors. That is why we use the cheaper quadratic model for feasibility and leave inter-frame dependency to the learner. Consistent Quality Oriented Rate Control in HEVC Via Balancing Intra and Inter Frame Coding reports 99.5% bitrate accuracy from support-vector regression plus adaptive QP clipping. This partly contradicts NFWPO's claim that clipping is harmful. Our clipping-versus-reparameterization ablation tests that disagreement directly.

The rate-distortion view of RL in On Rate-Distortion Theory in Capacity-Limited Cognition & Reinforcement Learning and Between Rate-Distortion Theory & Value Equivalence in Model-Based Reinforcement Learning treats rate as an abstract information budget, solved by Blahut-Arimoto in small discrete problems. We do not borrow its machinery. We share only its stance that a budget should be a constraint rather than a reward weight, here with physically measured bits.

Research Program

We build the allocator on x265 at the frame level, as in the two HEVC papers above, so their numbers are directly comparable. The state includes the remaining budget, frame position and temporal layer, the current fitted $(a, b)$, the interval width, recent prediction error, and the hand-crafted complexity features used by NFWPO. The agent is a standard deterministic actor-critic with one distortion critic. Training uses JCT-VC and held-out non-test sequences, and testing uses JCT-VC Classes B and C, UVG, and MCL-JCV.

Three analyses accompany the main system. The first measures how often the realized group-of-pictures rate falls outside the target as a function of the margin quantile. This tests whether rate adherence is truly delegated to the model. The second inspects learned behavior on reference versus non-reference frames, to confirm that the agent learns inter-frame dependency rather than restating the model. The third is a stress test on concatenated sequences with hard scene cuts, where parameter drift in the quadratic model is worst.

Baselines

The naive reference point is x265 single-pass average-bitrate mode at the same target. It reflects what a deployed encoder does with no learning. The quality reference is x265 two-pass average-bitrate encoding, the paper-reported target that NFWPO matches.

The strongest existing method is NFWPO (Action-Constrained Reinforcement Learning for Frame-Level Bit Allocation in HEVC/H.265 through Frank-Wolfe Policy Optimization). It is the only prior allocator that also treats rate as an action constraint, and it reports average bit-rate deviation of 2.1% to 2.5% on UVG, MCL-JCV, and JCT-VC. No reported BD-rate figure for NFWPO against x265 was found on Lacuna beyond the claim of matching two-pass performance. We therefore reimplement it, if code is unavailable, with the same state features, actor network size, training sequences, environment-step budget, and hyperparameter-search budget as our method. Beating it means equal or better BD-rate (PSNR and VMAF) against two-pass x265, together with lower mean and lower worst-case group-of-pictures rate deviation, at no greater per-frame inference cost.

We also run the dual-critic allocator (A Dual-Critic Reinforcement Learning Framework for Frame-level Bit Allocation in HEVC/H.265), whose reported 18.8% BD-rate savings over x265 and 6.2% rate deviation on Classes B and C serve as a sanity anchor for our reproduction. A single-critic scalarized agent is included, given a grid search over the rate weight equal in compute to our margin tuning, so the reward-engineering cost is charged fairly.

The non-learning competitor is a model-predictive controller. It uses the identical online quadratic fit and margin, and chooses each frame's QP by minimizing predicted distortion over the remaining frames under the budget, with distortion modeled per frame as proportional to $Q^2$.

Three ablations isolate the key ingredient. The first replaces the analytic interval with a neural rate critic's interval, holding everything else fixed. The second removes the adaptive margin. The third replaces the smooth reparameterization with clipping an unconstrained output.

Why not just…?

Why not just keep a scalarized reward and tune the weight carefully? The dual-critic paper's own comparison is the evidence: its single scalarized critic reached about 8.8% BD-rate savings against 18.8% with decoupled critics, and the neural-codec paper reports overshoot under naive scalarization. Our grid-searched scalarized baseline, given the same tuning compute, tests whether a better weight closes that gap on held-out sequences. We expect it to fail mainly in cross-dataset transfer.

Why not just run model-predictive control with the same quadratic model and skip RL? This is the real threat. If the analytic interval does most of the work, a planner using the same interval might match the learned policy. We expect RL to win only where the crude distortion model ignores how reference-frame quality propagates to dependent frames. The comparison should therefore show gains concentrated in hierarchical random-access structures and on reference frames. If the controller matches our agent within noise, the right conclusion is that the contribution is the analytic budget set, not RL. We would report it that way.

Why not just add the fitted $(a,b)$ as state features to NFWPO? That gives the critic better information but still asks a learned rate critic to find the boundary, so rate errors remain whatever the critic's approximation errors are. Running NFWPO with our features added, as an extra variant, separates "better inputs" from "analytic constraint". If it closes the gap, the analytic interval adds nothing beyond its features.

Why not just use supervised QP regression like the support-vector approach? It reaches 99.5% accuracy on its 18 sequences (Consistent Quality Oriented Rate Control in HEVC Via Balancing Intra and Inter Frame Coding). However, its labels come from exhaustive QP sweeps, and it predicts one quantity rather than a sequential allocation that accounts for downstream frames. Its adaptive clipping idea is tested directly in our clipping ablation.

Decisive Checks

The proposal succeeds if three conditions hold on UVG, MCL-JCV, and JCT-VC Classes B and C. First, our agent matches or beats NFWPO in BD-rate against two-pass x265. Second, its mean rate deviation is at or below NFWPO's reported 2.1–2.5%, with a smaller worst-case tail. Third, its rate deviation stays within budget on scene-cut stress sequences, where a learned critic should degrade more.

The neural-interval ablation must lose on rate adherence for the analytic set to be credited. The clipping ablation tells us whether NFWPO's zero-gradient argument or the support-vector paper's clipping result holds in this setting. The model-predictive comparison decides whether the learned component earns its place.

If the margin rule transfers across datasets without retuning, the weighting problem has been removed rather than relocated. The broader lesson for reward engineering would then be concrete: when a cheap analytical model of a constraint exists, enforce the constraint through the action set and stop encoding it in the reward.