Contextual Decision Processes with Low Bellman Rank are PAC-Learnable

2016/10/29 by Nan Jiang, Akshay Krishnamurthy, Jiang, Nan +7 · 20 citations
Computer Science · Engineering · #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Fault Detection and Control Systems #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Neural Networks and Applications

paper · pdf · doi:10.48550/arxiv.1610.09512

openalex publication_date 2016/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Online Robust Reinforcement Learning with General Function Approximation
• To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learning
• Expert or not? assessing data quality in offline reinforcement learning
• ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertainty
• Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learning
• Offline Reinforcement Learning in Large State Spaces: Algorithms and Guarantees
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable\n Optimal Action-Value Functions
• Linear Dynamics meets Linear MDPs: Closed-Form Optimal Policies via Reinforcement Learning
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Feature-Based Q-Learning for Two-Player Stochastic Games
• Outcome-based Exploration for LLM Reasoning
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Minimax Weight and Q-Function Learning for Off-Policy Evaluation
• Sample-Optimal Parametric Q-Learning Using Linearly Additive Features
• Representation Learning for Online and Offline RL in Low-rank MDPs
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function\n Approximation

Related

• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• PAC Reinforcement Learning with Rich Observations
• Efficient PAC Reinforcement Learning in Regular Decision Processes
• A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning
• Learning Near Optimal Policies with Low Inherent Bellman Error