Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes

Abstract

We study reinforcement learning (RL) with linear function approximation. For episodic time-inhomogeneous linear Markov decision processes (linear MDPs) whose transition probability can be parameterized as a linear function of a given feature mapping, we propose the first computationally efficient algorithm that achieves the nearly minimax optimal regret \(\tilde O(d\sqrt\{H^3K\})\), where \(d\) is the dimension of the feature mapping, \(H\) is the planning horizon, and \(K\) is the number of episodes. Our algorithm is based on a weighted linear regression scheme with a carefully designed weight, which depends on a new variance estimator that (1) directly estimates the variance of the optimal value function, (2) monotonically decreases with respect to the number of episodes to ensure a better estimation accuracy, and (3) uses a rare-switching policy to update the value function estimator to control the complexity of the estimated value function class. Our work provides a complete answer

Stats

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

Related papers

• Model-based Reinforcement Learning With Multinomial Logistic Function Approximation (2022)2.26
• Reward-free Model-based Reinforcement Learning With Linear Function Approximation (2021)0.00
• Efficient Learning In Non-stationary Linear Markov Decision Processes (2020)6.77
• Online Reinforcement Learning In Markov Decision Process Using Linear Programming (2023)3.58
• Nonstationary Reinforcement Learning With Linear Function Approximation (2020)0.00
• Value-biased Maximum Likelihood Estimation For Model-based Reinforcement Learning In Discounted Linear Mdps (2023)0.00
• Near-optimal Policy Optimization Algorithms For Learning Adversarial Linear Mixture Mdps (2021)0.00
• Nearly Minimax Optimal Offline Reinforcement Learning With Linear Function Approximation: Single-agent MDP And Markov Game (2022)0.00