liveBook · Manning

Curse of dimensionality

As explained in Applied Reinforcement Learning

The curse of dimensionality is the rapid growth of computational complexity as the number of dimensions or tracked variables increases.

As the number of dimensions or tracked variables grows, the possible states can multiply until storing or iterating over them becomes impractical. Dynamic programming faces this when it must process every state. section 4.5 section 2.2

Resource allocation

A budget of 12 across four projects produces 1,053 states. Increasing the budget to 100 and the projects to 10 produces nearly six million states, making enumeration far more demanding. section 4.5

Tracking every previously visited state can also make predicting what comes next computationally overwhelming. The Markov property offers a shortcut by avoiding dependence on the full history. section 2.2

Figure 2.2 Conditional probability of dependency of next state to all previous states.

Illustrates how a next-state prediction can depend on all previously visited states. section 2.2

How Applied Reinforcement Learning covers it

How deep it goes
Explains the computational intuition and gives state-count examples, without deriving the growth mathematically.
Examples
Uses resource-allocation state counts and prediction based on all previously visited states.
What you can do after
Understand why enumerating states or tracking long histories can become computationally impractical.
How it connects
Connects the problem to dynamic programming, the Markov property, and Markov chains.

Also explained in

Compare how 10 books explain curse of dimensionality →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Applied Reinforcement Learning. The section links point to the parts of the book it draws on.