This is a linkpost for https://nibnalin.me/dust-nib/bellmans-curse-of-dimensionality.html
In dynamic programming and reinforcement learning, the most fundamental challenge we face is just grokking the high dimensionality of a state space. Go is a "simple" game whose rules can be fully explained on a single sheet of paper, yet those rules yield more board configurations than the number of atoms in the universe (). Given the state space, how does any solver for this game even represent these configurations, let alone evaluate them? While games are helpful toys to start with, this phenomenon of “exponential explosion” in systems is extremely common in many real-world problems, where we’ve given it the stage name: Bellman’s Curse of Dimensionality.
While... (read 815 more words →)