Optimism in Reinforcement Learning with Generalized Linear Function Approximation

Abstract

We design a new provably efficient algorithm for episodic reinforcement learning with generalized linear function approximation. We analyze the algorithm under a new expressivity assumption that we call "optimistic closure," which is strictly weaker than assumptions from prior analyses for the linear setting. With optimistic closure, we prove that our algorithm enjoys a regret bound of $\tilde{O}(\sqrt{d^{3}T})$ where $d$ is the dimensionality of the state-action features and $T$ is the number of episodes. This is the first statistically and computationally efficient algorithm for reinforcement learning with generalized linear functions.

References in corpus (3)

• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?

Cited by in corpus (2)

• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity