So, I consider the "go back in time" aspect of this unnecessarily confusing... the important part from my perspective is what events my timeline contains, not where I am on that timeline. For example, suppose I'm offered a choice between two identical boxes, one of which contains a million dollars. I choose box A, which is empty. What I want at that point is not to go back in time, but simply to have chosen the box which contained the money... if a moment later the judges go "Oh, sorry, our mistake... box A had the money after all, you win!" I will no longer regret choosing A. If a moment after that they say "Oh, terribly sorry, we were right the first time... you lose" I will once more regret having chosen A (as well as being irritated with the judges for jerking me around, but that's a separate matter). No time-travel required.

All of that said, the distinction you raise here (between regretting an improperly made decision whose consequences were undesirable, vs. regretting a properly made decision whose consequences were undesirable) applies either way. And as you say, a rational agent ought to do the former, but not the latter.

(There's also in principle a third condition, which is regretting an improperly made decision whose consequences were desirable. That is, suppose the judges rigged the game by providing me with evidence for "A contains the money," when in fact B contains the money. Suppose further that I completely failed to notice that evidence, flipped a coin, and chose B. I don't regret winning the money, but I might still look back on my decision and regret that my decision procedure was so flawed. In practice I can't really imagine having this reaction, though a rational system ought to.)

(And of course, for completeness, we can consider regretting a properly made decision whose consequences were desirable. That said, I have nothing interesting to say about this case.)

All of which is completely tangential to your lexical question.

I can't think of a pair of verbs that communicate the distinction in any language I know. In practice, I would communicate it as "regret the process whereby I made the decision" vs "regret the results of the decision I made," or something of that sort.