4 ms·

Yes you can, but said representations will necessarily be misleading. It's illuminating to consider Big-O notations: why don't we "simplify", since real numbers

by xamuel 6y ago

Yes you can, but said representations will necessarily be misleading. It's illuminating to consider Big-O notations: why don't we "simplify", since real numbers are so much easier, why don't we declare, e.g., that O(n) is "1", O(n^2) is "2", etc.? Well, then what should O(2^n) be? A million, perhaps? But then what about O(n^1000000)? To be consistent, you'd have to say O(n^1000000) was something below a million, since that complexity level is below O(2^n). And then whatever you chose for that, that would constrain you to pack O(n^billion), O(n^trillion), etc., into smaller and smaller ranges of possible numbers. You'd inevitably be forced to eventually assign almost identical numbers to, say, O(n^(2^100)) and O(n^(2^999)), which is misleading because those are not at all close to each other in complexity.

lostmsu 6y ago
I don't see how representation of floats by natural numbers that we all use on daily basis is misleading. In fact, your entire comment is just an ordered sequence of natural numbers, and it does not seem to be very misleading (though it tried to trick). Besides, the article is purposed to be a rigorous mathematical proof of current representations in RL being unsuitable for AGI, but I haven't seen a Definition for "misleading" there.
- sebastos 6y ago
  ?? Current reinforcement learning algorithms don't score an action by producing a line of text that is read by a human. It assigns a value by writing a floating point number into a register on the computer somewhere. If it were otherwise, and there was some kind of interpretation unit that was needed to compare two rewards and decide which one was bigger, then hey, you're not using the reals for your rewards anymore, just like the paper suggested you'd have to.
  - lostmsu 6y ago
    In that interpretation the article basically says "you can't precisely optimize function F in domain X with by optimizing function F' in domain Y, when cardinality of Y < cardinality of X". Well, obviously! That is basically the definition of cardinality!
    - xamuel 6y ago
      The argument in the paper has nothing to do with cardinality. Review my comment a few steps above about Big-O. The reasoning there shows the real numbers, despite having cardinality of the continuum, are inadequate for measuring even the following countable set of Big-O complexity classes: O(2^n) together with O(n),O(n^2),...,O(n^i),... Is there something special about intelligence that implies we only need to consider RL-environments with real-valued rewards, and not, say, big-O-complexity-class rewards? Maybe there is. But if there is, the proof will have to be nontrivial---at a bare minimum, it should make some reference to what the reals are (e.g., the unique complete ordered field). This would be quite world-shattering, to real analysts if to no-one else. But none of the RL literature seems to make any reference to what the reals actually are, instead just taking it for granted that the reals are a magical number system as flexible as anybody could ever want. (Other authors essentially pointed this out before I did; see footnote 10 in my paper.)
      - lostmsu 6y ago
        I re-read your Big-O comment, and it still does not make sense. The fact, that mapping all n^i to arctan(i) and i^n to arctan(i) + pi is somehow "misleading" is not making it theoretically impossible for RL algorithms from finding an optimal solution in that metric. If for a specific instance you're saying n^1e300 is wrong because it is impractical, and 2^n would be preferred, you simply posed the original task incorrectly by asking for a wrong metric.
        xamuel 6y ago
        It's not about whether the agent will or will not find an optimal solution (no agent can possibly find good solutions in every environment). It's about whether the agent could even understand the true environment based on your real-value-reward description of it. Suppose the true environment has various tasks the agent can do which give big-O-complexity-valued rewards, one task giving a reward of O(2^n), and others giving rewards of O(n^i) for various i. For concreteness, say Task A rewards O(2^n), Task B rewards O(n^10000), and Task C rewards O(n^20000). Now suppose you present this to the agent using real-valued rewards, say, where O(n^i) is replaced by arctan(i) and O(2^n) is replaced by arctan(2)+pi, as you suggest, then the agent will be deluded into thinking, e.g., that Task B and Task C give almost identical rewards (Task B gives reward 1.57069633 and Task C gives reward 1.57074633, which barely differ from each other at all). This is misleading because in the true environment, Task C gives much more reward than Task B. Yes, the agent understands Task C gives a bigger reward, but the agent totally mis-understands how much bigger :)
