Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation

Abstract

We develop several new algorithms for learning Markov Decision Processes in an infinite-horizon average-reward setting with linear function approximation. Using the optimism principle and assuming that the MDP has a linear structure, we first propose a computationally inefficient algorithm with optimal $\tilde{O}(\sqrt{T})$ regret and another computationally efficient variant with $\tilde{O}(T^{3/4})$ regret, where $T$ is the number of interactions. Next, taking inspiration from adversarial linear bandits, we develop yet another efficient algorithm with $\tilde{O}(\sqrt{T})$ regret under a different set of assumptions, improving the best existing result by Hao et al. (2020) with $\tilde{O}(T^{2/3})$ regret. Moreover, we draw a connection between this algorithm and the Natural Policy Gradient algorithm proposed by Kakade (2002), and show that our analysis improves the sample complexity bound recently given by Agarwal et al. (2020).

References in corpus (11)

• Trust Region Policy Optimization
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• A unified view of entropy-regularized Markov decision processes
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Scalable Bilinear $\pi$ Learning Using State and Action Features
• Exploration-Enhanced POLITEX
• Improved Analysis of UCRL2 with Empirical Bernstein Inequality
• Online learning in MDPs with linear function approximation and bandit feedback

Cited by in corpus (2)

• Nonstationary Reinforcement Learning with Linear Function Approximation
• Improved Regret Bound and Experience Replay in Regularized Policy Iteration