That original post lays out UDT1.0, I don't see anything about precomputing the optimal policy within it. The UDT1.1 fix of optimizing the global policy instead of figuring out the best thing to do on the fly, was first presented here, note that the 1.1 post that I linked came chronologically after the post you linked.

I'd strongly agree with that, mainly because, while points with this property exist, they are not necessarily unique. The non-uniqueness is a big issue.

It was a typo! And it has been fixed.

It is because beach/beach is the surplus-maximizing result. Any Pareto-optimal bargaining solution where money is involved will involve the surplus-maximizing result being played, and a side payment occuring.

I have a reduction of this problem to a (hopefully) simpler problem. First up, establish the notation used.

[n] refers to the set $\left\{\mathrm{1...}n\right\}$. $n$ is the number of candidates. Use $C$ as an abbreviation for the space $\Delta \left[n\right]$, it's the space of probability distributions over the candidates. View $C$ as embedded in $R^{n-1}$, and set the origin at the center of $C$.

At this point, we can note that we can biject the following: 
1: Functions of type $\left[n\right]\to [0,1]$ 
2: Affine functions of type $C\to [0,1]$ 
3: Functions of the form $\lambda x.⟨a,x⟩+c$, where $x,a\in R^{n-1}$, and and $c\in R$, and everything's suitably set so that these functions are bounded in $[0,1]$ over $C$. (basically, we extend our affine function to the entire space with the Hahn-Banach theorem, and use that every affine function can be written as a linear function plus a constant) We can reexpress our distribution $V$ over utility functions as a distribution over these normal vectors $a$.

Now, we can reexpress the conjecture as follows. Is it the case that there exists a $\mu :\Delta C$ s.t. for all $\nu :\Delta C$, we have 

 Where $\text{sgn}$ is the function that's -1 if the quantity is negative, 0 if 0, and 1 if the quantity is positive. To see the equivalence to the original formulation, we can rewrite things as 

 Where the bold 1 is an indicator function. And split up the expectation and realize that this is a probability, so we get 

 And this then rephrases as 

 Which was the original formulation of the problem.

Abbreviating the function $E_{x,y,a\sim \mu \times \nu \times V}\left[\text{sgn}\right(⟨a,x-y⟩\left)\right]$ as $f(\mu ,\nu )$, then a necessary condition to have a $\mu :\Delta C$ that dominates everything is that 

 If you have this property, then you might not necessarily have an optimal $\mu$ that dominates everything, but there are $\mu$ that get a worst-case expectation arbitrarily close to 0. Namely, even if the worst possible $\nu$ is selected, then the violation of the defining domination inequality happens with arbitrarily small magnitude. There might not be an optimal lottery-lottery, but there are lottery-lotteries arbitrarily close to optimal where this closeness-to-optimality is uniform over every foe. Which seems good enough to me. So I'll be focused on proving this slightly easier statement and glossing over the subtle distinction between that, and the existence of truly optimal lottery-lotteries.

As it turns out, this slightly easier statement (that sup inf is 0 or higher) can be outright proven assuming the following conjecture.

Stably-Good-Response Conjecture: For every $\nu :\Delta C$, and $ϵ>0$, there exists a $\mu :\Delta C$ and a $\delta >0$ s.t. 

Pretty much, for any desired level of suckage and any foe $\nu$, there's a probability distribution $\mu$ you can pick which isn't just a good response (this always exists, just pick $\nu$ itself), but a stably good response, in the sense that there's some nonzero level of perturbation to the foe where $\mu$ remains a good response no matter how the foe is perturbed.

Theorem 1 Assuming the Stably-Good-Response Conjecture, ${sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )\ge 0$.

I'll derive a contradiction from the assumption that $0>{sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )$. Accordingly, assume the strict inequality.

In such a case, there is some $ϵ$ s.t. $0>-ϵ>{sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )$. Let the set $A_{\mu }:=\left\{\nu |f\right(\mu ,\nu )>-ϵ\}$. Now, every $\nu$ lies in the interior of $A_{\mu }$ for some $\mu$, by the Stably-Good-Response Conjecture. Since $\Delta C$ is a compact set, we can isolate a finite subcover and get some finite set $M$ of probability distributions $\mu$ s.t. $\forall \nu \exists \mu \in M:f(\mu ,\nu )>-ϵ$.

