Provably Efficient Reinforcement Learning with Linear Function Approximation 2: LSVI-UCB Has Regret O(√(d³H³Tι²) + ζdHT√ι) on ζ-Approximately Linear MDPsResearch Paper
Reinforcement learning with large or continuous state spaces relies on function approximation: value functions are represented as functions of a -dimensional feature map instead of tables indexed by states. Before 2019, regret guarantees for exploration with function approximation either needed strong assumptions (deterministic dynamics, a generative…