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-or

Stats

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

Related papers

• Learning Near Optimal Policies With Low Inherent Bellman Error (2020)0.00
• Reward-free Model-based Reinforcement Learning With Linear Function Approximation (2021)0.00
• Improved Bounds For Reward-agnostic And Reward-free Exploration (2026)0.00
• Optimal Horizon-free Reward-free Exploration For Linear Mixture Mdps (2023)0.00
• Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes (2022)0.00
• Minimax-optimal Reward-agnostic Exploration In Reinforcement Learning (2023)0.00
• Nonstationary Reinforcement Learning With Linear Function Approximation (2020)0.00
• Provably Efficient Reinforcement Learning With Linear Function Approximation (2019)11.76