Now, let the set $B_{\nu }:=\{\mu \in c.h(M\left)|f\right(\mu ,\nu )<-ϵ\}$. Since $-ϵ>{sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )$, this family of sets manages to cover all of $c.h\left(M\right)$ (convex hull of our finite set.) Further, for any fixed $\nu$, $f(\mu ,\nu )$ is a continuous function $c.h\left(M\right)\to R$ (a bit nonobvious, but true nontheless because there's only finitely many vertices to worry about). Due to continuity, all the sets $B_{\nu }$ will be open. Since we have an open cover of $c.h\left(M\right)$, which is a finite simplex (and thus compact), we can isolate a finite subcover, to get a finite set $N$ of $\nu$ s.t. $\forall \mu \in c.h\left(M\right)\exists \nu \in N:f(\mu ,\nu )<-ϵ$. And now we can go 

 The first strict inequality was from how all $\mu \in c.h\left(M\right)$ had some $\nu \in N$ which made $f(\mu ,\nu )$ get a bad score. The $\ge$ was from expanding the set of options. The $=$ was from how $f$ is a continuous linear function when restricted to $c.h\left(M\right)\times c.h\left(N\right)$, both of which are compact convex sets, so the minimax theorem can be applied. Then the next $\ge$ was from restricting the set of options, and the $>$ was from how every $\nu \in \Delta C$ had some $\mu \in M$ that'd make $f(\mu ,\nu )$ get a good score, by construction of $M$ (and compactness to make the inequality a strict one).

But wait, we just showed $-ϵ>-ϵ$, that's a contradiction. Therefore, our original assumption must have been wrong. Said original assumption was that $0>{sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )$, so negating it, we've proved that 

 As desired.

With this.

What I mean is, the players hit each other up, are like "yo, let's decide on which ROSE point in the object-level game we're heading towards"
Of course, they don't manage to settle on what equilibrium to go for in the resulting bargaining game, because, again, multiple ROSE points might show up in the bargaining game. 
But, the ROSE points in the bargaining game are in a restricted enough zone (what with that whole "must be better than the random-dictator point" thing) to seriously constrain the possibilities in the object-level game. "Worst ROSE point for Alice in the object-level-game" is a whole lot worse for her than "Worst ROSE point for Alice in the bargaining game about what to do in the object-level-game".

So, the players should be able to ratchet up their disagreement point and go "even if the next round of bargaining fails, at least we can promise that everyone does this well, right? Sure, everyone's going for their own idea of fairness, but even if Alice ends up with her worst ROSE point in the bargaining game, her utility is going to be at least this high, and similar for everyone else."

And so, each step of bargaining that successfully happens ratchets up the disagreement point closer to the Pareto frontier, in a way that should quickly converge. If someone disagrees on step 3, then the step-3 disagreement point gets played, which isn't that short of the Pareto frontier. And if someone doesn't have time for all this bargaining, they can just break things off at step 10 or something, that's just about as good as going all the way to infinity.

Or at least, it should work like this. I haven't proved that it does, and it depends on things like "what does ROSE bargaining look like for n players" and "does the random-dictator-point-dominance thing still hold in the n-player case" and "what's the analogue of that strategy where you block your foe from getting more than X utility, when there are multiple foes?". But this disagreement-point ratcheting is a strategy that address your worries with "ever-smaller pieces of the problem live on higher meta-levels, so the process of adding layers of meta actually converges to solving the problem, and breaking it off early solves most of the problem"

Regarding your last comment, yes, you could always just have a foe that's a jerk, but you can at least act so they don't gain from being an jerk, in a way robust against you and a foe having slightly different definitions of "jerk".

I think I have a contender for something which evades the conditional-threat issue stated at the end, as well as obvious variants and strengthenings of it, and which would be threat-resistant in a dramatically stronger sense than ROSE.

There's still a lot of things to check about it that I haven't done yet. And I'm unsure how to generalize to the n-player case. And it still feels unpleasantly hacky, according to my mathematical taste.

But the task at least feels possible, now.

EDIT: it turns out it was still susceptible to the conditional-threat issue, but then I thought for a while and came up with a different contender that feels a lot less hacky, and that provably evades the conditional-threat issue. Still lots of work left to be done on it, though.

For 1, it's just intrinsically mathematically appealing (continuity is always really nice when you can get it), and also because of an intution that if your foe experiences a tiny preference perturbation, you should be able to use small conditional payments to replicate their original preferences/incentive structure and start negotiating with that, instead.

I should also note that nowhere in the visual proof of the ROSE value for the toy case, is continuity used. Continuity just happens to appear.

For 2, yes, it's part of game setup. The buttons are of whatever intensity you want (but they have to be intensity-capped somewhere for technical reasons regarding compactness). Looking at the setup, for each player pair i,j, $D_{i,j}$ is the cap for how much of j's utility that i can destroy. These can vary, as long as they're nonnegative and not infinite. From this, it's clear "Alice has a powerful button, Bob has a weak one" is one of the possibilities, that would just mean $D_{a,b}>>D_{b,a}$. There isn't an assumption that everyone has an equally powerful button, because then you could argue that everyone just has an equal strength threat and then it wouldn't be much of a threat-resistance desideratum, now would it? Heck, you can even give one player a powerful button and the other a zero-strength button that has no effect, that fits in the formalism.

So the theorem is actually saying "for all members of the family of destruction games with the button caps set wherever the heck you want, the payoffs are the same as the original game".

My preferred way of resolving it is treating the process of "arguing over which equilibrium to move to" as a bargaining game, and just find a ROSE point from that bargaining game. If there's multiple ROSE points, well, fire up another round of bargaining. This repeated process should very rapidly have the disagreement points close in on the Pareto frontier, until everyone is just arguing over very tiny slices of utility.

This is imperfectly specified, though, because I'm not entirely sure what the disagreement points would be, because I'm not sure how the "don't let foes get more than what you think is fair" strategy generalizes to >2 players. Maaaybe disagreement-point-invariance comes in clutch here? If everyone agrees that an outcome as bad or worse than their least-preferred ROSE point would happen if they disagreed, then disagreement-point-invariance should come in to have everyone agree that it doesn't really matter exactly where that disagreement point is.

Or maybe there's some nice principled property that some equilibria have, which others don't, that lets us winnow down the field of equilibria somewhat. Maybe that could happen.

I'm still pretty unsure, but "iterate the bargaining process to argue over which equilibria to go to, you don't get an infinite regress because you rapidly home in on the Pareto frontier with each extra round you add" is my best bad idea for it.

EDIT: John Harsanyi had the same idea. He apparently had some example where there were multiple CoCo equilibria and his suggestion was that a second round of bargaining could be initiated over which equilibria to pick, but that in general, it'd be so hard to compute the n-person Pareto frontier for large n, that an equilibria might be stable because nobody can find a different equilibria nearby to aim for.

So this problem isn't unique to ROSE points in full generality (CoCo equilibria have the exact same issue), it's just that ROSE is the only one that produces multiple solutions for bargaining games, while CoCo only returns a single solution for bargaining games. (bargaining games are a subset of games in general)

So, if you are limited to only pure strategies, for some reason, then yes, Chinese would be on the Pareto frontier.
But if you can implement randomization, then Chinese is not on the Pareto frontier, because both sides agree that "flip a coin, Heads for Sushi, Tails for Italian" is just strictly better than Chinese.

The convex shape consists of all the payoff pairs you can get if you allow randomization.

Alright, this is kind of a Special Interest, so here's your relevant thought dump.

First up, the image is kind of misleading, in the sense that you can always tack on extra orders of magnitude. You could tack on another thousand orders of magnitude and make it look even longer, or just go "this is 900 OOM's of literally nothing happening, lets clip that off and focus on the interesting part"

Assuming proton decay is a thing (that free protons decay with a ridiculously long half-life)....

ok, I was planning on going "as a ludicrous upper bound, here's the number", but, uh, the completely ludicrous upper bound wound up being a WHOLE LOT longer than I thought. I... I didn't even think it was possible to stall till the evaporation of even a small black hole. But this calculation indicates that if you're aiming solely at living ludicrously long, you can stall about a googol years, enough for even the largest black holes to evaporate, and to get to the end of the black hole era. I'm gonna need to rethink some stuff.

EDIT: rethought some stuff, realized it doesn't change my conclusions from when I last looked into this. The fundamental problem is that, for any remotely realistic numbers, if you're trying to catch the final evaporation of a black hole to harvest its mass-energy, you'll blow a lot more than the amount of mass-energy that you could gain, in order to wait that long.

Final conclusion: If proton decay is a thing, it's definitely not worth waiting to the end of a black hole, you'll want to have things wrapped up far earlier. If proton decay isn't a thing, you'll want to wait till the black hole evaporates to catch that final party and last ${10}^{19}$ kg of mass-energy. If proton decay is a thing and you're willing to blow completely ridiculous cosmic amounts of resources on it, you can last till the late parts of the black hole era.

The rough rationale is as follows. Start with 10x the mass of the largest black holes in the universe, around ${10}^{12}$ solar masses stockpiled. If they're spinning fast enough, you can extract energy from them, assume you can extract all of it (it's over 10 percent, so let's round it up to 100 percent). Assume that proton decay is ${10}^{40}$ years (a high estimate), and that we use the energy at 100 percent efficiency to make matter (also high estimate), you can take out one proton, wait for around a proton decay time, take out the next proton, and so on. Then you can take out around ${10}^{69}$ protons, and each one lasts you around ${10}^{40}$ years, getting around ${10}^{109}$ years (high uncertainty). And, coincidentally, natural Hawing radiation finishes off the black hole of that size in ${10}^{103}$ years, leaving a small margin left over for silly considerations like "maybe the intelligence needs more than one proton to physically implement".

So, not remotely practical, but maybe something like ${10}^{80}$ years would actually be doable? That extra 29 OOM's of wiggle room patches over a lot of sins in this calculation.

But, in terms of what would actually be practical for the far future of humanity, it'd be the strat of "dump as much mass into a fast-spinning black hole as possible. Like, eat the entire Laniakea supercluster complex. Wait a trillion years for the cosmic microwave background radiation to cool to its floor temperature. You'd be in the late Stelliferous era at this point, with a few red dwarfs around, if you didn't dump all the stars in the mega-black-hole already. Set up some infrastructure around the mega-hole, and use the Blandford-Znajek mechanism to convert the mega-hole spin into electrical power. You should be able to get about a gigawatt of power for the next ${10}^{45}$ years to run a whole lotta computation and a little bit of maintanence, and if proton decay is messing with things, chop however many OOM's you need off the time and add those OOM's to the power output. Party for a trillion trillion trillion eons with your super-optimized low-temperature computing infrastructure"

Yeah, "transferrable utility games" are those where there is a resource, and the utilities of all players are linear in that resource (in order to redenominate everyone's utilities as being denominated in that resource modulo a shift factor). I believe the post mentioned this.

Task completed.

Agreed. The bargaining solution for the entire game can be very different from adding up the bargaining solutions for the subgames. If there's a subgame where Alice cares very much about victory in that subgame (interior decorating choices) and Bob doesn't care much, and another subgame where Bob cares very much about it (food choice) and Alice doesn't care much, then the bargaining solution of the entire relationship game will end up being something like "Alice and Bob get some relative weights on how important their preferences are, and in all the subgames, the weighted sum of their utilities is maximized. Thus, Alice will be given Alice-favoring outcomes in the subgames where she cares the most about winning, and Bob will be given Bob-favoring outcomes in the subgames where he cares the most about winning"

And in particular, since it's a sequential game, Alice can notice if Bob isn't being fair, and enforce the bargaining solution by going "if you're not aiming for something sorta like this, I'll break off the relationship". So, from Bob's point of view, aiming for any outcome that's too Bob-favoring has really low utility since Alice will inevitably catch on. (this is the time-extended version of "give up on achieving any outcome that drives the opponent below their BATNA") Basically, in terms of raw utility, it's still a bargaining game deep down, but once both sides take into account how the other will react, the payoff matrix for the restaurant game (taking the future interactions into account) will look like "it's a really bad idea to aim for an outcome the other party would regard as unfair"

Actually, they apply anyways in all circumstances, not just after the rescaling and shifting is done! Scale-and-shift invariance means that no matter how you stretch and shift the two axes, the bargaining solution always hits the same probability-distribution over outcomes,  so monotonicity means "if you increase the payoff numbers you assign for some or all of the outcomes, the Pareto frontier point you hit will give you an increased number for your utility score over what it'd be otherwise" (no matter how you scale-and-shift). And independence of irrelevant alternatives says "you can remove any option that you have 0 probability of taking and you'll still get the same probability-distribution over outcomes as you would in the original game" (no matter how you scale-and-shift)

If you're looking for curriculum materials, I believe that the most useful reference would probably be my "Infra-exercises", a sequence of posts containing all the math exercises you need to reinvent a good chunk of the theory yourself. Basically, it's the textbook's exercise section, and working through interesting math problems and proofs on one's own has a much better learning feedback loop and retention of material than slogging through the old posts. The exercises are short on motivation and philosophy compared to the posts, though, much like how a functional analysis textbook takes for granted that you want to learn functional analysis and doesn't bother motivating it.

The primary problem is that the exercises aren't particularly calibrated in terms of difficulty, and in order for me to get useful feedback, someone has to actually work through all of them, so feedback has been a bit sparse. So I'm stuck in a situation where I keep having to link everyone to the infra-exercises over and over and it'd be really good to just get them out and publicly available, but if they're as important as I think, then the best move is something like "release them one at a time and have a bunch of people work through them as a group" like the fixpoint exercises, instead of "just dump them all as public documents".

I'll ask around about speeding up the public - ation of the exercises and see what can be done there.

I'd strongly endorse linking this introduction even if the exercises are linked as well, because this introduction serves as the table of contents to all the other applicable posts.

So, if you make Nirvana infinite utility, yes, the fairness criterion becomes "if you're mispredicted, you have any probability at all of entering the situation where you're mispredicted" instead of "have a significant probability of entering the situation where you're mispredicted", so a lot more decision-theory problems can be captured if you take Nirvana as infinite utility. But, I talk in another post in this sequence (I think it was "the many faces of infra-beliefs") about why you want to do Nirvana as 1 utility instead of infinite utility.

Parfit's Hitchiker with a perfect predictor is a perfectly fine acausal decision problem, we can still represent it, it just cannot be represented as an infra-POMDP/causal decision problem.

Yes, the fairness criterion is tightly linked to the pseudocausality condition. Basically, the acausal->pseudocausal translation is the part where the accuracy of the translation might break down, and once you've got something in pseudocausal form, translating it to causal form from there by adding in Nirvana won't change the utilities much.

So, the flaw in your reasoning is after updating we're in the city, $e_2$ doesn't go "logically impossible, infinite utility". We just go "alright, off-history measure gets converted to 0 utility", a perfectly standard update. So $e_2$ updates to (0,0) (ie, there's 0 probability I'm in this situation in the first place, and my expected utility for not getting into this situation in the first place is 0, because of probably dying in the desert)

As for the proper way to do this analysis, it's a bit finicky. There's something called "acausal form", which is the fully general way of representing decision-theory problems. Basically, you just give an infrakernel $\Theta :\Pi \to \square (A\times O{)}^{\omega }$ that tells you your uncertainty over which history will result, for each of your policies.

So, you'd have 
$\Theta \left(\text{pay}\right)=(0.99{\delta }_{\text{alive,poor}}+0.01{\delta }_{\text{dead}},0)$
$\Theta \left(\text{nopay}\right)=(0.99{\delta }_{\text{dead}}+0.01{\delta }_{\text{alive,rich}},0)$
Ie, if you pay, 99 percent chance of ending up alive but paying and 1 percent chance of dying in the desert, if you don't pay, 99 percent chance of dying in the desert and 1 percent chance of cheating them, no extra utility juice on either one.

You update on the event "I'm alive". The off-event utility function is like "being dead would suck, 0 utility". So, your infrakernel updates to (leaving off the scale-and-shift factors, which doesn't affect anything)
$\Theta \left(\text{pay}\right)=(0.99{\delta }_{\text{alive,poor}},0)$
$\Theta \left(\text{nopay}\right)=(0.01{\delta }_{\text{alive,rich}},0)$
Because, the probability mass on "die in desert" got burned and turned into utility juice, 0 of it since it's the worst thing. Let's say your utility function assigns 0.5 utility to being alive and rich, and 0.4 utility to being alive and poor. So the utility of the first policy is $0.99\cdot 0.4=0.396$, and the utility of the second policy is $0.01\cdot 0.5=0.005$, so it returns the same answer of paying up. It's basically thinking "if I don't pay, I'm probably not in this situation in the first place, and the utility of "I'm not in this situation in the first place" is also about as low as possible."

BUT

There's a very mathematically natural way to translate any decision theory to "causal form", and as it turns out, the process which falls directly out of the math is that thing where you go "hard-code in all possible policies, go to Nirvana if I behave differently from the hard-coded policy". This has an advantage and a disadvantage. The advantage is that now your decision-theory problem is in the form of an infra-POMDP, a much more restrictive form, so you've got a much better shot at actually developing a practical algorithm for it. The disadvantage is that not all decision-theory problems survive the translation process unchanged. Speaking informally the "fairness criterion" to translate a decision-theory problem into causal form without too much loss in fidelity is something like "if I was mispredicted, would I actually have a good shot at entering the situation where I was mispredicted to prove the prediction wrong".

Counterfactual mugging fits this. If Omega flubs its prediction, you've got a 50 percent chance of being able to prove it wrong.
XOR blackmail fits this. If the blackmailer flubs its prediction and thinks you'll pay up, you've got like a 90 percent chance of being able to prove it wrong.
Newcomb's problem fits this. If Omega flubs its prediction and thinks you'll 2-box, you'll definitely be able to prove it wrong.

Transparent Newcomb and Parfait's Hitchiker don't fit this "fairness property" (especially for 100 percent accuracy), and so when you translate them to a causal problem, it ruins things. If the predictor screws up and thinks you'll 2-box on seeing a filled transparent box/won't pay up on seeing you got saved, then the transparent box is empty/you die in the desert, and you don't have a significant shot at proving them wrong.

Let's see what's going wrong. Our two a-environments are
$(\text{predicted to not pay, probably die in desert},0)$
$(\text{predicted to pay, probably survive},0)$

Update on the event "I didn't die in the desert". Then, neglecting scale-and-shift, our two a-environments are
$(0.01\text{in city, pay implies Nirvana},0)$
$(0.99\text{in city, no-pay implies Nirvana},0)$

Letting N be the utility of Nirvana,
If you pay up, then the expected utilities of these are $0.01\cdot N$ and $0.99\cdot 0.4$
If you don't pay up, then the expected utilities of these are $0.01\cdot 0.5$ and $0.99\cdot N$

Now, if N is something big like 100, then the worst-case utilities of the policies are 0.396 vs 0.005, as expected, and you pay up. But if N is something like 1, then the worst-case utilities of the policies are 0.01 vs 0.005, which... well, it technicallygets the right answer, but those numbers are suspiciously close to each other, the agent isn't thinking properly. And so, without too much extra effort tweaking the problem setup, it's possible to generate decision-theory problems where the agent just straight-up makes the wrong decision after changing things to the causal setting.
 

Omega and hypercomputational powers isn't needed, just decent enough prediction about what someone would do. I've seen Transparent Newcomb being run on someone before, at a math camp. They were predicted to not take the small extra payoff, and they didn't. And there was also an instance of acausal vote trading that I managed to pull off a few years ago, and I've put someone in a counterfactual mugging sort of scenario where I did pay out due to predicting they'd take the small loss in a nearby possible world. 2/3 of those instances were cases where I was specifically picking people that seemed unusually likely to take this sort of thing seriously, and it was predictable what they'd do.

I guess you figure out the entity is telling the truth in roughly the same way you'd figure out a human is telling the truth? Like "they did this a lot against other humans and their prediction record is accurate".

And no, I don't think that you'd be able to get from this mathematical framework to proving "a proof of benevolence is impossible". What the heck would that proof even look like?

The key piece that makes any Lobian proof tick is the "proof of X implies X" part. For Troll Bridge, X is "crossing implies bridge explodes".

For standard logical inductors, that Lobian implication holds because, if a proof of X showed up, every trader betting in favor of X would get free money, so there could be a trader that just names a really really big bet in favor of the X (it's proved, after all), the agent ends up believing X, and so doesn't cross, and so crossing implies bridge explodes.

For this particular variant of a logical inductor, there's an upper limit on the number of bets a trader is able to make, and this can possibly render the statement "if a proof of X showed up, the agent would believe X" false. And so, the key piece of the Lobian proof fails, and the agent happily crosses the bridge with no issue, because it would disbelieve a proof of bridge explosion if it saw it (and so the proof does not show up in the first place).

Said actions or lack thereof cause a fairly low utility differential compared to the actions in other, non-doomy hypotheses. Also I want to draw a critical distinction between "full knightian uncertainty over meteor presence or absence", where your analysis is correct, and "ordinary probabilistic uncertainty between a high-knightian-uncertainty hypotheses, and a low-knightian uncertainty one that says the meteor almost certainly won't happen" (where the meteor hypothesis will be ignored unless there's a meteor-inspired modification to what you do that's also very cheap in the "ordinary uncertainty" world, like calling your parents, because the meteor hypothesis is suppressed in decision-making by the low expected utility differentials, and we're maximin-ing expected utility)

Something analogous to what you are suggesting occurs. Specifically, let's say you assign 95% probability to the bandit game behaving as normal, and 5% to "oh no, anything could happen, including the meteor". As it turns out, this behaves similarly to the ordinary bandit game being guaranteed, as the "maybe meteor" hypothesis assigns all your possible actions a score of "you're dead" so it drops out of consideration.

The important aspect which a hypothesis needs, in order for you to ignore it, is that no matter what you do you get the same outcome, whether it be good or bad. A "meteor of bliss hits the earth and everything is awesome forever" hypothesis would also drop out of consideration because it doesn't really matter what you do in that scenario.

To be a wee bit more mathy, probabilistic mix of inframeasures works like this. We've got a probability distribution $\zeta \in \Delta N$, and a bunch of hypotheses ${\psi }_i\in \square X$, things that take functions as input, and return expectation values. So, your prior, your probabilistic mixture of hypotheses according to your probability distribution, would be the function

$f\mapsto {\sum }_{i\in N}\zeta \left(i\right)\cdot {\psi }_i\left(f\right)$

It gets very slightly more complicated when you're dealing with environments, instead of static probability distributions, but it's basically the same thing. And so, if you vary your actions/vary your choice of function f, and one of the hypotheses ${\psi }_i$ is assigning all these functions/choices of actions the same expectation value, then it can be ignored completely when you're trying to figure out the best function/choice of actions to plug in.

So, hypotheses that are like "you're doomed no matter what you do" drop out of consideration, an infra-Bayes agent will always focus on the remaining hypotheses that say that what it does matters.

Well, taking worst-case uncertainty is what infradistributions do. Did you have anything in mind that can be done with Knightian uncertainty besides taking the worst-case (or best-case)?

And if you were dealing with best-case uncertainty instead, then the corresponding analogue would be assuming that you go to hell if you're mispredicted (and then, since best-case things happen to you, the predictor must accurately predict you).

This post is still endorsed, it still feels like a continually fruitful line of research. A notable aspect of it is that, as time goes on, I keep finding more connections and crisper ways of viewing things which means that for many of the further linked posts about inframeasure theory, I think I could explain them from scratch better than the existing work does. One striking example is that the "Nirvana trick" stated in this intro (to encode nonstandard decision-theory problems), has transitioned from "weird hack that happens to work" to "pops straight out when you make all the math as elegant as possible". Accordingly, I'm working on a "living textbook" (like a textbook, but continually being updated with whatever cool new things we find) where I try to explain everything from scratch in the crispest way possible, to quickly catch up on the frontier of what we're working on. That's my current project.

I still do think that this is a large and tractable vein of research to work on, and the conclusion hasn't changed much.

Availability: Almost all times between 10 AM and PM, California time, regardless of day. Highly flexible hours. Text over voice is preferred, I'm easiest to reach on Discord. The LW Walled Garden can also be nice.

Amendment made.

A note to clarify for confused readers of the proof. We started out by assuming $\square (cross\to U=-10)$, and $cross$. We conclude $\square (cross\to U=10)\vee \square (cross\to U=0)$ by how the agent works. But the step from there to $\square \perp$ (ie, inconsistency of PA) isn't entirely spelled out in this post.

Pretty much, that follows from a proof by contradiction. Assume con(PA) ie $\neg \square \perp$, and it happens to be a con(PA) theorem that the agent can't prove in advance what it will do, ie, $\neg \square \left(\neg cross\right)$. (I can spell this out in more detail if anyone wants) However, combining $\square (cross\to U=-10)$ and $\square (cross\to U=10)$ (or the other option) gets you $\square \left(\neg cross\right)$, which, along with $\neg \square \left(\neg cross\right)$, gets you $\perp$. So PA isn't consistent, ie, $\square \perp$.

In the proof of Lemma 3, it should be 

"Finally, since ${\chi }_C^F(z,z)=z$, we have that ${\text{poly}}_C^F\left(z\right)\cdot {\text{poly}}_{B\setminus C}^F\left(z\right)=Q_z^F$.

Thus, $Q_z^F\cdot Q_{x\cap y\cap z}^F$ and $Q_{x\cap z}^F\cdot Q_{y\cap z}^F$ are both equal to ${\text{poly}}_C^F(x\cap z)\cdot {\text{poly}}_{B\setminus C}^F(y\cap z)\cdot {\text{poly}}_C^F\left(z\right)\cdot {\text{poly}}_{B\setminus C}^F\left(z\right)$.

instead.

Any idea of how well this would generalize to stuff like Chicken or games with more than 2-players, 2-moves?

I was subclinically depressed, acquired some bupropion from Canada, and it's been extremely worthwhile.

I don't know, we're hunting for it, relaxations of dynamic consistency would be extremely interesting if found, and I'll let you know if we turn up with anything nifty.

Looks good. 

Re: the dispute over normal bayesianism: For me, "environment" denotes "thingy that can freely interact with any policy in order to produce a probability distribution over histories". This is a different type signature than a probability distribution over histories, which doesn't have a degree of freedom corresponding to which policy you pick.

But for infra-bayes, we can associate a classical environment with the set of probability distributions over histories (for various possible choices of policy), and then the two distinct notions become the same sort of thing (set of probability distributions over histories, some of which can be made to be inconsistent by how you act), so you can compare them.

I'd say this is mostly accurate, but I'd amend number 3. There's still a sort of non-causal influence going on in pseudocausal problems, you can easily formalize counterfactual mugging and XOR blackmail as pseudocausal problems (you need acausal specifically for transparent newcomb, not vanilla newcomb). But it's specifically a sort of influence that's like "reality will adjust itself so contradictions don't happen, and there may be correlations between what happened in the past, or other branches, and what your action is now, so you can exploit this by acting to make bad outcomes inconsistent". It's purely action-based, in a way that manages to capture some but not all weird decision-theoretic scenarios.

In normal bayesianism, you do not have a pseudocausal-causal equivalence. Every ordinary environment is straight-up causal.

Re point 1, 2: Check this out. For the specific case of 0 to even bits, ??? to odd bits, I think solomonoff can probably get that, but not more general relations.

Re: point 3, Solomonoff is about stochastic environments that just take your action as an input, and aren't reading your policy. For infra-Bayes, you can deal with policy-dependent environments without issue, as you can consider hard-coding in every possible policy to get a family of stochastic environments, and UDT behavior naturally falls out as a result from this encoding. There's still some open work to be done on which sorts of policy-dependent environments like this are learnable (inferrable from observations), but it's pretty straightforward to cram all sorts of weird decision-theory scenarios in as infra-Bayes hypothesis, and do the right thing in them.

Ah. So, low expected utility alone isn't too much of a problem. The amount of weight a hypothesis has in a prior after updating depends on the gap between the best-case values and worst-case values. Ie, "how much does it matter what happens here". So, the stuff that withers in the prior as you update are the hypotheses that are like "what happens now has negligible impact on improving the worst-case". So, hypotheses that are like "you are screwed no matter what" just drop out completely, as if it doesn't matter what you do, you might as well pick actions that optimize the other hypotheses that aren't quite so despondent about the world.

In particular, if all the probability distributions in a set are like "this thing that just happened was improbable", the hypothesis takes a big hit in the posterior, as all the a-measures are like "ok, we're in a low-measure situation now, what happens after this point has negligible impact on utility". 

I still need to better understand how updating affects hypotheses which are a big set of probability distributions so there's always one probability distribution that's like "I correctly called it!".

The motivations for different g are: 

If g is your actual utility function, then updating with g as your off-event utility function grants you dynamic consistency. Past-you never regrets turning over the reins to future you, and you act just as UDT would.

If g is the constant-1 function, then that corresponds to updates where you don't care at all what happens off-history (the closest thing to normal updates), and both the "diagonalize against knowing your own action" behavior in decision theory and the Nirvana trick pops out for free from using this update.

"mixture of infradistributions" is just an infradistribution, much like how a mixture of probability distributions is a probability distribution.

Let's say we've got a prior $\zeta \in \Delta N$, a probability distribution over indexed hypotheses.

If you're working in a vector space, you can take any countable collection of sets in said vector space, and mix them together according to a prior $\zeta \in \Delta N$ giving a weight to each set. Just make the set of all points which can be made by the process "pick a point from each set, and mix the points together according to the probability distribution $\zeta$"

For infradistributions as sets of probability distributions or a-measures or whatever, that's a subset of a vector space. So you have a bunch of sets ${\Psi }_i$, and you just mix the sets together according to $\zeta$, that gives you your set ${\Psi }_{\zeta }$.

If you want to think about the mixture in the concave functional view, it's even nicer. You have a bunch of ${\psi }_i:(X\to R)\to R$ which are "hypothesis i can take a function and output what its worst-case expectation value is". The mixture of these, ${\psi }_{\zeta }$, is simply defined as ${\psi }_{\zeta }\left(f\right):=E_{i\sim \zeta }\left[{\psi }_i\right(f\left)\right]$. This is just mixing the functions together!

Both of these ways of thinking of mixtures of infradistributions are equivalent, and recover mixture of probability distributions as a special case.

The concave functional view is "the thing you do with a probability distribution is take expectations of functions with it. In fact, it's actually possible to identify a probability distribution with the function $(X\to R)\to R$ mapping a function to its expectation. Similarly, the thing we do with an infradistribution is taking expectations of functions with it. Let's just look at the behavior of the function $(X\to R)\to R$ we get, and neglect the view of everything as a set of a-measures."

As it turns out, this view makes proofs a whole lot cleaner and tidier, and you only need a few conditions on a function like that for it to have a corresponding set of a-measures.

Sounds like a special case of crisp infradistributions (ie, all partial probability distributions have a unique associated crisp infradistribution)

Given some $Q$, we can consider the (nonempty) set of probability distributions equal to $Q$ where $Q$ is defined. This set is convex (clearly, a mixture of two probability distributions which agree with $Q$ about the probability of an event will also agree with $Q$ about the probability of an event).

Convex (compact) sets of probability distributions = crisp infradistributions.

You're completely right that hypotheses with unconstrained Murphy get ignored because you're doomed no matter what you do, so you might as well optimize for just the other hypotheses where what you do matters. Your "-1,000,000 vs -999,999 is the same sort of problem as 0 vs 1" reasoning is good.

Again, you are making the serious mistake of trying to think about Murphy verbally, rather than thinking of Murphy as the personification of the "inf" part of the $E_{\Psi }\left[f\right]:={inf}_{(m,b)\in \Psi }m\left(f\right)+b$ definition of expected value, and writing actual equations. $\Psi$ is the available set of possibilities for a hypothesis. If you really want to, you can think of this as constraints on Murphy, and Murphy picking from available options, but it's highly encouraged to just work with the math.

For mixing hypotheses (several different ${\Psi }_i$ sets of possibilities) according to a prior distribution $\zeta \in \Delta N$, you can write it as an expectation functional via ${\psi }_{\zeta }\left(f\right):=E_{i\sim \zeta }\left[{\psi }_i\right(f\left)\right]$ (mix the expectation functionals of the component hypotheses according to your prior on hypotheses), or as a set via ${\Psi }_{\zeta }:=\left\{\right(m,b\left)|\exists \right(m_i,b_i)\in {\Psi }_i:E_{i\sim \zeta }(m_i,b_i)=(m,b\left)\right\}$ (the available possibilities for the mix of hypotheses are all of the form "pick a possibility from each hypothesis, mix them together according to your prior on hypotheses")

This is what I meant by "a constraint on Murphy is picked according to this probability distribution/prior, then Murphy chooses from the available options of the hypothesis they picked", that ${\Psi }_{\zeta }$ set (your mixture of hypotheses according to a prior) corresponds to selecting one of the ${\Psi }_i$ sets according to your prior $\zeta$, and then Murphy picking freely from the set ${\Psi }_i$.


Using ${\psi }_{\zeta }\left(f\right):=E_{i\sim \zeta }\left[{\psi }_i\right(f\left)\right]$ (and considering our choice of what to do affecting the choice of $f$, we're trying to pick the best function $f$) we can see that if the prior is composed of a bunch of "do this sequence of actions or bad things happen" hypotheses, the details of what you do sensitively depend on the probability distribution over hypotheses. Just like with AIXI, really.
Informal proof: if ${\psi }_i\left(f_i\right)\simeq 1$ and ${\psi }_i\left(f_j\right)\simeq 0$ (assuming $j\ne i$), then we can see that
${\psi }_{\zeta }\left(f_i\right)=E_{j\sim \zeta }\left[{\psi }_j\right(f_i\left)\right]={\sum }_{j\ne i}{\zeta }_j\cdot {\psi }_j\left(f_i\right)+{\zeta }_i\cdot {\psi }_i\left(f_i\right)\simeq {\zeta }_i$
and so, the best sequence of actions to do would be the one associated with the "you're doomed if you don't do blahblah action sequence" hypothesis with the highest prior. Much like AIXI does.


Using the same sort of thing, we can also see that if there's a maximally adversarial hypothesis in there somewhere that's just like "you get 0 reward, screw you" no matter what you do (let's say this is psi_0), then we have
${\psi }_{\zeta }\left(f_i\right)=E_{j\sim \zeta }\left[{\psi }_j\right(f_i\left)\right]={\sum }_{j\ge 1}{\zeta }_j\cdot {\psi }_j\left(f_i\right)+{\zeta }_0\cdot {\psi }_0\left(f_i\right)\simeq {\sum }_{j\ge 1}{\zeta }_j\cdot {\psi }_j\left(f_i\right)$
And so, that hypothesis drops out of the process of calculating the expected value, for all possible functions/actions. Just do a scale-and-shift, and you might as well be dealing with the prior $(\zeta |i\ne 0)$, which a-priori assumes you aren't in the "screw you, you lose" environment.


Hm, what about if you've just got two hypotheses, one where you're like "my knightian uncertainty scales with the amount of energy in the universe so if there's lots of energy available, things could e really bad, while if there's little energy available, Murphy can't make things bad" (${\psi }_0$) and one where reality behaves pretty much as you'd expect it to(${\psi }_1)$? And your two possible options would be "burn energy freely so Murphy can't use it" (the choice $f_0$, attaining a worst-case expected utility of $x_0$ in ${\psi }_0$ and $x_1$ in ${\psi }_1$), and "just try to make things good and don't worry about the environment being adversarial" (the choice $f_1$, attaining 0 utility in ${\psi }_0$, 1 utility in ${\psi }_1$).

The expected utility of $f_0$ (burn energy) would be ${\psi }_{\zeta }\left(f_0\right)={\zeta }_0\cdot {\psi }_0\left(f_0\right)+{\zeta }_1\cdot {\psi }_1\left(f_0\right)={\zeta }_0\cdot x_0+{\zeta }_1\cdot x_1$
And the expected utility of $f_1$(act normally) would be 
${\psi }_{\zeta }\left(f_1\right)={\zeta }_0\cdot {\psi }_0\left(f_1\right)+{\zeta }_1\cdot {\psi }_1\left(f_1\right)={\zeta }_0\cdot 0+{\zeta }_1\cdot 1={\zeta }_1$
So "act normally" wins if ${\zeta }_1\ge {\zeta }_0\cdot x_0+{\zeta }_1\cdot x_1$, which can be rearranged as ${\zeta }_1(1-x_1)\ge {\zeta }_0(x_0-0)$. Ie, you'll act normally if the probability of "things are normal" times the loss from burning energy when things are normal exceeds the probability of "Murphy's malice scales with amount of available energy" times the gain from burning energy in that universe.
So, assuming you assign a high enough probability to "things are normal" in your prior, you'll just act normally. Or, making the simplifying assumption that "burn energy" has similar expected utilities in both cases (ie, $x_1\simeq x_0$), then it would come down to questions like "is the utility of burning energy closer to the worst-case where Murphy has free reign, or the best-case where I can freely optimize?"
And this is assuming there's just two options, the actual strategy selected would probably be something like "act normally, if it looks like things are going to shit, start burning energy so it can't be used to optimize against me"

Note that, in particular, the hypothesis where the level of attainable badness scales with available energy is very different from the "screw you, you lose" hypothesis, since there are actions you can take that do better and worse in the "level of attainable badness scales with energy in the universe" hypothesis, while the "screw you, you lose" hypothesis just makes you lose. And both of these are very different from a "you lose if you don't take this exact sequence of actions" hypothesis. 

Murphy is not a physical being, it's a personification of an equation, thinking verbally about an actual Murphy doesn't help because you start confusing very different hypotheses, think purely about what the actual set of probability distributions ${\Psi }_i$ corresponding to hypothesis $i$ looks like. I can't stress this enough.

Also, remember, the goal is to maximize worst-case expected value, not worst-case value.

 

There's actually an upcoming post going into more detail on what the deal is with pseudocausal and acausal belief functions, among several other things, I can send you a draft if you want. "Belief Functions and Decision Theory" is a post that hasn't held up nearly as well to time as "Basic Inframeasure Theory".

If you use the Anti-Nirvana trick, your agent just goes "nothing matters at all, the foe will mispredict and I'll get -infinity reward" and rolls over and cries since all policies are optimal. Don't do that one, it's a bad idea.

For the concave expectation functionals: Well, there's another constraint or two, like monotonicity, but yeah, LF duality basically says that you can turn any (monotone) concave expectation functional into an inframeasure. Ie, all risk aversion can be interpreted as having radical uncertainty over some aspects of how the environment works and assuming you get worst-case outcomes from the parts you can't predict.

For your concrete example, that's why you have multiple hypotheses that are learnable. Sure, one of your hypotheses might have complete knightian uncertainty over the odd bits, but another hypothesis might not. Betting on the odd bits is advised by a more-informative hypothesis, for sufficiently good bets. And the policy selected by the agent would probably be something like "bet on the odd bits occasionally, and if I keep losing those bets, stop betting", as this wins in the hypothesis where some of the odd bits are predictable, and doesn't lose too much in the hypothesis where the odd bits are completely unpredictable and out to make you lose.

Maximin, actually. You're maximizing your worst-case result.

It's probably worth mentioning that "Murphy" isn't an actual foe where it makes sense to talk about destroying resources lest Murphy use them, it's just a personification of the fact that we have a set of options, any of which could be picked, and we want to get the highest lower bound on utility we can for that set of options, so we assume we're playing against an adversary with perfectly opposite utility function for intuition. For that last paragraph, translating it back out from the "Murphy" talk, it's "wouldn't it be good to use resources in order to guard against worst-case outcomes within the available set of possibilities?" and this is just ordinary risk aversion.

For that equation ${\text{argmax}}_{\pi }{inf}_{e\in B}{E}_{\pi \cdot e}\left[U\right]$, B can be any old set of probabilistic environments you want. You're not spending any resources or effort, a hypothesis just is a set of constraints/possibilities for what reality will do, a guess of the form "Murphy's operating under these constraints/must pick an option from this set."

You're completely right that for constraints like "environment must be a valid chess board", that's too loose of a constraint to produce interesting behavior, because Murphy is always capable of screwing you there.

This isn't too big of an issue in practice, because it's possible to mix together several infradistributions with a prior, which is like "a constraint on Murphy is picked according to this probability distribution/prior, then Murphy chooses from the available options of the hypothesis they picked". And as it turns out, you'll end up completely ignoring hypotheses where Murphy can screw you over no matter what you do. You'll choose your policy to do well in the hypotheses/scenarios where Murphy is more tightly constrained, and write the "you automatically lose" hypotheses off because it doesn't matter what you pick, you'll lose in those.

But there is a big unstudied problem of "what sorts of hypotheses are nicely behaved enough that you can converge to optimal behavior in them", that's on our agenda.

An example that might be an intuition pump, is that there's a very big difference between the hypothesis that is "Murphy can pick a coin of unknown bias at the start, and I have to win by predicting the coinflips accurately" and the hypothesis "Murphy can bias each coinflip individually, and I have to win by predicting the coinflips accurately". The important difference between those seems to be that past performance is indicative of future behavior in the first hypothesis and not in the second. For the first hypothesis, betting according to Laplace's law of succession would do well in the long run no matter what weighted coin Murphy picks, because you'll catch on pretty fast. For the second hypothesis, no strategy you can do can possibly help in that situation, because past performance isn't indicative of future behavior.

I found this Quanta magazine article about it which seems to indicate that it fits the CMB spectrum well but required a fair deal of fiddling with gravity to do so, but I lamentably lack the physics capabilities to evaluate the original paper.

If there's something wrong with some theory, isn't it quite odd that looking around at different parts of the universe seems to produce such a striking level of agreement on how much missing mass there is? If there was some out-of-left-field thing, I'd expect it to have confusing manifestations in many different areas and astronomers angsting about dramatically inconsistent measurements, I would not expect the CMB to end up explained away (and the error bars on those measurements are really really small) by the same 5:1 mix of non-baryonic matter vs baryonic matter the astronomers were postulating for everything else.

In other words, if you were starting out blind, the "something else will be found for a theory" bucket would not start out with most of its probability mass on "and in every respect, including the data that hasn't come in yet since it's the 1980's now, it's gonna look exactly like the invisible mass scenario". It's certainly not ruled out, but it has taken a bit of a beating.

Also, physics is not obligated to make things easy to find. Like how making a particle accelerator capable of reaching the GUT scale to test Grand Unified Theories takes a particle accelerator the size of a solar system.

Yes, pink is gas and purple is mass, but also the gas there makes up the dominant component of the visible mass in the Bullet Cluster, far outweighing the stars.

Also, physicists have come up with a whole lot of possible candidates for dark matter particles. The supersymmetry-based ones took a decent kicking at the LHC, and I'm unsure of the motivations for some of the other ones, but the two that look most promising (to me, others may differ in opinion) are axions and sterile neutrinos, as those were conjectured to plug holes in the Standard Model, so they've got a stronger physics motivation than the rest. But again, it might be something no physicist saw coming.

For axions, there's something in particle physics called the strong CP problem, where there's no theoretical reason whatsoever why strong-force interactions shouldn't break CP symmetry. And yet, as far as we can tell, the CP-symmetry-breakingness of the strong-force interaction is precisely zero. Axions were postulated as a way to deal with this, and for certain mass ranges, they would work. They'd be extremely light particles.

And for sterile neutrinos, there's a weird thing we've noticed where all the other quarks and leptons can have left-handed or right-handed chirality, but neutrinos only come in the left-handed form, nobody's ever found a right-handed neutrino. Also, in the vanilla Standard Model, neutrinos are supposed to be massless. And as it turns out, if you introduce some right-handed neutrinos and do a bit of physics fiddling, something called the seesaw mechanism shows up, which has the two effects of making ordinary neutrinos very light (and they are indeed thousands of times lighter than any other elementary particle with mass), and the right-handed neutrinos very heavy (so it's hard to make them at a particle accelerator). Also, since the weak interaction (the major way we know neutrinos are a thing) is sensitive to chirality, the right-handed neutrinos don't really do much of anything besides have gravity and have slight interactions with neutrinos, with are already hard to detect. So that's another possibility.

I'd go with number 2, because my snap reaction was "ooh, there's a "show personal blogposts" button?"

EDIT: Ok, I found the button. The problem with that button is that it looks identical to the other tags, and is at the right side of the screen when the structure of "Latest" draws your eyes to the left side of the screen. I'd make it a bit bigger and on the left side of the screen.

So, first off, I should probably say that a lot of the formalism overhead involved in this post in particular feels like the sort of thing that will get a whole lot more elegant as we work more things out, but "Basic inframeasure theory" still looks pretty good at this point and worth reading, and the basic results (ability to translate from pseudocausal to causal, dynamic consistency, capturing most of UDT, definition of learning) will still hold up.

Yes, your current understanding is correct, it's rebuilding probability theory in more generality to be suitable for RL in nonrealizable environments, and capturing a much broader range of decision-theoretic problems, as well as whatever spin-off applications may come from having the basic theory worked out, like our infradistribution logic stuff.

It copes with unrealizability because its hypotheses are not probability distributions, but sets of probability distributions (actually more general than that, but it's a good mental starting point), corresponding to properties that reality may have, without fully specifying everything. In particular, if an agent learns a class of belief functions (read: properties the environment may fulfill) is learned, this implies that for all properties within that class that the true environment fulfills (you don't know the true environment exactly), the infrabayes agent will match or exceed the expected utility lower bound that can be guaranteed if you know reality has that property (in the low-time-discount limit)

There's another key consideration which Vanessa was telling me to put in which I'll post in another comment once I fully work it out again.

Also, thank you for noticing that it took a lot of work to write all this up, the proofs took a while. n_n

So, we've also got an analogue of KL-divergence for crisp infradistributions. 

We'll be using $P$ and $Q$ for crisp infradistributions, and $p$ and $q$ for probability distributions associated with them. $D_{KL}$ will be used for the KL-divergence of infradistributions, and $d_{KL}$ will be used for the KL-divergence of probability distributions. For crisp infradistributions, the KL-divergence is defined as

$D_{KL}\left(P|Q\right):={max}_{q\in Q}{min}_{p\in P}{d}_{KL}\left(p|q\right)$

I'm not entirely sure why it's like this, but it has the basic properties you would expect of the KL-divergence, like concavity in both arguments and interacting well with continuous pushforwards and semidirect product.

Straight off the bat, we have:

Proposition 1: $D_{KL}\left(P|Q\right)\ge 0$

Proof: KL-divergence between probability distributions is always nonnegative, by Gibb's inequality.

Proposition 2: $D_{KL}\left(P|Q\right)=0\leftrightarrow Q\subseteq P$

$D_{KL}\left(P|Q\right)=0\leftrightarrow {max}_{q\in Q}{min}_{p\in P}{d}_{KL}\left(p|q\right)=0\leftrightarrow \forall q\in Q:{min}_{p\in P}{d}_{KL}\left(p|q\right)=0$

$\forall q\in Q:{min}_{p\in P}{d}_{KL}\left(p|q\right)=0\leftrightarrow \forall q\in Q\exists p\in P:d_{KL}\left(p|q\right)=0$

And now, because KL-divergence between probability distributions is 0 only when they're equal, we have:

$\forall q\in Q\exists p\in P:d_{KL}\left(p|q\right)=0\leftrightarrow \forall q\in Q:q\in P\leftrightarrow Q\subseteq P$

Proposition 3: If $u$ is the uniform distribution on $X$, then $D_{KL}\left(P|u\right)=\ln \left(|X|\right)-H\left(P\right)$

$D_{KL}\left(P|u\right)={min}_{p\in P}{d}_{KL}\left(p|u\right)={min}_{p\in P}\left(H\right(p,u)-H(p\left)\right)$

And the cross-entropy of any distribution with the uniform distribution is always $\ln \left(|X|\right)$, so:

$=\ln \left(|X|\right)+{min}_{p\in P}(-H(p\left)\right)=\ln \left(|X|\right)-{max}_{p\in P}H\left(p\right)=\ln \left(|X|\right)-H\left(P\right)$

Proposition 4: $D_{KL}$ is a concave function over $({\square }^{crisp}X{)}^2$.

Proof: Let's use $a$ as our number in $[0,1]$ in order to talk about mixtures. Then,

$D_{KL}(a{P}_1+(1-a)P_2|a{Q}_1+(1-a\left)Q_2\right)={max}_{q\in a{Q}_1+(1-a)Q_2}{min}_{p\in a{P}_1+(1-a)P_2}{d}_{KL}\left(p|q\right)$

$={max}_{q_1\in Q_1,q_2\in Q_2}{min}_{p_1\in P_1,p_2\in P_2}{d}_{KL}(a{p}_1+(1-a)p_2|a{q}_1+(1-a\left)q_2\right)$

Then we apply concavity of the KL-divergence for probability distributions to get:

$\le {max}_{q_1\in Q_1,q_2\in Q_2}{min}_{p_1\in P_1,p_2\in P_2}\left(a{d}_{KL}\right(p_1|q_1)+(1-a\left)d_{KL}\right(p_2|q_2\left)\right)$

$={max}_{q_1\in Q_1,q_2\in Q_2}\left(a{min}_{p_1\in P_1}{d}_{KL}\right(p_1|q_1)+(1-a\left){min}_{p_2\in P_2}{d}_{KL}\right(p_2|q_2\left)\right)$

$=a{max}_{q_1\in Q_1}{min}_{p_1\in P_1}{d}_{KL}\left(p_1|q_1\right)+(1-a){max}_{q_2\in Q_2}{min}_{p_2\in P_2}{d}_{KL}\left(p_2|q_2\right)$

$=a{D}_{KL}\left(P_1|Q_1\right)+(1-a)D_{KL}\left(P_2|Q_2\right)$

Proposition 5: $D_{KL}(P⋉K|Q⋉J)\ge D_{KL}\left(P|Q\right)+{min}_{p\in P}{E}_p[\lambda x.D_{KL}(K\left(x\right)|J\left(x\right)\left)\right]$

$D_{KL}(P⋉K|Q⋉J)={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}{d}_{KL}(p⋉k|q⋉j)$

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}{\sum }_{x,y}(p⋉k)(x,y)\cdot \ln \left(\frac{(p⋉k)(x,y)}{(q⋉j)(x,y)}\right)$

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}{\sum }_{x,y}p\left(x\right)\cdot k_x\left(y\right)\cdot \ln \left(\frac{p\left(x\right)\cdot k_x\left(y\right)}{q\left(x\right)\cdot j_x\left(y\right)}\right)$

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}{\sum }_{x,y}p\left(x\right)\cdot k_x\left(y\right)\cdot (\ln \left(\frac{p\left(x\right)}{q\left(x\right)}\right)+\ln \left(\frac{k_x\left(y\right)}{j_x\left(y\right)}\right))$

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}\left({\sum }_{x,y}p\right(x)\cdot k_x(y)\cdot \ln \left(\frac{p\left(x\right)}{q\left(x\right)}\right)+{\sum }_{x,y}p(x)\cdot k_x(y)\cdot \ln \left(\frac{k_x\left(y\right)}{j_x\left(y\right)}\right))$

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}(\left({\sum }_{x}p\right(x)\cdot \ln \left(\frac{p\left(x\right)}{q\left(x\right)}\right)\cdot \left({\sum }_y{k}_x\right(y\left)\right))$
$+\left({\sum }_{x}p\right(x)\cdot \left({\sum }_y{k}_x\right(y)\cdot \ln \left(\frac{k_x\left(y\right)}{j_x\left(y\right)}\right))))$

At this point we can abbreviate the KL-divergence, and observe that we have a multiplication by 1, to get:

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}\left(d_{KL}\right(p|q)+{\sum }_{x}p(x)\cdot d_{KL}(k_x|j_x\left)\right)$

