Policy Gradient Methods for Non-Markovian Reinforcement Learning

• URL: http://arxiv.org/abs/2605.10816v1
• Date: Mon, 11 May 2026 16:34:28 GMT
• Title: Policy Gradient Methods for Non-Markovian Reinforcement Learning
• Abstract summary: We study policy gradient methods for reinforcement learning in non-Markovian decision processes (NMDPs)<n>In contrast to approaches that treat the agent state dynamics as fixed or learn it via predictive objectives, we propose a reward-centric formulation.<n>We establish a novel policy gradient theorem for ASM policies, extending the classical policy gradient results from the Markovian setting to episodic and infinite-horizon discounted NMDPs.
• Score: 26.23306267677347
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study policy gradient methods for reinforcement learning in non-Markovian decision processes (NMDPs), where observations and rewards depend on the entire interaction history. To handle this dependence, the agent maintains an internal state that is recursively updated to provide a compact summary of past observations and actions. In contrast to approaches that treat the agent state dynamics as fixed or learn it via predictive objectives, we propose a reward-centric formulation that jointly optimizes the agent state dynamics and the control policy to maximize the expected cumulative reward. To this end, we consider a class of Agent State-Markov (ASM) policies, comprising an agent state dynamics and a control policy that maps the agent state to actions. We establish a novel policy gradient theorem for ASM policies, extending the classical policy gradient results from the Markovian setting to episodic and infinite-horizon discounted NMDPs. Building on this gradient expression, we propose the Agent State-Markov Policy Gradient (ASMPG) algorithm, which leverages the recursive structure of the agent state dynamics for efficient optimization. We establish finite-time and almost sure convergence guarantees, and empirically demonstrate that, on a range of non-Markovian tasks, ASMPG outperforms baselines that learn state representations via predictive objectives.

Related papers

• Learning Policy Representations for Steerable Behavior Synthesis [80.4542176039074]
  Given a Markov decision process (MDP), we seek to learn representations for a range of policies to facilitate behavior steering at test time.<n>We show that these representations can be approximated uniformly for a range of policies using a set-based architecture.<n>We use variational generative approach to induce a smooth latent space, and further shape it with contrastive learning so that latent distances align with differences in value functions.
  arXiv  Detail & Related papers  (2026-01-29T21:52:06Z)
• SEMDICE: Off-policy State Entropy Maximization via Stationary Distribution Correction Estimation [54.537828696303286]
  In unsupervised-training for reinforcement learning, the agent aims to learn a prior policy for downstream tasks without relying on task-specific reward functions.<n>We focus on state entropy (SEM), where the goal is to learn a policy that maximizes the entropy of the state stationary distribution.<n>We introduce SEMDICE, a principled off-policy algorithm that computes an SEM policy from an arbitrary off-policy dataset.
  arXiv  Detail & Related papers  (2025-12-10T19:50:21Z)
• 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)
• Sequential Monte Carlo for Policy Optimization in Continuous POMDPs [10.675160254513615]
  We introduce a novel policy optimization framework for continuous partially observable Markov decision processes.<n>Our method casts policy learning as probabilistic inference in a non-Markovian Feynman--Kac model.<n>We demonstrate the effectiveness of our algorithm across standard continuous POMDP benchmarks.
  arXiv  Detail & Related papers  (2025-05-22T14:45:46Z)
• Agent-state based policies in POMDPs: Beyond belief-state MDPs [1.918334858770111]
  We present a unified treatment of some approaches to learning in POMDPs. We highlight the different classes of agent-state based policies and the various approaches that have been proposed in the literature to find good policies within each class. We then present how ideas from the approximate information state approach have been used to improve Q-learning and actor-critic algorithms for learning in POMDPs.
  arXiv  Detail & Related papers  (2024-09-24T03:32:10Z)
• Score-Aware Policy-Gradient and Performance Guarantees using Local Lyapunov Stability [2.180257135067774]
  We introduce a policy-gradient method for model-based reinforcement learning (RL)<n>We exploit a type of stationary distributions commonly obtained from Markov decision processes (MDPs) in networks.<n>We show that SAGE-based policy-gradient locally converges, and we obtain its regret.
  arXiv  Detail & Related papers  (2023-12-05T14:44:58Z)
• Time-Efficient Reinforcement Learning with Stochastic Stateful Policies [20.545058017790428]
  We present a novel approach for training stateful policies by decomposing the latter into a gradient internal state kernel and a stateless policy. We introduce different versions of the stateful policy gradient theorem, enabling us to easily instantiate stateful variants of popular reinforcement learning algorithms.
  arXiv  Detail & Related papers  (2023-11-07T15:48:07Z)
• A Deep Reinforcement Learning Approach to Marginalized Importance Sampling with the Successor Representation [61.740187363451746]
  Marginalized importance sampling (MIS) measures the density ratio between the state-action occupancy of a target policy and that of a sampling distribution. We bridge the gap between MIS and deep reinforcement learning by observing that the density ratio can be computed from the successor representation of the target policy. We evaluate the empirical performance of our approach on a variety of challenging Atari and MuJoCo environments.
  arXiv  Detail & Related papers  (2021-06-12T20:21:38Z)
• Privacy-Constrained Policies via Mutual Information Regularized Policy Gradients [54.98496284653234]
  We consider the task of training a policy that maximizes reward while minimizing disclosure of certain sensitive state variables through the actions. We solve this problem by introducing a regularizer based on the mutual information between the sensitive state and the actions. We develop a model-based estimator for optimization of privacy-constrained policies.
  arXiv  Detail & Related papers  (2020-12-30T03:22:35Z)
• Stable Policy Optimization via Off-Policy Divergence Regularization [50.98542111236381]
  Trust Region Policy Optimization (TRPO) and Proximal Policy Optimization (PPO) are among the most successful policy gradient approaches in deep reinforcement learning (RL) We propose a new algorithm which stabilizes the policy improvement through a proximity term that constrains the discounted state-action visitation distribution induced by consecutive policies to be close to one another. Our proposed method can have a beneficial effect on stability and improve final performance in benchmark high-dimensional control tasks.
  arXiv  Detail & Related papers  (2020-03-09T13:05:47Z)

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.