Information-Theoretic Confidence Bounds for Reinforcement Learning

Abstract

We integrate information-theoretic concepts into the design and analysis of optimistic algorithms and Thompson sampling. By making a connection between information-theoretic quantities and confidence bounds, we obtain results that relate the per-period performance of the agent with its information gain about the environment, thus explicitly characterizing the exploration-exploitation tradeoff. The resulting cumulative regret bound depends on the agent's uncertainty over the environment and quantifies the value of prior information. We show applicability of this approach to several environments, including linear bandits, tabular MDPs, and factored MDPs. These examples demonstrate the potential of a general information-theoretic approach for the design and analysis of reinforcement learning algorithms.

Cited by in corpus (9)

• Information Theoretic Regret Bounds for Online Nonlinear Control
• Entropy Regularization for Mean Field Games with Learning
• Reinforcement Learning, Bit by Bit
• Meta-Thompson Sampling
• A Bit Better? Quantifying Information for Bandit Learning
• Thompson Sampling with a Mixture Prior
• Hierarchical Bayesian Bandits
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
• No Regrets for Learning the Prior in Bandits