Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration

Abstract

There has been growing progress on theoretical analyses for provably efficient learning in MDPs with linear function approximation, but much of the existing work has made strong assumptions to enable exploration by conventional exploration frameworks. Typically these assumptions are stronger than what is needed to find good solutions in the batch setting. In this work, we show how under a more standard notion of low inherent Bellman error, typically employed in least-square value iteration-style algorithms, we can provide strong PAC guarantees on learning a near optimal value function provided that the linear space is sufficiently "explorable". We present a computationally tractable algorithm for the reward-free setting and show how it can be used to learn a near optimal policy for any (linear) reward function, which is revealed only once learning has completed. If this reward function is also estimated from the samples gathered during pure exploration, our results also provide same-order PAC guarantees on the performance of the resulting policy for this setting.

arXiv commentMinor update; appears in NeurIPS

References in corpus (16)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Provably Efficient Maximum Entropy Exploration
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Provably efficient RL with Rich Observations via Latent State Decoding
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Fast active learning for pure exploration in reinforcement learning
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Reward-Free Exploration for Reinforcement Learning
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Adaptive Reward-Free Exploration

Cited by in corpus (9)

• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• A Simple Reward-free Approach to Constrained Reinforcement Learning
• On the Theory of Reinforcement Learning with Once-per-Episode Feedback
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Improved Algorithms for Misspecified Linear Markov Decision Processes