PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive importance sampling for control and inference

Hilbert Johan Kappen, Hans Christian Ruiz

arXiv:1505.01874v4eess.SYcs.ROcs.SY

TL;DR

High-dimensional stochastic optimal control is difficult to solve, and effective state-feedback controllers are challenging to represent. The paper uses importance sampling and cross-entropy ideas to learn parameterized controllers, and demonstrates path-integral control for posterior estimation in a latent-state model. In the neural-network example, the method estimates the posterior distribution with a reported computation time of 35.1 seconds, compared with 638 seconds for FFBSi.

  • Problem

    High-dimensional Bellman equations are difficult to solve, while state- and time-dependent feedback controllers are challenging to represent for nonlinear stochastic control.

    Source: §1 · pp. 2–3

  • Method

    The paper connects optimal control with importance sampling and uses cross-entropy optimization to learn parameterized state-feedback controllers and apply path-integral control to latent-state inference.

    Source: §1 · p. 2, Outline · p. 5, §6 · p. 20

  • Results

    RPIIS estimated the posterior distribution with a computation time of 35.1 s, compared with 638 s for FFBSi.

    Source: §5 · p. 18

  • Takeaways & Limitations

    Path-integral control provides an alternative for estimating posterior distributions in latent-state models, including neuroscience inference from noisy observations.

    Source: Outline · p. 5

    Small λ reduces effective sample size, while choosing ν and R to avoid that also constrains disturbance and control-cost settings.

    Source: §4 · p. 17

Abstract

from arXiv · show

Path integral (PI) control problems are a restricted class of non-linear control problems that can be solved formally as a Feyman-Kac path integral and can be estimated using Monte Carlo sampling. In this contribution we review path integral control theory in the finite horizon case. We subsequently focus on the problem how to compute and represent control solutions. Within the PI theory, the question of how to compute becomes the question of importance sampling. Efficient importance samplers are state feedback controllers and the use of these requires an efficient representation. Learning and representing effective state-feedback controllers for non-linear stochastic control problems is a very challenging, and largely unsolved, problem. We show how to learn and represent such controllers using ideas from the cross entropy method. We derive a gradient descent method that allows to learn feed-back controllers using an arbitrary parametrisation. We refer to this method as the Path Integral Cross Entropy method or PICE. We illustrate this method for some simple examples. The path integral control methods can be used to estimate the posterior distribution in latent state models. In neuroscience these problems arise when estimating connectivity from neural recording data using EM. We demonstrate the path integral control method as an accurate alternative to particle filtering.

1 Introduction

Path integral control makes a restricted class of nonlinear stochastic control problems amenable to path-integral estimation, while importance sampling connects computation to control quality. The paper reviews approaches to representing controllers and outlines learning controllers and applying them to latent-state inference.

1 Introduction

  • Path integral control covers nonlinear problems with arbitrary dynamics and state cost under linear control dependence and quadratic control cost, enabling a linear Bellman equation and path-integral Monte Carlo estimates.In general, solving the Bellman equation for high-dimensional systems is difficult.Source: §1 · p. 2
  • Importance sampling can estimate path integrals with suboptimal controls, and the optimal sampler is the optimal control; better samplers have higher effective sample size and lower control cost.This relation supports iterative sampler improvement, increasing sampling efficiency.Source: §1 · p. 2
  • State-feedback control depends on the current state and time, making the general controller an infinite-dimensional object that is difficult to represent for all states.The paper calls this the representation problem.Source: §1 · pp. 2–3

Deterministic control and local linearisation

  • Deterministic open-loop control can work for tasks such as grasping or reaching, but is generally suboptimal and fails for unstable systems requiring state feedback.Linear feedback around the trajectory can stabilize it; iterative trajectory and controller updates are known as Differential Dynamic Programming or Iterative LQG [Mayne, 1966, Murray and Yakowitz, 1984; Todorov and Li, 2005].Source: Deterministic control and local… · p. 3

Model predictive control

  • Model predictive control computes a finite-horizon solution from the current state at run time, avoiding explicit representation of a controller for all states.For path integral control, the challenge is evaluating the path integral accurately enough in real time.Source: Model predictive control · pp. 3–4

Outline

  • The chapter outlines cross-entropy learning of parameterized controllers and a path-integral-control approach to latent-state inference in neuroscience.The inference example estimates neural activity from noisy observations in a toy network.Source: Outline · pp. 4–5

2 Path integral control

