ICLR Poster Optimism in Reinforcement Learning with Generalized Linear Function Approximation

Poster

Optimism in Reinforcement Learning with Generalized Linear Function Approximation

Yining Wang · Ruosong Wang · Simon Du · Akshay Krishnamurthy

Keywords: [ reinforcement learning ] [ exploration ] [ function approximation ] [ theory ] [ optimism ] [ regret analysis ] [ provable sample efficiency ]

[ Abstract ] [ Paper PDF ]

[ Paper ]

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} (H \sqrt{d^{3} T})

$\widetilde{O}\left(H\sqrt{d^3 T}\right)$ where

H

$H$ is the horizon,

d

$d$ is the dimensionality of the state-action features and

T

$T$ is the number of episodes. This is the first statistically and computationally efficient algorithm for reinforcement learning with generalized linear functions.

Chat is not available.