Attention Conservation Notice: This is a moderately mathy post.

Affineness, it's Useful!

So, if we're going to be restricting the sorts of environments we're considering, and trying to build an algorithm that's closer to UDT1.0 (just pick your action to optimize global utility without the whole "coordinating with alternate versions of me" aspect), it's probably worthwhile to consider what sorts of environments naturally work well with UDT1.0. What sorts of environments/games let you craft a notion of "the effect that a single player is having" in a way that doesn't really depend on what everyone else is doing?

If we've got some global high-dimensional maximization problem, ${max}_{x, y, z} f (x, y, z)$ , what sorts of functions let you split it into a bunch of little low-dimensional maximization problems that don't interact? Well, if $f$ is a sum of a bunch of other functions which only depend on a single input, then something like ${max}_{x, y, z} (f_{1} (x) + f_{2} (y) + f_{3} (z))$ splits up as ${max}_{x} f_{1} (x) + {max}_{y} f_{2} (y) + {max}_{z} f_{3} (z)$ .

If we've got some game with a bunch of players, what sort of game lets you consider the plays of the players individually without worrying about interactions between the actions of the various different players? Linear games. If $A_{i}$ is the space of player i's actions, then a game in general would have every player $i$ be associated with a utility function $U_{i} : (\prod_{j} A_{j}) \to [0, 1]$ . But in linear games, everyone's utility function $U_{i}$ breaks down as a weighted sum of component utility functions $U_{i, j} : A_{j} \to [0, 1]$ , which could be viewed as "how much player $i$ likes or dislikes the action that player $j$ took". No interaction between the different actions. How much player $i$ approves of $j$ 's action has nothing to do with the actions that everyone else is taking. I actually have a whole ton to say about linear games, they're incredibly interesting, but that's probably a matter for another post that isn't a part of this sequence.

So what's the analogue of this "split stuff into a weighted sum" thing for policy selection environments? Well, permitting probabilistic choice of actions, if $O^{< n}$ is the space of histories of length less-than-n (places where we can make a decision), and our action space is $A$ , and we're playing up to a time horizon of $n$ , then the space of policies is.. $\prod := O^{< n} \to Δ A$ And, from the previous post, a policy-selection environment (in full generality) is one where there's a function $O^{<}$ ...

UDT1.01