And then pack up the expectation

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P,k\in {\prod }_{x}K\left(x\right)}\left(d_{KL}\right(p|q)+E_p[\lambda x.d_{KL}\left(k_x|j_x\right)\left]\right)$

Then, with the choice of $q$ and $j$ fixed, we can move the choice of the $k_x$ all the way inside, to get:

$={max}_{q\in Q,j\in {\prod }_{x}J\left(x\right)}{min}_{p\in P}\left(d_{KL}\right(p|q)+E_p[\lambda x.{min}_{k_x\in K\left(x\right)}{d}_{KL}\left(k_x|j_x\right)\left]\right)$

Now, there's something else we can notice. When choosing $j$, it doesn't matter what $p$ is selected, you want to take every $x$ and maximize the quantity inside the expectation, that consideration selects your $j_x$. So, then we can get:

$={max}_{q\in Q}{min}_{p\in P}\left(d_{KL}\right(p|q)+E_p[\lambda x.{max}_{j_x\in J\left(x\right)}{min}_{k_x\in K\left(x\right)}{d}_{KL}\left(k_x|j_x\right)\left]\right)$

And pack up the KL-divergence to get:

$={max}_{q\in Q}{min}_{p\in P}\left(d_{KL}\right(p|q)+E_p[\lambda x.D_{KL}\left(K\right(x\left)|J\right(x\left)\right)\left]\right)$

