Contextual Decision Processes With Low Bellman Rank Are Pac-learnable

Abstract

This paper studies systematic exploration for reinforcement learning with rich observations and function approximation. We introduce a new model called contextual decision processes, that unifies and generalizes most prior settings. Our first contribution is a complexity measure, the Bellman rank, that we show enables tractable learning of near-optimal behavior in these processes and is naturally small for many well-studied reinforcement learning settings. Our second contribution is a new reinforcement learning algorithm that engages in systematic exploration to learn contextual decision processes with low Bellman rank. Our algorithm provably learns near-optimal behavior with a number of samples that is polynomial in all relevant parameters but independent of the number of unique observations. The approach uses Bellman error minimization with optimistic exploration and provides new insights into efficient exploration for reinforcement learning with function approximation.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyjiang2016contextual

Related papers

• Model-based RL In Contextual Decision Processes: PAC Bounds And Exponential Improvements Over Model-free Approaches (2018)0.00
• PAC Bounds For Imitation And Model-based Batch Learning Of Contextual Markov Decision Processes (2020)0.00
• No-regret Exploration In Contextual Reinforcement Learning (2019)0.00
• Efficient PAC Reinforcement Learning In Regular Decision Processes (2021)2.26
• Learning Near Optimal Policies With Low Inherent Bellman Error (2020)0.00
• Deep Exploration With Pac-bayes (2024)0.00
• Markov Decision Processes With Continuous Side Information (2017)0.00
• Beyond No Regret: Instance-dependent PAC Reinforcement Learning (2021)0.00