Variational Regret Bounds for Reinforcement Learning
This addresses the problem of adapting to changing environments in reinforcement learning for applications like robotics or finance, representing a foundational advance with a novel theoretical guarantee.
The paper tackles reinforcement learning in non-stationary Markov decision processes with varying rewards and transitions, proposing an algorithm that achieves a regret bound in terms of total variation, which is the first such result for general RL.
We consider undiscounted reinforcement learning in Markov decision processes (MDPs) where both the reward functions and the state-transition probabilities may vary (gradually or abruptly) over time. For this problem setting, we propose an algorithm and provide performance guarantees for the regret evaluated against the optimal non-stationary policy. The upper bound on the regret is given in terms of the total variation in the MDP. This is the first variational regret bound for the general reinforcement learning setting.