And the many worlds-interpretation is deterministic in exactly that sense: the wave function of the universe today is completely determined by the wave function of the universe at the beginning of the universe; in fact, it’s basically just a rotation of the latter through a high-dimensional, abstract space.
Saying this is simply wrong in many worlds. The wave function there evolves from a completely undecayed atom into a coherent superposition of decayed and undecayed states—which, again, is completely equivalent with regards to its information content to the wave function at any prior point.
What I’m saying is that I think you misunderstand what most people mean when they claim that they ‘could have done otherwise’. Again, of course, if you have them do everything in the same way as before, they will choose the same—but the potential of making a different choice is not touched by this, because to choose differently, you have to do something differently. Choice is an action; if you simply replay a sequence of actions, the outcome won’t be any more different than when you record it on film, and then replay the movie. Just because you can do so, because you can record me choosing something, and then replay the movie, and observe me choosing the same way again, simply has no impact on whether the choice was free.
It’s the same thing as with me ordering pizza yesterday: just because the fact of me making that order is fixed doesn’t mean that I didn’t order it freely. The same is true if you’ve recorded me placing that order on video: no matter how often you replay it, you won’t observe me placing a different order. And in the last consequence, this is also true if you just reset the universe to a point before I place my order, and observe me placing that same order again: I may do so, every time again, completely freely.
Although of course there’s a difficulty with the coherence of that last scenario: if you’d really reset the universe, you wouldn’t know anything about my order.