Learning Near Optimal Policies with Low Inherent Bellman Error

2020/02/29 by Andrea Zanette, Zanette, Andrea, Alessandro Lazaric +5 · 13 citations
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Reinforcement Learning in Robotics #Smart Grid Energy Management

paper · pdf · doi:10.48550/arxiv.2003.00153

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

Abstract

We study the exploration problem with approximate linear action-value functions in episodic reinforcement learning under the notion of low inherent Bellman error, a condition normally employed to show convergence of approximate value iteration. First we relate this condition to other common frameworks and show that it is strictly more general than the low rank (or linear) MDP assumption of prior work. Second we provide an algorithm with a high probability regret bound \widetilde O(∑_t=1^H d_t √(K) + ∑_t=1^H √(d_t) \IBE K) where H is the horizon, K is the number of episodes, \IBE is the value if the inherent Bellman error and d_t is the feature dimension at timestep t. In addition, we show that the result is unimprovable beyond constants and logs by showing a matching lower bound. This has two important consequences: 1) it shows that exploration is possible using only batch assumptions with an algorithm that achieves the optimal statistical rate for the setting we consider, which is more general than prior work on low-rank MDPs 2) the lack of closedness (measured by the inherent Bellman error) is only amplified by √(d_t) despite working in the online setting. Finally, the algorithm reduces to the celebrated LinUCB when H=1 but with a different choice of the exploration parameter that allows handling misspecified contextual linear bandits. While computational tractability questions remain open for the MDP setting, this enriches the class of MDPs with a linear representation for the action-value function where statistically efficient reinforcement learning is possible.

Citations

• Model-Based Reinforcement Learning with a Generative Model is Minimax\n Optimal
• Provably Efficient Reinforcement Learning with Linear Function Approximation

Cited by

• Online Robust Reinforcement Learning with General Function Approximation
• FIRM: Federated In-client Regularized Multi-objective Alignment for Large Language Models
• Model Selection in Contextual Stochastic Bandit Problems
• Regret Bound Balancing and Elimination for Model Selection in Bandits\n and RL
• Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear q^π-Realizability and Concentrability
• Logarithmic Regret for Reinforcement Learning with Linear Function\n Approximation
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal\n Algorithm Escaping the Curse of Horizon
• Linear Dynamics meets Linear MDPs: Closed-Form Optimal Policies via Reinforcement Learning
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory
• Efficient Learning in Non-Stationary Linear Markov Decision Processes
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function\n Approximation

Related

• The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation
• Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation
• Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions
• Learning with Good Feature Representations in Bandits and in RL with a Generative Model
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration