Reinforcement learning with function approximation has two well-understood regimes. In one, the approximator is an averager: every prediction is a weighted average of training targets with nonnegative weights. Examples are state aggregation, nearest neighbours, and interpolation on a grid. Averagers provably never diverge, but they spread resolution uniformly and so waste most of it. In the other regime, a neural network places its capacity wherever the data demands, but repeated bootstrapped updates can blow up or oscillate. This proposal sits between the two. We keep a fixed grid whose node values are linear parameters fitted as averages. We then learn a smooth, invertible warp of the state space, a diffeomorphism, that moves the grid's nodes toward regions where the value function bends sharply. Any warp leaves the averaging property intact, so value iteration stays convergent at every step. Invertibility is the extra ingredient: the grid can stretch and compress, but it cannot fold onto itself or abandon a region.
The pitch in two sentences is this. Gordon's stability guarantee for averagers does not depend on which coordinates the averager lives in, so we are free to learn those coordinates. Making the learned coordinates a topology-preserving deformation of a fixed grid is meant to buy the adaptivity of a learned representation without giving up convergence, and without letting resolution vanish from states the policy has not yet visited. The tools are scaling-and-squaring warps taken from medical image registration, and the application is fitted value iteration on low-dimensional continuous control.
Core Claim
Stable Fitted Reinforcement Learning proved that if the fitting step is a max-norm non-expansion, then fitted value iteration remains a $\gamma$-contraction. Gordon also conceded that averagers generalize poorly and scale badly with dimension. Our observation is simple. If $w_i(z)$ are the nonnegative, sum-to-one interpolation weights of a fixed regular grid in a canonical cube $\mathcal{Z}$, and $\phi:\mathcal{S}\to\mathcal{Z}$ is any map, then the features $w_i(\phi(s))$ still define an averager. The fit is
$$\theta_i=\frac{\sum_j w_i(\phi(s_j))\,y_j}{\sum_j w_i(\phi(s_j))},\qquad \hat V(s)=\sum_i w_i(\phi(s))\,\theta_i,$$
where $\theta_i$ is the value stored at grid node $i$, $(s_j,y_j)$ are batch states with bootstrapped targets $y_j=r_j+\gamma\max_a \hat Q(s'_j,a)$, and $\hat V$ is the resulting value estimate. One action-value table $\theta^a$ is kept per discrete action. Every $\hat V(s)$ is a convex combination of targets. For any fixed $\phi$, iterating this fit is therefore a contraction, and every iterate is bounded by $R_{\max}/(1-\gamma)$, where $R_{\max}$ is the largest reward magnitude. The map $\phi$ is a free design choice that the theory does not constrain, and we learn it.
The warp is parameterized as $\phi=\exp(v)$, the time-one flow of a smooth stationary velocity field $v$. The velocity field's normal component vanishes on the state-box boundary, so the warp maps the box onto itself. We compute $\phi$ with the differentiable scaling-and-squaring layer of Unsupervised learning of probabilistic diffeomorphic registration for images and surfaces, which turns a velocity field into an invertible deformation in one fast forward pass. The local Jacobian determinant $\det J_\phi(s)>0$ then has a direct meaning: it measures how many grid cells per unit of state volume the warp allocates near $s$. The claim to be tested is that a warped grid with $N$ nodes matches the value accuracy of a uniform grid with several times more nodes, that it never diverges, and that the diffeomorphic constraint specifically matters. The constraint should matter for two reasons. It prevents folding, which would make a grid cell average together states that are far apart in the true space. It also guarantees nonzero resolution everywhere, which matters when the policy changes and visits new states.
Why this, and not the obvious bridge
The obvious combination of these directions is Gap 1 of the file: learn a diffeomorphism that turns a nonlinear MDP into a linear MDP, and so escape the $\Omega(2^H)$ reward-free lower bound for linear-$Q^*$ models. Here a linear MDP is one whose transition probabilities are a $d$-dimensional inner product $\langle\phi(s,a),\mu(s')\rangle$, and $H$ is the episode horizon. That bound was established in On Reward-Free Reinforcement Learning with Linear Function Approximation. We think this bridge is conceptually broken, and we say so rather than pursue it.
The linear-MDP property is a statement about the rank of the transition kernel. Relabelling states through a bijection $g$ multiplies the kernel by $|\det J_g|$ and composes it with $g$, but leaves its rank unchanged. A coordinate change therefore cannot make a non-low-rank MDP low-rank. What a diffeomorphism can do is make deterministic dynamics linear in its coordinates, as Learning the Koopman Eigendecomposition: A Diffeomorphic Approach does near a hyperbolic equilibrium of an uncontrolled system. That is a linear dynamical system, which is a different object from a linear MDP. Bevanda's construction also relies on a known Jacobian at a single equilibrium, which contact-rich control does not offer.
We use the deformation for a different job: to choose features for a linear approximator that is guaranteed stable. A modest link to linear structure still survives. With averaging fits of this kind, fitted value iteration is exactly value iteration on a small surrogate MDP whose states are the grid nodes. This is the stochastic-factorization view of Kernel-Based Stochastic Factorization, in which a large transition matrix is replaced by a product of two stochastic matrices that preserves the contraction. Barreto et al. fix the representative states in advance. We learn where they sit, subject to a topology-preserving constraint.
The proposal also differs from Diffeomorphism-Equivariant Neural Networks in two ways. DiffeoNN solves an energy minimization per input to undo distortions for a pretrained image model. Our warp is amortized and fixed at test time, so evaluating $\hat V$ costs one interpolation lookup, which addresses the latency tension the file raises for control. And our warp is trained to minimize Bellman fitting error rather than to recover a canonical image pose.
Research Program
The algorithm alternates two steps. In the first step the warp is frozen and the node values are refit by the averaging update above until convergence; this inner loop is a contraction with modulus $\gamma$ by Gordon's theorem. In the second step the targets $y_j$ are frozen and the velocity field $v$ takes a few gradient steps on the squared fitting error $\sum_j(\hat V(s_j)-y_j)^2$. The gradient flows through the interpolation weights and the scaling-and-squaring layer, and a smoothness penalty on $v$ follows registration practice (VoxelMorph: A Learning Framework for Deformable Medical Image Registration). We use simplex (Kuhn) interpolation, which touches $d+1$ nodes per query instead of $2^d$, where $d$ is the state dimension.
The outer loop carries no contraction guarantee, because the features change. It does carry a boundedness guarantee, since every iterate remains a convex combination of bounded targets. Empirically we will measure whether it settles or cycles. We will also prove what we can about it. The analysis is planned in two parts. The first is a bound on the fixed-point error of the warped averager, in terms of the interpolation error of $V^*$ under $\phi$, obtained by adapting Gordon's $1/(1-\gamma)$ error amplification to grid interpolation. The second is a condition on the step size of the warp update under which the composite outer map is itself a contraction. The intended form of that condition is a Lipschitz requirement on the map from targets to the warp, in the spirit of the smooth policy-improvement operator in A Convergent Form of Approximate Policy Iteration.
We expect the second result to inherit Perkins and Precup's "small constant" problem: the step size it requires will depend on unknown dynamics. We will report it as a sufficient condition and test empirically how conservative it is. Policy improvement uses a softmax over the warped $Q$ with a temperature, for the same Perkins–Precup reason. The scope is explicitly low-dimensional, two to six state dimensions. A full-rank invertible warp of a high-dimensional observation space onto a grid is not feasible, and we do not claim otherwise.
Baselines
The naive reference is the same averager on a uniform unwarped grid at an equal node count, with no learning of coordinates. Any gain over it is the value of learning the warp at all. A second fixed-representation reference is Sutton-style tile coding (Generalization in Reinforcement Learning: Successful Examples Using Sparse Coarse Coding) at an equal parameter count, trained with fitted Q-iteration. This is the classic stable local representation, and it would only fail by mis-allocating resolution. Kernel-based stochastic factorization with representative states chosen by k-means on the batch (Kernel-Based Stochastic Factorization) tests data-driven placement that has no smoothness or connectivity.
The strongest stability-oriented nonlinear competitor is SBEED (SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation), alongside neural fitted Q-iteration with a target network as the practitioner's default. SBEED reports "significantly higher average rewards and faster convergence" than DDPG, TRPO, and Dual-AC on Pendulum, InvertedDoublePendulum, HalfCheetah, Swimmer, and Hopper. It also reports that DDPG "completely failed to learn" on InvertedDoublePendulum and Hopper. The file gives these results only as curves: no reported numeric return found on Lacuna for SBEED on Pendulum or InvertedDoublePendulum. We will therefore rerun SBEED with its published architecture.
The two ablations that isolate the key ingredient both feed the same grid averager through a learned map, so both keep the convergence guarantee. In the first, the map is an unconstrained MLP that is allowed to fold. In the second, the same MLP carries a soft Jacobian-determinant and cycle-consistency penalty in the manner of Kim and Kim. A third averager baseline uses free-moving softmax-normalized radial basis function anchors with learned centers. It adapts resolution with no topology at all.
Every method sees the same transition batches, the same number of environment interactions in online runs, an equal parameter budget (nodes, tiles, anchors, or network weights matched within 10%), and the same hyperparameter search budget of 30 configurations per method chosen on held-out seeds. Beating a baseline means a statistically separated improvement over 10 seeds in value error against ground truth or in final return. For the neural baselines, it additionally means zero divergent runs, where they show some.
Why not just…?
Why not just use a finer uniform grid or more tiles? In two dimensions this may genuinely suffice, which makes it a real threat there. The case for warping is parameter efficiency: we will plot value error against node count, and if the uniform grid's curve matches ours within a constant factor below two, the warp is not earning its complexity. The argument strengthens with dimension, because a uniform grid's node count grows as resolution raised to the power $d$. The four- to six-dimensional tasks are therefore where this question is settled.
Why not just run neural fitted Q-iteration with target networks, or SBEED? These are the methods people actually use, and on easy tasks they may win on return. The question here is reliability under the deadly triad. The deadly triad is the combination of function approximation, bootstrapping, and off-policy data that causes divergence. We record the fraction of seeds whose value estimates exceed $R_{\max}/(1-\gamma)$ or never stabilize. SBEED's own report that DDPG fails on InvertedDoublePendulum shows such failures are not hypothetical. SBEED also carries a smoothing bias set by its temperature, whereas our inner loop introduces no smoothing and has none. If SBEED matches our return with no divergence at equal budget, the contribution narrows to interpretability and guaranteed boundedness, and we would say so.
Why not just let the representative points move freely, with no diffeomorphism? This is the most serious alternative, because learned-center normalized RBFs and unconstrained warps are still averagers and so inherit the same convergence guarantee. Our hypothesis is that, without topology preservation, anchors drift toward the current visitation distribution and abandon other regions. When policy improvement shifts the distribution, the mechanism behind Gordon's Sarsa oscillation counterexample, those regions are then served by distant, unrelated anchors. Folding would also average non-adjacent states together, much as soft-penalty registration models still produce "thousands of non-physical folds" while VoxelMorph-diff averages 0.2 (Unsupervised learning of probabilistic diffeomorphic registration for images and surfaces). The distribution-shift experiment below is designed to settle this. If free anchors match the warped grid there, we drop the topology claim and report a simpler method.
Proposed Experiments
The first experiment targets stability on known failure cases. It covers the classic off-policy divergence examples, and it reproduces Gordon's Sarsa oscillation example from Stable Fitted Reinforcement Learning to measure whether the outer warp loop introduces new cycling. The metrics are the maximum absolute value over training and the policy-change rate per iteration.
The second experiment measures approximation efficiency against ground truth. On mountain car, discretized-torque Pendulum, Acrobot, and cart-pole swing-up, a reference $V^*$ comes from dynamic programming on a very fine grid with simulator access. We report sup-norm and mean value error and greedy-policy return as functions of node count. We also report the fraction of states with $\det J_\phi\le 0$, which should be near zero, with residual numerical folding measured as in registration work.
The third experiment is the decisive distribution-shift test. A batch is collected under a poor initial policy, and representations are trained on it. The policy is then improved for several rounds with fresh data, with no reinitialization allowed. The comparison is the warped grid against free RBF anchors and the unconstrained warp, measured by value error on newly visited states and by final return.
The fourth experiment is online return on Pendulum and InvertedDoublePendulum from the MuJoCo suite used by SBEED. Here we report return curves and the fraction of divergent seeds against SBEED and neural fitted Q-iteration.
The proposal stands if three things hold. The warped grid must reach the uniform grid's value error with at least two to three times fewer nodes on the four-dimensional tasks. It must show zero divergent seeds where the neural baselines show some. And it must beat the non-diffeomorphic ablations specifically in the distribution-shift test. If the third condition fails, the result reduces to "learned coordinates for averagers," which is still useful but smaller, and we will report it that way.
References
- Stable Fitted Reinforcement Learning
- Unsupervised learning of probabilistic diffeomorphic registration for images and surfaces
- On Reward-Free Reinforcement Learning with Linear Function Approximation
- Learning the Koopman Eigendecomposition: A Diffeomorphic Approach
- Reinforcement Learning using Kernel-Based Stochastic Factorization.
- Diffeomorphism-Equivariant Neural Networks
- VoxelMorph: A Learning Framework for Deformable Medical Image Registration.
- A Convergent Form of Approximate Policy Iteration
- Generalization in Reinforcement Learning: Successful Examples Using Sparse Coarse Coding
- SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
- Unsupervised Deformable Image Registration Using Cycle-Consistent CNN