Recurrent Natural Policy Gradient for POMDPs

• URL: http://arxiv.org/abs/2405.18221v3
• Date: Fri, 17 Oct 2025 02:04:22 GMT
• Title: Recurrent Natural Policy Gradient for POMDPs
• Authors: Semih Cayci, Atilla Eryilmaz,
• Abstract summary: Solving partially observable Markov decision processes (POMDPs) remains a fundamental challenge in reinforcement learning (RL)<n>We study a natural actor-critic (NAC) algorithm that integrates recurrent neural network (RNN) architectures into a natural policy gradient (NPG) method and a temporal difference (TD) learning method.<n>We provide non-asymptotic theoretical guarantees for this method, including bounds on sample iteration and complexity to achieve global optimality up to function approximation.
• Score: 18.619204672433998
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solving partially observable Markov decision processes (POMDPs) remains a fundamental challenge in reinforcement learning (RL), primarily due to the curse of dimensionality induced by the non-stationarity of optimal policies. In this work, we study a natural actor-critic (NAC) algorithm that integrates recurrent neural network (RNN) architectures into a natural policy gradient (NPG) method and a temporal difference (TD) learning method. This framework leverages the representational capacity of RNNs to address non-stationarity in RL to solve POMDPs while retaining the statistical and computational efficiency of natural gradient methods in RL. We provide non-asymptotic theoretical guarantees for this method, including bounds on sample and iteration complexity to achieve global optimality up to function approximation. Additionally, we characterize pathological cases that stem from long-term dependencies, thereby explaining limitations of RNN-based policy optimization for POMDPs.

Related papers

• Policy Regularized Distributionally Robust Markov Decision Processes with Linear Function Approximation [10.35045003737115]
  Decision-making under distribution shift is a central challenge in reinforcement learning (RL), where training and deployment environments differ.<n>We propose DR-RPO, a model-free online policy optimization method that learns robust policies with sublinear regret.<n>We show that DR-RPO can achieve suboptimality bounds and sample efficiency in robust RL, matching the performance of value-based approaches.
  arXiv  Detail & Related papers  (2025-10-16T02:56:58Z)
• Learning Deterministic Policies with Policy Gradients in Constrained Markov Decision Processes [59.27926064817273]
  We introduce an exploration-agnostic algorithm, called C-PG, which enjoys global last-iterate convergence guarantees under domination assumptions.<n>We empirically validate both the action-based (C-PGAE) and parameter-based (C-PGPE) variants of C-PG on constrained control tasks.
  arXiv  Detail & Related papers  (2025-06-06T10:29:05Z)
• Reinforcement Learning with Continuous Actions Under Unmeasured Confounding [14.510042451844766]
  This paper addresses the challenge of offline policy learning in reinforcement learning with continuous action spaces. We develop a minimax estimator and introduce a policy-gradient-based algorithm to identify the in-class optimal policy. We provide theoretical results regarding the consistency, finite-sample error bound, and regret bound of the resulting optimal policy.
  arXiv  Detail & Related papers  (2025-05-01T04:55:29Z)
• Understanding Inverse Reinforcement Learning under Overparameterization: Non-Asymptotic Analysis and Global Optimality [52.906438147288256]
  We show that our algorithm can identify the globally optimal reward and policy under certain neural network structures.<n>This is the first IRL algorithm with a non-asymptotic convergence guarantee that provably achieves global optimality.
  arXiv  Detail & Related papers  (2025-03-22T21:16:08Z)
• Strongly-polynomial time and validation analysis of policy gradient methods [3.722665817361884]
  This paper proposes a novel termination criterion, termed the advantage gap function, for finite state and action Markov decision processes (MDP) and reinforcement learning (RL)<n>By incorporating this advantage gap function into the design of step size rules, we deriving a new linear rate of convergence that is independent of the stationary state distribution of the optimal policy.<n>This is the first time that such strong convergence properties have been established for policy gradient methods.
  arXiv  Detail & Related papers  (2024-09-28T18:56:48Z)
• Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning [62.81324245896717]
  We introduce an exploration-agnostic algorithm, called C-PG, which exhibits global last-ite convergence guarantees under (weak) gradient domination assumptions. We numerically validate our algorithms on constrained control problems, and compare them with state-of-the-art baselines.
  arXiv  Detail & Related papers  (2024-07-15T14:54:57Z)
• Joint Admission Control and Resource Allocation of Virtual Network Embedding via Hierarchical Deep Reinforcement Learning [69.00997996453842]
  We propose a deep Reinforcement Learning approach to learn a joint Admission Control and Resource Allocation policy for virtual network embedding. We show that HRL-ACRA outperforms state-of-the-art baselines in terms of both the acceptance ratio and long-term average revenue.
  arXiv  Detail & Related papers  (2024-06-25T07:42:30Z)
• Linear Function Approximation as a Computationally Efficient Method to Solve Classical Reinforcement Learning Challenges [0.0]
  We present an implementation of Natural Actor Critic algorithms with actor updates through Natural Policy Gradient methods. We observe that our algorithm trains much faster than complex neural network architectures, and obtains an equivalent or greater result.
  arXiv  Detail & Related papers  (2024-05-27T22:51:58Z)
