Convergence and action-value gap guarantees for the Imagination-Limited Bellman operator under function approximation

Imagination-Limited Q-learning (ILQ) is a model-based offline reinforcement-learning method that controls over-optimistic value estimates for out-of-distribution (OOD) actions by imagining their values with a learned dynamics model and clipping these imagined values at the maximum behavior value. Its core theory — a contraction-based convergence proof for the Imagination-Limited Bellman (ILB) operator and bounds showing that OOD action-value errors are of the same magnitude as in-distribution ones — holds only for tabular Markov decision processes, under a Lipschitz-reward assumption that the authors themselves note theoretically fails for the sparse-reward tasks they study, together with empirical-model concentration bounds. The open problem, which the authors explicitly leave to future research, is to establish whether these guarantees persist, in an appropriately formulated form, for the practical algorithm with neural-network critics and actors trained by stochastic optimization.

Background

Offline reinforcement learning (RL) seeks an improved policy purely from a static dataset collected by an unknown behavior policy, without further environment interaction. Because the learner never observes the outcomes of actions the behavior policy did not take, standard Q-learning can assign wildly over-optimistic values to such out-of-distribution (OOD) actions — the value estimates are queried at actions where the dataset provides no corrective signal. Existing remedies fall into two broad families: policy-constraint methods that restrict the learned policy to stay close to the behavior policy, and conservative value-regularization methods that deliberately lower value estimates for OOD actions. Both can be overly restrictive or biased, giving up legitimate performance gains.

Imagination-Limited Q-learning (ILQ), proposed by Liu, Wu, Wang, Huang, and Zhou (IJCAI 2025), takes a different route. For state–action pairs inside the dataset support it applies the ordinary Bellman optimality backup. For an OOD action, it uses the learned empirical dynamics and reward models to imagine the one-step outcome of taking that action, forming an imagined action-value, and then clips that imagined value at the maximum value achieved by actions the behavior policy actually takes — the limitation value, estimated from $M$ actions sampled from a diffusion generative model of the behavior policy. The resulting update rule defines the Imagination-Limited Bellman (ILB) operator. The design intends to retain justified optimism about OOD actions while capping unjustified over-optimism, and empirically the method performs strongly on the D4RL benchmark suites (standard offline-RL evaluation tasks including MuJoCo locomotion, Adroit hand manipulation, and Maze navigation).

The theoretical analysis, however, is tabular — it assumes finite state and action spaces with the Q-function represented as a lookup table. In that setting, the paper proves that the ILB operator is a $\gamma$ -contraction in the $\mathcal{L}_{\infty}$ norm (where $\gamma\in(0,1)$ is the discount factor), so iterated application converges to a unique fixed point, and it bounds the action-value gap between that fixed point and the ideal support-constrained value in terms of: the deviation $\epsilon_{\pi}$ between the learned and behavior policies, the deviation $\epsilon_{P}=\|P^{\pi}-P^{\beta}\|_{\infty}$ between the next-state transition distributions induced by the learned policy and by the behavior policy under the true dynamics, the empirical-model concentration terms $\zeta_{r}/\sqrt{D}$ and $\zeta_{P}/\sqrt{D}$ for the reward and dynamics models (with $D$ the effective dataset size), a Lipschitz constant $\ell$ of the reward in the action argument, and the small offset hyperparameter $\delta$ that enters the OOD branch of the ILB operator. The headline conclusion is that OOD state–actions enjoy an error bound of the same magnitude as in-distribution ones, i.e. the method's value bias is controlled. Three limitations are explicit in the paper. First (Appendix A.7): the analysis assumes tabular MDPs, and the authors state that formal guarantees under neural-network function approximation remain challenging and defer them to future research. Second (Appendix A.9 and Section 4.3): the analysis assumes the reward is Lipschitz continuous in the action (any continuously differentiable reward on a compact action set qualifies), and that the empirical reward and dynamics models concentrate around the true ones; the authors note the Lipschitz assumption holds for the smooth MuJoCo and Adroit rewards but theoretically fails for the sparse-reward Maze tasks they study. Third (Appendix A.4): the interplay between dynamics-model accuracy, the behavior-support sampling number $M$ , and performance is examined only through empirical sensitivity analyses, not theory.

The obstacle is well known in the field: combining off-policy value estimation, function approximation, and bootstrapping — the so-called deadly triad — is classically unstable, because a sup-norm contraction argument on the space of Q-functions no longer applies once the Q-function is restricted to a function class such as a neural network; the tabular proof cannot simply be replayed. This is why the function-approximation regime for this specific operator constitutes a genuine open question rather than a routine exercise.

Problem Statement

As posed by the ILQ authors, the guarantees for the Imagination-Limited Bellman (ILB) operator hold only for tabular Markov decision processes, under a boundedness assumption on the reward, a Lipschitz-continuity assumption on the reward in the action argument, and concentration bounds ( $\|\hat{r}-r\|_{1}\leq\zeta_{r}/\sqrt{D}$ , $\|\hat{P}-P\|_{1}\leq\zeta_{P}/\sqrt{D}$ with probability at least $1-\zeta$ ) for the empirical reward and dynamics models; in Appendix A.7 the authors state that formal guarantees under neural-network function approximation remain challenging and note this as a direction for future research. Determine whether these guarantees — the $\gamma$ -contraction/fixed-point convergence of the ILB operator and the comparability of OOD and in-distribution action-value error bounds — persist, in an appropriately formulated form and for a stated function class and optimization scheme, for the practical ILQ algorithm, which represents the critic (and actor) with neural networks trained by stochastic gradient descent, imagines OOD one-step outcomes with a learned dynamics/reward model, and estimates the maximum behavior value from $M$ samples of a diffusion generative model of the behavior policy. The $\gamma$ -contraction/fixed-point convergence of the ILB operator and the comparability of the OOD and in-distribution action-value error bounds are two separate parts of this target, neither implying the other. Two further limitations acknowledged by the authors are context the formulation must remain consistent with: the Lipschitz-reward assumption theoretically fails for the sparse-reward Maze tasks (Appendix A.9), and the deviation of the sampled limitation value from the true maximum behavior value is absorbed by the heuristic offset $\delta$ rather than analyzed, with the interplay between dynamics-model accuracy, the sampling number $M$ , and performance studied only empirically (Section 4.2.2 and Appendix A.4). The question may be settled either affirmatively or by a refutation — a concrete demonstration that no reasonable analogue of the tabular guarantees survives under function approximation — and such an argument must address the ILB operator as defined, not merely generic instability of Q-learning.

References

Wenhui Liu, Zhijian Wu, Jingchao Wang, Dingjiang Huang, Shuigeng Zhou. Imagination-Limited Q-Learning for Offline Reinforcement Learning. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2025), pp. 5770–5778. arXiv:2505.12211. DOI: 10.24963/ijcai.2025/642. https://arxiv.org/abs/2505.12211
Hongqiang Lin, Dongxu Zhang, Yiding Sun, Mingzhe Li, Ning Yang, Haijun Zhang. Offline Policy Optimization with Posterior Sampling. arXiv:2605.07393 (2026). https://arxiv.org/abs/2605.07393
Chayoung Kim. Efficient Classification-Based Constraints for Offline Reinforcement Learning. Applied Sciences 15(22):12197, 2025. DOI: 10.3390/app152212197. https://www.mdpi.com/2076-3417-15-22-12197