Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
Not on the map. Why?
Abstract (arXiv)
We study reinforcement learning (RL) with linear function approximation under the adaptivity constraint. We consider two popular limited adaptivity models: the batch learning model and the rare policy switch model, and propose two efficient online RL algorithms for episodic linear Markov decision processes, where the transition probability and the reward function can be represented as a linear function of some known feature mapping. In specific, for the batch learning model, our proposed LSVI-UCB-Batch algorithm achieves an tilde O(√d3H3T + dHT/B) regret, where d is the dimension of the feature mapping, H is the episode length, T is the number of interactions and B is the number of batches. Our result suggests that it suffices to use only √T/dH batches to obtain tilde O(√d3H3T) regret. For the rare policy switch model, our proposed LSVI-UCB-RareSwitch algorithm enjoys an tilde O(√d3H3T[1+T/(dH)]dH/B) regret, which implies that dHlog T policy switches suffice to obtain the tilde O(√d3H3T) regret. Our algorithms achieve the same regret as the LSVI-UCB algorithm (Jin et al., 2019), yet with a substantially smaller amount of adaptivity. We also establish a lower bound for the batch learning model, which suggests that the dependency on B in our regret bound is tight.
Key facts. Cited by 124 papers in the map (data through 14 Oct 2026). Builds on 25 of its 51 references that are in the map. First posted on arXiv 6 Jan 2021.
Builds on
25 of 51 references.
References · 25
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
- 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
- 2019Provably Efficient Exploration in Policy Optimizationcited by 205
- 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
- 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
- 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
- 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
- 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
- 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
- 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
- 2019Batched Multi-armed Bandits Problemcited by 98
- 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
13 more
- 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
- 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
- 2020Sequential Batch Learning in Finite-Action Linear Contextual Banditscited by 63
- 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 61
- 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 52
- 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
- 2019Regret Bounds for Batched Banditscited by 49
- 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
- 2013Bandits with Switching Costs: T^{2/3} Regretcited by 39
- 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 37
- 2018Online learning over a finite action set with limited switchingcited by 21
- 2020On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spacescited by 19
- 2019Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transitioncited by 17
Built on by
Citing papers per year: 2021: 45; 2022: 39; 2023: 25; 2024: 7; 2025: 7; 2026: 1.
124 papers.
Sort:
By area:
- 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
- 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 158
- 2021Recent Advances in Reinforcement Learning in Financecited by 110
- 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
- 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
- 2021Reinforcement Learning, Bit by Bitcited by 59
- 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
- 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
- 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
- 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
- 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
- 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
38 more
- 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
- 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 44
- 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
- 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
- 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
- 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
- 2021A Minimax Learning Approach to Off-Policy Evaluation in Confounded Partially Observable Markov Decision Processescited by 36
- 2021Safe Reinforcement Learning with Linear Function Approximationcited by 35
- 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
- 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
- 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 32
- 2023Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaRcited by 32
- 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
- 2023Bridging RL Theory and Practice with the Effective Horizoncited by 31
- 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
- 2021Minimax Regret for Stochastic Shortest Pathcited by 30
- 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 30
- 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 30
- 2021Online Apprenticeship Learningcited by 29
- 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 29
- 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 28
- 2021Principled Exploration via Optimistic Bootstrapping and Backward Inductioncited by 26
- 2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
- 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
- 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
- 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
- 2021Efficient Local Planning with Linear Function Approximationcited by 23
- 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
- 2021Dynamic Bottleneck for Robust Self-Supervised Explorationcited by 21
- 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
- 2022Offline Reinforcement Learning with Differential Privacycited by 20
- 2022Active Exploration via Experiment Design in Markov Chainscited by 19
- 2021Design of Experiments for Stochastic Contextual Linear Banditscited by 18
- 2022Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learningcited by 18
- 2021Online Learning for Unknown Partially Observable MDPscited by 17
- 2022Learning Bellman Complete Representations for Offline Policy Evaluationcited by 17
- 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
- 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
50 most cited of 124 All 124 (JSON)
- 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost31 Aug 2026
- 2025Optimizing LVLMs with On-Policy Data for Effective Hallucination Mitigation30 Nov 2025
- 2025The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin5 Nov 2025
- 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory11 Aug 2025
- 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning5 Jun 2025
- 2025Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximation20 May 2025
- 2025Towards Optimal Differentially Private Regret Bounds in Linear MDPs12 Apr 2025
- 2025Gap-Dependent Bounds for Federated Q-learning5 Feb 2025
- 2024Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs16 Nov 2024
- 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition10 Oct 2024
- 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning30 Sep 2024
- 2024To Switch or Not to Switch? Balanced Policy Switching in Offline Reinforcement Learning1 Jul 2024
38 more
- 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs23 May 2024
- 2024Batched Nonparametric Contextual Bandits27 Feb 2024
- 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints2 Feb 2024
- 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation26 Nov 2023
- 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity2 Oct 2023
- 2023On the Convergence of Bounded Agents20 Jul 2023
- 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data10 Jul 2023
- 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP21 Jun 2023
- 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs20 Jun 2023
- 2023A Markovian Formalism for Active Querying13 Jun 2023
- 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time24 May 2023
- 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes15 May 2023
- 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation10 May 2023
- 2023Bridging RL Theory and Practice with the Effective Horizon19 Apr 2023
- 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards9 Mar 2023
- 2023Optimistic Planning by Regularized Dynamic Programming27 Feb 2023
- 2023Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learning24 Feb 2023
- 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPs24 Feb 2023
- 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimization14 Feb 2023
- 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learning8 Feb 2023
- 2023Near-Optimal Adversarial Reinforcement Learning with Switching Costs8 Feb 2023
- 2023Online Reinforcement Learning with Uncertain Episode Lengths7 Feb 2023
- 2023Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR7 Feb 2023
- 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedback3 Feb 2023
- 2023Sample Complexity of Kernel-Based Q-Learning1 Feb 2023
- 2023Sample Efficient Deep Reinforcement Learning via Local Planning29 Jan 2023
- 2023Multi-Agent Congestion Cost Minimization With Linear Function Approximations26 Jan 2023
- 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient19 Jan 2023
- 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes12 Dec 2022
- 2022Near-Optimal Differentially Private Reinforcement Learning9 Dec 2022
- 2022Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximation28 Nov 2022
- 2022CIM: Constrained Intrinsic Motivation for Sparse-Reward Continuous Control28 Nov 2022
- 2022On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization14 Nov 2022
- 2022Linear Reinforcement Learning with Ball Structure Action Space14 Nov 2022
- 2022A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Design19 Oct 2022
- 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies4 Oct 2022
- 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation3 Oct 2022
- 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization30 Sep 2022
50 newest of 124 All 124 (JSON)
- 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 158
- 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 32
- 2022Offline Reinforcement Learning with Differential Privacycited by 20
- 2022Learning Bellman Complete Representations for Offline Policy Evaluationcited by 17
- 2022On the Role of Discount Factor in Offline Reinforcement Learningcited by 16
- 2021Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximationcited by 11
- 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithmcited by 10
- 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2
- 2024To Switch or Not to Switch? Balanced Policy Switching in Offline Reinforcement Learningcited by 1
- 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theorycited by 1
- 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory11 Aug 2025
- 2024To Switch or Not to Switch? Balanced Policy Switching in Offline Reinforcement Learning1 Jul 2024
- 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity2 Oct 2023
- 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximation14 Sep 2022
- 2022Learning Bellman Complete Representations for Offline Policy Evaluation12 Jul 2022
- 2022On the Role of Discount Factor in Offline Reinforcement Learning7 Jun 2022
- 2022Offline Reinforcement Learning with Differential Privacy2 Jun 2022
- 2021Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation19 Aug 2021
- 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun 2021
- 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm17 Mar 2021
- 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 16
- 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
- 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
- 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 4
- 2025Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximationcited by 3
- 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
- 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 1
- 2024Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPscited by 0
- 2025Towards Optimal Differentially Private Regret Bounds in Linear MDPscited by 0
- 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost31 Aug 2026
- 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning5 Jun 2025
- 2025Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximation20 May 2025
- 2025Towards Optimal Differentially Private Regret Bounds in Linear MDPs12 Apr 2025
- 2024Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs16 Nov 2024
- 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition10 Oct 2024
- 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning30 Sep 2024
- 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs23 May 2024
- 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints2 Feb 2024
- 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
- 2021Recent Advances in Reinforcement Learning in Financecited by 110
- 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
- 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
- 2021Reinforcement Learning, Bit by Bitcited by 59
- 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
- 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
- 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
- 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
- 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
- 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
- 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
12 most cited of 104 All 104 (JSON)
- 2025The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin5 Nov 2025
- 2025Gap-Dependent Bounds for Federated Q-learning5 Feb 2025
- 2024Batched Nonparametric Contextual Bandits27 Feb 2024
- 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation26 Nov 2023
- 2023On the Convergence of Bounded Agents20 Jul 2023
- 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data10 Jul 2023
- 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP21 Jun 2023
- 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs20 Jun 2023
- 2023A Markovian Formalism for Active Querying13 Jun 2023
- 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time24 May 2023
- 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes15 May 2023
- 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation10 May 2023
12 newest of 104 All 104 (JSON)