- drdeca 6y ago
  misleading in the sense of "doesn't preserve the desired properties of closeness and such."

by xamuel 6y ago

lostmsu 6y ago

I don't see how representation of floats by natural numbers that we all use on daily basis is misleading. In fact, your entire comment is just an ordered sequence of natural numbers, and it does not seem to be very misleading (though it tried to trick). Besides, the article is purposed to be a rigorous mathematical proof of current representations in RL being unsuitable for AGI, but I haven't seen a Definition for "misleading" there.

sebastos 6y ago
?? Current reinforcement learning algorithms don't score an action by producing a line of text that is read by a human. It assigns a value by writing a floating point number into a register on the computer somewhere. If it were otherwise, and there was some kind of interpretation unit that was needed to compare two rewards and decide which one was bigger, then hey, you're not using the reals for your rewards anymore, just like the paper suggested you'd have to.
- lostmsu 6y ago
  In that interpretation the article basically says "you can't precisely optimize function F in domain X with by optimizing function F' in domain Y, when cardinality of Y < cardinality of X". Well, obviously! That is basically the definition of cardinality!
  - xamuel 6y ago
    The argument in the paper has nothing to do with cardinality. Review my comment a few steps above about Big-O. The reasoning there shows the real numbers, despite having cardinality of the continuum, are inadequate for measuring even the following countable set of Big-O complexity classes: O(2^n) together with O(n),O(n^2),...,O(n^i),... Is there something special about intelligence that implies we only need to consider RL-environments with real-valued rewards, and not, say, big-O-complexity-class rewards? Maybe there is. But if there is, the proof will have to be nontrivial---at a bare minimum, it should make some reference to what the reals are (e.g., the unique complete ordered field). This would be quite world-shattering, to real analysts if to no-one else. But none of the RL literature seems to make any reference to what the reals actually are, instead just taking it for granted that the reals are a magical number system as flexible as anybody could ever want. (Other authors essentially pointed this out before I did; see footnote 10 in my paper.)
    - lostmsu 6y ago
      I re-read your Big-O comment, and it still does not make sense. The fact, that mapping all n^i to arctan(i) and i^n to arctan(i) + pi is somehow "misleading" is not making it theoretically impossible for RL algorithms from finding an optimal solution in that metric. If for a specific instance you're saying n^1e300 is wrong because it is impractical, and 2^n would be preferred, you simply posed the original task incorrectly by asking for a wrong metric.
      - xamuel 6y ago
        It's not about whether the agent will or will not find an optimal solution (no agent can possibly find good solutions in every environment). It's about whether the agent could even understand the true environment based on your real-value-reward description of it. Suppose the true environment has various tasks the agent can do which give big-O-complexity-valued rewards, one task giving a reward of O(2^n), and others giving rewards of O(n^i) for various i. For concreteness, say Task A rewards O(2^n), Task B rewards O(n^10000), and Task C rewards O(n^20000). Now suppose you present this to the agent using real-valued rewards, say, where O(n^i) is replaced by arctan(i) and O(2^n) is replaced by arctan(2)+pi, as you suggest, then the agent will be deluded into thinking, e.g., that Task B and Task C give almost identical rewards (Task B gives reward 1.57069633 and Task C gives reward 1.57074633, which barely differ from each other at all). This is misleading because in the true environment, Task C gives much more reward than Task B. Yes, the agent understands Task C gives a bigger reward, but the agent totally mis-understands how much bigger :)
drdeca 6y ago
misleading in the sense of "doesn't preserve the desired properties of closeness and such."