Technical Report: The Policy Graph Improvement Algorithm

Joni PajarinenarXiv 2020 · arXiv

Introduction

Partially Observable Markov Decision Processes (POMDPs) represent a significant challenge in reinforcement learning. Unlike standard MDPs, where the agent has full state visibility, a POMDP agent must make decisions based on noisy observations. This requires maintaining a "belief"—a probability distribution over all possible states. Traditional "alpha vector" methods often suffer from exponential complexity growth and a lack of interpretability.

The Policy Graph Improvement (PGI) algorithm addresses these issues by constraining the policy to a fixed-size, layered graph. This approach ensures monotonic performance improvements and predictable computation times, providing a transparent alternative to traditional black-box solvers.

The Policy Graph Framework

In PGI, a policy is represented as an acyclic graph with $T$ layers, corresponding to discrete time steps. Each node within a layer specifies an action $a$. Transitions between layers are governed by observations $o$; upon receiving an observation, the agent follows the corresponding edge to a node in the subsequent layer.

The Two-Pass Optimization Process

The core of the PGI algorithm is an iterative two-pass process designed to optimize the graph's actions and transitions.

1. Forward Pass: Belief Projection

The forward pass begins with an initial belief $b_0(s)$. The algorithm "projects" this belief through the current policy graph to calculate the probability of being in specific states at each node. This step identifies which states are reachable at different points in the execution of the policy.

Visualization of the forward pass: projecting beliefs through the policy graph layers.

2. Backward Pass: Dynamic Programming

Starting from the final time step and moving backward, the algorithm updates each node to maximize expected rewards. For every node, PGI selects the optimal action and the best "next-node" transitions for every possible observation. This dynamic programming approach ensures that each update step contributes to a global improvement in the policy's value.

Visualization of the backward pass: optimizing actions and transitions using dynamic programming.

Scaling to High-Dimensional Spaces: Particle PGI

For environments with massive state spaces where exact belief updates are computationally infeasible, the report introduces Particle PGI (PPGI). Instead of full probability distributions, PPGI utilizes a set of "particles" (samples) to represent beliefs. Monte Carlo simulations are then used to estimate future rewards, allowing the algorithm to scale to complex, high-dimensional problems.

Key Advantages

  • Monotonic Improvement: PGI is guaranteed to either improve the policy or maintain its performance at each iteration, preventing "regression" during training.
  • Predictable Computation: Since the graph size is pre-defined, the computational cost per iteration is fixed, making it suitable for resource-constrained engineering environments.
  • Interpretability: The resulting policy is a human-readable graph, allowing for easier debugging and visualization compared to abstract mathematical representations.

Conclusion and Limitations

While PGI offers stability and clarity, it is subject to certain constraints. The fixed size of the graph limits the policy's expressivity; if the graph is too small, the agent may not reach the true optimal policy. Additionally, the current acyclic formulation is tailored for finite-horizon tasks. Future work may involve extending these principles to infinite-horizon tasks using cyclic graphs. Despite these limitations, PGI serves as a robust framework for distilling complex POMDP policies into manageable, improvable structures.

Summary updated

Abstract

Optimizing a partially observable Markov decision process (POMDP) policy is challenging. The policy graph improvement (PGI) algorithm for POMDPs represents the policy as a fixed size policy graph and improves the policy monotonically. Due to the fixed policy size, computation time for each improvement iteration is known in advance. Moreover, the method allows for compact understandable policies. This report describes the technical details of the PGI [1] and particle based PGI [2] algorithms for POMDPs in a more accessible way than [1] or [2] allowing practitioners and students to understand and implement the algorithms.
BibTeX
@misc{pajarinen2020technical,
  author = {Joni Pajarinen},
  title = {{Technical Report: The Policy Graph Improvement Algorithm}},
  year = {2020},
  eprint = {2009.02164},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2009.02164},
}
Figure