And distribute the min to get:

$\ge {max}_{q\in Q}\left({min}_{p\in P}{d}_{KL}\right(p|q)+{min}_{p\in P}{E}_p[\lambda x.D_{KL}\left(K\right(x\left)|J\right(x\left)\right)\left]\right)$

And then, we can pull out that fixed quantity and get:

$={max}_{q\in Q}{min}_{p\in P}{d}_{KL}\left(p|q\right)+{min}_{p\in P}{E}_p[\lambda x.D_{KL}(K\left(x\right)|J\left(x\right)\left)\right]$

And pack up the KL-divergence to get:

$=D_{KL}\left(P|Q\right)+{min}_{p\in P}{E}_p[\lambda x.D_{KL}(K\left(x\right)|J\left(x\right)\left)\right]$

Proposition 6: $D_{KL}(P_1\times P_2|Q_1\times Q_2)=D_{KL}\left(P_1|Q_1\right)+D_{KL}\left(P_2|Q_2\right)$

To do this, we'll go through the proof of proposition 5 to the first place where we have an inequality. The last step before inequality was:

$D_{KL}(P⋉K|Q⋉J)={max}_{q\in Q}{min}_{p\in P}\left(d_{KL}\right(p|q)+E_p[\lambda x.D_{KL}\left(K\right(x\left)|J\right(x\left)\right)\left]\right)$

