Learning Near Optimal Policies With Low Inherent Bellman Error

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(\sum_\{t=1\}^H d_t \sqrt\{K\} + \sum_\{t=1\}^H \sqrt\{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 statis

Stats

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

Related papers

• Provably Efficient Reward-agnostic Navigation With Linear Value Iteration (2020)0.00
• Improved Bounds For Reward-agnostic And Reward-free Exploration (2026)0.00
• The Uncertainty Bellman Equation And Exploration (2017)0.00
• Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes (2022)0.00
• Guarantees For Epsilon-greedy Reinforcement Learning With Function Approximation (2022)0.00
• \(\sqrt{n}\)-regret For Learning In Markov Decision Processes With Function Approximation And Low Bellman Rank (2019)0.00
• Minimax-optimal Reward-agnostic Exploration In Reinforcement Learning (2023)0.00
• Beyond Value-function Gaps: Improved Instance-dependent Regret Bounds For Episodic Reinforcement Learning (2021)0.00