The Asymptotic Cost of Complexity

2024/08/27 by Martin W. Cripps, Cripps, Martin W
Computer Science · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Economics and business #Information Theory (cs.IT) #Theoretical Economics (econ.TH)

paper · pdf · doi:10.48550/arxiv.2408.14949

openalex publication_date 2024/08/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose a measure of learning efficiency for non-finite state spaces. We characterize the complexity of a learning problem by the metric entropy of its state space. We then describe how learning efficiency is determined by this measure of complexity. This is, then, applied to two models where agents learn high-dimensional states.

Related

• The Information Complexity of Learning Tasks, their Structure and their\n Distance
• Theoretical bound of the efficiency of learning with coarse-graining
• Theoretical bound of the efficiency of learning
• Learning Capacity: A Measure of the Effective Dimensionality of a Model
• The complexity of non-stationary reinforcement learning