Now, for a direct product, it's like semidirect product but all the $K\left(x\right)$ and $J\left(x\right)$ are the same infradistribution, so we have:

$D_{KL}(P_1\times P_2|Q_1\times Q_2)={max}_{q_1\in Q_1}{min}_{p_1\in P_1}\left(d_{KL}\right(p_1|q_1)+E_{p_1}[\lambda x.D_{KL}\left(P_2|Q_2\right)\left]\right)$

Now, this is a constant, so we can pull it out of the expectation to get:

$={max}_{q_1\in Q_1}{min}_{p_1\in P_1}\left(d_{KL}\right(p_1|q_1)+D_{KL}(P_2|Q_2\left)\right)$

$={max}_{q_1\in Q_1}{min}_{p_1\in P_1}{d}_{KL}\left(p_1|q_1\right)+D_{KL}\left(P_2|Q_2\right)=D_{KL}\left(P_1|Q_1\right)+D_{KL}\left(P_2|Q_2\right)$

Proposition 7: $D_{KL}\left(g_{\ast }\right(P\left)|g_{\ast }\right(Q\left)\right)\le D_{KL}\left(P|Q\right)$

For this, we'll need to use the Disintegration Theorem (the classical version for probability distributions), and adapt some results from Proposition 5. Let's show as much as we can before showing this.

