On Representation Complexity of Model-based and Model-free Reinforcement Learning
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 unique insights into why model-based algorithms usually enjoy better sample complexity than model-free algorithms from a novel representation complexity perspective: in some cases, the ground-truth rule (model) of the environment is simple to represent, while other quantities, such as $Q$-function, appear complex. We empirically corroborate our theory by comparing the approximation error of the transition kernel, reward function, and optimal $Q$-function in various Mujoco environments, which demonstrates that the approximation errors of the transition kernel and reward function are consistently lower than those of the optimal $Q$-function. To the best of our knowledge, this work is the first to study the circuit complexity of RL, which also provides a rigorous framework for future research.
Code (0)
등록된 구현이 없습니다.
Tasks
modelMuJoCoreinforcement-learningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs
In reward-free reinforcement learning (RL), an agent explores the environment first without any reward information, in order to achieve certain learning goals afterwards for any given reward. In this paper we focus on re…
reinforcement-learningReinforcement Learning (RL)Representation LearningContinuous Deep Q-Learning with Model-based Acceleration
Model-free reinforcement learning has been successfully applied to a range of challenging problems, and has recently been extended to handle large neural network policies and value functions. However, the sample complexi…
continuous-controlContinuous ControlDeep Reinforcement LearningQ-Learning+3On Reward-Free Reinforcement Learning with Linear Function Approximation
Reward-free reinforcement learning (RL) is a framework which is suitable for both the batch RL setting and the setting where there are many reward functions of interest. During the exploration phase, an agent collects sa…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)LIMT: Language-Informed Multi-Task Visual World Models
Most recent successes in robot reinforcement learning involve learning a specialized single-task agent. However, robots capable of performing multiple tasks can be much more valuable in real-world applications. Multi-tas…
Multi-Task Learningreinforcement-learningReinforcement LearningRethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity
Reinforcement Learning (RL) encompasses diverse paradigms, including model-based RL, policy-based RL, and value-based RL, each tailored to approximate the model, optimal policy, and optimal value function, respectively. …
Reinforcement Learning (RL)