Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation

Reinforcement Learning (RL; Sutton and Barto, 2018; Mannor et al., 2022) studies online decision making problems in which an agent learns through experience within a dynamic environment, with the goal to minimize a loss function associated with the agent-environment interaction. Modern applications of RL such as robotics(Schulman et al., 2015; Lillicrap et al., 2015; Akkaya et al., 2019), game playing (Mnih et al., 2013; Silver et al., 2018) and autonomous driving (Kiran et al., 2021), almost invariably consist of large scale environments where function approximation techniques are necessary to allow the agent to generalize across different states. Furthermore, some form of agent robustness is usually required to cope with environment irregularities that cannot be faithfully represented by stochasticity assumptions (see e.g., Dulac-Arnold et al., 2021). Theoretical foundations for RL with function approximation (e.g., Jiang et al., 2017; Yang and Wang, 2019; Jin et al., 2020b; Agarwal et al., 2020) have been steadily coming into fruition.