Optimism in Reinforcement Learning with Generalized Linear Function Approximation

Yining Wang; Ruosong Wang; Simon Shaolei Du; Akshay Krishnamurthy

ICLR 2021poster186 citations

Optimism in Reinforcement Learning with Generalized Linear Function Approximation

Yining Wang, Ruosong Wang, Simon Shaolei Du, Akshay Krishnamurthy

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 $\widetilde{O}\left(H\sqrt{d^3 T}\right)$ where $H$ is the horizon, $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.

reinforcement learningoptimismexplorationfunction approximationtheoryregret analysisprovable sample efficiency

BibTeX

@inproceedings{
wang2021optimism,
title={Optimism in Reinforcement Learning with Generalized Linear Function Approximation},
author={Yining Wang and Ruosong Wang and Simon Shaolei Du and Akshay Krishnamurthy},
booktitle={International Conference on Learning Representations},
year={2021},
url={https://openreview.net/forum?id=CBmJwzneppz}
}