curse of dimensionality (in RL)

Dynamic programming is exact, but it stores and updates one number per state — and the number of states explodes as you add variables. A gridworld with ten cells is trivial; track ten independent things, each taking ten values, and you already face ten billion states. This combinatorial blow-up, where adding one dimension multiplies the work, is the curse of dimensionality, and the main reason tabular DP does not scale.

If the state is described by d features, each with k possible values, the state space has k to the power d entries — exponential in d. A full DP sweep must touch them all, so both memory and computation become impossible well before realistic problems. This is exactly why modern RL replaces lookup tables with function approximation, such as neural networks, that generalise across states, and why sampling replaces exhaustive sweeps.