Copying a comment from @dominiccooney:

When there is no match key set, what to encrypt. I suggest random bytes which are then the match key for the epoch. There were some proposals to try and carve up the key space amongst UA brands though.
When there was a match key for a prior epoch, but none set this epoch, what to encrypt. I suggest the UA should re-commit to the previous match key for this epoch.
...if you accept 2, then there's the obvious question of how they get updated.

So I think the UA stores two match keys per provider, an operative one+epoch, and a pending one. Here's a rough proposal:

Writes:

• If there's no operative match key, writing the match key sets both the pending and operative match keys; the operative match key gets the current epoch.
• If there is an operative match key, writing the match key sets the pending one.

Reads:

• If there is an operative match key for the current epoch, reading the match key returns it.
• If there is no pending match key, reading the match key sets the operative match key to a random string and the current epoch.
• If your UA wanted its identity to be sticky, also set the pending match key to the same string of bits. The UA should reflect user preference here.
• If there is an operative match key for an old epoch, set the operative match key to the pending match key and the current epoch.