The section derives a path-integral solution to a class of stochastic optimal control problems by linearizing the Bellman equation. It then shows how Monte Carlo sampling estimates the solution and how the control used for sampling affects efficiency.

2 Path integral control

  • For the specified path integral control problem, the optimal cost-to-go is the negative log of an expectation over trajectories, giving a path-integral solution.The multidimensional formulation requires the noise covariance and control cost matrix to satisfy λI = Rν, with λ > 0.Source: §2 · pp. 5–6

2.1 The linear HJB equation

  • The log transform ψ(t, x) = e^-J(t, x) turns the nonlinear Hamilton-Jacobi-Bellman equation into a linear partial differential equation.The HJB equation describes the evolution of the cost-to-go and has terminal boundary condition J(x, T) = φ(x).Source: §2.1 · p. 7

2.2 Proof of the Theorem

  • The proof establishes a closed-form path-integral expression for the optimal cost-to-go using a lemma for the transformed Bellman equation.Taking the expectation in the lemma yields the stated solution.Source: §2.2 · p. 8

2.3 Monte Carlo sampling

  • Monte Carlo estimates the path integral, and using the optimal control as the sampling control gives equal trajectory weights and zero variance; controls closer to optimal yield more effective sampling.The exact optimal control is generally infeasible to compute, motivating the cross-entropy method; numerical estimation also uses a finite time increment to avoid instability, at the expense of theoretical correctness.Source: §2.3 · p. 9

3 The cross-entropy method

The cross-entropy method improves Monte Carlo importance sampling by adapting a parameterized sampler toward the ideal distribution. The paper reformulates path integral control as trajectory-distribution matching and derives PICE updates for learning controls.

3 The cross-entropy method

  • The ideal importance sampler has zero variance but cannot be used in practice because it requires the unknown quantity being estimated.When naive sampling has little overlap with the integrand's support, most samples contribute nearly zero and the estimate has high variance.Source: §3 · p. 10
  • Cross-entropy adapts a parameterized sampling distribution toward the ideal sampler by minimizing KL divergence, with iterative sampling and parameter updates.For tilted distributions, the update matches the sampler's expected value to the h-weighted expectation under the original distribution.Source: §3 · pp. 10–11

3.1 The Kullback-Leibler formulation of the path integral control problem

  • Path integral control's quadratic control cost equals the KL divergence between controlled and uncontrolled trajectory distributions, allowing control optimization to be written as distribution optimization.The optimal trajectory distribution is expressed using the uncontrolled dynamics weighted by the exponential of the state cost.Source: §3.1 · p. 12

3.2 The cross entropy method for path integral control

  • PICE uses gradient descent on the KL objective to learn parameterized controls, using the latest control estimate as the sampling control.Linear combinations of basis functions yield solvable linear systems; time-independent controls can reduce storage when that representation is appropriate.Source: §3.2 · pp. 13–14

4 Numerical illustration

The illustrations apply path-integral learning to a linear-quadratic control problem and an inverted pendulum, estimating state-feedback controllers. The learned controller approaches the linear-quadratic solution and can swing up and stabilize the pendulum, while stochastic-control estimation remains challenging.

Linear-quadratic control

  • The linear-quadratic controller parameters rapidly approach their optimal values, θ1 = 0 and θ2 = −1.41.The entropic sample size increases as the sampling control improves; finite horizon and initial-state transients account for underestimation of |θ1|.Source: §4 · p. 15

Inverted pendulum

  • The learned inverted-pendulum controller swings the pendulum up and stabilizes it, with distinct control behavior for positive- and negative-velocity trajectories.The control solution requires no control along a ridge of states moving toward the target, but requires balancing control in the orthogonal direction.Source: §4 · p. 16

Limitations

  • Stochastic path-integral control can show large fluctuations even with many samples, because small effective sample size and finite controller capacity constrain estimation.The temperature λ = Rν links noise variance and control cost: reducing ν or R can reduce effective sample size, while larger noise makes control harder.Source: §4 · p. 17

Representation challenge

  • Successful path-integral learning depends on balancing controller flexibility against the number of parameters that can be learned from available samples.The representation must be flexible enough for arbitrary functions without requiring too many samples.Source: §4 · p. 17

Inverted pendulum

  • The pendulum example illustrates learning a multimodal, time-independent state-feedback controller, unlike iterative LQG’s unimodal, time-dependent solution.The controller represents both possible swing-up solutions simultaneously.Source: §4 · pp. 16–17

5 Bayesian system identification: potential for neuroscience data analysis

