Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation
This addresses the problem of efficient online RL with limited feedback for researchers and practitioners, offering concrete regret improvements over prior work.
The paper tackles online reinforcement learning with linear function approximation and adversarial costs under unknown dynamics and bandit feedback, presenting a computationally efficient algorithm that achieves $\widetilde O(K^{6/7})$ regret, improving over the previous $\widetilde O(K^{14/15})$ state-of-the-art, and $\widetilde O(K^{2/3})$ regret with a simulator.
We study reinforcement learning with linear function approximation and adversarially changing cost functions, a setup that has mostly been considered under simplifying assumptions such as full information feedback or exploratory conditions.We present a computationally efficient policy optimization algorithm for the challenging general setting of unknown dynamics and bandit feedback, featuring a combination of mirror-descent and least squares policy evaluation in an auxiliary MDP used to compute exploration bonuses.Our algorithm obtains an $\widetilde O(K^{6/7})$ regret bound, improving significantly over previous state-of-the-art of $\widetilde O (K^{14/15})$ in this setting. In addition, we present a version of the same algorithm under the assumption a simulator of the environment is available to the learner (but otherwise no exploratory assumptions are made), and prove it obtains state-of-the-art regret of $\widetilde O (K^{2/3})$.