  Relative entropy coding (REC) algorithms encode a sample from a target
distribution $Q$ using a proposal distribution $P$, such that the expected
codelength is $\mathcal{O}(D_{KL}[Q \,||\, P])$. REC can be seamlessly
integrated with existing learned compression models since, unlike entropy
coding, it does not assume discrete $Q$ or $P$, and does not require
quantisation. However, general REC algorithms require an intractable
$\Omega(e^{D_{KL}[Q \,||\, P]})$ runtime. We introduce AS* and AD* coding, two
REC algorithms based on A* sampling. We prove that, for continuous
distributions over $\mathbb{R}$, if the density ratio is unimodal, AS* has
$\mathcal{O}(D_{\infty}[Q \,||\, P])$ expected runtime, where $D_{\infty}[Q
\,||\, P]$ is the R\'enyi $\infty$-divergence. We provide experimental evidence
that AD* also has $\mathcal{O}(D_{\infty}[Q \,||\, P])$ expected runtime. We
prove that AS* and AD* achieve an expected codelength of $\mathcal{O}(D_{KL}[Q
\,||\, P])$. Further, we introduce DAD*, an approximate algorithm based on AD*
which retains its favourable runtime and has bias similar to that of
alternative methods. Focusing on VAEs, we propose the IsoKL VAE (IKVAE), which
can be used with DAD* to further improve compression efficiency. We evaluate A*
coding with (IK)VAEs on MNIST, showing that it can losslessly compress images
near the theoretically optimal limit.
