PAC Reinforcement Learning With an Imperfect Model
By Nan Jiang. 2018
25 citations recorded by the source corpus.
Reinforcement learning (RL) methods have proved to be successful in many simulated environments. The common approaches, however, are often too sample intensive to be applied directly in the real world. A promising approach to addressing this issue is to train an RL agent in a simulator and transfer the solution to the real environment. When a high-fidelity simulator is available we would expect significant reduction in the amount of real trajectories needed for learning. In this work we aim at better understanding the theoretical nature of this approach. We start with a perhaps surprising result that, even if the approximate model (e.g., a simulator) only differs from the real environment in a single state-action pair (but which one is unknown), such a model could be information-theoretically useless and the sample complexity (in terms of real trajectories) still scales with the total number of states in the worst case. We investigate the hard instances and come up with natural conditions that avoid the pathological situations. We then propose two conceptually simple algorithms that enjoy polynomial sample complexity guarantees with no dependence on the size of the state-action space, and prove some foundational results to provide insights into this important problem.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Sergey Levine
- Aravind Rajeswaran
- Praneeth Netrapalli
- Rahul Kidambi
- Chelsea Finn
- Doina Precup
- Thorsten Joachims
- Khimya Khetarpal
In Computational Theory and Mathematics
- Gheorghe Comanici
- David Abel
- Khimya Khetarpal
- Doina Precup
- Thorsten Joachims
- Praneeth Netrapalli
- Rahul Kidambi
- Aravind Rajeswaran
In Management Science and Operations Research
- Aravind Rajeswaran
- Thorsten Joachims
- Praneeth Netrapalli
- Rahul Kidambi
- Doina Precup
- David Abel
- Gheorghe Comanici
- Khimya Khetarpal
Citations in the corpus
- MOReL : Model-Based Offline Reinforcement Learning (2020, background): “Similar ideas have been explored in related settings like online RL [58, 59] and imitation learning [60].”
- What can I do here? A Theory of Affordances in Reinforcement Learning (2020, methodology): “(Jiang, 2018) Given any M1 and M2, and any set F of value functions containing V ∗ M1 (i.”