The first problem is to take a full description of an environment and an agent, and identify the best action available to that agent, explicitly assuming "full, post-hoc information." At this level we're not looking for a process that can be run, we're looking for a formal description of what is meant by "best available action." I would be very surprised if the resulting function could be evaluated within the described environment in general, and yeah, it will "require a halting oracle" (if the environment can implement Turing machines). Step one is not writing a practical program, step one is describing what is meant by "good decision." If you could give me a description of how to reliably identify "the best choice available" which assumed not only a halting oracle but logical omniscience and full knowledge of true arithmetic, that would constitute great progress. (The question is still somewhat ill-posed, but that's part of the problem: a well-posed question frames its answer.) At this level we're going to need something like logical counterfactuals, but we won't necessarily need logical uncertainty.

The second problem is figuring out how to do something kinda like evaluating that function inside the environment on a computer with unlimited finite computing power. This is the level where you need logical uncertainty etc. The second problem will probably be much easier to answer given an answer to the first question, though in practice I expect both problems will interact a fair bit.

Solving these two problems still doesn't give you anything practical: the idea is that answers would reveal the solution which practical heuristics must approximate if they're going to act as intended. (It's hard to write a program that reliably selects good decisions even in esoteric situations if you can't formalize what you mean by "good decisions"; it's easier to justify confidence in heuristics if you understand the solution they're intended to approximate; etc.)