Algorithms for Learning Markov Field Policies

Abdeslam Boularias, Oliver Kroemer, Jan Peters

Introduction

In traditional Reinforcement Learning (RL), finding an optimal policy usually requires high-quality "features"—mathematical descriptions of the environment that help the agent understand the value of its actions. However, designing these features is notoriously difficult, especially in robotics where visual data is noisy and object shapes are complex.

This paper introduces a novel way to represent policies in RL and Inverse Reinforcement Learning (IRL) using Markov Random Fields (MRFs). By incorporating a "state similarity graph" as a structural prior, the authors enable agents to learn smoother, more effective policies even when precise feature engineering is difficult or sensor data is noisy.

The Value of Spatial Consistency

The authors identify a critical gap: while we might not know the perfect features for a task, we often possess "loose" domain knowledge. For example, in a robotic grasping task, we know that if a specific point on a mug's handle is a good place to grip, a point just a few millimeters away is likely also a good spot. Standard RL often struggles to exploit this spatial consistency. This paper aims to bake this "smoothness" directly into the mathematical framework of the policy.

Methodology: Policy as a Graphical Model

The core innovation of this work is treating the policy search as an inference problem within a graphical model. The most significant insight is realizing that the dependencies between actions in different states can be modeled as an MRF. This allows the agent to "fill in the gaps" in its knowledge by looking at what works in similar states.

The approach is built on several key components:

  1. The State Similarity Graph: The user provides a graph (or a kernel) where edges connect states that should likely have similar optimal actions (e.g., physically adjacent points in a robot's workspace).
  2. Bellman Error as a Penalty: Instead of solely maximizing reward, the authors introduce a constraint based on the Bellman error. They argue that an optimal policy should have a low Bellman error when approximated by the provided similarity kernel. This uses structure as regularization, guiding the agent without strictly limiting it to a specific functional form.
  3. MRF Policy Distribution: By solving a constrained optimization problem (maximizing expected reward and entropy while minimizing Bellman error), they derive a policy distribution that takes the form of an MRF. This distribution balances an exploration factor, an expected reward term, and a smoothness term that encourages actions consistent with neighbors in the similarity graph.
  4. AL-MRF: The authors extend this framework to Apprenticeship Learning (learning from expert demonstrations), creating an algorithm called AL-MRF that matches both the expert's performance and the expert's policy structure.

Experimental Results

The authors evaluated their approach on two distinct simulated environments to test both standard RL and IRL capabilities.

Swing-up Cart-Balancing

The first environment is a classic control problem modified with non-uniform friction across the track to make it more challenging.

Learning curves for the cart-balancing task

The MRF-based policy converged significantly faster than standard Metropolis-Hastings sampling. As shown in the learning curves, enforcing stricter smoothness (lower thresholds for Bellman error, such as BE < 0.6) led to higher average rewards per time-step, demonstrating the value of the structural prior.

Precision Grasping of Unknown Objects

The second task involved a complex simulated three-fingered Barrett hand. The dataset consisted of 3D point clouds of various household objects (mugs, buckets, etc.). The goal was to learn to grasp these objects specifically by their handles based on limited expert demonstrations.

Qualitative heatmaps of grasping Q-values

The AL-MRF algorithm significantly outperformed baselines like Maximum Entropy IRL and Associative Markov Networks (AMN), achieving a near-perfect percentage of successful grasps. The baselines often got "confused" by noisy point cloud data and self-occlusions. Qualitatively, the AL-MRF Q-values—visualized as heatmaps on the objects—were much cleaner. The algorithm successfully learned "object recognition by functionality," highlighting handles specifically while ignoring the noisy body of the objects.

Limitations and Future Work

While powerful, the approach has notable limitations:

  • Computational Complexity: Calculating the "partition function" (a normalization constant for the MRF) is computationally expensive, scaling at $O(|A||S|^2)$. While the authors suggest tricks like decomposing the state space into weakly connected components, this remains a bottleneck for very large state spaces.
  • Kernel Dependency: The performance is heavily tied to the quality of the state similarity graph. If the provided similarity measure is fundamentally wrong for the task, the introduced bias could favor suboptimal policies.

For future work, the paper suggests applying more recent, efficient inference techniques for MRFs (like those used in modern computer vision) to help scale the algorithm to even more complex, high-dimensional robotic tasks.

Summary updated

Abstract

We present a new graph-based approach for incorporating domain knowledge in reinforcement learning applications. The domain knowledge is given as a weighted graph, or a kernel matrix, that loosely indicates which states should have similar optimal actions. We first introduce a bias into the policy search process by deriving a distribution on policies such that policies that disagree with the provided graph have low probabilities. This distribution corresponds to a Markov Random Field. We then present a reinforcement and an apprenticeship learning algorithms for finding such policy distributions. We also illustrate the advantage of the proposed approach on three problems: swing-up cart-balancing with nonuniform and smooth frictions, gridworlds, and teaching a robot to grasp new objects.
BibTeX
@inproceedings{boularias2012algorithms,
  author = {Abdeslam Boularias and Oliver Kroemer and Jan Peters},
  title = {{Algorithms for Learning Markov Field Policies}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2012},
}
Figure