Efficient Inference in Markov Control Problems

Thomas Furmston, David Barber

TL;DR

This paper introduces a novel, more efficient algorithm for performing inference in Markov Control Problems (MCPs), specifically for policy gradient and Expectation Maximization (EM) methods. The new "Q-inference" approach achieves linear time complexity with respect to the planning horizon, a significant improvement over the standard quadratic complexity, and also provides a principled way to handle infinite horizon problems.

What Problem Does This Paper Address?

Markov Decision Problems (MDPs) are a fundamental framework for sequential decision-making. Finding an optimal policy (a strategy for choosing actions) in an MDP is often computationally challenging, especially for complex, continuous, or long-horizon problems. While traditional methods like Value Iteration and Policy Iteration focus on greedy policy updates, they struggle with these complexities. More advanced methods like policy gradients and Expectation Maximization (EM) offer smoother policy updates and have been successful in various domains. However, these methods critically rely on computing marginal distributions of reward-weighted trajectories. The standard approach for this, using forward-backward recursions, has a computational complexity that scales quadratically with the planning horizon, making it inefficient for long-horizon problems. Furthermore, extending these methods to infinite horizon MDPs presents its own set of challenges. This paper aims to address these inefficiencies by developing a more computationally efficient inference algorithm for these crucial marginals, applicable to both finite and infinite horizon MDPs.

Methods

The core contribution of this paper is a new inference algorithm, termed "Q-inference," which significantly improves the efficiency of computing reward-weighted trajectory distributions.

  • Q-Functions: The paper introduces a new set of functions called "Q-functions" (not to be confused with standard Q-learning Q-functions). These Q-functions are defined as sums of state-action marginals over different time components, weighted by future rewards. They offer an intuitive interpretation: proportional to the probability of reaching a state-action pair at a given time, multiplied by the total expected future reward.
  • Recursive Relation: A key lemma establishes a recursive relationship between these Q-functions. This allows for the efficient calculation of Q-functions by propagating information backward in time, leveraging the system's reversal dynamics.
  • Finite Horizon Efficiency: For finite horizon problems, this recursive structure allows for the calculation of all necessary Q-functions in linear time with respect to the planning horizon (O(H)), a substantial improvement over the standard quadratic time complexity (O(H^2)) of forward-backward recursions.
  • Infinite Horizon Extension: The paper extends the Q-inference approach to infinite horizon MDPs. This is achieved by utilizing the fact that for controllable systems, state-action distributions converge to a stationary distribution. By exploiting this convergence and the recursive Q-function relation, the paper derives a method to analytically calculate the infinite number of marginals needed for policy updates. This provides a principled alternative to approximations like the "time-marginal" criterion used in prior work.
  • Continuous MDPs: The framework is also extended to continuous state and action spaces, where moments of the Q-functions are calculated recursively, maintaining linear time complexity.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and algorithmic improvements, demonstrating its methods on synthetic problems and standard robotics benchmarks.

Key Insights and Ideas

  • Decomposition into Q-functions: The insight of decomposing the reward-weighted trajectory distribution into a set of Q-functions, which have a recursive structure, is central. This decomposition allows for a more efficient inference process.
  • Leveraging Reversal Dynamics: The Q-inference algorithm effectively utilizes the system's reversal dynamics to propagate information backward in time, leading to the linear time complexity. This is a departure from traditional forward-backward recursions that operate more concurrently.
  • Principled Infinite Horizon Approach: The paper offers a theoretically sound method for handling infinite horizon problems by exploiting the convergence of state-action distributions, avoiding ad-hoc approximations.
  • Connection to Dynamic Programming: The Q-functions share a resemblance with dynamic programming value functions, but the paper highlights key differences, particularly the weighting by expected reward and dependence on previous time steps, which are crucial for EM and policy gradient methods.

Key Results

  • Linear Time Complexity for Finite Horizons: The Q-inference algorithm achieves O(H) complexity for finite horizon problems, compared to the O(H^2) of standard forward-backward recursions.
  • Efficient Infinite Horizon Inference: The paper provides a novel algorithm for calculating the necessary statistics for infinite horizon EM and policy gradient methods, offering a principled approach.
  • Experimental Validation:
    • Double Reward Chain Problem: The Q-inference algorithm successfully identified the global optimum in an infinite horizon setting, outperforming the "time-marginal" criterion which often got stuck in local optima, especially for longer chains.
  • 2-Link Robot Manipulator: In a continuous control experiment, the Q-inference algorithm achieved comparable performance to a standard forward-backward inference method but required significantly less training time (around 35 seconds vs. 300 seconds). Furthermore, with the same training time, Q-inference achieved a higher normalized total expected reward.

Limitations and Future Work

  • Initialization Dependence: As noted in the experiments, the performance of EM-based algorithms, including the one presented, can depend on the initialization of the policy. The paper acknowledges that for complex problems, multiple runs with different initializations might be necessary.
  • Generalization to Other Algorithms: While the paper focuses on policy gradients and EM, it suggests that the Q-inference framework is readily applicable to other algorithms that rely on reward-weighted trajectory distributions.
  • Partially Observable MDPs: The authors mention that their methods are readily applicable to other Markovian control problems, such as Partially Observable Markov Decision Processes (POMDPs), indicating a promising avenue for future research.
  • Comparison with Other Inference Methods: While the paper compares its method to forward-backward recursions, further comparisons with other approximate inference techniques in the context of MCPs could be valuable.

Summary updated

Abstract

Markov control algorithms that perform smooth, non-greedy updates of the policy have been shown to be very general and versatile, with policy gradient and Expectation Maximisation algorithms being particularly popular. For these algorithms, marginal inference of the reward weighted trajectory distribution is required to perform policy updates. We discuss a new exact inference algorithm for these marginals in the finite horizon case that is more efficient than the standard approach based on classical forward-backward recursions. We also provide a principled extension to infinite horizon Markov Decision Problems that explicitly accounts for an infinite horizon. This extension provides a novel algorithm for both policy gradients and Expectation Maximisation in infinite horizon problems.
BibTeX
@inproceedings{furmston2011efficient,
  author = {Thomas Furmston and David Barber},
  title = {{Efficient Inference in Markov Control Problems}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=y5UuDoJjag},
}
Figure