Computational limitations in Artificial Intelligence algorithms
(2025)
Files
ThesisBrieucPinon.pdf
Open Access - Adobe PDF
- 1.17 MB
Details
- Authors
- Supervisors
- Abstract
- This thesis investigates fundamental limitations and potential opportunities of learning-based Artificial Intelligence algorithms. A contribution is the comparison of sample efficiency between expressive Deep Learning architectures close to Turing-complete systems of computation, to simpler architectures stacking linear operators and non-linear activation functions. We conclude that a detailed characterization of potential gains is tightly linked to open problems in Computational Complexity, but that an assumption from derandomization research entails a clear advantage to expressive architectures. Additionally, we study empirically the relevance of the Transformer architecture and online planning in meta-Reinforcement Learning. Our numerical results suggest that an architecture like the Transformer is useful to model partially observable problem dynamics arising in meta-Reinforcement Learning. Moreover, extensive planning is crucial to handle the exploration and exploitation of the unknown dynamics. This work also analyzes the interplay between learning and algorithms for problem-solving. We formalize computational limitations through counterexamples for multiple classical algorithms in Reinforcement Learning, such as algorithms treating the model of the dynamics as a black-box and universal value function estimating state-to-state reachability. These fundamental limitations open the possibility of designing more efficient algorithms leveraging Machine Learning for problem-solving.
- Affiliations
UCLouvain SST/ICTM/INMA - Pôle en ingénierie mathématique
Citations
Pinon, B. (2025). Computational limitations in Artificial Intelligence algorithms. https://hdl.handle.net/2078.5/256533