Discrete-Time Distribution Steering using Monte Carlo Tree Search

Alexandros E. Tzikas, Liam A. Kruse, Mansur M. Arief, Mykel J. Kochenderfer, Stephen BoydarXiv 2024 · DOI · arXiv

Introduction

Quantifying the similarity between probability distributions is a foundational requirement in control theory, essential for tasks such as steering a set of particles to a target shape or ensuring a robot's path covers an area according to a specific density. While metrics like Kullback–Leibler (KL) divergence or Wasserstein distance are popular, they often become computationally prohibitive or difficult to differentiate in high-dimensional spaces. This paper introduces a unified, differentiable family of distances for comparing high-dimensional probability distributions by averaging the discrepancies between their one-dimensional linear projections.

Methodology: Sliced CDF Distance

The core innovation is the Sliced CDF Distance. Instead of comparing high-dimensional distributions directly, the method projects them onto a random unit vector $q$ (a "slice"). In one dimension, comparing Cumulative Distribution Functions (CDFs) is mathematically simple and interpretable.

Conceptual illustration of the Sliced CDF Distance. High-dimensional distributions (X and Y) are projected onto a line, and the discrepancy between their resulting 1D CDFs is measured.

To make this distance useful for control, the authors replace the standard step-function CDF with a smooth sigmoid approximation. This allows for the calculation of gradients with respect to sample positions, enabling the use of standard gradient-based optimizers like Adam or SGD. This turns complex distribution matching problems into standard loss-minimization tasks.

Experimental Results

The paper evaluates the method using synthetic benchmarks designed to simulate real-world control challenges, including multivariate Gaussians and non-linear robotics models.

Two-sample testing results in 2D and 50D. The metric effectively distinguishes between identical (Null) and non-identical (Alternative) distributions, maintaining high discernibility even in high-dimensional spaces.

Key results from the evaluation include:

  • Two-Sample Testing: The metric clearly distinguished between identical and non-identical distributions in high dimensions (up to 50D), matching or outperforming standard baselines.
  • Distribution Steering: The algorithm successfully steered 3,000 particles following non-linear unicycle dynamics to match a target Gaussian Mixture Model (GMM).
  • Ergodic Control: In a long-horizon task, a single agent's trajectory was optimized so that its time-averaged occupancy matched a spatial target distribution, with the loss decreasing consistently over time.

Conclusion

The Sliced CDF Distance offers a computationally efficient, interpretable, and gradient-friendly framework for distribution matching. By providing theoretical guarantees and a differentiable implementation, it enables the application of simple optimization techniques to complex high-dimensional control problems.

Summary updated

BibTeX
@misc{tzikas2024discrete,
  author = {Alexandros E. Tzikas and Liam A. Kruse and Mansur M. Arief and Mykel J. Kochenderfer and Stephen Boyd},
  title = {{Discrete-Time Distribution Steering using Monte Carlo Tree Search}},
  year = {2024},
  eprint = {2412.06220},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.06220},
}
Figure