Policy Gradient With Serial Markov Chain Reasoning

Edoardo Cetin, Oya Celiktutan

TL;DR

This paper introduces Steady-State Policy Gradient (SSPG), a framework that replaces traditional "one-shot" feed-forward policies with an iterative reasoning process modeled as a Markov chain. By treating action selection as a search for a steady-state distribution, the agent gains the ability to represent complex, multi-modal behaviors and adapt its computational effort to the difficulty of the task at hand.

What Problem Does This Paper Address?

In deep reinforcement learning (RL), agents typically use feed-forward neural networks to map a state directly to an action distribution. The authors identify three major limitations with this "rigid" approach:

  1. Limited Expressivity: Standard policies often use simple distributions (like squashed Gaussians) that struggle to capture the multi-modality required for complex tasks.
  2. Fixed Computation: A feed-forward network uses the same amount of compute for a trivial decision as it does for a highly complex one.
  3. Lack of Information Reuse: Traditional agents start every decision from scratch, ignoring the fact that past actions in a continuous environment are often highly relevant to the current state.

Methods

The core innovation is Serial Markov Chain Reasoning. Instead of a standard policy $\pi(a|s)$, the authors define a Belief Transition (BT) policy, $\pi^b(a'|a, s)$.

To select an action, the agent starts with an initial "belief" $a_0$ and iteratively samples new actions using the BT-policy. This creates a Reasoning Markov Chain (RMC). The agent's actual behavior is defined by the steady-state distribution of this chain—the distribution it settles into after enough reasoning steps.

Key technical components include:

  • Steady-State Policy Gradient (SSPG): A novel, tractable method to estimate gradients for an implicitly defined steady-state distribution. It uses a reparameterization trick to backpropagate through the reasoning steps.
  • Adaptive Reasoning: The agent uses a statistical tool called the Gelman-Rubin (GR) diagnostic (specifically the Pseudo Scale Reduction Factor, or PSRF) to detect when the RMC has converged, allowing it to stop reasoning once it reaches the steady state.
  • Short-term Action Memory: To speed up convergence, the agent initializes its reasoning process using a buffer of recent past actions, exploiting the temporal consistency of physical environments.
Figure 2: (Left) BT-policy transition probabilities and quantized RMC state diagram. (Right) Sample approxi- mation of related steady-state distribution as compared to canonical distribution of the soft Q-function.

Datasets

The authors evaluated SSPG on two major benchmarks:

  • OpenAI Gym Mujoco: 6 proprioceptive continuous control tasks (e.g., Ant-v2, Humanoid-v2).
  • DeepMind Control (DMC) Suite: 12 pixel-based tasks (e.g., Finger-turn-hard, Cartpole-swingup-sparse).
  • Positional Bandits: A custom 2D toy environment designed to test the agent's ability to learn multi-modal distributions (visiting multiple goals).

Key Insights and Ideas

  • Universal Approximation via Iteration: Even if the BT-policy is a simple Gaussian, the resulting steady-state distribution can represent virtually any continuous distribution. This effectively turns a simple model into a powerful mixture model with potentially infinite components.
  • System 2 for RL: The framework brings a form of "deliberative reasoning" to RL. The agent "thinks" longer on harder problems.
  • Computational Efficiency: While reasoning takes time, the authors found that the number of steps required scales sub-linearly with performance gains. Furthermore, by reusing past solutions, the agent can reach the steady state much faster than starting from random noise.

Key Results

SSPG achieved state-of-the-art performance across both benchmarks:

  • Mujoco: SSPG significantly outperformed strong baselines like SAC, REDQ, and MBPO in terms of sample efficiency and final return.
  • DMC from Pixels: SSPG surpassed DrQv2, the previous state-of-the-art, particularly in tasks with sparse rewards where exploration is difficult.
  • Adaptivity: Experiments confirmed that the agent naturally performs more reasoning steps in complex environments like Humanoid compared to simpler ones like InvertedPendulum.
Figure 3: Performance evaluation of SSPG and recent state-of-the-art baselines using Rliable [55]. We consider six OpenAI Gym Mujoco tasks [29] (Top) and twelve DeepMind Control tasks from pixels [30] (Bottom).

Limitations and Future Work

  • Deployment Overhead: Performing multiple reasoning steps per action increases the time required for real-time inference, though the authors argue this is often negligible compared to environment simulation or sensor processing times.
  • Recurrent Memory: The current framework is purely Markovian. The authors noted that adding recurrent hidden states to the BT-policy made training unstable, suggesting a need for better architectures to handle long-term temporal dependencies.
  • Theoretical Assumptions: The convergence diagnostics rely on assumptions that are difficult to strictly guarantee in deep learning contexts, leaving room for more robust convergence detection methods.

Summary updated

Abstract

We introduce a new framework that performs decision-making in reinforcement learning (RL) as an iterative reasoning process. We model agent behavior as the steady-state distribution of a parameterized reasoning Markov chain (RMC), optimized with a new tractable estimate of the policy gradient. We perform action selection by simulating the RMC for enough reasoning steps to approach its steady-state distribution. We show our framework has several useful properties that are inherently missing from traditional RL. For instance, it allows agent behavior to approximate any continuous distribution over actions by parameterizing the RMC with a simple Gaussian transition function. Moreover, the number of reasoning steps to reach convergence can scale adaptively with the difficulty of each action selection decision and can be accelerated by re-using past solutions. Our resulting algorithm achieves state-of-the-art performance in popular Mujoco and DeepMind Control benchmarks, both for proprioceptive and pixel-based tasks.
BibTeX
@inproceedings{cetin2022policy,
  author = {Edoardo Cetin and Oya Celiktutan},
  title = {{Policy Gradient With Serial Markov Chain Reasoning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=iIVvD2Ym7n},
}
Figure