How do you sample particle filters? This doesn’t work for a continuous action space.

Contributions

• Uses KLD sampling—adaptive sampling of particple filters
• “belief packing”—pack similar beliefs together, making observation tree smaller

KLD Sampling

KLD Sampling uses KL Divergence to approximate difference between two probability distributions:

\begin{equation} N \approx \frac{k-1}{2\xi} \qty(1- \frac{2}{9(k-1)} + \sqrt{\frac{2}{9(k-1)}} z_{1-\eta})^{3} \end{equation}

“Propagation”

We want to get a set of sampled observations from belief + action.

Belief Packing

L1 norm between beliefs. If its too small consider them the same beliefs.

Some more improvements to Importance Sampling.

Cross Entropy Method

1. draw initial samples
2. fit a new distribution with the subset that failed: weight each sample by

\begin{equation} w\qty(\tau) = \frac{p\qty(\tau) \qty {\tau \not \in \psi}}{q\qty(\tau)} \end{equation}

problem: what if, immediately on the first proposal, we never got any failures? Then the weight of everything is zero and then life is bad.

adaptive cross entropy method with adaptive importance sampling

Pick a notion of “distance to failure” \(f\qty(\tau)\)

Operation that adds elements in a set

constituents

• A set \(V\)
• Each non-necessarily-distinct elements \(u,v \in V\)

requirements

addition on a set \(V\) is defined by a function that assigned an element named \(u+v \in V\) (its closed), \(\forall u,v\in V\)

additional information

See also addition in \(\mathbb{F}^n\)

The additive identity allows another number to retain its identity after adding. That is: there exists an element \(0\) such that \(v+0=v\) for whatever structure \(v\) and addition \(+\) you are working with.

Assume for the sake of contradiction \(\exists\ 0, 0’\) both being additive identities in vector space \(V\).

Therefore:

\begin{equation} 0+0’ = 0’ +0 \end{equation}

commutativity.

Therefore:

\begin{equation} 0+0’ = 0 = 0’+0 = 0' \end{equation}

defn. of identity.

Hence: \(0=0’\), \(\blacksquare\).