liveBook · Manning

Relative complexity

As explained in Evolutionary Deep Learning: Genetic algorithms and neural networks

Relative complexity is a metric defined here as the size of the state space raised to the power of the action-space size.

Relative complexity estimates an environment’s combinatorial scale by raising the size of its state space to the power of its action-space size: |S|^|A|. It compares environments with continuous states and discrete actions. section 11.2

Mountain Car calculation

For a Mountain Car version with a state-space size of 2 and an action-space size of 3, relative complexity is 2^3 = 8. section 11.2

How Evolutionary Deep Learning: Genetic algorithms and neural networks covers it

How deep it goes
Defines the exponent formula and works one numerical example, stopping short of deriving a broader complexity theory.
Examples
Uses Gym environments including CartPole, Acrobot, CubeCrash, MountainCar, and LunarLander, plus a Mountain Car calculation.
What it assumes
Assumes familiarity with reinforcement-learning environments and state and action spaces while introducing the metric calculation directly.
What you can do after
Evaluate reinforcement-learning environments by inspecting their spaces and calculating a relative-complexity score.
How it connects
Connects environment complexity with state spaces, action spaces, reinforcement learning, deep reinforcement learning, Q-learning, and DQN.
Cover of Evolutionary Deep Learning: Genetic algorithms and neural networks
liveBookmanning.com
Read Evolutionary Deep Learning: Genetic algorithms and neural networks on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Evolutionary Deep Learning: Genetic algorithms and neural networks. The section links point to the parts of the book it draws on.