Model-based RL In Contextual Decision Processes: PAC Bounds And Exponential Improvements Over Model-free Approaches
2018 · Wen Sun, Nan Jiang, Akshay Krishnamurthy, et al.
Abstract
We study the sample complexity of model-based reinforcement learning (henceforth RL) in general contextual decision processes that require strategic exploration to find a near-optimal policy. We design new algorithms for RL with a generic model class and analyze their statistical properties. Our algorithms have sample complexity governed by a new structural parameter called the witness rank, which we show to be small in several settings of interest, including factored MDPs. We also show that the witness rank is never larger than the recently proposed Bellman rank parameter governing the sample complexity of the model-free algorithm OLIVE (Jiang et al., 2017), the only other provably sample-efficient algorithm for global exploration at this level of generality. Focusing on the special case of factored MDPs, we prove an exponential lower bound for a general class of model-free approaches, including OLIVE, which, when combined with our algorithmic results, demonstrates exponential separat
Authors
(none)
Tags
Stats
Related papers
- Contextual Decision Processes With Low Bellman Rank Are Pac-learnable (2016)0.00
- When Simple Exploration Is Sample Efficient: Identifying Sufficient Conditions For Random Exploration To Yield PAC RL Algorithms (2018)0.00
- Improved Sample Complexity For Reward-free Reinforcement Learning Under Low-rank Mdps (2023)0.00
- PAC Bounds For Imitation And Model-based Batch Learning Of Contextual Markov Decision Processes (2020)0.00
- Reward-free RL Is No Harder Than Reward-aware RL In Linear Markov Decision Processes (2022)0.00
- On Oracle-efficient PAC RL With Rich Observations (2018)0.00
- Distributionally Robust Model-based Offline Reinforcement Learning With Near-optimal Sample Complexity (2022)0.00
- Model-free Reinforcement Learning: From Clipped Pseudo-regret To Sample Complexity (2020)0.00