It may help to think about video codecs as standards on how to decode images from a series of bits, not on how to encode them.
Decoding is deterministic, encoding is not.
You have to consider that these encoders are lossy, i.e. while encoding they modify the information so that it is more easily compressible. Different encoders will do different choices and produce different result while using the same bitrate.
Obviously encoders are constrained by the fact that they must produce a series of bits that can be decoded according to a certain standard, so a new video format can enable encoders to compress information more efficiently (i.e. less perceptual loss of quality at the same bitrate).
Obviously encoders are constrained by the fact that they must produce a series of bits that can be decoded according to a certain standard, so a new video format can enable encoders to compress information more efficiently (i.e. less perceptual loss of quality at the same bitrate).