|
|
|
|
|
by JoshCole
1460 days ago
|
|
Take the simplest problem of searching over a continuous range between zero and one exhaustively. Let the value you search for be 0.1. By a diagnolization argument we can realize that even a search carried on for an infinite amount of time and granted an infinite amount of space would not terminate. After all, to find 0.1 you need to make it past 0.01. But to reach that you have to reach 0.001. And so on. Let abstraction map from N to 1 over this space. As N goes up, abstraction error goes up, but the problem is no longer impossible because the diagnolization proof no longer holds. Let b be a branching factor in a game. As b goes to infinity, the game graph becomes continuous. In learning formulations under the game theoretic school of thought you have to search the game graph to get the average of your policies proportional to your counterfactual regret. That implies walking the continuous game graph. In reinforcement learning the bellman equations give you your values. This is also defined in terms of the game graph. So again we fall prey to the problem. We've shown that walking continuous things is impossible even under conditions that are ideal - infinite speed and memory and we've shown that this relates to the learning problem formulations I spoke of. Obviously this only gets worse when we impose reality - we don't actually have infinite space on our computers. They don't compute for an infinite amount of time either. But notice that before we searched for infinite space and time and we failed? When we move down to finite space and finite time we still have the property of completing after full enumeration. We have a finite amount of computing capacity. We have a finite amount of computational storage. Yet the growth rate for unabstracted game trees is exponential. Let c be our constraints. An abstracted game maps n states to one state. So it has log_n(X) where X is your state count. An abstracted game has X states. Since log_n(x) < X we know there exist terminating algorithms for abstraction that are not terminating for unabstracted because log_n(x) < X when X = c. So we get log_n(X) < c when X = c. This is actually much less than the real world gains. Since in learning we get the policy expectations multiple times over the game graph and the convergence guarantees relate to the complexity of the graph you get a much more worthwhile window than just the difference of log_n(X) versus X. For much tighter bounds check out game theory research. They get error bounds on the abstraction error too by choosing clustering solutions with provable properties. So it really has a much stronger formal treatment than you might imagine. |
|
One abstraction that is very useful is linear algebra which is an abstraction without errors. Same goes for category theory. Grothendiecks work wasn't about tolerating errors in abstractions either. Simple abstractions like generic containers are also not about ignoring errors.
Honestly, the random segues to diagonalization arguments, game theory, continuous functions, RL and Bellman equations(WTF!) sound like stream of conciousness random ramblings and an attempt at "out jargoning", much less a "formal proof". Reminds me of this story by Tadelis.
https://thecorrespondent.com/100/the-new-dot-com-bubble-is-h...
"We use Lagrange multipliers," one of them said. And for a second, Tadelis was astounded. What? Lagrange multipliers? But Lagrange multipliers don’t have anything to do with ..."Then it hit me," Tadelis recalled. "This guy is trying to out-jargon me!"