Regret Bounds for Information-Directed Reinforcement Learning
This work provides theoretical foundations for data-efficient RL algorithms, benefiting researchers and practitioners by improving regret bounds and computational efficiency, though it is incremental in building on existing IDS methods.
The paper tackles the limited theoretical understanding of information-directed sampling (IDS) for reinforcement learning in Markov Decision Processes by developing novel information-theoretic tools to bound regret, resulting in prior-free Bayesian regret bounds for tabular finite-horizon MDPs and extensions to linear MDPs.
Information-directed sampling (IDS) has revealed its potential as a data-efficient algorithm for reinforcement learning (RL). However, theoretical understanding of IDS for Markov Decision Processes (MDPs) is still limited. We develop novel information-theoretic tools to bound the information ratio and cumulative information gain about the learning target. Our theoretical results shed light on the importance of choosing the learning target such that the practitioners can balance the computation and regret bounds. As a consequence, we derive prior-free Bayesian regret bounds for vanilla-IDS which learns the whole environment under tabular finite-horizon MDPs. In addition, we propose a computationally-efficient regularized-IDS that maximizes an additive form rather than the ratio form and show that it enjoys the same regret bound as vanilla-IDS. With the aid of rate-distortion theory, we improve the regret bound by learning a surrogate, less informative environment. Furthermore, we extend our analysis to linear MDPs and prove similar regret bounds for Thompson sampling as a by-product.