Variational Autoencoders (VAEs) have seen widespread use in learned image\ncompression. They are used to learn expressive latent representations on which\ndownstream compression methods can operate with high efficiency. Recently\nproposed 'bits-back' methods can indirectly encode the latent representation of\nimages with codelength close to the relative entropy between the latent\nposterior and the prior. However, due to the underlying algorithm, these\nmethods can only be used for lossless compression, and they only achieve their\nnominal efficiency when compressing multiple images simultaneously; they are\ninefficient for compressing single images. As an alternative, we propose a\nnovel method, Relative Entropy Coding (REC), that can directly encode the\nlatent representation with codelength close to the relative entropy for single\nimages, supported by our empirical results obtained on the Cifar10, ImageNet32\nand Kodak datasets. Moreover, unlike previous bits-back methods, REC is\nimmediately applicable to lossy compression, where it is competitive with the\nstate-of-the-art on the Kodak dataset.\n