Opportunistic Episodic Reinforcement Learning
This work addresses the exploration-exploitation trade-off in reinforcement learning for episodic MDPs, offering a novel framework that could enhance efficiency in dynamic environments, though it appears incremental as it builds on existing algorithms like UCRL2 and PSRL.
The paper tackles the problem of reinforcement learning where regret varies with an external environmental condition, proposing opportunistic reinforcement learning to dynamically balance exploration and exploitation based on this condition. The result includes an algorithm with a regret bound of O(HS sqrt(AT)) and simulations showing improved performance over baseline methods.
In this paper, we propose and study opportunistic reinforcement learning - a new variant of reinforcement learning problems where the regret of selecting a suboptimal action varies under an external environmental condition known as the variation factor. When the variation factor is low, so is the regret of selecting a suboptimal action and vice versa. Our intuition is to exploit more when the variation factor is high, and explore more when the variation factor is low. We demonstrate the benefit of this novel framework for finite-horizon episodic MDPs by designing and evaluating OppUCRL2 and OppPSRL algorithms. Our algorithms dynamically balance the exploration-exploitation trade-off for reinforcement learning by introducing variation factor-dependent optimism to guide exploration. We establish an $\tilde{O}(HS \sqrt{AT})$ regret bound for the OppUCRL2 algorithm and show through simulations that both OppUCRL2 and OppPSRL algorithm outperform their original corresponding algorithms.