Information-Theoretic Confidence Bounds for Reinforcement Learning

Understand

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.