I came across this problem awhile ago, made some notes and never published. Seems like a good time to write up the highlights.
A world model is a mapping from decisions to probability distributions over outcomes. A preference function is a total ordering over probability distributions over outcomes. Utility functions are the subset of preference functions which is conveniently linear (but we don't need those linearity properties right now). A decision theory maps from (world model, preference function) pairs to decisions, and the goodness of decision theories is a partial order such that for decision theories A and B, A>=B if for all preference functions Pref and world models World, Pref(World(A(World,Pref))) >= Pref(World(B(World,Pref))). This order has a supremum iff for all world models Pref(World(d)) has a supremum.
Where these orderings lack suprema, it is nevertheless possible to define limiting sequences of successively better options and successively better decision theories which generate them, such that for any single decision or decision theory the seqeunce must contain an element which is better. Finding and proving the correctness of such a sequence, for a particular world model, is proving that there is no optimal decision for that world model.
A bounded agent could approximate (but not reach) optimality by finding such a sequence, and traversing some distance along it. Such sequences, and the number of steps taken along them, can each be classified by their improvement rates. The partial order formed by those rates (with an ignored multiplicative constant on the sequence traversal distance) makes a second-order decision problem. If you ignore the constant, this one does have a supremum: the busy beaver function. (All further games you could play with BB can be folded into the one constant.)
In an earlier post, I talked about how we could deal with variants of the Heaven and Hell problem - situations where you have an infinite number of options, and none of them is a maximum. The solution for a (deterministic) agent was to try and implement the strategy that would reach the highest possible number, without risking falling into an infinite loop.
Wei Dai pointed out that in the cases where the options are unbounded in utility (ie you can get arbitrarily high utility), then there are probabilistic strategies that give you infinite expected utility. I suggested you could still do better than this. This started a conversation about choosing between strategies with infinite expectation (would you prefer a strategy with infinite expectation, or the same plus an extra dollar?), which went off into some interesting directions as to what needed to be done when the strategies can't sensibly be compared with each other...
Interesting though that may be, it's also helpful to have simple cases where you don't need all these subtleties. So here is one:
Omega approaches you and Mrs X, asking you each to name an integer to him, privately. The person who names the highest integer gets 1 utility; the other gets nothing. In practical terms, Omega will reimburse you all utility lost during the decision process (so you can take as long as you want to decide). The first person to name a number gets 1 utility immediately; they may then lose that 1 depending on the eventual response of the other. Hence if one person responds and the other doesn't, they get the 1 utility and keep it. What should you do?
In this case, a strategy that gives you a number with infinite expectation isn't enough - you have to beat Mrs X, but you also have to eventually say something. Hence there is a duel of (likely probabilistic) strategies, implemented by bounded agents, with no maximum strategy, and each agent trying to compute the maximal strategy they can construct without falling into a loop.