The section applies path integral control and importance sampling to posterior estimation in latent state models. In a two-dimensional neural-network example, RPIIS estimates the marginal posterior using less computation than FFBSi, while feedback control improves sampling efficiency over open-loop control.

5 Bayesian system identification: potential for neuroscience data analysis

  • Particle filtering-smoothing methods are commonly used, but their smoothing estimates rely heavily on filtering distributions that may differ substantially in high-dimensional problems.The passage links this mismatch to poor estimation accuracy.Source: §5 · p. 18
  • Representing the posterior as a path-integral control problem lets Monte Carlo sampling estimate it, with computation linear in particle count rather than quadratic for particle smoothing.The passage notes that practical accelerations of particle smoothing are possible.Source: §5 · pp. 17–18
  • The example estimates the posterior distribution of a noisy two-dimensional firing-rate model from 12 noisy observations of one neuron.The model uses a Gaussian observation model with σ_obs = 0.2 and dynamical noise variance σ²_dyn = 0.2.Source: §5 · p. 18
  • RPIIS computed the posterior estimates in 35.1 s, compared with 638 s for FFBSi, in the two-dimensional neural-network example.The comparison used 22 importance-sampling iterations with 6,000 particles each for RPIIS and 6,000 forward and 3,600 backward particles for FFBSi.Source: §5 · p. 18, Figure 3 · p. 19
  • Feedback control yielded 60% ESS, versus around 29% for open-loop control, and the lower open-loop sampling efficiency increased estimation error, especially posterior-marginal variance.The open-loop controller steers particles toward observations; the feedback controller stabilizes them around observations, including non-observed neurons through coupling.Source: §5 · p. 19
  • The example indicates potential for adaptive importance sampling in continuous state-space inference, including neuroscience applications, while high-dimensional analysis remains future work.The authors mention connectivity estimation, neural-population decoding, and spike-rate-function estimation as possible applications.Source: §5 · pp. 18–19

6 Summary and discussion

The discussion frames path-integral control as an importance-sampling method whose asymptotic result is independent of the sampling control, although efficiency depends on that choice. It presents cross-entropy learning as a way to obtain parameterized controls and discusses its relation to other approaches.

6 Summary and discussion

  • Any exploration control gives the same asymptotic path-integral result because it acts as a Monte Carlo importance sampler, though sampling efficiency depends critically on the control.Theorem 1 is also described as useful for high-dimensional stochastic control in a Model Predictive Control setting [Gómez et al., 2015].Source: §6 · pp. 19–20
  • Figure 4 presents control parameters: the left panel shows open-loop controller b_i(t) for i = 1, 2, and the right panel shows diagonal entries of feedback linear controller A_ii(t), t = 1, 2.Source: Figure 4 · p. 20
  • Theorem 1 is limited for computing a parameterized control over all states and times; cross-entropy learning instead fits a trajectory distribution to the optimally controlled distribution by minimizing reverse KL.The resulting framework supports controls that are arbitrary functions of state and parameters.Source: §6 · p. 20
  • The numerical examples restrict control parameterizations to be linear in their parameters, while nonlinear forms such as neural networks or Gaussian processes are described as readily extendable.The authors state that such generalization would entail no significant extra computational cost.Source: §6 · p. 20
  • Cross-entropy optimization for discrete Markov decision problems targets a zero-entropy solution, whereas path-integral control retains an entropy term and a finite-entropy solution.The discussion says local-minimum problems are therefore expected to be less severe, not absent.Source: §6 · pp. 20–21
  • Unlike discrete-state, discrete-action policy-gradient methods, path-integral learning concerns controlled nonlinear diffusions and uses an Itô stochastic integral in its gradient rule.The policy-gradient expectation is weighted by Qπ, whereas the path-integral expression uses e^-S; the latter gradient expectation is also independent of π.Source: §6 · p. 21

A Itˆo calculus

The appendix introduces Itô calculus rules for products and functions of stochastic processes. It also states an expectation-taking step and the Itô isometry.

A Itô calculus

  • Itô’s product rule gives the evolution of a product process, with a quadratic-covariance term identified as d[Y, Z].The passage writes that term as d[Y, Z] = B(Y)D(Z)ds.Source: A Itˆo calculus · p. 21
  • Itô’s lemma is presented as a chain rule giving the evolution of a function F(Y) of a stochastic process Y.Source: A Itˆo calculus · p. 21
  • The appendix describes putting a process equation in integral form and taking its expected value, then states the Itô isometry.Source: A Itˆo calculus · p. 22

Related papers

Loading 1505.01874v4…