Weird. I didn’t expect this to be wrong and I did not expect the other one to be right. Glad I asked.
“Minimal number of character it takes to implement this game in python” would be small because the “game code” part is the laws and the reward.
Not so sure about that. The game has to describe and model “everything” about the situation. So if you want to describe interaction with details of a “real world” then you also need a complete simulation of said real world.
While everything is “contained” in the reward function, it is not like the reward function can be computed independently of “what happens” in the game.
It is however true that you only need to compute the most minimal version of the game relevant to the outcome. So if your game contains a lot of “pointless” rules that do nothing then they can be safely ignored when computing the complexity of the game. I think that’s normal.
In the case of the real world, even restricting it to a bounded precision, the program would need to be very long. It is not just a description of the sentence “you win if there are a lot of diamonds in the world” (or whatever the goal is). It is also a complete “simulation” of the world.
and it would be difficult to write a non-dominated strategy which tries to be non-dominated just by not accruing that much energy overall and instead moving a lot of energy at some time step. Yet it’s probably possible [...]
Depending on the exact parameter, an intuitive strategy that is not dominated but not optimal long terms either could be “never invest anything”, in which you value the present so much that you never move because that would cost energy.
Remark that this strategy is still “a” utility maximisation (just value each step more than the next to a high amount). But it is very bad for the utility you described.
But this kind of trick becomes more difficult if I restrict the number of branches you can make in the preferences tree; it’s possible to be non-dominated “just” because you have many non-comparable branches and it suffices to do OK on just one branch. As I restrict the number of branches, you’ll have to do better overall.
I still get the feeling that your notion of preference tree is not equivalent to my own concept of a partial order on the set of outcomes. Could you clarify?
I think simulating the real world requires a lot of memory and computations, not a large program. (Not that I know the program.) Komogorov complexity does not put restrictions on the computations. Think about Conway’s game of life.
Depending on the exact parameter, an intuitive strategy that is not dominated but not optimal long terms either could be “never invest anything”
It’s not obvious to me that “do nothing” is not dominated. Even if an active agent didn’t start pumping energy right away in the designated region to work on some master plan instead, the energy in the region would, if the active agent is somewhere else, be the same as if the agent was the null agent, until the active agent started doing something. Then, if the active agent never passes through some small phase were energy is pumped out of the region for some reason, it dominates the null agent.
You seem to interpret that in my example the energy “in the battery of the agent” counts, such that not moving can’t be dominated. I said “energy accumulated in some region of the universe” to avoid this kind of thing. Anyway, the point of the example is not showing a completely general property, but to point at things which have the property, so I expect you to fix yourself counter-specifications that make the example fail, unless of course you thought the example was very broken.
I still get the feeling that your notion of preference tree is not equivalent to my own concept of a partial order on the set of outcomes. Could you clarify?
Sorry, my choice of expression is confusing. I was thinking about a directed acyclic graph representing the order in my mind, and called that “tree”, but indeed the standard definition of tree is acyclic without orientation, so the skeleton of a DAG does not qualify in general. A minimal representation total order would be a chain, while a partial order has to contain “parallel branches”.
You seem to interpret that in my example the energy “in the battery of the agent” counts, such that not moving can’t be dominated. I said “energy accumulated in some region of the universe” to avoid this kind of thing. Anyway, the point of the example is not showing a completely general property, but to point at things which have the property, so I expect you to fix yourself counter-specifications that make the example fail, unless of course you thought the example was very broken.
Sure. I agree counterexamples that rely on a small specification flaw are not relevant to your point.
I don’t know if that class of examples works.
My intuition is somewhat that there will be nondominated strategies that are not utility maximization “by default” on that sort of games. At least if we only look at utilities that are weighted sums of the energy at various points in time.
On the whole and in general, it is still not intuitive to me whether utility maximization become ubiquitous when the “complexity” ratio you defines goes down.
Sorry for only answering now, I was quite busy in the last few days.
I think simulating the real world requires a lot of memory and computations, not a large program. (Not that I know the program.) Komogorov complexity does not put restrictions on the computations. Think about Conway’s game of life.
You also need a specification of the initial state, which dramatically increases the size of the program!
Because the formalism only requires turing machines (or any equivalent computation formalism), there is no distinction between the representation of the “rules” and the rest of the necessary data.
So even if the rules of physics themselves are very simple (like in the game of life), the program that simulates the world is very big. It probably requires something like “position of every atom at step t”.
Sorry, my choice of expression is confusing. I was thinking about a directed acyclic graph representing the order in my mind, and called that “tree”, but indeed the standard definition of tree is acyclic without orientation, so the skeleton of a DAG does not qualify in general. A minimal representation total order would be a chain, while a partial order has to contain “parallel branches”.
Ok thank you. I will keep reading “order relation” for those.
You also need a specification of the initial state, which dramatically increases the size of the program! Because the formalism only requires turing machines (or any equivalent computation formalism), there is no distinction between the representation of the “rules” and the rest of the necessary data. So even if the rules of physics themselves are very simple (like in the game of life), the program that simulates the world is very big. It probably requires something like “position of every atom at step t
The initial conditions can be simple. Do you expect that the real universe requires very specific boundary conditions?
In the game of life it is necessary to set up specific initial configurations for something interesting to happen, but the configurations can be computed with a program much smaller than the number of cells to set (e.g., repetitive patterns). It is not necessary to explicitly lay out the values of all the cells.
Let’s put aside the distiction between initial conditions and rules, I think it is just a distraction at this point.
In general I would even expect a complete simulation of the univers to be non-computable. Ie I expect that the univers contains an infinite amount of information.
If we bound the problem to some finite part of time and space then I expect, just as an intuition, that a complete simulation would require a lot of information. Ie, the minimal turing machine / python code that consistently outputs the same result as the simulation for each input is very long.
I do not have a good number to give that translates this intuition of “very long”.
Let’s say that simulating the earth during the last 10 days would take multiple millions of terrabits of data?
Of course the problem is underspecified. We also need to specify what the legal inputs are.
Weird. I didn’t expect this to be wrong and I did not expect the other one to be right. Glad I asked.
Not so sure about that. The game has to describe and model “everything” about the situation. So if you want to describe interaction with details of a “real world” then you also need a complete simulation of said real world. While everything is “contained” in the reward function, it is not like the reward function can be computed independently of “what happens” in the game. It is however true that you only need to compute the most minimal version of the game relevant to the outcome. So if your game contains a lot of “pointless” rules that do nothing then they can be safely ignored when computing the complexity of the game. I think that’s normal.
In the case of the real world, even restricting it to a bounded precision, the program would need to be very long. It is not just a description of the sentence “you win if there are a lot of diamonds in the world” (or whatever the goal is). It is also a complete “simulation” of the world.
Btw, the notion I was alluding to is Kolmogorov complexity.
Depending on the exact parameter, an intuitive strategy that is not dominated but not optimal long terms either could be “never invest anything”, in which you value the present so much that you never move because that would cost energy. Remark that this strategy is still “a” utility maximisation (just value each step more than the next to a high amount). But it is very bad for the utility you described.
I still get the feeling that your notion of preference tree is not equivalent to my own concept of a partial order on the set of outcomes. Could you clarify?
I think simulating the real world requires a lot of memory and computations, not a large program. (Not that I know the program.) Komogorov complexity does not put restrictions on the computations. Think about Conway’s game of life.
It’s not obvious to me that “do nothing” is not dominated. Even if an active agent didn’t start pumping energy right away in the designated region to work on some master plan instead, the energy in the region would, if the active agent is somewhere else, be the same as if the agent was the null agent, until the active agent started doing something. Then, if the active agent never passes through some small phase were energy is pumped out of the region for some reason, it dominates the null agent.
You seem to interpret that in my example the energy “in the battery of the agent” counts, such that not moving can’t be dominated. I said “energy accumulated in some region of the universe” to avoid this kind of thing. Anyway, the point of the example is not showing a completely general property, but to point at things which have the property, so I expect you to fix yourself counter-specifications that make the example fail, unless of course you thought the example was very broken.
Sorry, my choice of expression is confusing. I was thinking about a directed acyclic graph representing the order in my mind, and called that “tree”, but indeed the standard definition of tree is acyclic without orientation, so the skeleton of a DAG does not qualify in general. A minimal representation total order would be a chain, while a partial order has to contain “parallel branches”.
Sure. I agree counterexamples that rely on a small specification flaw are not relevant to your point.
I don’t know if that class of examples works. My intuition is somewhat that there will be nondominated strategies that are not utility maximization “by default” on that sort of games. At least if we only look at utilities that are weighted sums of the energy at various points in time.
On the whole and in general, it is still not intuitive to me whether utility maximization become ubiquitous when the “complexity” ratio you defines goes down.
Sorry for only answering now, I was quite busy in the last few days.
You also need a specification of the initial state, which dramatically increases the size of the program! Because the formalism only requires turing machines (or any equivalent computation formalism), there is no distinction between the representation of the “rules” and the rest of the necessary data. So even if the rules of physics themselves are very simple (like in the game of life), the program that simulates the world is very big. It probably requires something like “position of every atom at step t”.
Ok thank you. I will keep reading “order relation” for those.
The initial conditions can be simple. Do you expect that the real universe requires very specific boundary conditions?
In the game of life it is necessary to set up specific initial configurations for something interesting to happen, but the configurations can be computed with a program much smaller than the number of cells to set (e.g., repetitive patterns). It is not necessary to explicitly lay out the values of all the cells.
Let’s put aside the distiction between initial conditions and rules, I think it is just a distraction at this point.
In general I would even expect a complete simulation of the univers to be non-computable. Ie I expect that the univers contains an infinite amount of information. If we bound the problem to some finite part of time and space then I expect, just as an intuition, that a complete simulation would require a lot of information. Ie, the minimal turing machine / python code that consistently outputs the same result as the simulation for each input is very long.
I do not have a good number to give that translates this intuition of “very long”. Let’s say that simulating the earth during the last 10 days would take multiple millions of terrabits of data? Of course the problem is underspecified. We also need to specify what the legal inputs are.
Anyway, do you agree with this intuition?
I think that simulating a specific slice of spacetime is more kolmogorov-complex that simulating the entire universe.