Uncertainty-Weighted Kernel Terminal Values for Short-Horizon Planning

A common recipe for sample-efficient control is to plan a few steps ahead with a dynamics model and then add a learned estimate of "how good is the state I end up in". That estimate is called a terminal value function. The planner searches hard for high-scoring futures, so it actively seeks out states where the terminal value is wrong in the optimistic direction. Those states are usually the ones the agent has rarely visited. This proposal fits the terminal value with kernel regression, a nonparametric method that predicts a state's value as a weighted combination of values at nearby observed states. Each training target receives its own regularization strength, set by how uncertain that particular target is. That uncertainty includes error inherited from the previous value estimate the target bootstraps from. The intended result is a terminal value that trusts well-supported regions and shrinks in thinly supported ones, together with a clean test of whether this is the right kind of local regularization.

The opportunity comes from a specific open failure. Rethinking Discount Regularization and The Unintended Consequences of Discount Regularization show that global regularizers such as a lowered discount factor regularize most heavily exactly where data is plentiful. They fix this with a regularization strength tied to the local sample count. Their fix works for learned transition models, including kernelized ones. Its model-free version performed substantially worse, which they attribute to errors compounding through repeated value updates. Our claim is that this failure is diagnostic. For a value function learned by bootstrapping, the right local regularization depends on the propagated uncertainty of each target, not on the visitation count. Short-horizon planning with multi-step targets is the setting where this propagated uncertainty is small enough to estimate and use.

Core Claim

Kernel value learners regularize with one global penalty. This holds for Regularized Fitted Q-Iteration (RFQI), for KQLearn in Sample Complexity of Kernel-Based Q-Learning, and for the iteration-level schedule $\lambda_k$ in Sampling Complexity of TD and PPO in RKHS. Terminal-value planners such as POLO and TD-MPC instead use neural networks with uniform weight decay or ensembles.

We propose to fit the terminal value $V_k$ at learning round $k$ by heteroscedastic kernel ridge regression:

$$ V_k = \arg\min_{f \in \mathcal{H}} \sum_{i=1}^{M} \frac{\big(y_i - f(s_i)\big)^2}{\sigma_i^2} + \|f\|_{\mathcal{H}}^2, $$

The symbols are as follows. $\mathcal{H}$ is the function space defined by the kernel, $y_i$ is an $N$-step target collected from the planner's own rollouts starting at state $s_i$, and $M$ is the number of stored targets. The per-target weight $\sigma_i^2$ is

$$ \sigma_i^2 = \hat{\rho}^2(s_i) + \gamma^{2N}\, v_{k-1}(s_{i,N}), $$

Here $\hat{\rho}^2(s_i)$ is the locally estimated variance of the $N$-step reward sum, $s_{i,N}$ is the state at which the target bootstraps, and $v_{k-1}$ is the posterior variance of the previous value estimate at that state. Kernel regression provides this posterior variance in closed form.

The form of $\sigma_i^2$ follows from treating each target as a noisy observation. Its error is the reward noise plus the discounted error of the value it bootstraps from, and the two are assumed independent.

The penalty is therefore state-specific in the sense of Rathnam et al. A target that bootstraps into a poorly covered region is down-weighted even if its starting state $s_i$ is densely visited. A count-based scheme would trust exactly that target. Conversely, a sparsely visited state with a long, low-variance, mostly observed reward sum is trusted. The first falsifiable prediction is the following. A direct port of count-based local regularization to kernel values will reproduce the model-free degradation Rathnam et al. report, and propagated-uncertainty weighting will not.

Research Program

The method has three components. First, the planner is MPPI, a sampling-based optimizer that perturbs action sequences and averages them by score, run over horizon $H$ with the kernel terminal value. Second, a replay store holds $N$-step targets from executed and planned trajectories, following POLO's plan-online, learn-offline loop. Third, the kernel learner refits $V_k$ on inducing points selected by a sparse dictionary, so that evaluation costs $O(m)$ per query for $m$ inducing points rather than $O(M)$. The fit uses the RKHS-gradient update of Zou et al. instead of full matrix inversion, which the file reports as both stabilizing and fast.

The posterior variance $v_k$ is recomputed with every refit. It serves two purposes: it sets the next round's weights, and it is logged at the terminal states the planner picks, so that we can measure exploitation directly.

The analysis has a deliberately modest target. POLO bounds planner suboptimality by $\gamma^H$ times the terminal value error. KQLearn's guarantee scales as $(1-\gamma)^{-7}$ for learning a full infinite-horizon value. We will derive a bound in which the terminal error is measured under the distribution of planner-selected terminal states. We will then show that propagated-uncertainty weighting controls this error as long as the $N$-step targets reduce bootstrap variance by $\gamma^{2N}$. We will not claim to fix KQLearn's horizon dependence. We will report empirically how the number of samples needed to reach a fixed return changes as $H$ and $N$ vary.

The work proceeds in two stages. Stage one uses known simulator dynamics, as POLO does, so that terminal value effects are isolated. Stage two replaces the simulator with a learned kernel dynamics model, regularized in the count-based style of Rathnam et al. This is where their transition-side method and our value-side method meet.

Baselines

