Complexity distribution of agent policies
This work provides a theoretical framework for understanding environment complexity in agent-based systems, but it is incremental as it builds on existing concepts in a minimalistic setting.
The paper analyzes environment complexity by examining the distribution of policy complexities needed for high performance, introducing concepts like environment response curves and applying them to elementary cellular automata to show variations in difficulty and discriminating power.
We analyse the complexity of environments according to the policies that need to be used to achieve high performance. The performance results for a population of policies leads to a distribution that is examined in terms of policy complexity and analysed through several diagrams and indicators. The notion of environment response curve is also introduced, by inverting the performance results into an ability scale. We apply all these concepts, diagrams and indicators to a minimalistic environment class, agent-populated elementary cellular automata, showing how the difficulty, discriminating power and ranges (previous to normalisation) may vary for several environments.