$D_{KL}\left(g_{\ast }\right(P\left)|g_{\ast }\right(Q\left)\right)={max}_{q^{\prime }\in g_{\ast }\left(Q\right)}{min}_{p^{\prime }\in g_{\ast }\left(P\right)}{d}_{KL}\left(p^{\prime }|q^{\prime }\right)={max}_{q\in Q}{min}_{p\in P}{d}_{KL}\left(g_{\ast }\right(p\left)|g_{\ast }\right(q\left)\right)$

Now, hypothetically, if we had

$d_{KL}\left(g_{\ast }\right(p\left)|g_{\ast }\right(q\left)\right)\le d_{KL}\left(p|q\right)$

then we could use that result to get

$\le {max}_{q\in Q}{min}_{p\in P}{d}_{KL}\left(p|q\right)=D_{KL}\left(P|Q\right)$

and we'd be done. So, our task is to show

$d_{KL}\left(g_{\ast }\right(p\left)|g_{\ast }\right(q\left)\right)\le d_{KL}\left(p|q\right)$

for any pair of probability distributions $p$ and $q$. Now, here's what we'll do. The $p$ and $q$ gives us probability distributions over $X$, and the $g_{\ast }\left(p\right)$ and $g_{\ast }\left(q\right)$ are probability distributions over $Y$. So, let's take the joint distribution over $X\times Y$ given by selecting a point from $X$ according to the relevant distribution and applying $g$. By the classical version of the disintegration theorem, we can write it either way as starting with the marginal distribution over $X$ and a semidirect product to $Y$, or by starting with the marginal distribution over $Y$ and you take a semidirect product with some markov kernel to $X$ to get the joint distribution. So, we have:

$d_{KL}(p⋉g|q⋉g)=d_{KL}\left(g_{\ast }\right(p)⋉k|g_{\ast }(q)⋉j)$

for some Markov kernels $k,j:Y\to X$. Why? Well, the joint distribution over $X\times Y$ is given by $p⋉g$ or $q⋉g$ respectively (you have a starting distribution, and $g$ lets you take an input in $X$ and get an output in $Y$). But, breaking it down the other way, we start with the marginal distribution of those joint distributions on $Y$ (the pushforward w.r.t. $g$), and can write the joint distribution as semidirect product going the other way. Basically, it's just two different ways of writing the same distributions, so that's why KL-divergence doesn't vary at all.