Policy Gradient Methods for Non-Markovian Reinforcement Learning
This work addresses the challenge of learning in non-Markovian environments for reinforcement learning practitioners, offering a principled gradient-based method that improves over predictive state representation approaches.
The authors propose a reward-centric approach for non-Markovian reinforcement learning that jointly optimizes agent state dynamics and control policy, deriving a policy gradient theorem for Agent State-Markov policies. Their ASMPG algorithm outperforms baselines on non-Markovian tasks, with finite-time and almost sure convergence guarantees.
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.