On Representation Complexity of Model-based and Model-free Reinforcement Learning

arXiv:2310.01706v2 Announce Type: replace
Abstract: We study the representation complexity of model-based and model-free reinforcement learning (RL) in the context of circuit complexity. We prove theoretically that there exists a broad class of MDPs such that their underlying transition and reward functions can be represented by constant depth circuits with polynomial size, while the optimal $Q$-function suffers an exponential circuit complexity in constant-depth circuits. By drawing attention to the approximation errors and building connections to complexity theory, our theory provides …

abstract arxiv class complexity context cs.lg free functions polynomial prove reinforcement reinforcement learning representation study transition type