Online RL In Linearly \(q^\pi\)-realizable Mdps Is As Easy As In Linear Mdps If You Learn What To Ignore

Abstract

We consider online reinforcement learning (RL) in episodic Markov decision processes (MDPs) under the linear \(q^\pi\)-realizability assumption, where it is assumed that the action-values of all policies can be expressed as linear functions of state-action features. This class is known to be more general than linear MDPs, where the transition kernel and the reward function are assumed to be linear functions of the feature vectors. As our first contribution, we show that the difference between the two classes is the presence of states in linearly \(q^\pi\)-realizable MDPs where for any policy, all the actions have approximately equal values, and skipping over these states by following an arbitrarily fixed policy in those states transforms the problem to a linear MDP. Based on this observation, we derive a novel (computationally inefficient) learning algorithm for linearly \(q^\pi\)-realizable MDPs that simultaneously learns what states should be skipped over and runs another learning al

Stats

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

Related papers

• Sample-efficient Reinforcement Learning Is Feasible For Linearly Realizable Mdps With Limited Revisiting (2021)0.00
• Confident Natural Policy Gradient For Local Planning In \(q_\pi\)-realizable Constrained Mdps (2024)0.00
• Trajectory Data Suffices For Statistically Efficient Learning In Offline RL With Linear \(q^\pi\)-realizability And Concentrability (2024)0.00
• Online Target Q-learning With Reverse Experience Replay: Efficiently Finding The Optimal Policy For Linear Mdps (2021)0.00
• Sample And Oracle Efficient Reinforcement Learning For Mdps With Linearly-realizable Value Functions (2024)0.00
• Reward-free Model-based Reinforcement Learning With Linear Function Approximation (2021)0.00
• Online Reinforcement Learning In Markov Decision Process Using Linear Programming (2023)3.58
• Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes (2022)0.00