Provably Efficient Reinforcement Learning with Linear Function Approximation

Abstract

Modern Reinforcement Learning (RL) is commonly applied to practical problems with an enormous number of states, where function approximation must be deployed to approximate either the value function or the policy. The introduction of function approximation raises a fundamental set of challenges involving computational and statistical efficiency, especially given the need to manage the exploration/exploitation tradeoff. As a result, a core RL question remains open: how can we design provably efficient RL algorithms that incorporate function approximation? This question persists even in a basic setting with linear dynamics and linear rewards, for which only linear function approximation is needed. This paper presents the first provable RL algorithm with both polynomial runtime and polynomial sample complexity in this linear setting, without requiring a "simulator" or additional assumptions. Concretely, we prove that an optimistic modification of Least-Squares Value Iteration (LSVI)---a classical algorithm frequently studied in the linear setting---achieves $\tilde{\mathcal{O}}(\sqrt{d^3{H}^{3}T})$ regret, where $d$ is the ambient dimension of feature space, $H$ is the length of each episode, and $T$ is the total number of steps. Importantly, such regret is independent of the number of states and actions.

Cited by in corpus (150)

• Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domain
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Rule-Based Reinforcement Learning for Efficient Robot Navigation with Space Reduction
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Understanding Domain Randomization for Sim-to-real Transfer
• Naive Exploration is Optimal for Online LQR
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Batch Value-function Approximation with Only Realizability
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Is Pessimism Provably Efficient for Offline RL?
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Model Selection in Contextual Stochastic Bandit Problems
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Accuracy-Efficiency Trade-Offs and Accountability in Distributed ML Systems
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Corruption-robust exploration in episodic reinforcement learning
• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
• Provably Efficient Exploration in Policy Optimization
• $Q$-learning with Logarithmic Regret
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Bellman-consistent Pessimism for Offline Reinforcement Learning
• Adaptive Discretization in Online Reinforcement Learning
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Constrained episodic reinforcement learning in concave-convex and knapsack settings
• Provably Efficient Causal Reinforcement Learning with Confounded Observational Data
• Nonstationary Reinforcement Learning with Linear Function Approximation
• Dynamic Bottleneck for Robust Self-Supervised Exploration
• Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency
• Tactical Optimism and Pessimism for Deep Reinforcement Learning
• Robust Reinforcement Learning using Least Squares Policy Iteration with Provable Performance Guarantees
• Regret Bound Balancing and Elimination for Model Selection in Bandits and RL
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• MADE: Exploration via Maximizing Deviation from Explored Regions
• V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL
• Model-free Representation Learning and Exploration in Low-rank MDPs
• Dynamic Regret of Policy Optimization in Non-stationary Environments
• Provably Efficient Reinforcement Learning with Aggregated States
• Robust Policy Gradient against Strong Data Corruption
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
• Online learning in MDPs with linear function approximation and bandit feedback
• Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles
• Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret
• Com-DDPG: A Multiagent Reinforcement Learning-based Offloading Strategy for Mobile Edge Computing
• Adaptive Discretization for Model-Based Reinforcement Learning
• Efficient Planning in Large MDPs with Weak Linear Function Approximation
• No-regret Exploration in Contextual Reinforcement Learning
• Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning
• Conservative Exploration in Reinforcement Learning
• Adaptive Approximate Policy Iteration
• Zap Q-Learning With Nonlinear Function Approximation
• Leveraging Good Representations in Linear Contextual Bandits
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Online Learning for Unknown Partially Observable MDPs
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Accountable Off-Policy Evaluation With Kernel Bellman Statistics
• Corruption-Robust Offline Reinforcement Learning
• Principled Exploration via Optimistic Bootstrapping and Backward Induction
• Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• On the Approximation of Cooperative Heterogeneous Multi-Agent Reinforcement Learning (MARL) using Mean Field Control (MFC)
• Reinforcement Learning with Function Approximation: From Linear to Nonlinear
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Efficient Learning in Non-Stationary Linear Markov Decision Processes
• A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• Causal Markov Decision Processes: Learning Good Interventions Efficiently
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing
• On the Power of Multitask Representation Learning in Linear MDP
• A Simple Reward-free Approach to Constrained Reinforcement Learning
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Representation Learning for Online and Offline RL in Low-rank MDPs
• Minimax Regret for Stochastic Shortest Path
• Uncertainty-aware transfer across tasks using hybrid model-based successor feature reinforcement learning
• Breaking the Deadly Triad with a Target Network
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
• Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximation
• Linear Representation Meta-Reinforcement Learning for Instant Adaptation
• Towards General Function Approximation in Zero-Sum Markov Games
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL
• Learning Good State and Action Representations via Tensor Decomposition
• Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
• Fast Rates for the Regret of Offline Reinforcement Learning
• On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function
• Generative Adversarial Imitation Learning with Neural Networks: Global Optimality and Convergence Rate
• $\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank
• Dimension-Free Rates for Natural Policy Gradient in Multi-Agent Reinforcement Learning
• Online Model Selection for Reinforcement Learning with Function Approximation
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Online Sparse Reinforcement Learning
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis
• Towards a Dimension-Free Understanding of Adaptive Linear Control
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Efficient Local Planning with Linear Function Approximation
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Learning Stochastic Shortest Path with Linear Function Approximation
• A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning
• Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge
• Safe Reinforcement Learning with Linear Function Approximation
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
• Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses
• Provably Correct Optimization and Exploration with Non-linear Policies
• Explaining Off-Policy Actor-Critic From A Bias-Variance Perspective
• Reinforcement Learning with Feedback Graphs
• PerSim: Data-Efficient Offline Reinforcement Learning with Heterogeneous Agents via Personalized Simulators
• Policy Information Capacity: Information-Theoretic Measure for Task Complexity in Deep Reinforcement Learning
• Optimistic Policy Iteration for MDPs with Acyclic Transient State Structure
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
• Logistic Q-Learning
• Actor-critic is implicitly biased towards high entropy optimal policies
• Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation
• Improved Algorithms for Misspecified Linear Markov Decision Processes
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation
• Towards Tractable Optimism in Model-Based Reinforcement Learning
• A Contraction Approach to Model-based Reinforcement Learning
• Reinforcement Learning in Reward-Mixing MDPs
• Wasserstein Flow Meets Replicator Dynamics: A Mean-Field Analysis of Representation Learning in Actor-Critic
• Variance-Aware Off-Policy Evaluation with Linear Function Approximation
• A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
• Regret Bounds for Adaptive Nonlinear Control
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
• Gap-Dependent Bounds for Two-Player Markov Games
• Theoretically Principled Deep RL Acceleration via Nearest Neighbor Function Approximation
• Reinforcement learning with distance-based incentive/penalty (DIP) updates for highly constrained industrial control systems