• Intelligent Hybrid Resource Allocation in MEC-assisted RAN Slicing Network [72.2456220035229]
  We aim to maximize the SSR for heterogeneous service demands in the cooperative MEC-assisted RAN slicing system. We propose a recurrent graph reinforcement learning (RGRL) algorithm to intelligently learn the optimal hybrid RA policy.
  arXiv  Detail & Related papers  (2024-05-02T01:36:13Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• High-probability sample complexities for policy evaluation with linear function approximation [88.87036653258977]
  We investigate the sample complexities required to guarantee a predefined estimation error of the best linear coefficients for two widely-used policy evaluation algorithms. We establish the first sample complexity bound with high-probability convergence guarantee that attains the optimal dependence on the tolerance level.
  arXiv  Detail & Related papers  (2023-05-30T12:58:39Z)
• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [101.5329678997916]
  We study sample efficient reinforcement learning (RL) under the general framework of interactive decision making. We propose a novel complexity measure, generalized eluder coefficient (GEC), which characterizes the fundamental tradeoff between exploration and exploitation. We show that RL problems with low GEC form a remarkably rich class, which subsumes low Bellman eluder dimension problems, bilinear class, low witness rank problems, PO-bilinear class, and generalized regular PSR.
  arXiv  Detail & Related papers  (2022-11-03T16:42:40Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  We present a new algorithm for a policy gradient in TMDPs by a simple extension of the proximal policy optimization (PPO) algorithm. We demonstrate this on a real-world multiple-objective navigation problem with an arbitrary ordering of objectives both in simulation and on a real robot.
  arXiv  Detail & Related papers  (2022-09-15T07:22:58Z)
• Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithm [29.978816372127085]
  We present a finite-time analysis of Natural actor-critic (NAC) with neural network approximation. We identify the roles of neural networks, regularization and optimization techniques to achieve provably good performance.
  arXiv  Detail & Related papers  (2022-06-02T02:13:29Z)
• Occupancy Information Ratio: Infinite-Horizon, Information-Directed, Parameterized Policy Search [21.850348833971722]
  We propose an information-directed objective for infinite-horizon reinforcement learning (RL) called the occupancy information ratio (OIR) The OIR enjoys rich underlying structure and presents an objective to which scalable, model-free policy search methods naturally apply. We show by leveraging connections between quasiconcave optimization and the linear programming theory for Markov decision processes that the OIR problem can be transformed and solved via concave programming methods when the underlying model is known.
  arXiv  Detail & Related papers  (2022-01-21T18:40:03Z)
• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence [60.20076757208645]
  This paper proposes a general policy mirror descent (GPMD) algorithm for solving regularized RL. We demonstrate that our algorithm converges linearly over an entire range learning rates, in a dimension-free fashion, to the global solution.
  arXiv  Detail & Related papers  (2021-05-24T02:21:34Z)
• On Finite-Sample Analysis of Offline Reinforcement Learning with Deep ReLU Networks [46.067702683141356]
  We study the statistical theory of offline reinforcement learning with deep ReLU networks. We quantify how the distribution shift of the offline data, the dimension of the input space, and the regularity of the system control the OPE estimation error.
  arXiv  Detail & Related papers  (2021-03-11T14:01:14Z)
• Identification of Unexpected Decisions in Partially Observable Monte-Carlo Planning: a Rule-Based Approach [78.05638156687343]
  We propose a methodology for analyzing POMCP policies by inspecting their traces. The proposed method explores local properties of policy behavior to identify unexpected decisions. We evaluate our approach on Tiger, a standard benchmark for POMDPs, and a real-world problem related to mobile robot navigation.
  arXiv  Detail & Related papers  (2020-12-23T15:09:28Z)
• A Study of Policy Gradient on a Class of Exactly Solvable Models [35.90565839381652]
  We explore the evolution of the policy parameters, for a special class of exactly solvable POMDPs, as a continuous-state Markov chain. Our approach relies heavily on random walk theory, specifically on affine Weyl groups. We analyze the probabilistic convergence of policy gradient to different local maxima of the value function.
  arXiv  Detail & Related papers  (2020-11-03T17:27:53Z)
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization [44.24881971917951]
  Natural policy gradient (NPG) methods are among the most widely used policy optimization algorithms. We develop convergence guarantees for entropy-regularized NPG methods under softmax parameterization. Our results accommodate a wide range of learning rates, and shed light upon the role of entropy regularization in enabling fast convergence.
  arXiv  Detail & Related papers  (2020-07-13T17:58:41Z)
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy [119.12515258771302]
  We show that a variant of PPOO equipped with over-parametrization converges to globally optimal networks. The key to our analysis is the iterate of infinite gradient under a notion of one-dimensional monotonicity, where the gradient and are instant by networks.
  arXiv  Detail & Related papers  (2019-06-25T03:20:04Z)

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.