The naive reference point is the same MPPI planner with no terminal value, and separately with a reduced global discount. This shows how much any learned terminal value buys. On a U-shaped obstacle, Infinite-Horizon Value Function Approximation for MPC reports that MPC without a terminal value gets trapped in local minima. On their KUKA hardware task this gave total cost 1311, against 213 with a learned terminal value. We expect the no-value planner to fail similarly on our point-mass tasks.

The kernel competitor closest to us is RFQI-style homoscedastic kernel ridge regression with one global $\lambda$. It is tuned by holdout over the same number of refits we spend computing weights. The planner, inducing-point budget, and target-collection pipeline are identical, so only the weighting differs. RFQI's Sinus World experiments show a U-shaped error curve over $\lambda$, with $\lambda = 0.01$ best and $10^{-6}$ and $0.5$ failing. No numeric error values are reported in the file. Beating this baseline means higher return at matched environment steps, or fewer steps to a fixed return, on tasks with clearly non-uniform coverage.

Two further kernel baselines bracket the design. The first is a pessimistic variant: global-$\lambda$ kernel regression with the planner scoring mean minus $\beta$ times posterior standard deviation at $s_H$, with $\beta$ tuned under the same budget. The second is the direct port: per-sample weights proportional to local kernel-density counts, as in Rathnam et al., with no propagation term. The second is the ablation that isolates our key ingredient. Two further ablations keep only $\hat{\rho}^2$ or only the propagated term.

The strongest existing method with known dynamics is POLO's neural value ensemble with optimistic softmax aggregation. The file's number for it is Humanoid Getup mastered in 12,000 timesteps, about 96 seconds of simulated time. With learned dynamics the strongest method is TD-MPC, which the file reports solving DMControl Dog in 1 million environment steps.

We rerun POLO's ensemble inside our planner on our tasks with matched planning compute. TD-MPC is run with its released configuration. For most of the low-dimensional tasks we use there is no reported number on Lacuna for POLO or TD-MPC, so all comparisons there come from our reruns. Beating POLO means matching or exceeding its steps-to-success at lower terminal-value error at planner-selected states. Matching it with a method that comes with an explicit uncertainty model is already informative.

Why not just…?

Why not just tune one global regularizer by cross-validation? RFQI's Sinus World curve shows that one $\lambda$ trades smoothing against noise everywhere at once. Planner-generated data is dense near start states and goal bottlenecks and sparse at the frontier, so this tradeoff is likely to bind. The weakness of this argument is that kernel regression already reverts toward its prior mean far from data, so global $\lambda$ may handle sparsity adequately. The global-$\lambda$ baseline under an equal tuning budget is the honest test. If it ties us on the high-variance-coverage tasks, the per-target weighting is not worth its complexity.

Why not just subtract posterior uncertainty in the planner (pessimism)? This is the most serious threat, because it uses the same uncertainty signal at the decision step rather than the fitting step. The two methods do different jobs. Pessimism corrects how the planner uses a value whose fit may already be corrupted by unreliable bootstrapped targets. Our weighting prevents that corruption in the fit itself, which is the compounding mechanism Rathnam et al. identify. The experiment is a two-by-two comparison: weighting on or off, crossed with pessimism on or off. If pessimism alone captures the gains, we will report the weighting as unnecessary.

Why not just use neural ensembles as POLO and TD-MPC do? They work well empirically, and our method may not beat them on return. They have no explicit model of which targets are unreliable. TD-MPC is noted to struggle with uncalibrated extrapolation in sparse-reward tasks. Our sparse-reward variants measure how well each method's uncertainty correlates with true terminal error at the states the planner selects. That is where a kernel model should win if it wins anywhere.

Why not just port count-based local regularization from Rathnam et al.? This is the default reading of "state-action-specific regularization for value functions". Their own model-free results suggest it fails. Keeping it as an explicit arm turns their negative result into the central contrast of the paper.

Proposed Experiments

Experiments start with Sinus World from RFQI, modified to sample states non-uniformly. On it we visualize fitted values against ground truth under each weighting scheme. Next come POLO's 2D point-mass maze and the U-obstacle navigation task from Infinite-Horizon MPC, both with sparse rewards. We then move to state-based DMControl tasks from the DeepMind Control Suite: cartpole swingup, acrobot, reacher, and cheetah run, with returns normalized to a maximum of 1000. Humanoid Getup is a stretch target for comparison against POLO's 12,000 steps. The comparison is planned rather than promised, because high state dimension is the known weak point of kernels.

The metrics are steps to a fixed normalized return, return at a fixed step budget, terminal value error at planner-selected states measured against long Monte Carlo rollouts in simulation, correlation between posterior variance and that error, and planner throughput. For throughput, the file reports more than 7,200 steps per second on CartPole-v1 for the kernel TD critic of Zou et al.

Three outcomes are decisive. First, the count-based port should degrade relative to global $\lambda$ while propagated weighting improves on it, on the tasks with the most skewed coverage. Second, in the two-by-two comparison against pessimism, weighting should add value beyond pessimism. Third, in stage two, the gain should persist when dynamics are learned rather than given. If the first fails, the main claim is wrong. If the second fails, the contribution reduces to "use kernel posterior variance in planning", and we would say so.