On notation for modal UDT

by Benya Fallenstein4 min read3rd Feb 2015No comments


Personal Blog

Patrick thinks that the notation I've been using for talking about modal UDT is too hard to read. I agree that it's annoying that after defining a decision problem and choosing a decision theory ---say, ---, I every time have to explicitly give separate names to the fixed points of the decision problem and the decision theory, for example by stating that are such that

In "Obstacle to modal optimality when you're being modalized", Patrick uses a pretty free-wheeling notation loosely inspired by the notation used in the modal agents paper. As Patrick notes in that post, I'm very much not sold on this notation. Partly, this is because various pieces of the notation don't seem very consistent to me. However, there's also a somewhat subtle problem with adopting notation that's too close to the modal agents paper, which I'm worried will lead to confusion; in this post, I'll explain that problem, and suggest some possible changes to modal UDT notation that might go part of the way towards the kind of notation Patrick prefers.

Comments appreciated!

Agents and universes

In the context of modal UDT, an agent is a sequence of formulas , such that the formula means that the agent takes action , and a universe is a sequence , where means that the universe returns the 'th-best outcome ( is best, is worst; this way, we can define modal UDT as looping over to ).

When we talk about modal agents, we write for the formula saying that agent cooperates when playing against agent . I wouldn't be averse to similarly writing, say, and for and , though I'm not sure whether we gain much from it. I wouldn't object too strongly to and , though it does look a bit ugly to me.

Orthogonally, I would be ok with naming actions and perhaps outcomes when this makes a decision problem easier to understand. For example, if an agent has to decide whether or not to press a certain button, I'd be happy to write that as . If we like, we can combine that with the above and write and , although the subscript notation feels pretty fine to me. I'm really not sold on using the symbol in the names of actions, though (e.g. ""), as Patrick's post does; that seems bound to lead to confusion with the use of as negation in the logic.

I think it's useful to be able to talk about the sequences of formulas explicitly, so I'm not excited about using subscripts to distinguish different sequences, as in Patrick's vs. , since then I don't know how to name the individual items of these sequences. Instead, I suggest using superscripts in parantheses, e.g. for the first universe and for the formula which says whether the first universe leads to outcome . I've used this convention occasionally in my previous posts.

This is basically bikeshedding, though. Let's move on to the more substantial issue.

Modal agents vs. modal decision theory

In the modal agents work, we use the notation to mean that cooperates when it plays against . On a formal level, each agent is represented by a one-variable formula in the language of arithmetic. To compute , we substitute the Gödel number of 's formula for the variable in 's formula, i.e., . If the resulting sentence is true, cooperates with , otherwise, it defects. Crucially, this means that can not only evaluate what will do against ; it can, for example, evaluate what would do against some other agent, such as or .

This is very different from the situation with modal decision problems and modal decision theories! A modal decision problem takes a parameterless agent, which picks a single action, and a modal decision theory takes a parameterless universe, which returns a single outcome. For example, the decision theory is never passed the source code of the decision problem, just of the universe that is the fixed point of the problem with the theory. If we think of decision problems and decision theories as formulas in the language of arithmetic, then they're again formulas with one free variable, but the free variable in the decision theory doesn't get instantiated to the Gödel number of the decision problem, it gets instantiated to the Gödel number of the universe which is the fixed point of decision theory and decision problem, and similarly for the free variable in the formula representing the decision problem.

This is important! If the decision theory was passed the decision problem, it could make its decision using physical counterfactuals: It could go, "Which utility does the decision problem assign to the agent ? To the agent ? The agent ? Ok, looks like gets the best payoff; I'll take action , thank you." On extensional decision problems, this procedure would perform optimally. (Extensional decision problems are problems where an agent's payoff only depends on the action the agent decides to take, not on the computation the agent uses to arrive at this decision.) But this "optimal" procedure doesn't solve the challenge we're interested in solving: How do you make decisions given that you're just an ordinary part of the universe, not a specially marked thing that can be swapped out for an alternative agent?

So I really don't think we should write or to denote the agent and universe that are the fixed point of a decision theory with a decision problem. This makes it look like we're substituting for the free variable(s) inside , which is not what we're doing.

Possible notations

Here's a suggestion that seems reasonable to me, if not perfect: Suppose that we write and for the agent and universe that result from combining the decision theory with the decision problem ; that is, for the solution of If we combine this with the earlier notation, we can then, e.g., write .

This is still pretty noisy, though. Another possibility would be to have some more syntaxy syntax for taking the fixed point of two sequences of formulas and ; perhaps define and to be sequences of formulas such that

Again, we could combine this with the previous notation to allow us to write, e.g., .

If we adopt that notation, I'd feel better about seeing a decision problem notationally just as "a universe with free variables" representing an agent's actions, and similarly a decision theory as "an agent with free variables" representing a universe (getting closer to the notation Patrick would like to use). The reason I'd be more sold on this now is that we wouldn't have to use separate letters for the no-variable agent and universe that result from taking the fixed point, we'd just write and , and . Again, and would represent sequences of formulas satisfying


Personal Blog