Neural Value Iteration

• URL: http://arxiv.org/abs/2511.08825v1
• Date: Thu, 13 Nov 2025 01:10:16 GMT
• Title: Neural Value Iteration
• Abstract summary: We show that a POMD's value function can be represented as a finite set of neural networks.<n>Our approach achieves near-dimensional solutions even in offline solvers.
• Score: 14.535957451368608
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The value function of a POMDP exhibits the piecewise-linear-convex (PWLC) property and can be represented as a finite set of hyperplanes, known as $α$-vectors. Most state-of-the-art POMDP solvers (offline planners) follow the point-based value iteration scheme, which performs Bellman backups on $α$-vectors at reachable belief points until convergence. However, since each $α$-vector is $|S|$-dimensional, these methods quickly become intractable for large-scale problems due to the prohibitive computational cost of Bellman backups. In this work, we demonstrate that the PWLC property allows a POMDP's value function to be alternatively represented as a finite set of neural networks. This insight enables a novel POMDP planning algorithm called \emph{Neural Value Iteration}, which combines the generalization capability of neural networks with the classical value iteration framework. Our approach achieves near-optimal solutions even in extremely large POMDPs that are intractable for existing offline solvers.

Related papers

• Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks [20.951741111898897]
  We propose a Max-Cut-specific graph neural network that serves as a principled, lightweight neural proxy for SDP solvers.<n>We show that our architecture can substantially reduce the cost of bounding in exact Max-Cut solving by up to $10.6 times$ compared with using the state-of-the-art SDP solver Mosek.
  arXiv  Detail & Related papers  (2026-05-08T01:41:40Z)
• End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions [66.17960480460185]
  We study reinforcement learning with linear function approximation in Decision Processes (MDPs)<n>We provide a computationally efficient algorithm for linear Bellman complete oracles with emphdeterministic transitions, initial states, and rewards.
  arXiv  Detail & Related papers  (2026-03-24T17:32:29Z)
• Deep neural networks can provably solve Bellman equations for Markov decision processes without the curse of dimensionality [3.6185342807265415]
  Discrete time optimal control problems and leaky decision processes (MDPs) are fundamental models for sequential decision-making under uncertainty.<n>In this article, we construct deep neural network (DNN) approximations for $Q$-functions associated to MDPs with infinite time horizon and finite control set $A$.
  arXiv  Detail & Related papers  (2025-06-28T11:25:44Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Novel Quadratic Constraints for Extending LipSDP beyond Slope-Restricted Activations [52.031701581294804]
  Lipschitz bounds for neural networks can be computed with upper time preservation guarantees. Our paper bridges the gap and extends Lipschitz beyond slope-restricted activation functions. Our proposed analysis is general and provides a unified approach for estimating $ell$ and $ell_infty$ Lipschitz bounds.
  arXiv  Detail & Related papers  (2024-01-25T09:23:31Z)
• A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes [13.466249082564213]
  We propose an optimistic variant of PPO for episodic adversarial linear MDPs with full-information feedback. Compared with existing policy-based algorithms, we achieve the state-of-the-art regret bound in both linear MDPs and adversarial linear MDPs with full information.
  arXiv  Detail & Related papers  (2023-05-15T17:55:24Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  We propose the first computationally efficient algorithm that achieves the nearly minimax optimal regret $tilde O(dsqrtH3K)$. Our work provides a complete answer to optimal RL with linear MDPs, and the developed algorithm and theoretical tools may be of independent interest.
  arXiv  Detail & Related papers  (2022-12-12T18:58:59Z)
• Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
  We propose a novel offline reinforcement learning algorithm called Pessimistic vAlue iteRaTion with rEward Decomposition (PARTED) PARTED decomposes the trajectory return into per-step proxy rewards via least-squares-based reward redistribution, and then performs pessimistic value based on the learned proxy reward. To the best of our knowledge, PARTED is the first offline RL algorithm that is provably efficient in general MDP with trajectory-wise reward.
  arXiv  Detail & Related papers  (2022-06-13T19:11:22Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
  We study the reinforcement learning for finite-horizon episodic Markov decision processes with adversarial reward and full information feedback. We show that it can achieve $tildeO(dHsqrtT)$ regret, where $H$ is the length of the episode. We also prove a matching lower bound of $tildeOmega(dHsqrtT)$ up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-02-17T18:54:08Z)
• Convolutional Proximal Neural Networks and Plug-and-Play Algorithms [0.225596179391365]
  In this paper, we introduce convolutional proximal neural networks (cPNNs) For filters of full length, we propose a submanifold of the Stiefel manifold to train cPNNs. Then, we investigate how scaled cPNNs with a prescribed Lipschitz constant can be used for denoising signals images.
  arXiv  Detail & Related papers  (2020-11-04T13:32:46Z)
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
  In this paper, we study reinforcement learning for discounted Decision (MDP) We propose a novel algorithm that makes use of the feature mapping and obtains a $tilde O(dsqrtT/ (1-gamma)2)$ regret. Our upper and lower bound results together suggest that the proposed reinforcement learning algorithm is near-optimal up to a $ (1-gamma)-0.5$ factor.
  arXiv  Detail & Related papers  (2020-06-23T17:08:54Z)
• Deep neural networks for inverse problems with pseudodifferential operators: an application to limited-angle tomography [0.4110409960377149]
  We propose a novel convolutional neural network (CNN) designed for learning pseudodifferential operators ($Psi$DOs) in the context of linear inverse problems. We show that, under rather general assumptions on the forward operator, the unfolded iterations of ISTA can be interpreted as the successive layers of a CNN. In particular, we prove that, in the case of LA-CT, the operations of upscaling, downscaling and convolution, can be exactly determined by combining the convolutional nature of the limited angle X-ray transform and basic properties defining a wavelet system.
  arXiv  Detail & Related papers  (2020-06-02T14:03:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.