Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation

2022/06/23 by Hu, Pihe, Chen, Yu, Huang, Longbo · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2206.11489

Abstract

We study reinforcement learning with linear function approximation where the transition probability and reward functions are linear with respect to a feature mapping \boldsymbolϕ(s,a). Specifically, we consider the episodic inhomogeneous linear Markov Decision Process (MDP), and propose a novel computation-efficient algorithm, LSVI-UCB⁺, which achieves an \widetildeO(Hd√(T)) regret bound where H is the episode length, d is the feature dimension, and T is the number of steps. LSVI-UCB⁺ builds on weighted ridge regression and upper confidence value iteration with a Bernstein-type exploration bonus. Our statistical results are obtained with novel analytical tools, including a new Bernstein self-normalized bound with conservatism on elliptical potentials, and refined analysis of the correction term. This is a minimax optimal algorithm for linear MDPs up to logarithmic factors, which closes the √(Hd) gap between the upper bound of \widetildeO(√(H³d³T)) in (Jin et al., 2020) and lower bound of Ω(Hd√(T)) for linear MDPs.

Cited by

• World Action Planner: Generalizable Decision-Making with Action-Conditioned World Models

Related

• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints